- Write several useful functions for drawing box
structures:
- (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.
- (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.
- (down-arrow x y yto ) should draw a downward arrow from (x, y) to (x, yto).
- (right-arrow x y xto ) should draw a right-pointing arrow from (x, y) to (xto, y).
- (stringify x ) should convert its argument to a string if it is not one already; it should handle symbols and integers.
- (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.
- 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:
- If tree is not a pair, use atom-draw to draw it.
- Otherwise, draw a pair box (two squares) to represent the pair.
- 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.
- 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.
- Make sure that all cases of draw-lisp return the maximum x value of the drawing made during that call.
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 |
| 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:
- If the argument is terminal, draw it by sending it a
draw message:
(drsend tree 'draw x y size). - Otherwise, for a nonterminal node:
- 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.
- 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.
- Calculate the center x position over the two subtrees and draw the nonterminal node there (subtract half its width from the center).
- 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?
