Comp202: Principles of Object-Oriented Programming II
Fall 2006 -- Project #3: Tournament Trees
In this project 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. 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 first thing you may want to do is to review
the binary tree structure material from Comp201.
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:
method that returns the name of the team as a am as a
- 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
In addition, a team is either:
- "unknown", which represents the absence
of a team. A unknown team always has a fixed name, such as "???".
- "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
- All "known"
teams are located on the leaves of the tree initially.
- All interior nodes of the tree contain
teams initially. After rounds have been played, the unknown
teams are replaced by the winner between the winning teams in the 2
- 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.
- 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
(You are not allowed to reverse engineer
the demo applet to do your project.)
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 web page 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 web page on the PlayRoundAlgo.
Supplied Utility Graphics Classes
These classes are needed to display a binary tree (BiTree) on a
JPanel or JFrame
in a horizontal, graphical layout.
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.
-- 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.
See the documentation for the above
Your final program must:
- Use an MVC architecture.
- Show the vertically oriented String representation of the tree.
- Show the horizontally oriented graphical representation of the tree.
- Use direct dispatching (delegation) algorithms with no conditionals
except when random choices are involved. There should be no other
conditionals ("if's" or "?") in your project!
- Enable the user to input one team (name) at a time into the tournament
tree at a random location.
- Enable the user to create a random, but still legal, structure with a
fixed set of teams.
- Enable the user to play one round at a time, displaying the overall
tournament winner at each stage.
- The GUI should have
- a "Clear" button
to clear all the tournament tree displays.
- a JTextField
to enter the name of a known team.
- a "Insert"
button to insert the known team with the name shown in the text box into the
- a "Make Tournament"
button to randomly create a tournament tree.
- a "Play Round"
button to play one round of the current tournament.
- scrollable text areas that display the tournament
tree both vertically and horizontally.
- a label that displays the ultimate winner when it is
Note that these are the capabilities of the demo.
The project is to be submitted electronically.
The project is to be submitted via the turn-in script, with project name
tree. No late submission will be accepted. The submission should
contain the following:
- A plain text file called README
documenting what you have and/or have not done, describing
specific details that you feel we need to know when grading your work.
This README file alone is worth 5 points.
- Full javadoc documentation with UML class diagrams.
- Pledge of Honor: add
your pledge of honor to the README file.
- All the Java source code necessary to compile and execute your code.
Notes and Hints:
- THINK SIMPLE, THINK SMALL!!
- Don't program too much at once. Writing more code when you're stuck
almost always make the problem worse.
- We suggest that you try to implement the following first:
- GUI up and running with the ability to
- display the tree in vertical text form.
- clear the tree (reset tree back to empty tree).
- input a known team by typing in a name and then having that
name appear in a tournament-valid position in the tree.
- Then try to implement the following.
- The ability to create a whole tournament with at least 8 known
teams in a single button click. The button click should produce a
different arrangement for the tournament every time.
- The ability to display the tree simultaneously in horizontal
graphical form and vertical text form..
- The ability to play one round of the tournament at a time,
including a display on the GUI showing the current overall winner at
- TEST OFTEN AND EARLY!
- Test your view and your model separately.
- Test the pieces of your model before you integrate everything
- Make test code that initially creates the tree by hand--that way you
will know what is where in it.
- Get the vertical text tree display code working
BEFORE you attempt the InsertTeamAlgo!
- A controller doesn't always just attach adapters between the model(s) and
view(s). Sometimes it simply needs to transfer a piece of information from
one to the other for initialization purposes.
- Another interpretation of the previous note is to consider the idea that
the model or the view may have a factory method that produces the adapter
the other needs. Thus the controller doesn't need to instantiate the
adapter, it merely obtains it from one and passes it to the other.
- A JScrollPane is a container that holds a
single component, but allows that component to be bigger than its displayed
size. The most common components for a scroll pane to hold are text areas
- To add a a component to a scroll pane, use a call like
- To enable automatically appearing scroll bars, use the
- After making changes to a JScrollPane,
such as changing what components are contained by the panel it holds, be
sure to "validate" it. Multiple scroll panes can be validated by calling
the validate() method of the container that holds them, e.g. the frame.
- There are numerous ways of putting multiple scroll panes on the
screen. For example:
- Put them both on a panel in the center of the frame. Use a 1x2 grid
layout for the panel. This will make both the same size always.
- Put one in the center of the frame--this will resize with the window.
Put the other on the edge of the frame, e.g. west. The size of this
scroll pane will need to be fixed using a call like
myScrollPane.setPreferredSize(new Dimension(200, 21)). Note that
one of the dimensions will be ignored, depending on which edge of the
frame the scroll pane is placed.
- Working with dynamically generated components can be a bit tricky. If the
screen doesn't seem to be updating with the correct information, try
repainting and/or validating the frame.
- The ? :
Java's "? :" operator is like an
if statement that returns you choices of values rather than code blocks. The
basic syntax is:
statement] ? [value1] : [value2]
- If the conditional statement evaluates to
true, then the entire statement evaluates to
- If the conditional statement evaluates to
false, then the entire statement evaluates to
must have the same type.
- x = ( a< b) ? y : z; // x = y if a >b
otherwise x = z
- // Obj1 and
are the same type and both have the doIt()
((Math.random() < 0.5) ? Obj1 : Obj2 ).doIt();
// randomly executes the doIt()
method of either Obj1
or Obj2 .
Thursday, 03-Jun-2010 09:52:23 CDT
©2006 Stephen Wong and Dung Nguyen