Comp202: Principles of Object-Oriented Programming II
Fall 2006 -- The PlayRoundAlgo   

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 problem.

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 those situations.

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 played.
  • 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 condition.
      • 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 conditional statements.

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:

1. 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".
2. 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).
3. 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.
4. 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!).
5. 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.
6. No method has more than 3 lines of code. Many only have one line, the return statement.
7. 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.
8. Put stub code in for pieces where you need return values but aren't ready to code it all yet.
9. 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!
10. Under no circumstances attempt to program the whole algorithm at once!

Back to main project page

Last Revised Thursday, 03-Jun-2010 09:52:23 CDT

©2006 Stephen Wong and Dung Nguyen