.so ../ADM/mac .XX anim 451 "A System for Algorithm Animation" .EQ delim @@ .EN .nr dP 1 .nr dV 1 .nr dT 8 \" tab stops this far apart in .P1/.P2 .nr NH .5v \" adds extra space before NH or SH heading .nr ds .5i \" default indent for programs .hy 14 \" set hyphenation: 2=not last lines; 4= no -xx; 8=no xx- .\" .de IN \" assumes called as .INCLUDE filename .sy compile \\$2.t .so \\$2.o .. .de ge \" assumes .ge called as .get .sy trget \\n(.$ \\$2 '\\$3' '\\$4' '\\$5' >junk.\\n($$ .so junk.\\n($$ .sy rm junk.\\n($$ .. .de ru \" assumes .ru called as .run .sy \\$2 \\$3 \\$4 \\$5 \\$6 \\$7 \\$8 \\$9 >junk1.\\n($$ .get junk1.\\n($$ .sy rm junk1.\\n($$ .. .TL A System for Algorithm Animation .br Tutorial and User Manual .AU Jon L. Bentley Brian W. Kernighan .AI .MH .AB A program or an algorithm can be animated by a movie that graphically represents its dynamic execution. For instance, a memory allocator might be animated by lines that appear when memory is allocated and disappear when it is freed; a sort might be animated by a randomly scrambled sequence of lines being permuted into order. Such animations are useful for debugging programs, for developing new programs, and for communicating information about how programs work. This paper describes a basic system for algorithm animation: the output is crude, but the system is easy to use; novice users can animate a program in a couple of hours. The system currently produces movies on Teletype 5620 terminals and workstations that support the X window system, and also renders movies into ``stills'' that can be included in .I troff documents. This paper is a user manual and a tutorial introduction to algorithm animation using the system. .AE .NH Introduction .PP Dynamic displays are better than static displays for giving insight into the behavior of dynamic systems. The pictures in Figure 1, for instance, illustrate four equal-mass bodies moving in the plane under Newtonian attraction. .KF .INCLUDE stars .sp .ce \f3Figure 1:\fP Bodies moving under Newtonian attraction .KE Time marches across the pictures left to right, at roughly equal intervals. Each column, called a .I snapshot , depicts three .I views of the bodies. The top view gives the current position as a dot; the tail formed by the last few positions hints at the velocity and the acceleration. The middle view renders the path of each body as a line. The bottom view depicts the history of velocities by dots recorded at equal time intervals: low velocities give close dots and high velocities leave the dots far apart. .PP The first snapshot shows the bodies starting slowly, far apart. In the second snapshot they have recently experienced a high-velocity encounter near the center. In the third snapshot the bodies are again far apart, moving slowly toward another encounter in the fourth snapshot. In the fifth snapshot the large time-step of our simulation program violates conservation of energy and sends the bodies racing away from each other. .PP This paper describes the animation system that produced those pictures. A sixty-line C simulation program was augmented with eight .I printf statements to generate a .I script file describing the paths of the four bodies in the three views. That file was processed by a program named .I stills to produce the pictures above, using .I pic and .I troff ; we were able to control what frames were displayed, in what size and form. A program named .I movie displays the same data on a Teletype 5620 terminal or an X workstation; the viewer can control the speed of display, proceed forward or backward through time, and change the screen layout to emphasize certain views. Those components can be depicted as: .PS boxht = .25; boxwid = .6 ellipseht = .25; ellipsewid = .6 lineht = .1; linewid = .4 down box "generator" line down A: ellipse "script" line from A.se right down box "stills" line down box invis "pic | troff | ..." line from A.sw left down box "movie" line down box invis "5620, X, ..." .PE .PP Several systems have been developed for algorithm animation |reference(sedgewick brown ieee). Most of those systems produce animations of very high quality; unfortunately, they are expensive in both programmer time and CPU time. Our system is at the opposite end of the spectrum: its output is primitive, but the system is easy to use; a new user can animate a simple program in an hour or two by adding a few lines of code. Although our system was designed primarily with program animation in mind, the gravitational example shows that it can be useful in other domains as well. .PP Section 2 introduces the system by animating a sorting algorithm. Sections 3 through 5 describe the three primary components of the system: script files, .I movie , and .I stills . Section 6 describes the animation of several larger programs, and Section 7 discusses a few everyday matters about using the system. .NH A Simple Example \(em Sorting .PP Insertion sort is the method most card players use. As each card is dealt, it is inserted into its proper place among the existing cards. To sort the array @X[1..N]@, insertion sort maintains the sorted subset in @X[1..I]@ and increases @I@ from 2 to @N@. The subarray @X[1..1]@ is sorted by definition. The first phase of the algorithm sifts @X[2]@ down so that @X[1..2]@ is sorted, the second phase sifts @X[3]@ down so that @X[1..3]@ is sorted, and so on. .PP Here is an implementation of insertion sort in .I awk |reference(awk book): .P1 .get is.awk .P2 The first .CW for statement sprinkles .CW x[1..n] with random integers in the range @1..25@, and the second and third .CW for statements perform the insertion sort. The function .CW swap exchanges array elements; .CW show prints the current state of the array. .PP If we run this program with .CW n set to 7, we get this static display of sorting a 7-element array of random integers: .P1 .run sh is.awk 7 .P2 .PP The animation system provides an alternative: by adding a few more .CW print statements to the program, we can produce input for the animation system, thus providing a dynamic display of the sorting process. Furthermore, we can use graphics as well as text, to give a more visual presentation of the algorithm. .PP For this example, we decided to present two views. The top view simply shows the numbers in the array as they are sorted; it is essentially the same as the textual output above, except that we have added a vertical bar: elements to the left of the bar are in order. The bottom view is graphical: the value of each element is represented by the length of the corresponding vertical line. .PP These six snapshots show the state after each phase of the sorting algorithm: .sy make.sorts .INCLUDE is3 .PP Although the two views represent the same information, they are useful for different tasks. The textual nature of the top view is easier for novices to follow, and the complete information is handy for debugging small examples. The more visual bottom view is better for displaying large sorts. .sp 1 .LP .I "The Program." .PP Here is the complete .I awk program .CW is.gen that generated the animation depicted above. .P1 .get is.gen .P2 It is very similar to the first version, but we have added the functions .CW less to make comparisons and .CW draw to display elements, as well as several .CW print statements. In addition to performing their sorting functions, .CW less and .CW swap record their actions by printing output into a script file that will serve as input to .I movie and .I stills . This animation uses four commands: .CW line , .CW text , .CW view and .CW click . .PP A line from @( x sub 1 , y sub 1 )@ to @( x sub 2 , y sub 2 )@ is drawn by a command of the form .P1 @optional_label:@ line @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@ .P2 (Throughout this paper, literals are shown in .CW typewriter font and categories are in @italics@.) The coordinates of the line can lie in any range; later programs will scale them appropriately. The label on a line is optional. When a labeled object is drawn the object that previously had that label is erased. Thus for all lines that have the same label, the act of drawing one line erases its predecessor. (There is also an explicit .CW erase command.) .PP Text is produced at @( x , y )@ by a command of the form .P1 @optional_label:@ text @x@ @y@ @anything@ @at@ @all@ .P2 As with lines, labels are permitted; re-use of a label erases whatever object previously had that label. For example, the vertical bar is always printed with the label .CW bar , so each bar erases the previous one. .PP The .CW view command is used to place output in a particular view. There are two views here, .CW text and .CW geom : .P1 view text view geom .P2 The .CW draw function draws text in the .CW text view and lines in the .CW geom view, relying on implicit erasure to remove the previous object before creating a new one. Different views are independent, so a label like .CW a1 can be used in several views without interference. .PP Interesting events are marked by the .CW click command: .P1 click swap click comp click phase .P2 .I Stills and .I movie can refer to each click with this mechanism, as we will see in more detail shortly. .PP Labels, view names and click names are arbitrary and unrelated to one another. .sp 1 .LP .I "The Script File." .PP Executing the command .P1 is.gen 3 >is1.s .P2 produces the script file .CW is1.s containing a sort of three elements. The basename .CW is1 is for ``insertion sort 1''; the suffix .CW .s identifies it as a script file and is required by the animation system. Here is .CW is1.s , printed in two columns to save space: .P1 .ps 8 .vs 8 .ta 3i .run 2col is1.s .P2 .sp .PP Here is a picture of all clicks in the script file .CW is1.s , produced by .I stills . .INCLUDE is1 As before, time goes from left to right. Both views of the current state are depicted in a snapshot at each .CW click ; the label below each frame tells the name and number of the click. This detailed picture illustrates the animation system; here is a sparser picture that illustrates insertion sort on a 14-element array: .INCLUDE is2 .sp 1 .LP .I "Making Stills." .PP The last picture was included in this document by this .I stills description: .P1 .get is2.t .P2 The description is delimited by the lines .CW "\&.begin stills" and .CW \&.end (which correspond, for instance, to .CW \&.EQ and .CW \&.EN in .CW eqn or .CW \&.TS and .CW \&.TE in .CW tbl ). Text following the sharp character .CW # is a comment to be ignored. The .CW view statements specify the empty string as the title for both views of the data. The .CW print statement displays snapshots at the requested .CW click s of .CW phase . .PP The last four statements are parameter assignments of the form .P1 @parameter_name@ @value@ .P2 Assignment to the .CW file parameter names the script file to be displayed. The next two assignments set the height and width of frames, and the final statement causes .CW medium text (the default text size) to be set five points smaller than the current .I troff point size. .sp 1 .LP .I "Viewing A Movie." .PP To watch a movie on the 5620, make a window of suitable size and shape and in it type the command .P1 is.gen 20 | movie .P2 If you want to access the script later, type instead .P1 is.gen 20 >is.s movie is.s .P2 After a pause to run .CW is.gen (about 15 seconds on a VAX\(tm-750 in this case), the 5620 down-loading procedure will begin; after that (another 30 seconds), the data for the movie itself will begin to appear. When this is finished (also about 30 seconds), a message about the number of bytes sent (about 9500) appears in the upper left corner. .PP At this point, the mouse buttons can be used to redisplay the movie. Button 3 is the main control. It has 9 menu items: .P1 again faster 1 slower 1 1 step backward fatter 1 thinner 1 or mode new file Quit? .P2 To play the movie again, select .CW again . (This movie takes about 6 seconds at full speed.) You can stop it at any point by pushing any button; a further push of button 1 continues it. To slow the display, select .CW slower ; each selection halves the speed by increasing a wait interval by a factor of two. After three selections the menu reads .P1 again faster 8 slower 8 \&... .P2 Try selecting .CW again to see the sort once at this speed, then select .CW faster three times to get back to full speed. .PP The items labeled .CW fatter and .CW thinner control the thickness of lines in an analogous manner. Selecting .CW fatter several times results in obese lines; you may return things to normal with .CW thinner . .PP Three menu items control binary mode settings: .CW 1 .CW step or .CW run ; .CW backward or .CW forward ; and .CW or .CW mode or .CW xor .CW mode . For each, the label indicates the next state, not the current state. .PP Normally the movie is played from beginning to end without pause. The menu item labeled .CW 1 .CW step puts it into a mode where it displays only one ``step'' each time button 1 is pushed. This allows you to inspect the sort a frame at a time. This item changes to .CW run when .CW 1 .CW step has been selected so you can revert to continuous action. .PP The .CW backward item causes the steps to be taken in reverse order (time runs backwards); the menu item changes to .CW forward when selected. After the sort ends, select .CW backward and .CW again and watch the array scramble itself before your very eyes. Judicious use of .CW 1 .CW step and .CW backward and .CW forward make it easy to examine a few snapshots in detail. .PP Normally items are displayed in ``exclusive OR'' mode, which means that a bit drawn over a previous one erases it. If you are drawing numerous objects in a crowded area, this can lead to unintended erasures. The .CW or .CW mode item switches to ``inclusive OR'' for drawing objects, and erases objects by clearing. Some movies are far better in one mode than the other. .PP The .CW new .CW file item allows one to view a new movie without having to reload the .I movie program into the 5620. We'll see how it works in Section 4. .PP The .CW Quit? menu item is the way to exit. If selected, it displays a skull and crossbones to warn that its effect is irreversible. Pushing button 3 again exits; a different button avoids quitting. .PP Button 2 contains menu items to control the size and shape of the views on the screen and to control the meaning of a ``step'' in 1-step mode. For this sorting movie, button 2 looks like: .P1 view text view geom click comp click swap click phase .P2 When a view is selected, you can sweep a rectangle in which that view is to be displayed; the use is exactly like the .CW New menu item in .I mux . You can arrange the views any way you like; try deleting the textual view by sweeping its rectangle out of the window. .PP When a .CW click is selected, 1-stepping proceeds to the next occurrence of that click. So, for example, to see swaps one at a time, select .CW click .CW swap on button 2 then select .CW 1 .CW step on button 3. Each hit of button 1 will pause at the next .CW click .CW swap statement in the script file, in either .CW forward and .CW backward mode. .PP Multiple clicks may be selected. Selecting both .CW click .CW comp and .CW click .CW swap will cause a pause after every comparison and every swap. Selected clicks are marked with an asterisk in the menu; selecting a click that already has an asterisk removes the asterisk and turns off the click. .PP In .CW run mode, the movie runs at full speed until it encounters a selected click, then pauses for a time proportional to the selected speed. Selecting no clicks is equivalent to having selected an implicit click that occurs after each geometric object (text, line, circle, rectangle) is drawn or erased, so animations run faster when some clicks are turned on (with .CW click .CW phase selected, for instance, the sorting movie runs nearly twice as fast). .sp 1 .LP .I "Summary." .PP This exercise illustrates the capabilities and limitations of our animation system. The output of .I movie is a crude but useful animation. The output of .I stills is handy for more detailed study and for presentation in documents (we would like to include a movie in this document, for instance, but paper is easier to distribute than videotape). A sophisticated animation system might require 500 lines of code to produce beautiful animations of insertion sort. Our output is unpolished by comparison, but it is adequate for many purposes and requires just a few dozen lines. .PP If our system is so crude, why bother using it? Why not animate an algorithm simply by drawing geometric objects on the output device you happen to be using? Some of the answer lies in extra services like these: .IP .I "Device Independence." A script file can be rendered as a movie on a 5620 or an X11 workstation; the system is designed to make it easy to port to additional output devices. The same script file can be incorporated into a document by .I stills . .IP .I "Names." Labels allow geometric objects to be erased; implicit erasure by re-using a label avoids much of the tedium of bookkeeping. Click names mark key events; they can be used to group related events. .IP .I "Independent Views." Different simultaneous views of a process are crucial for animating algorithms. In our system, a single statement moves from one view to another. Within a view, the user need not be concerned about the range of coordinates; the system scales automatically. Labels in different views are independent. .IP .I "Viewer Control." Both .I movie and .I stills allow the viewer to select which views will be displayed and which clicks will be recognized. Additionally, .I movie allows the viewer to go forward or backward, in single steps or running at a selected speed. .IP .I "An Interface To The World." Although writing to files takes more computer time than using the geometric primitives provided by a specific output device, we will soon see how those files allow complicated tasks to be easily composed out of simple software tools. .LP Our system does not support interactive animations, however: once the script has been generated, there's no way to change it except to generate it again. .NH The Script Language .PP This section is a more complete description of the script language in which animations are described. A script file is processed by the heretofore unmentioned program .I develop ; errors in script files are reported by that program. The output of .I develop feeds .I stills and .I movie : .PS boxht = .25; boxwid = .6 ellipseht = .25; ellipsewid = .6 lineht = .1; linewid = .4 down box "generator" line down ellipse "fname.s" line down box "develop" line down A: ellipse "fname.i" B: box "stills" with .w at A.e + (.2, -.4) line down box invis "pic | troff | ..." C: box "movie" with .e at A.w - (.2, .4) line down box invis "5620, X, ..." line from A.se to B.nw line from A.sw to C.ne up line up from B.n ellipse "docfile" .PE The command .CW develop .CW fname.s produces the .I intermediate file .CW fname.i from the script file .CW fname.s , unless .CW fname.i already exists and is newer than the corresponding script file. Fortunately, most users need not be concerned with intermediate files and the .I develop program; both .I movie and .I stills call .I develop implicitly. Appendix I defines the format of an intermediate file. .PP The script language provides commands to draw geometric objects and commands that control the pictures. A line whose first non-blank character is .CW # is a comment; comments may not appear on the line after other commands. Blank lines are ignored. .sp 1 .LP .I "Geometric Commands" : .CW text , .CW line , .CW box , .CW circle . .PP Geometric commands describe text, lines, rectangles, or circles. They share the common form .P1 @optional_label:@ @command@ @options@ @x@ @y@ @additional@ @parts@ .P2 If a label is present, it names the object and will implicitly erase any existing object with the same name in the same view. The options are a (possibly null) list of names, terminated by the next numeric field. .PP Text is placed at a position by the command .P1 @optional_label:@ text @options@ @x@ @y@ @string@ .P2 The available options are .P1 [center] ljust rjust above below small [medium] big bigbig .P2 At most one option may be selected from each line; if none is selected, the option in brackets is used. The first line describes text position, and the second line describes text size. The text string may be quoted. If there is no leading quote, then the string starts at the first non-blank character and continues until the end of the line. If there is a leading quote, subsequent leading white space is kept and any trailing quote at the end of the line is removed; intermediate quotes are kept. Some strings, including (but not necessarily limited to) .CW bullet , .CW dot , .CW circle , and .CW times , are recognized by later processors. .PP A line is drawn by .P1 @optional_label:@ line @options@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@ .P2 The available options are .P1 [-] -> <- <-> [solid] fat fatfat dotted dashed .P2 The first line of options describe whether the line should be drawn with arrowheads; the default is without arrowheads. The option .CW <- puts an arrowhead at the @( x sub 1 , y sub 1 )@ end of the line, .CW -> puts an arrowhead at the other end, and .CW <-> puts them at both ends. The second line of options describes the body of the line. .PP A rectangle is drawn by .P1 @optional_label:@ box @options@ @xmin@ @ymin@ @xmax@ @ymax@ .P2 The only options are .P1 [nofill] fill .P2 Under the default .CW nofill only the border of the box is drawn; a .CW fill ed box has a solid interior as well. .PP A circle is drawn by .P1 @optional_label:@ circle @options@ @x@ @y@ @radius@ .P2 The radius is measured in the @x@ dimension. Circles will look right only if @x@ and @y@ are in about the same range. As with rectangles, the options are .P1 [nofill] fill .P2 .sp 1 .LP .I "Control Commands" : .CW view , .CW click , .CW erase , .CW clear . .PP The current view is set by the statement .P1 view @name@ .P2 If there are no view statements in the script file, .I develop generates a single implicit view named .CW def.view . If geometric objects appear before the first view statement, they go in that view and a warning message is generated. .PP A click is named by .P1 click @optional_name@ .P2 If no name is present, then the name .CW def.click is implicitly supplied. .PP A labeled geometric object can be explicitly erased by the command .P1 erase @label@ .P2 .I develop prints a warning if the object was never defined or has already been erased. The various views have distinct name spaces; the same label may be applied to two unrelated objects in two different views. All objects in the current view can be erased by the statement .P1 clear .P2 .PP None of these commands may have labels. .sp 1 .LP .I "Summary." .PP The script language contains the following commands; options are indented on a subsequent line, with defaults in brackets: .P1 # comment @optional_label:@ line @options@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@ [-] -> <- <-> [solid] fat fatfat dotted dashed @optional_label:@ text @options@ @x@ @y@ @string@ [center] ljust rjust above below small [medium] big bigbig @optional_label:@ box @options@ @xmin@ @ymin@ @xmax@ @ymax@ [nofill] fill @optional_label:@ circle @options@ @x@ @y@ @radius@ [nofill] fill view @name@ click @optional_name@ erase @label@ clear .P2 .PP The shell command .CW develop .CW fname.s makes the intermediate file .CW fname.i from the script file .CW fname.s , if .CW fname.i is out of date. The purpose of the intermediate file is to trade increased space (for storing the intermediate file) for reduced run time (a script file is developed just once, not each time it is used). The .I movie and .I stills shell scripts could be rewritten to pipe their inputs through .I fdevelop , a filter form of .I develop . The .I fdevelop program can handle script files with at most 20,000 lines; the argument .CW -l\f2n\fP changes the upper bound to .I n instead. It can similarly handle at most 10,000 pieces of geometry active at any time; the argument .CW -s\f2n\fP (for ``slots'') changes that upper bound. Error messages tell when these bounds need to be increased. After any .CW -l and .CW -s arguments, .I fdevelop can have an optional file name. If there is a name, that is the input file; otherwise, the standard input is used. The output is written on the standard output. .NH The Movie Program .PP Movie production, as with most 5620 programs, uses a host process and a terminal process. The host sends the intermediate file produced by .I develop in a compact form to the terminal, which stores it in a form suited for forward or backward display. As the file is shipped, the line number in the intermediate file is displayed in the upper-left corner of the window every 100 lines. Afterwards, the total number of bytes stored is displayed in that location. The terminal process allocates 80,000 bytes (typically 5-10,000 objects) for the picture; the argument .CW -m\f2n\fP sets the allocation to .I n instead. .PP The button 3 menu was sketched in Section 2. In general, drawing can be interrupted at any point by pushing any button, then resumed by pushing button 1. .PP Four menu items control two variables: .P1 faster [speed] slower [speed] .P2 decrease (halve) and increase (double) the pause at selected clicks, and .P1 thinner [line width] fatter [line width] .P2 alter the width of lines. (If the line thickness is @n@, then .CW solid lines are @2n - 1@ bits wide; .CW fat and .CW fatfat lines are larger.) Three menu items control binary attributes: .P1 backward forward or mode xor mode 1 step run .P2 The mode displayed on the menu is the next state, not the current one. If the program is currently in .CW or .CW mode , for instance, then .CW xor .CW mode is displayed. .PP The .CW new .CW file item allows one to view a new movie without downloading the .I movie program again. After selecting that item, text in the upper left of the window asks for the name of the intermediate file to be processed. The .I movie program does not call .I develop to make the intermediate .CW .i ) ( file from the script .CW .s ) ( file; that is the responsibility of the user, typically in a separate window. .PP Button 2 lists views and clicks. Selecting a view results in an icon for sweeping a rectangle, as in .I mux . Views may be positioned anywhere; portions positioned outside the window will not be shown. Initially, views have a 5 percent margin at each edge; this margin is zero for views that have been reshaped. If the window itself is reshaped, all views revert to the default position and margin. .PP Normally, in 1-step mode, the display pauses after each primitive object (line, text, etc.) has been drawn or erased. If any clicks are defined and turned on by button 2, however, then the display pauses only at those points. Any number of clicks may be turned on. Clicks that are turned on are marked with an asterisk; they may be turned off by selecting them again. .PP As it is for the 5620, so it is for X workstations, although the exigencies of the X window system have forced us to curtail some features. To keep the code relatively portable, there are again two processes, so the window in which one starts the animation clones another window of uncontrolled size, shape and position where the animation itself occurs. .PP The current terminal programs support many, but not all, text size and line mode options. .PP If .I movie has a single argument, it must be either a .CW .s or .CW .i file; .I movie .I develop s a .CW .s file. If it has no arguments, then it will pipe the standard input through .I fdevelop ; no intermediate file is created. For more exotic situations, use .I fmovie : with no arguments, it projects the intermediate file from the standard input; with a single argument, it projects that intermediate file. .NH The Stills Language .PP The .I stills program is a typical .I troff preprocessor. Portions of its input bracketed by .CW .begin .CW stills and .CW .end are translated into .I pic commands, and the rest of the input is passed through untouched. A paper containing .I stills input is typically compiled by a command like .P1 stills paper | pic | troff >paper.out .P2 .PP There are three classes of statements in a .I stills description: .CW print , .CW view , and parameter assignments. Only two statements are mandatory in a particular description: an assignment to the .CW file parameter and a .CW print statement. Text following the sharp symbol .CW # is discarded as a comment; blank lines are ignored. .PP There may be any number of .CW print statements of any combination of the following forms: .P1 print all print final print @clickname@ all print @clickname@ @number@ @number@ @number@ ... .P2 The first statement causes a snapshot to be drawn at each .CW click statement in the script file; the second draws one at the end of the file. The third form prints all .CW click s of the designated name, and the fourth prints only the clicks enumerated in the list of numbers. .PP View statements select which views are to be printed in snapshots and assign titles to views. .P1 view @name@ @optional@ @title@ .P2 The views appear in the order they are named, either top-to-bottom if time goes .CW across the page or left-to-right if time goes .CW down the page. If there are no .CW view statements, each snapshot depicts all views in the script. If the title is enclosed in quote marks, they are stripped and leading space is kept. If no title is given for a particular view, the view name itself is used as a title; thus an empty title is needed to turn off printing. .PP Parameters can be set by assignment statements of the form .P1 @parameter_name@ @value@ .P2 All parameters are reset to their default values at each .CW .begin .I stills statement. Numeric values may be of the form .CW n , .CW +n , .CW -n , or absent (zero default). .IP .I Filename parameter: .CW file . The script file is named by assigning to the .CW file parameter with a statement of the form .CW file .CW basename.s . The .I stills program .I develop s that script file and then reads .CW basename.i . .IP .I "Text sizes" : .CW "small medium big bigbig" . The assignment .CW small .CW -2 causes text with the .CW small option to be printed two point sizes smaller than the current .I troff point size. Assigning .CW "+5" or .CW "5" to .CW "bigbig" increases the point size by 5 for .CW bigbig text. All changes are relative; there is no way to set absolute point size. .IP .I "Line widths" : .CW "solid fat fatfat" . Relative size changes for line widths, exactly as for text sizes. .IP .I "Direction" : .CW "across down" . By default, snapshots proceed across the page in time. The assignment .CW down .CW 5 causes time to proceed down the page for 5 snapshots before starting a new column; .CW down .CW 0 or .CW "down" yields as many snapshots as will fit on an 8-inch page. The assignment .CW across .CW 7 gives 7 snapshots in a row before starting a new row; .CW across .CW 0 or .CW across adapts to a 6-inch width. .IP .I "Frame parameters" : .CW "frameht framewid margin" . The height and width of frames are given in inches; defaults are 1.5. The margin of a frame is the white space surrounding the data; the default is 0.05, or a five percent border. .IP .I "Optional parts" : .CW "frames times" . Frames are the solid borders around pictures; times are the click name and number that triggered a snapshot. Both have the default value .CW vis and are shown; they may be suppressed by assigning them the value .CW invis . .PP In summary, .I stills input consists of these commands: .P1 print all print final print @clickname@ all print @clickname@ @number@ @number@ @number@ ... view @name@ @optional@ @title@ @parameter_name@ @value@ .P2 .LP At least one .CW print statement and a .CW file assignment are mandatory; other statements are optional. The parameter names in the right column may appear on the left side of a name/value assignment: .P1 .ta 1.1i \f2Filename\fP file \f2Text sizes\fP small medium big bigbig \f2Line widths\fP solid fat fatfat \f2Direction\fP across down \f2Frame parameters\fP frameht framewid margin \f2Optional parts\fP frames times .P2 ......... .NH Larger Animations .PP The examples in this section illustrate algorithms on several classes of data structures, including arrays, trees and graphs. The graphical style is simple; this is easy for the animator and effective for the viewer. The programs in this section are not presented as paradigms of good programming style; rather, they show how succinct programs can yield useful animations. .PP In the paper cited earlier, Brown and Sedgewick employ several conceptual levels in animating an algorithm. .IP .I Execution. At one extreme is the program to be animated, executing on the data of interest. .IP .I "History of ``Interesting Events.'' What events in a computation should be depicted in the animation? The simple animation of insertion sort in Section 2 used augmented .CW less and .CW swap routines to capture two primitives of most sorting programs: comparisons and data movements. It also explicitly recorded information associated with the interesting event of finishing a phase. .IP .I "Geometric interpretation of events. One must next decide how to represent the interesting events pictorially. An array of integers, for instance, might be represented by a sequence of numbers, a scatterplot of bullets, or a sequence of vertical bars. .IP .I "Rendering on a device. In our system, this is the job of .I movie and .I stills . .LP The sample program .CW is.gen identified interesting events and gave them a geometric interpretation in separate procedures within a single program. Alternatively, it may be more convenient to implement the various tasks as a pipeline of two programs: a generator program writes interesting events that are given a geometric interpretation by a program that writes a script file. .PP One usually prints a .CW click statement immediately after the event it marks. Sometimes, though, one draws additional objects to highlight the event, which are erased immediately after the .CW click . In that case, one uses a sequence like .P1 @draw@ @event@ @E@ @highlight@ @E@ click E @remove@ @highlights@ .P2 .sp 1 .LP .I "Sorting, Again." .PP We will return to the subject of sorting with a more interesting animation: a race of insertion sort versus quicksort. We will use the same insertion sort we saw earlier, and a quicksort described in Section 10.2 of |reference(programming pearls). The two sorting routines and their supporting functions are contained in this .I awk program: .P1 .get race.gen .P2 Quicksort is called as .CW "qsort(l,u)" to sort the subarray .CW x[l..u] . The function .CW draw represents the numbers to be sorted as vertical lines. The .CW BEGIN block sets .CW n , initializes the array, draws the initial representation, and then calls a sort routine. As it stands, the code depicts a 50-element quicksort. .PP Some algorithm animation systems present races of programs by implementing a simple form of time slicing. To create a race in our system, we first ran the program into the file .CW qs.s . We then changed the final line in the .CW BEGIN section to call .CW isort , and ran that into the file .CW is.s . Finally, we merged the two scripts into one with this .I awk program: .P1 .get race.splice .P2 The loop copies the script of insertion sort until it encounters a .CW click .CW comp statement; it then copies quicksort until it encounters the corresponding .CW click , at which points it prints the .CW click statement. The variables .CW s1 and .CW s2 store the status of the most recent .CW getline s of the two files; the status is one if a record was found and zero if an end-of-file was encountered. When one file is exhausted, the remainder of the other is copied. (A production splicer should have a more graceful interface for naming the files and views.) .PP The resulting script file is an execution of the sorts in two parallel views, synchronized by comparisons: .INCLUDE race As before, insertion sort sifts each element into place in turn. This picture only hints at the operation of quicksort; insight into that algorithm requires the identification of interesting events beyond comparisons and swaps. Quicksort finishes after 240 comparisons, while insertion sort takes almost three times as long. For completeness, here is the .I stills input that produced the picture: .P1 .get race.t .P2 .sp 1 .LP .I "Trees." .PP Here are pictures of a (nonbalanced) binary search tree after inserting 5, 10, 15 and 20 random integers in the range 0..999: .INCLUDE bst In the last two frames, the labels for node 3 and 13 are squeezed too close together. The script was generated by this .I awk program: .P1 .get bst.gen .P2 The animation code consists of just three lines in the .CW insert procedure. .PP The pictures give insight into random binary search trees in spite of being rather ugly. The trees have two distinct failings: the depiction of individual nodes, and the layout of the entire tree. .PP A node is represented by its numeric value; each node is connected to its parent. If the shape of the tree is more important than the values it contains, one can delete the values entirely. We will shortly see a tree with more graceful edges. .PP The other aesthetic issue is the layout of the tree. The @y@-value is the depth of the node in the tree, which is a very robust choice (one could also use the time at which the node was inserted). The @x@-value in this example is simply the randomly generated value itself; there are many alternative choices. One could instead use the number of the node in an inorder traversal, which involves a multiple-pass algorithm: the tree is first built, then traversed and numbered, and the insertions are then reported with knowledge of the numbers. For this representation, it is crucial to separate the interesting events from their geometric representation; it is convenient to calculate these in two filters in a pipeline. .PP This animation of heapsort uses an alternative representation of trees. It was generated by a 50-line .I awk program. .INCLUDE heap Each snapshot shows the result of a .CW sift operation. The first four .CW sift s build the heap; subsequent .CW sift s maintain the unsorted elements as a heap. Arrows point from lesser elements to greater elements. .PP A node in the heap is represented by its value; lines between nodes have a single arrowhead and are chopped by twenty percent at each end. The root of the heap is at @(1/2,~-1)@, its two children are at @(1/4,~-2)@ and @(3/4, ~-2)@, their four children are at @(1/8,~-3)@, @(3/8,~-3)@, @(5/8,~-3)@, @(7/8,~-3)@, etc. .PP Other tree layouts proved useful in animating two algorithms dealing with parse trees. In both cases, a node's @x@-value was the minimum of the @x@-values among the node's descendants (equivalently, the @x@-value of its leftmost child); all edges were therefore either vertical or slanting down to the right. A random sentence generator built the tree left-to-right and top-down; just as in the binary search tree, the height of a node was one less than its parent. A parser built the tree in postorder and bottom-up: the height of a node was one greater than the maximum of the heights of its children. .sp 1 .LP .I "A Graph Algorithm." .PP Prim's algorithm for computing the minimum spanning tree (MST) of a graph starts with a fragment consisting of a single vertex. It increases the fragment by adding the nearest vertex until all vertices are in the fragment, at which point it is the MST of the entire graph. This picture shows Prim's algorithm on the complete graph induced by a set of 50 planar points; the weight of an edge between two points is defined to be their Euclidean distance. .INCLUDE mst2 The snapshots are taken every ten stages. .PP The obvious implementation of Prim's algorithm on an @N@-point set requires time proportional to @N sup 3@. Dijkstra discovered an elegant implementation of the algorithm with running time proportional to @N sup 2@: every point not in the fragment keeps a pointer to its nearest neighbor in the fragment. Here is Dijkstra's implementation on a ten-node planar graph: .INCLUDE mst1 In this animation, nodes in the fragment are bullets, nodes not in the fragment are crosses, edges in the MST are .CW fat lines, and the nearest neighbors are pointed to by arrows. .PP These two sequences illustrate two styles of drawing graphs with our system. Dots and lines are sufficient for simple algorithms, while various symbols and line options can depict subtle processes. .PP The geometric nature of the above graphs made them easy to lay out. Laying out a general graph is very hard. If the graphs in your applications are specialized (such as trees), you might exploit that structure to compute an effective layout. A graph of @N@ vertices can be easily represented by an @N times N@ matrix in which the @i,j@-th element represents the edge from vertex @i@ to vertex @j@; that is useful for insight into some graph algorithms. If you have access to a program that produces good layouts of general graphs, you might use that program to compute positions of vertices, and then feed those into our system. .sp 1 .LP .I "A Memory Allocator." .PP The .I develop program uses the .I malloc memory allocator for several of its data structures. We augmented .I develop 's calls to the allocator with data gathering routines to produce an animation; here is the final snapshot. .KF .INCLUDE malloc .KE The left frame is the arena of storage from which memory is allocated. Memory blocks are represented by lines, low addresses are at the bottom of the picture, and the picture is 1024 bytes wide. The right frame is a histogram of the sizes of memory currently allocated; there is a dot for each element, a vertical bar every ten positions to help counting, and the maximum value is in the lower right corner. .PP This snapshot was taken at the end of execution of .I fdevelop . The histogram shows two large blocks of 20,000 and 40,000 bytes, 96 blocks of size 16, and 96 slightly larger blocks (the blocks of size 16 are symbol table records; each points to an allocated string). The arena shows the two huge pieces (the larger is higher) and a gap above the smaller (memory allocated by procedures that didn't call our augmented .I malloc ). The remainder of the arena is allocated efficiently. .PP A movie like this helped us find a bug in .I fdevelop : an early version allocated the symbol table nodes but did not .I free them. This problem manifested itself in an overloaded arena and a huge spike in the histogram at size 16. .PP The .I fdevelop program interacts with the storage allocator only through the two routines .I emalloc and .I efree . We animated the storage allocator by modifying those routines: .P1 .get malloc.c .P2 They write on the named file output lines of two types: .P1 m @address@ @length@ f @address@ .P2 The first line denotes that a .I malloc of the given length returned the given address; the second marks a .I free . .PP The resulting history file contains the interesting events; they are given a geometric interpretation by a subsequent program. Here is a simple program that generates only the arena view from the script file: .P1 .get malloc.awk .P2 The .CW BEGIN block initializes variables, the actions for .CW m lines draw memory, and those for .CW f lines erase memory. The variable .CW s is the starting byte of a block; .CW e is the ending block. The variables .CW sx and .CW sy are the @x@ and @y@ positions of the starting byte, and similarly for .CW ex and .CW ey . If the block fits on one line, then only a single line fragment need be drawn; otherwise, fragments of three types are needed. .PP The complete program for generating scripts from history files is 56 lines of .I awk . To ease tracing the action in the arena, it marks a .I malloc with an .CW x and a .I free with an .CW o . The histogram view is embellished with bars and the maximum value. There is room for further elaborations; one might, for instance, want to put either or both of the axes of the histogram on logarithmic scales. .sp 1 .LP .I "Dynamic Statistical Displays." .PP Rick Becker constructed this display of air pollution in the Northeast United States: .INCLUDE ozone The data was gathered hourly on a single summer day in the early 1970's. The radius of each circle is proportional to the ozone reading (a common measurement of air pollution) at one of 32 stations in New Jersey, New York, Connecticut, and Massachusetts. The radius of the clock denotes the maximum ozone level prescribed by the Environmental Protection Agency; its hour hand goes from 7:00 AM to midnight. .PP This display shows how New York City's air pollution is blown to the northeast. Becker and his colleagues prepared a similar movie in the early 1970's using the technology of the day; it required several weeks of programming time, then a weekend with a movie camera to make the final film. He built this display from the same data in a couple of hours, then prepared a video tape of the resulting movie in under thirty minutes. The original movie was a bit nicer (it drew the background map and the circles in two different colors), but the new movie is just as useful, and provides stills for free. ...... .NH Living With The System .PP The system that we have described is the bare bones of an animation environment. We have found that the most fruitful way of enhancing the environment is not by modifying the primary programs, but rather by using small filters that interact with the various files in the system. .PP We showed earlier, for instance, a race of two sorting algorithms. While other animation systems implement races with a general mechanism for time sharing, we did the job with a small .I awk program that merges two files. Our system does not have a facility for counting clicks; rather, we use filters such as .P1 grep 'click comps' | wc .P2 to see how many comparisons were made. We will even admit to using text editors to make minor changes to both script and intermediate files. .PP We have built several useful filters in addition to .I merge . The program .I view.clicks prints a summary of the views and clicks used in a script file; it is helpful as one is preparing a .I stills file. Its implementation uses the intermediate file described in Appendix I: .P1 .get view.clicks .P2 The first step of the shell script is to develop the script file; the subsequent .I awk program then reads the resulting intermediate file. The first pattern/action pair prints for each view its name and the @x@ and @y@ ranges in the script file. The second pair builds a string of all clicks from the define click statements, and the third pair prints that string and exits at the first non-define statement. .PP The program .I show.clicks takes a script file as input; its output is a new script file containing all information in the input and, in addition, a new view named .CW click.count in which the various clicks are counted. This is useful for preparing .I stills files and for debugging. Its input is a script file, either named explicitly or as the standard input. Here is the code: .P1 .get show.clicks .P2 The second pattern/action pair stores the name of the current view, and the fourth action copies each line onto the output file. The first pattern/action pair supplies a default view name, if needed. .PP The work is done when the third pattern recognizes a .CW click statement. The .CW if statement puts the click name in .CW cname , and the .CW print statement switches to the new view. The second .CW if statement is executed when a new .CW click statement is seen; it assigns it a number and prints out the click name, once and for all. The two following statements rewrite the appropriate count and place a bullet next to it. The final statement returns to the current view. .PP One can use the ideas in .I show.clicks to process lines in the script file of the form .P1 @name@ = @value@ .P2 The output script file has a new view named .CW variables ; it contains the name of each variable mentioned and its current value. .PP Larger filters have also proven useful. For instance, we built a set of tools to render animations of three-dimensional lines and text (circles and rectangles were not supported). The primary program translated a three-dimensional script into a standard script that contained two two-dimensional views for each three-dimensional view; the resulting .I movie and .I stills were suitable for viewing with standard stereo viewers. Support programs included a filter for rotating a view around a given line. .PP The .I movie and .I develop programs are in fact simple shell scripts that call filter versions named .I fmovie and .I fdevelop . You may find it convenient to rewrite those shell scripts for your environment. .SH Acknowledgements .PP We are deeply indebted to Howard Trickey; he gave us invaluable advice for getting a minimal animation facility working in the Sun environment, then finished the job properly. He subsequently made it all work under the X window system. Andrew Hume and Jane Elliott made possible our first experiments with animation. Our early users, Rick Becker and Chris Van Wyk, gave us bug reports and suggestions for improvements. Eric Grosse, John Linderman, Doug McIlroy, Steve Mahaney, Howard Trickey, and Chris Van Wyk made helpful comments on this paper. .SH References .LP |reference_placement .sp 100 .BP .SH Appendix I \(em Intermediate Files .PP This appendix defines the intermediate files produced by .I develop . The files are easier to process than the corresponding script files. For instance, names are converted to small integers, floating point numbers are scaled to integers in 0..9999, and commands are abbreviated to single letters. .PP A line whose first non-blank character is .CW # is a comment. .PP An intermediate file begins with define statements that give the names of the views and the clicks: .P1 d v @vnum@ @viewname@ @minx@ @miny@ @maxx@ @maxy@ d c @cnum@ @clickname@ d p @any@ @text@ d p e .P2 Fields are separated by tab characters. Both views and clicks are numbered 0, 1, 2, .... The four final numbers on a view line tell the range of the coordinates in the original script file. A line that begins with .CW "d p" is a ``pragma''; both .I movie and .I stills currently ignore all such lines. The defines appear at the front of the file in the order views, clicks, pragmas, then the ``end of defines'' pragma .CW "d p e" . .PP The geometric commands for lines, boxes, circles and text are mapped to the following: .P1 g @slotnum@ l @vnum@ @opts@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@ g @slotnum@ b @vnum@ @opts@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@ g @slotnum@ c @vnum@ @opts@ @x@ @y@ @rad@ g @slotnum@ t @vnum@ @opts@ @x@ @y@ @text@ @string@ .P2 Objects that are never erased have slot number 0; other objects are placed in ``slots'' that can hold at most one object. The third field is the type of geometric object; the fourth field is the view number. All @x@ and @y@ values are normalized to integers in the range 0..9999. There is a single separating tab before the (unquoted) text string. Options are given as a string of characters, whose length and interpretation are summarized as: .P1 .ps -2 .vs -3 OBJECT POS NAME ABBREV text 1 center c ljust l rjust r above a below b 2 medium m small s big b bigbig B line 1 solid s fat f fatfat F dotted o dashed a 2 - - -> > <- < <-> x box 1 nofill n fill f circle 1 nofill n fill f .vs +3 .ps +2 .P2 For instance, the options for a text string are described by two characters giving its position and its size; .CW small .CW center text has the option string .CW cs . Further options may be added at the right end of the string; subsequent programs should ignore letters they don't expect. .PP A click statement is represented as .P1 c @cnum@ .P2 .PP An erase statement is translated into .P1 e @line@ @repeated@ @here@, @except@ e @italic "for"@ @leading@ g .P2 A processor may choose to implement this statement using either the geometric description or the slot number. .PP A .CW clear statement (which erases all objects in a view) is translated into a pair of starting and ending ``blank'' commands that bracket a sequence of erase statements: .P1 b s @vnum@ b e @vnum@ .P2 The erase statements together clear the view. A processor may choose to implement the .CW clear either by ignoring the .CW b commands and letting the erase statements take their course or by explicitly processing the start command and then ignoring .CW e commands until encountering the .CW "b e" line. .PP As an example, running .CW develop on this trivial script file .P1 line 1 2 3 4 text small above 5 6 "Hello, world." click stage clear .P2 produces this intermediate file: .P1 d v 0 def.view 1 2 5 6 d c 0 stage d p e g 1 l 0 s- 0 0 4999 4999 g 2 t 0 as 9999 9999 Hello, world. c 0 b s 0 e 1 l 0 s- 0 0 4999 4999 e 2 t 0 as 9999 9999 Hello, world. b e 0 .P2 .PP Here is a summary of the commands in the intermediate language: .P1 # @comment@ b s @vnum@ b e @vnum@ c @cnum@ d v @vnum@ @viewname@ @minx@ @miny@ @maxx@ @maxy@ d c @cnum@ @clickname@ d p @any@ @text@ d p e e @line@ @repeated@ @here@, @except@ e @italic "for"@ @leading@ g g @slotnum@ l @vnum@ @opts@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@ g @slotnum@ b @vnum@ @opts@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@ g @slotnum@ c @vnum@ @opts@ @x@ @y@ @rad@ g @slotnum@ t @vnum@ @opts@ @x@ @y@ @text@ @string@ .P2