Comp 212 Project #3: Tournament Trees

Due 1:00 PM, Friday, Nov. 14, 2003.

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 lecture #23 and the code for the binary tree structure.

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.

(You are not allowed to reverse engineer the demo applet to do your project.)

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

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.

See the documentation for the above classes here.

 

Requirements

Your final program must:

  1. Use an MVC architecture.
  2. Show the vertically oriented String representation of the tree.
  3. Show the horizontally oriented graphical representation of the tree.
  4. 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!
  5. Enable the user to input one team (name) at a time into the tournament tree at a random location.
  6. Enable the user to create a random, but still legal, structure with a fixed set of teams.
  7. Enable the user to play one round at a time, displaying the overall tournament winner at each stage.

Note that these are the capabilities of the demo.

Submission

The project is to be submitted electronically.

The due date is due Wednesday, April 09, 2003 at 1:00 PM.  

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:

Notes and Hints:

  1. THINK SIMPLE, THINK SMALL!!
    1. Don't program too much at once. Writing more code when you're stuck almost always make the problem worse.
    2. 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.
    3. 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 the moment.
    4. TEST OFTEN AND EARLY!
    5. Test your view and your model separately.
    6. Test the pieces of your model before you integrate everything together.
    7. Make test code that initially creates the tree by hand--that way you will know what is where in it.
    8. Get the vertical text tree display code working BEFORE you attempt the InsertTeamAlgo!

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

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

  4. 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 and panels.
    1. To add a a component to a scroll pane, use a call like myScrollPane.getViewport().add(myComponent).
    2. To enable automatically appearing scroll bars, use the setAutoscrolls() method;
    3. 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.
    4. There are numerous ways of putting multiple scroll panes on the screen. For example:
    5. 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.
    6. 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.

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

  6. The ? : Operator

    Java's "? :" operator is like an if statement that returns you choices of values rather than code blocks. The basic syntax is:

    7. [conditional statement] ? [value1] : [value2]

    Note: value1 and value2 must have the same type.

    Examples: