## CS 307: Assignment 9: Drawing Trees

Due: Wednesday, November 7, 2001

This assignment involves two recursive programs to draw tree data structures; the second one will introduce object-oriented programming.

1. Write a program to draw box diagrams for Lisp list structures.
1. Write several useful functions for drawing box structures:
1. (draw-square x y size ) should draw a square. The square should be size wide and size high. (x, y) should be the upper-left corner of the square; we will use this upper-left convention for all locations in our tree-drawing programs.   Return the value x + size; we will follow the convention that all drawing programs return the x value of the rightmost thing that was drawn.
2. (draw-diagonal x y size ) should draw a diagonal line through the square whose upper-left corner is (x, y) and whose size is size.
3. (down-arrow x y yto ) should draw a downward arrow from (x, y) to (x, yto).
4. (right-arrow x y xto ) should draw a right-pointing arrow from (x, y) to (xto, y).
5. (stringify x ) should convert its argument to a string if it is not one already; it should handle symbols and integers.
6. (atom-draw atom x y size ) should draw an atom (symbol, number, or string) within an imaginary box whose upper-left corner is (x, y) and whose size is size. Return the value x + size.

2. Write a program (draw-lisp tree x y size ) to draw a box diagram for a list structure. (x, y) is the upper-left corner of the tree. We will use the convention that draw-lisp will return an integer that is the x value of the rightmost thing it has drawn. draw-lisp should be a recursive program using the following cases:
1. If tree is not a pair, use atom-draw to draw it.
2. Otherwise, draw a pair box (two squares) to represent the pair.
1. If the car of the pair is null?, draw a diagonal through the left half of the box; otherwise, call draw-lisp recursively to draw the car at the same x position and a y position that is 2 * size below the y of the box. Save the position of the rightmost part of the drawing that is returned by draw-lisp. Draw a downward arrow to the car diagram.
2. If the cdr of the pair is null?, draw a diagonal through the right half of the box; otherwise, call draw-lisp recursively to draw the cdr at the same y position and an x position that is size to the right of the maximum of the box size (2 * size) and the x value that is the rightmost part of the drawing of the car.
3. Make sure that all cases of draw-lisp return the maximum x value of the drawing made during that call.

2. Write an object-oriented program draw-tree to draw a picture of a binary tree structure. We would like for this program to implement the essence of drawing a binary tree and to work for any kind of tree and any way of drawing its components; therefore, we would like for the program to be abstract and not to include unnecessary assumptions about the implementation of binary trees.

We will use a form of object-oriented programming (OOP) to write the program in a data-independent form. In OOP, we send messages to objects rather than calling functions on data. Sending a message is in fact a function call, but the system determines what function to call from the class of the object to which the message is sent and the selector (abstract function name) of the message; the function that implements the message for a given class of objects is called a method.

Examine the file droop.scm to see the simple object-oriented system that we will use for this assignment. All of the methods mentioned in the list *methods* will be needed; some are defined in this file, and you will need to write the others. Your function draw-tree will send messages to the objects it deals with to avoid having to know about their implementations.

Load the file droop.scm and try the following examples to see how messages work.

```(drclass 5)               (drsend 5 'terminal)
(drclass 'foo)            (drsend '(a b) 'terminal)
(drclass '(a b))          (drsend '(a b) 'left)
(drclass '(box 30))       (drsend '(a b) 'right)
```

For purposes of drawing binary trees, we assume that objects can respond to the following messages. The argument self is the object to which the message is sent;
e.g., in (drsend 5 'terminal) self would be 5.
 terminal self True if self is a terminal node (has no children) draw self x y size Draw self in a box whose upper-left corner is (x,y) with size size
For non-terminal objects, the following additional messages are defined:
 left self Left subtree of self right self Right subtree of self leftx self x size x position of line from the drawing of self to its left subtree lefty self y size rightx self x size x position of line from the drawing of self to its right subtree righty self y size width self size width of the drawing of self drawline self x y xto yto Draw a line from (x,y) to (xto,yto)

draw-tree will follow the convention that its input position (x,y) is the upper-left position of the tree to be drawn; it will always return the rightmost x value of the tree that it draws. draw-tree should work as follows:

1. If the argument is terminal, draw it by sending it a draw message:
(drsend tree 'draw x y size).
2. Otherwise, for a nonterminal node:
1. Draw the left subtree at the given x value and a y value that is lower by 2 * size. Save the rightmost position of the left subtree.
2. Draw the right subtree at the rightmost x value of the left subtree plus a space of size, and the same y value as the left subtree. Save the rightmost position of the right subtree.
3. Calculate the center x position over the two subtrees and draw the nonterminal node there (subtract half its width from the center).
4. Draw lines from the two diagram positions (leftx,lefty) and (rightx,righty) to the top centers of the respective subtrees.

As one example of binary trees, we will use Lisp trees. A Lisp pair should be drawn as a pair box, with its arrow positions at the centers of the two halves of the pair drawing. Add a method to draw an empty list as a small square.

As a second example of binary trees, we will define a mobile object. A mobile node has two subtrees: (mobile left right ). The subtrees may be other mobiles, Lisp atoms (symbols or integers), or a box or triangle or diamond: (box width ), (triangle width ), (diamond width ). A mobile node should be drawn as a vertical line (zero width) with both connecting line positions at the bottom. A connecting line for a mobile should be drawn as vertical, horizontal, then vertical.

Demonstrate that the same program will draw both a Lisp tree and a mobile. Test data are provided in the file droop.scm . What happens if mobiles and Lisp trees are mixed in the same data structure?

3. Extra Credit: Add to the *methods* list a set of methods to allow an expression to be drawn as a binary tree. Represent an expression as a list consisting of the class name expr followed by the expression, e.g. (expr (= y (+ (* m x) b))). Draw the operator when the expression is a list, or the expression if it is not a list. Rather than creating a fully nested expression consisting of expr objects, simply "wrap" each subexpression in (expr ...) when asked to return the left and right subtrees.