Diseño y Programación Orientados a Objetos
1er. Sem 2008
Tarea 1: Herencia e Interfaces: programación genérica


Recomendación: Lea detenidamente la tarea, si algo no lo entiende consulte en clases, si es preciso se incorporarán aclaraciones al final.

Esta tarea tiene por objeto que:
  1. Usted se familiarice con el ambiente de desarrollo que usará en otras tareas y su proyecto.
  2. Evalúe la herramienta que resulte más cómoda para usted. En clases he sugerido trabajar con Emacs o Jgrasp.
  3. Practique la creación de (o aprenda a crear) Makefile
  4. Ejercite la generación automática de documentación usando javadoc.
  5. Ejercite los conceptos de clases, herencia, interfaces y entrada y salida de datos.

Descripción General
En esta tarea usted ejercitará interfaces y herencia a través de algunos ejercicios de programación genérica. Para ello deberá implementar dos algoritmos de búsqueda y dos algoritmos de ordenamiento; sus implementaciones deben procurar ser genéricas.
Dos algoritmos de ordenamiento son Bubble Sort e Insertion Sort y dos algoritmos de búsqueda son búsqueda lineal (linear search) y búsqueda binaria (binary search). Busque estos algoritmos en wikipedia.

Los algoritmos serán aplicados a arreglos de N objetos de la clase Estudiante. Para esta clase se tiene:
public class Persona {
  private Persona() {}
  public Persona (String nombre) {
     this.nombre=nombre;
  }
  public String getName() {
     return nombre;
  }
  private String nombre;
}
public class Estudiante {
  private Estudiante() {}
  public Estudiante(String nombre, float promedioPonderado) {
    super(nombre);
    pp= promedioPonderado;
  }
  public float getPromedioPonderado() {
    return pp;
  }
  private float pp;
}
Usted deberá completar estas clases para dar cumplimiento a los requerimientos de la primera y segunda parte de esta tarea.

La clase Ordenador es una clase abstracta con el siguiente método:
/**
 * Superclass para distintas implementaciones de algoritmos de ordenamiento.
 * @author Agustín J. González
 */
public abstract class Ordenador
{
/** Ordena una arreglo de objetos Comparable.
* @param A Arreglo de objetos comparables.
*/
  public abstract void ordenar(Comparable[] A);

/** Obtiene el número de comparaciones realizadas en la última invocación a ordenar.
* @return número de comparaciones hechas para ordenar el arreglo.
*/
  public abstract int getNumComparaciones();

/** Obtiene el número de intercambio o enroques de datos (swaps) durante la última operación de ordenamiento.
* @return número de intercambios de datos en última comparación.
*/
  public abstract int getNumIntercambios();
}

Primera Parte

Cree la clase BubbleSorter y la clase InsertionSorter como clases heredadas de Ordenador.

Estas clases serán probadas en un programa que leerá desde un archivo los nombres de aproximadamente 50 estudiantes (será proporcionado) a los cuales usted asociará promedios ponderados aleatorios (entre 55 y 100). El ayudante bien puede usar otro archivo con igual estructura (un nombre por línea). La lectura será almacenada en un arreglo de Estudiantes. Como respuesta su programa entregará el tamaño del arreglo analizado, el número de comparaciones y el número de intercambios requeridos para ordenar el arreglo por sus promedios ponderados. Luego de dar estos valores, esperará por un retorno de carro para arrojar el listado de alumnos ordenados por nombre promedio ponderado con el promedio ponderado nombre de cada uno.

Su programa debe repetir lo previo usando el algoritmo BubbleSort y luego Insertion Sort.
Se espera que su programa de prueba contenga al menos dos métodos: uno que efectuará la tarea antes señalada (por ejemplo computarParte1) usando como parámetro un objeto de clase Ordenador y el método main. Éste invocará dos veces el método previo primero con un instancia de BubbleSorter y luego con una instancia de InsertionSorter. La idea es que usted vea cómo el método computarParte1 puede diseñarse en forma genérica para trabajar en un caso con un algoritmo y luego con el otro, el cual será pasado como argumento.

Segunda Parte
Similar a lo anterior cree la clase abstracta Buscador, la cual tiene los métodos:
int buscar(Object [] A, Object obj); retorna el índice del arreglo que contiene el objeto ó -1 en caso de no encontrarlo.
int getNumComparaciones();   retorna el número de comparaciones efectuadas para dar con el objeto o concluir que no está.

Implemente las clases LinearSearcher y BinarySearcher como subclases de Buscador. En el caso de binary search se debe cumplir que el arreglo de datos del método buscar esté previamente ordenado. 
Extienda su programa de prueba previo para arrojar el número de comparaciones requeridas para buscar exitosamente un alumno (es decir un alumno que está en misma lista usada en la primera parte). Usted debe mostrar en pantalla el número de alumnos del arreglo y el número de comparaciones para encontrarlo. Primero hágalo con búsqueda lineal y luego con algoritmo de búsqueda binaria.

Observación: Daniel Caro ayer hizo notar la diferencia entre búsqueda lineal y búsqueda binaria. Mientras en la primera usar equals() es lo natural y pedido, en búsqueda binaria se requiere comparar los elementos para hacer la búsqueda. Esta comparación se debe hacer con método compareTo(). Como resultado la búsqueda retorna el índice del objeto con igual nota y no necesariamente el objeto igual - equals - al argumento usado en método buscar().
   En la misma línea otro de sus compañeros destacó que el arreglo en este caso no podía ser un arreglo de Objetos dado que éstos no ofrecen el método compareTo. Ayer expliqué la forma de resolver esta situación; manteniendo la firma del método (para que la redefinición opere y así también le ligado dinámico) en el código poner algo del tipo:
Comparable [] newA;
if ( A[0] instance of  Comparable) newA= (Comparable []) A;
else return -1;
Hacer algo similar con el parámetro que se busca.

La tarea será revisada usando una ventana terminal o consola en aragorn. Se requiere que usted cree un archivo Makefile para que el ayudante compile su trabajo usando:
$ make
Para ejecutar su programa el ayudante ejecutará
$ make run
Para generar la documentación el se correrá:
$ make doc

Notas:
En la documentación de esta tarea, no es necesario que usted haga una descripción en alto nivel de los algoritmos usados. Usted debe entregar su código documentado siguiendo el estándar del utilitario javadoc. Dé una mira al Generador de Documentación y en particular los rótulos.
El archivo de nombres proporcionado fue obtenido a partir de la lista del curso, la cual fue procesada para generar los nombres naturales.
Considere que el ayudante podría desarrollar otro main para probar sus clases. Por ejemplo al buscar podría hacerlo con una objeto copia (clone) de alguno del arreglo.

Vea el ejemplo de Makefile. Más información sobre Makefiles.