MODULE #3: Object Oriented Applications with Java

Overview

In this last module you will use the classes that you implemented in the previous modules. Your goal will be the design and development of a single-elimination tournament. You will base your work in binary trees, which will be used to model the tournament bracket.

Finally, you will create a simple user interface, to allow the program execution.

Single-elimination tournament modeled as a tree

A single-elimination tournament, also called a knockout or sudden death tournament, is a type of elimination tournament where players compete in pairs and the loser of each match (also called bracket) is inmediately eliminated. These rounds are repeated among winners of each game until there is just one remaining player that is the winner of the tournament. The assignment of players is usually predefined before the tournament starts, typically with statements similar to that "the winner of the A-B round will then compete against the winner of the C-D round". The result is a data structure similar to the one shown in the next figure:

Example of a single-elimination tournament that you may find familiar.

The table of competitors is actually a binary tree, a typical data structure in programming. In this case, you will have to model the tournament as a binary tree, with the following requirements:

Each node of the tree can store an object container, of the class that you have implemented in module 2. When the tree is initialized, all its nodes must remain empty.
After an empty tree is created, an object container has to be assigned to each of the leaf nodes in the tree (only to those nodes). You decide the assignment criteria (simple draw, manual assignment, seeded players, etc.). The easiest strategy is a simple draw.
Nodes in the tree must be able to make their branches compete, i.e., they can compare the object containers stored in the child branches among them (remember compareTo method in module 2). The winning container will advance further in the tournament, i.e., it will be copied a position above in the tree.

Update 23/03/2012: Note that copying the winner item into the upper level is not required to find the final winner. However, this operation records all the intermediate plays and allows to see who won each match after the tournament has finished.
The tournament will be recursively repeated until one of the competitors has reached the root node, which is the stop condition of the recursion process, and the moment when the tournament has a winner.

You must also create a Tournament class that performs the following tasks:

Ask the user how many matches a player must pass to be the winner. In other words, how many levels the tree must have. To make it simpler, make every tree node have 2 children, except leaf nodes that will have no children.
It will generate as many competitors as necessary to fill in the tournament table, i.e., it will generate as many object containers as leaf nodes exist in the tree.
It will initiate the competition among players, and, once finished, it will return the winner.

Specific requirements

Specific requirements are:

Update 23/03/2012: Implement a container class with a binary tree structure. Such class WILL NOT INHERIT from the abstract container that you designed in module 1.
Such container class must provide, at least, the following public methods:

In addition, implement another Tournament class, which provides a user interface (text mode) to create a tournament. The interface must have a look similar to the following:

    Choose one:
        1 - Create a new empty tournament
        2 - Assign players
        3 - Start the competition
        4 - Display the tournament table
        5 - Exit

Where the following comments apply:

When option 1 is selected, the user will be asked for the number of levels of the tournament (i.e., the tree).
With option 2, players (object containers in module 2) are assigned to leaf nodes in the tree. The easiest strategy is to assign them randomly, but you can choose any strategy you prefer.

With option 4, some similar to the following must be displayed on the screen (Update 23/03/2012): the example shows the result of three executions of the method, being the tournament table in different states):

Empty table
--null
        -- l: null
                -- l: null

                -- r: null

        -- r: null
                -- l: null

                -- r: null

------------------
Table with values in the leaf nodes
--null
        -- l: null
                -- l: 34

                -- r: 24

        -- r: null
                -- l: 19

                -- r: 38

------------------
Winner
19
------------------
Table after the tournament is finished
--19
        -- l: 24
                -- l: 34

                -- r: 24

        -- r: 19
                -- l: 19

                -- r: 38

Should you think that you need any extra class, please feel free to implement it.

Example of classes

In our sample application, we will have a CardDeckTree class, whose leaf nodes (first round matches) will store card decks (CardDeck objects). In each match, the winner will be given by the result of the compareTo method in CardDeck class.

Visually, the class structure has the following definition:

Some useful hints

This assignment mentions a tree shaped class, which you can implement following the guidelines studied in the lectures (BTree and BNode). In such case, BTree will be equivalent to CardDeckTree. Note that the BNode methods are, most likely, recursive methods.

Option 4 from the user interface prints the current state of the tournament tree. Consider to create a toString() method shaped as follows:

        public String toString() {
            return "--" + toString(0);
        }

        private String toString(int level) {
            //the level attribute says in which level am I, 
            //which is useful to know how many tabulars 
            //I need while printing
        }

In the program you are developing, to create the tree is the same as to initialize the tournament tree, initially empty. Thus, let's consider the following constructor method:
```
        public CardDeckTree(int n) {
            initEmptyTree(n);
        }
        
```

If there's a draw between players, a coin toss can decide:

        if (player1.compareTo(player2) == 0) {
            double lottery = Math.random();
            if (lottery > 0.5)
                winner = player1;
            else
                winner = player2;
        }

The insertInLeaves method fills the leaf nodes with container objects (CardDeck, in the example). That is, you will need as many containers as nodes you have to fill. To do that, one option is to randomly create containers, so you'll need a method that creates a container, then randomly creates several objects and insert them in the container before returning it; another opction is to ask the user, so you'll need a method that asks the user for the object's parameters and then returns the container. It is also possible for the insertInLeaves method to accept the containers to be inserted as parameters, so you'll need to declare the method as insertInLeaves(CardDeck []allDecksInTournament) (or similar). Choose the option that you consider most reasonable.

Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010