View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

James "Jorge" Roberts's CRAZY milestone 1

The code

the code

High level overview

What we're doing in this project is basically building a tree structure. Each node in the tree has to be able to contain data, and the tree has to be able to be drawn to the screen somehow.

So... when you think of trees you think of recursion? right? Well, that's what I think of, and this project uses it in spades. For starters, each node is capable of drawing itself, and all of its descendents. This makes things sound a lot easier than they actually turned out to be.

Otherwise things are pretty straight forward. That is, each Tree object contains a generic variable for holding its data, and some type of collection for holding its leaves.

The formatting is done pretty well if I do say so myself. Below we find an example output from a Tree, this one an organizational chart of team Fox Force Five basically showing you who's responsible for what:


The workspace code can be found here.

It also does a pretty descent job of getting everything onto the page, and generally avoiding stick situations. Oh yeah, it does more than just Strings too! Lets try to break it:


The workspace code can be found here.

OK, it doesn't look too pretty, but its still working as it should. Let's give it one more shot:


The contrived workspace code can be found here.

Reuse

Since this was my first Squeak (and Smalltalk for that matter) project, I wasn't too sure what classes were already built for me. In particular, I had a bit of trouble figuring out what type of collection to use for holding the leave nodes. I won't bore you with the details; I ended up using the OrderedCollection.

The code


Basically most of the code went into the formatting, and drawing of the tree. Everything else is pretty simple: The data is stored as a global variable, and leaf nodes are stored in an OrderedCollection.

One point of interest was the storage of DisplaySize and VSpacing. Those being the dimensions of the Form on which the Tree structure would be displayed and the distance between two node generations respectively. Using good ole' cs1501 mentality I felt that both these values should be constant variables and thus only a single copy should exist for all instances. The main obstruction to this mentality was that there was no central location in which to initialize these two variables. I ended up initializing them in the initialize method of the Tree object, which really defeats the purpose of having them as class variables.

displaying the tree

Like I said, the displaying is done recursively, but it is not as simple a task as it may seem. To put is simply, the formatting really gets in the way. The vertical location of a node is easy to figure out – just keep track of the depth of recursion. But what about the horizontal location? There's really know way to know to place a node if you don't know how many other nodes exist in its generation. And if you think that's tricky, consider those connecting lines! With them, you need to know were your current node will be drawn, and where all of its children will be drawn.

My basic solution to both problems was to consider recursion not in terms of individual Tree nodes, but rather in terms of generational levels. Each recursive call would take in two parameters: 1) the depth of recursion and 2) all of the nodes that exist at that depth.

Here's how it all works

display
| starterList |
	(Form extent: DisplaySize) fillWhite display.
	starterList _ OrderedCollection new.
	starterList add: self.
	self displayHelper: starterList startAt: 1.

This chunk of code is the method that gets it all started. It starts by creating a form, and throwing it on the screen. Note the use of the DisplaySize class variable as discussed above. Next an ordered collection is created, the self node added, and then the collection is thrown into another method.

So what's going on? Well, that method will display all the nodes on a generational level. And since we're now in the root node, we pass a collection in with only that root node, and tell it to start the graph at generational level 1.

The helpfull helper method


This thing is a monster. If you want the code, then download the whole thing. Here I will just try to explain how it works.

The first thing the method does is collect all of the nodes that make up the next generation of the tree structure. It does this for two reasons: First, we need the next generation to make the recursive call at the end of the method, and second, we need to know how many children nodes there will be so that we know where to draw the connecting lines.

Next we determine the horizontal spacing for the current generation. Simply the width of the Form (i.e. DisplaySize x) divided by the number of nodes. Here the rounded method helped out by keeping results as integers rather than floating point. The same deal is performed for the next level.

Once we know the current generation's spacing and the next generation's spacing we can begin to draw stuff. The current generation's text can be drawn at the calculated spacing. As for the connecting lines, for every node in the current generation, draw a line for each of its children.

Do some bounds checking along the way to make sure everything stays on screen and doesn't run all over itself, recurse, and your done!

What I would do differently


For starters I'd get rid of those class variables. They not doing much good. The whole situation leads me to ask "what is a good way to store constants in Smalltalk"... class variables seem like a good cantidate, but then you get involved with the whole initialization thing.

Link to this Page