Comp202: Principles of Object-Oriented Programming II
Fall 2006 -- The
The PlayRoundAlgo visitor
will cause a tournament tree to play one round of the tournament and return the
top level winner. That top level winner may be a Unknown Team
if the round did not create a winner at the top level. This is a somewhat more
complex algorithm than the InsertTeamAlgo, and here's
where we will see how the process flow analysis will make short work of the
Basically, the PlayRoundAlgo searches the tree for
nodes with Unknown Teams that have Known Teams in the data of both sub-trees.
The process flow analysis will automatically identify any possible error
conditions and force the programmer to write code to create robust behavior in
The above flow traces out the path needed to determine how to "play" a round
of the tournament. Here's the subsequenet layout in text terms, showing all the
cases and sub-cases:
- Top (parent) node is empty: Can't do anything!
- Top (parent) node is non-empty -- depends on state of the team held
as the rootDat., so delegate to it.
- Top (parent) ATeam is a Known Team: Don't do anything. Already
- Top (parent) team is an Unknown Team -- depends on states of
sub-trees, so delegate to (one of) them.
- Left child is empty: Can't do anything! Error condition.
- Left child is non-empty -- depends on state of sibling
sub-tree, so delegate to it.
- Right child is empty-- Can't do anything! Error
- Right child is non-emtpy-- depends what's in the
sub-trees are, so check out the local one.
- Right team is an Unknown Team: Cannot play at this
level yet. Recur into both sub-trees.
- Right team is Known Team -- depends on state of
sibling's Team, so delegate to it.
- Left Team is an Unknown Team: Can't play at
this level yet. Recur into this sub-tree.
- Left Team is Known Team: There are two Known
Teams present. Play them and set the top level rootDat
to the winner.
In procedural programming the above diagram would map to a a large nested
if-statement. In OOP, it maps to a series of delegating calls from one object to
the next. These calls use polymorphism to systematically figure out what state
the system is in and perform the correct behaviors. Note that the delegation
method automatically covers all the possible situations of the system, forcing
the programmer to deal with them. In procedural programming, it is common to
accidentally leave out certain rare or unexpected situations and then have the
code suddenly fail. The delegation method of OOP creates very robust code.
In a simple situation like this one, procedural code using if statements
would probably be faster and more efficient but at the price of robustness. The
point of this project is for you to gain experience in a technique that is
necesary in larger systems where the logic would be too complex and error-prone
to use procedural techniques. This dispatching technique is essentially
functional programming that utilizes OO prolymorphism to eliminate the
Program the above process using anonymous class IVisitor and ITeamAlgo
visitors dispatching into BiTrees and teams. You will have anonymous classes
nested inside of anonymous classes (5 levels deep at one point!). Here are some
tips to help keep you out of major amounts of trouble:
- Always know what node/object you are in at any given moment in your
algorithm! Use names that help you remember, like "leftBRSHost", "rightBRSHost",
"leftTeamHost", and "rightTeamHost".
- When writing nested anonymous classes of the same type, change the names
of the input parameters at each level. Use names that reflect what those
parameters actually are (see the above suggestion).
- If a nested anonymous class needs to access the input variable of the
method that encloses it, declare that variable "final" in the method
signature. Otherwise it won't be accessible.
- Remember that an inner class is scoped to private of the enclosing class,
so it has access to all the local variables and final input variables. (You
won't need any local variables in this algorithm!).
- No if statements are allowed or needed, except to decide a winner
when two Known Teams actually play. See the
description of the "?:" operator to see a nice way of doing this.
- No method has more than 3 lines of code. Many only have one line, the
- Work slowly, adding one more layer each time and testing the code at each
layer.You can test the partially completed code by putting in print
statements that show you where you are when a method is executed.
- Put stub code in for pieces where you need return values but aren't ready
to code it all yet.
- Watch the output and verify completely that it is doing what you think it
should be (check it against the process flow diagram above) before going to
the next level!
- Under no circumstances attempt to program the whole algorithm at once!
Back to main project page
Thursday, 03-Jun-2010 09:52:23 CDT
©2006 Stephen Wong and Dung Nguyen