MÓDULO #3: Aplicaciones Orientadas a Objetos con Java

Introducción

En este último módulo utilizarás las clases que has implementado en los módulos previos para modelar un sistema de competición de tipo torneo de eliminación directa. Necesitarás para ello trabajar con árboles binarios, que modelará la tabla de emparejamientos del torneo.

Finalmente, crearás una sencilla interfaz de usuario para poder ejecutar el programa.

Torneo de eliminación directa modelado como un árbol

Un torneo de eliminación directa es aquél en el que los contendientes compiten entre sí por parejas, quedando eliminado el perdedor. Los emparejamientos se repiten entre los vencedores hasta que sólo queda un único contendiente, que será el ganador del torneo. Es muy común que la asignación de rivales esté predefinida, siendo del tipo "el ganador de A-B se enfrentará con el ganador de C-D". El resultado es una estructura como la de la siguiente figura:

Ejemplo de un torneo de competición que quizás te resulte familiar

La tabla de emparejamientos no es más que un árbol binario, una estructura de datos muy utilizada en programación. En este caso, tendrás que modelar el torneo como un arbol binario, con los siguientes condicionantes:

Cada nodo del árbol podrá almacenar un contenedor de objetos, de la clase que hayas programado en el módulo 2. Al inicializar el árbol, todos sus nodos estarán vacíos.
Después de haber inicializado el árbol vacío, se asignará un contenedor de objetos a cada uno de los nodos hoja (sólo a los nodos hoja). Tú decides el criterio de asignación (sorteo puro, asignación manual, cabezas de serie, etc.). Lo más sencillo será sorteo puro.
Los nodos del árbol deberán ser capaces de "poner a competir" a sus ramas. Es decir, pueden comparar (recuerda el método compareTo del módulo 2) entre sí los contenedores almacenados en sus ramas hijas. El contenedor que resulte vencedor avanzará en la tabla del torneo. Es decir, será copiado una posición arriba en el árbol.

Actualización 23/03/2012: Observa que copiar el vencedor en una posición superior no es necesario para encontrar al vencedor del torneo. Sin embargo, será útil para grabar el historial del torneo y saber quién ganó a quien cuando el torneo haya finalizado.
El proceso de competición se repetirá recursivamente hasta que se uno de los competidores haya llegado al nodo raíz, momento en el que el torneo tendrá un ganador.

Deberás también crear una clase Tournament, que realizará las siguientes tareas:

Preguntará al usuario cuántos partidos habrá que jugar para ser campeón. Es decir, cuántos niveles tendrá el árbol. Para hacerlo más sencillo, haz que todos los nodos del árbol tengan siempre 2 hijos, salvo los nodos hoja que no tendrán ninguno.
Generará tantos competidores como sean necesarios para rellenar la tabla del torneo. Es decir, generará tantos contenedores de objetos como nodos hoja haya en el árbol.
Iniciará la competición entre los contendientes y, una vez finalizada ésta, informará de quién ha sido el campeón.

Requisitos específicos

Los requisitos específicos son:

Actualización 23/03/2012: Implementa una clase contenedora con estructura de árbol binario. Dicha clase NO HEREDARÁ del contenedor abstracto que hiciste en el módulo 1.
Dicha clase contenedora deberá ofrecer, como mínimo, los siguientes métodos públicos:
Implementa también una clase llamada Tournament, que ofrezca un interfaz de usuario (modo texto) para desplegar un torneo. La interfaz deberá tener un aspecto similar a éste:
```
    Elige una opción:
        1 - Crear la tabla de competición vacía
        2 - Realizar sorteo de equipos
        3 - Competir
        4 - Dibujar la tabla del torneo 
        5 - Salir
```
En la que valen los siguientes comentarios.
- Al elegir la opción 1, se preguntará al usuario por el número de niveles que tendrá el torneo (es decir, el árbol).
- Con la opción 2, sólo se introducirán equipos (contenedores de objetos del módulo 2) en los nodos hoja. Lo más fácil será generar equipos aleatorios cuando sean necesarios, aunque puedes asignarlos de otra forma si quieres.
- Con la opción 4, se pide algo similar a esto (Actualización 23/03/2012: se muestra el resultado de tres ejecuciones del método, con la tabla de competición en tres estados diferentes):
```
Tabla vacía
--null
        -- l: null
                -- l: null

                -- r: null

        -- r: null
                -- l: null

                -- r: null

------------------
Tabla con valores en las hojas
--null
        -- l: null
                -- l: 34

                -- r: 24

        -- r: null
                -- l: 19

                -- r: 38

------------------
Tabla después del torneo
--19
        -- l: 24
                -- l: 34

                -- r: 24

        -- r: 19
                -- l: 19

                -- r: 38
                
```
Si crees que necesitas programar alguna clase adicional, hazlo.

Ejemplo de clases

En nuestra aplicación de ejemplo, tendríamos un una clase CardDeckTree en cuyos nodos hoja (partidas de primera ronda) se almacenarán mazos de cartas (CardDeck. En cada emparejamiento, el ganador estará determinado por el método compareTo de la clase CardDeck.

Visualmente, la estructura de clases tendrá el siguiente aspecto:

Algunas pistas útiles

Este enunciado habla de una clase con estructura de árbol, que puedes implementar siguiendo las pautas estudiadas en teoría (BTree y BNode). En este caso, BTree será equivalente a CardDeckTree. Recuerda que los métodos de BNode son, por lo general, recursivos.

La opción 4 del interfaz de usuario pide imprimir por pantalla el estado actual del árbol. Considera la opción de crear un método toString() con la siguiente forma:

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

        private String toString(int level) {
            //el atributo level me indica 
            //en qué nivel del árbol estoy
            //lo que es útil para tabular debidamente
        }

En el contexto de este programa, construir el árbol es sinónimo de crear la tabla de competición inicialmente sin equipos. Por tanto, considera utilizar el siguiente constructor:
```
        public CardDeckTree(int n) {
            initEmptyTree(n);
        }
        
```

En caso de empate, puedes lanzar una moneda al aire:

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

El método insertInLeaves rellena los nodos hoja con objetos de tipo contenedor (CardDeck, en el ejemplo). Eso quiere decir que necesitarás construir tantos objetos contenedor como nodos tengas que rellenar. Una opción es generar los contenedores aleatoriamente, en cuyo caso deberás implementar un método que construya un contenedor, lo rellene con objetos creados aleatoriamente, y lo devuelva; otra posibilidad es preguntar al usuario, para lo que tendrás que implementar un método que pregunte al usuario los parámetros de cada objeto y construya el contenedor correspondiente. También cabe la posibilidad de que el método insertInLeaves acepte dichos contenedores como parámetro, para lo cual tendrás que declarar el método como insertInLeaves(CardDeck []allDecksInTournament) (o similar). Elige la forma de trabajar que te resulte más cómoda y asumible.

Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010