CS 60, Fall 2001

Assignment 5, Due Wed. 10 October

Applications that require drawing of trees are ubiquitous in current software products. For example, most operating systems have a way of drawing the file system as a tree. Construct a Java applet (small application) that displays any Polylist as a data structure box diagram. For example, this R-expression

[alpha,
 beta,
 [gamma, delta],
 epsilon,
 [],
 [zeta, [eta, [theta, iota]]],
 [[kappa, [lambda, mu]]]
]

should display as something close to the tree on the next page. This image was captured from an applet running in Netscape 4.74 on a Mac from a web page:

www.cs.hmc.edu/courses/2001/fall/cs60/examples/java/treeDraw/treeDraw.html

Your applet should include a method that accepts an arbitrary Object, which might be a Polylist, and draws the corresponding diagram. Objects that are not Polylists are shown by drawing the result of their toString() method. It is not necessary to do input of Polylists from a source outside the applet. The Polylist shown here was produced by the statement:

Polylist testTree =
    Polylist.list("alpha",
		  "beta",
		  Polylist.list("gamma", 
				"delta"
			       ),
		  "epsilon",
		  Polylist.nil,
		  Polylist.list("zeta",
				Polylist.list("eta",
					      Polylist.list("theta",
							    "iota"
							   )
					     )
			       ),
		  Polylist.list(Polylist.list("kappa",
					      Polylist.list("lambda",
							    "mu"
							   )
					     )
			       )
		 );

For grading and help purposes, please use the name TreeDraw as the name of your class.

Your tree drawing method should conform to the following prototype:

int drawTree(Object ob, 
             int Xoffset, 
             int Yoffset, 
             int Xdelta, 
             int Ydelta, 
             int featureSize)

where:

1. Ob is the Object to be drawn, which may or may not be a Polylist. If not, then just the value of the tostring() method is drawn.
2. Xoffset is the horizontal offset for the root of the object.
3. Yoffset is the vertical offset for the root of the object.
4. Xdelta is the number of pixels between horizontal layers.
5. Ydelta is the number of pixels between vertical items.
6. featureSize is the size of one box in pixels.

To help you get started with Java applets and graphics, we supply a sampler in

www.cs.hmc.edu/courses/2001/fall/cs60/examples/java/appletGraphics/

1. How to set up an applet. Note that an applet has no main program that you specify. The role of main is taken over by the init() and run() methods of the applet.

2. Setting up a .html file to drive the applet. Applets are invoked either through a web page or using the program appletviewer on the host. For the latter, you would need to use either an Xterm on turing (one of the terminals in B102) or an X windows client on your machine. For the former, you only need a web browser.

3. How to create an image buffer for flicker-free drawing. Although flicker is not a big issue with this assignment, it will be important later.

4. How to draw simple features, such as rectangles, lines, and character strings, on an image.

You may also use the skeletal program in

www.cs.hmc.edu/courses/2001/fall/cs60/examples/java/treeDraw/TreeDraw.java

www.cs.hmc.edu/courses/2001/fall/cs60/examples/java/treeDraw/treeDraw.html

Note also that the structure of the diagram is similar to that produced by the analysis method in the notes, the difference being that there the tree is printed out, whereas here it is drawn.

As always, let recursion do (some of) the work for you.