COMP 405 Spring 2014	Tournament Trees and Process Flow Diagrams

Here we will explore using binary trees and a their algorithms. To do so, we will set up a "tournament" tree that will simulate a sports playoff tournament (single elimination). This will involve creating classes that represent teams, and the associated algorithms to insert the teams into the tournament tree and to play one "round" of the playoffs, advancing the winning team to the next level.

This project will involve some tricky and involved algorithms, so proceed slowly, methodically and carefully. To assist our thinking, we will explore a technique we call "process flow diagramming" that will prove invaluable in pulling simplicity from chaos.

The Structure

In order to model the existence or non-existence of a "team" in the tournament, consider the following "data definition":

A "team" has the following:

1. A toString() method that returns the name of the team as a String.
2. An extensibility hook that allows variant behaviors to be added to the team. The extensibility hook method should accept encapsulated variant behaviors that can handle either type of team.

In addition, a team is either:

1. "unknown", which represents the absence of a team. A unknown team always has a fixed name, such as "???".
2. "known", which represents a concrete team with a unique name for every instance. (Don't worry about generating unique names, just name them by hand.)

A tournament has the following "data definition":

A "tournament" is a binary tree where

1. All "known" teams are located on the leaves of the tree initially.
2. All interior nodes of the tree contain "unknown" teams initially. After rounds have been played, the unknown teams are replaced by the winner between the winning teams in the 2 sub-trees.
3. All interior nodes of the tree have sub-trees that are the same type, either both empty or both non-empty. This ensures that there is always a team to play.
4. To "play a round" is defined as replacing all unknown teams on interior nodes that have sub-trees where both contain known teams with the "winner" between the sub-trees' teams.

Check out the demo of the project here.

The Algorithms

Inserting Teams Into A Tournament Tree

The challenge here is to randomly "grow" a tree by executing an algorithm on it. The algorithm will take a known team as an input parameter and then attempt to randomly create a leaf somewhere on the tree and place the team in it.

For a detailed discussion of this topic, please see the section below on the InsertTeamAlgo.

Playing Teams, One Round at a Time.

When a "round" of the tournament is "played", a known team plays it's opponent in its sibling sub-tree. The "winner" then replaces the unknown team in the parent tree's root data. If a team's opponent is an unknown team (i.e. it had a bye), then it must wait for the lower level known teams to play first. Another way to think about it is to say that, in the case of a bye, the winner is always an unknown team. Thus, unless the root data of a tree is a known team, the algorithm must check the left and right sub-trees to determine how to play the round at this level. Plus, playing a round at this level might entail recursively playing rounds at the lower levels of the tree.

For a detailed discussion of this topic, please see the secion below on the PlayRoundAlgo.

Supplied Utility Graphics Classes

brsVisitor.BRSDisplayAdapter (download)-- An MVC adapter that will connect a BiTree to a JPanel in the view. This adapter has much more intelligence that a normal adapter, so you might prefer to consider part of the model and create a smaller, more lightweight adapter that actual does the model-to-view connection.

brsVisitor.BRSGetMaxDepthVisitor (download) -- Used by BRSDisplayAdapter to find the depth of the tree. The depth of the tree is needed to calculate its (maximum) width, which is needed in order to properly place the elements in their horizontal positions

Process Flow Diagrams and the InsertTeamAlgo

Fundamentally the idea here is to insert known team objects (supplied as the input parameter) into a binary tree (BiTree). The known team objects should end up in "leaf" nodes in the tree. That is, the nodes they are in always have null trees as the sub-trees. A known team's "opponent" is the team held as the root data of the team's sibling tree. The interior (non-empty, non-leaf) nodes should always contain unknown teams.

Note that this does not preclude teams from having "bye's". In fact, this capability will insure that a team never has a null tree as an opponent. Thus if a team is inserted into empty tree, the team will be attached as the root data right there. But when the tree being inserted into is non-empty, thre are two possibilities.

1. The data held is an unknown team: Just randomly pick one side (left or right) and recursively add the new known team to that side.  (The ternary "? :" operator discussion for a nice easy way of doing this.)
2. The data held is a known team : Insert the existing known team to the left side, insert the new known team on the right side and replace the data at this node with an unknown team . To accomplish this, simply execute an ITeamAlgo on the team held at the node. Using this anonymous inner class will polymorphically distinguish between the two cases above. Pass the new known team in as the input parameter to the execution of the algorithm, so be sure to make it final so that the inner class can access it (or pass it as the param of the inner ITeamAlgos too -- no need for final then -- why?).

To help us figure out what to do when, we will create a "process flow diagram". A process flow diagram traces the program execution as it travels through a data structure. At every point there may be several cases to consider, each with different resulting actions. An OO system "gets the job done" by delegating from one object to the next until an unequivocal statement of what needs to be done can be made. At every dispatch, a little more is learned about the system, until finally, enough information has been accrued that the correct action can be taken. Process flow diagramming is a technique whose utility is not limited to OO systems. If one were to solve the problem using procedural programming techniques, a process flow diagram is also the correct way to start. This is because it helps formalize the whole process and because it clearly identifies each case encountered, it makes sure that there are no "holes" in the algorithm, creating more robust code.

Below, I have diagrammed out the process flow for the InsertTeamAlgo we need.

To intepret the diagram below:

• The dotted boxes represent individual BiTree nodes, which may or may not be empty.
• The circles represent the BiTree host itself.
• The square boxes represent the data held in non-empty nodes.
• The arrows represent a program flow (not UML-like ownership!).
  • The arrow indicates which object calls a method of or sends a visitor into another object.
  • The arrowhead points to the object to which the task is being delegated.
  • That is, the tail of the arrow is delegating to the head of the arrow.
  • The label on the arrow indicates the case of the caller which causes that delegation to occur

Spend some time convincing yourself that the above process will correctly form the tournament tree.

The next step is to lay the above process in a more tabular form with each case and indented sub-cases:

Empty case: Insert here!

NonEmpty case: Delegate to the team in the root data.

Known team case: Should be a leaf so insert the this team object into the left child tree (how do you insert a team into a tree?). Insert param into the right child tree. Replace the rootDat with an unknown team.

Unknown team case: No leaf or end-point yet. Randomly pick the left or right sub-tree and recur into it.

You should be able to write the code directly from the above description using an IVisitor-derived class with one anonymous inner class. Don't forget to make input parameters final if they are to be accessed by an inner class!

Note that there is no notion of "checking" in the above process. The nodes and data are the object that they are, which may be one of several possibilities. The actions take place due to the object being the type that it is--no checking or conditionals are required or allowed, except in the random direction choosing!

The InsertTeamAlgo assumes that the tree is in proper tournament form. What happens if, for some reason, the tree is incorrectly formed when the InsertTeamAlgo is executed? Can you create a tree such that your code to throws an exception? If so, can you modify your code so that your code won't throw an exception, even for very badly formed trees? In fact, if done correctly, the InsertTeamAlgo should progressively repair any damage in the tree as each new team is inserted. (Try this on the demo: Create a tournament and play a round or two. Now insert some new teams. Watch how the structure slowly returns to having all the teams back on the leaves! -- Note that some names will appear twice because they were in the tree twice to begin with.) Now that's robustness!

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.  The ternary "? :" 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!

© 2013 by Stephen Wong