Sincronización.

    Los hilos se comunican principalmente compartiendo el acceso a los campos y los objetos a los que hacen referencia dichos campos. Aunque este esquema es extremadamente eficiente, lleva implícito dos errores potenciales:

1. Interferencia de hilos (Thread interference).
2. Errores de consistencia de memoria (Memory consistency errors).
   

    Con la sincronización se pueden prevenir estos dos errores, pero también se puede incurrir en la contención de hilos, que ocurre cuando dos o más hilos tratan de acceder al mismo recurso de manera simultánea (condición de competencia) provocando que el entorno de la máquina virtual ejecute uno o más hilos más lentamente, o incluso que llegue a suspender su ejecución. 

    La inanición y el interbloqueo de hilos son dos formas de contención y su análisis y tratamiento quedan fuera de los alcances de este blog. Aquí sólo se proporcionarán los elementos básicos relacionados con la sincronización de hilos y la prevención de los dos errores mencionados con anterioridad.

Interferencia de hilos.

    El planteamiento iniciará con el análisis de una clase extremadamente simple (Ejemplo Contador) que implementa un contador, así como su respectivo incremento, decremento y acceso a través de los métodos correspondientes.

    Si sólo un hilo accede a los métodos para la modificación de c: todo trabaja como se espera; pero si un objeto de la clase Contador es referido por múltiples hilos, la interferencia entre ellos hará que las cosas se salgan de control.

    La interferencia acontece cuando dos operaciones, ejecutándose en diferentes hilos pero accediendo a los mismos datos, se intercalan. Las operaciones de alto nivel que se escriben en los lenguajes de programación, por simples y sencillas que parezcan, habitualmente consisten de múltiples pasos o suboperaciones, y cuando estos pasos de traslapan o superponen los problemas emergen (condiciones de competencia).

    Los detalles precisos respecto a la exactitud de cómo se descompone una operación tan simple como el incremento de una variable (c++) no son relevantes, basta con saber por ahora que dicha operación podría ser descompuesta en tres pasos (ocurre lo análogo y correspondiente para c--):

1. Obtener o recuperar el valor actual de c (fetch).
2. Incrementar dicho valor en 1.
3. Almacenar el valor incrementado nuevamente en c.
   

    Con base en lo anterior, supongamos ahora la existencia de dos hilos, y que el Hilo A invoca a incrementa y que casi al mismo tiempo el Hilo B invoca a decrementa. Si el valor inicial de c es 0, una posible secuencia de acciones traslapadas podría ser la siguiente:

1. Hilo A: Recupera c.
2. Hilo B: Recupera c.
3. Hilo A: Incrementa valor recuperado; resultado: 1.
4. Hilo B: Decrementa valor recuperado; resultado: -1.
5. Hilo A: Almacena resultado en c; c vale ahora 1.
6. Hilo B: Almacena resultado en c; c vale ahora -1.
   

    Como puede observarse, el resultado del Hilo A se pierde: es sobre escrito por el resultado del Hilo B. Este planteamiento es sólo una combinación posible, bajo distintas circunstancias, podría ser que ahora el resultado del Hilo B sea el que se pierda o también podría darse el caso de que todo resulte bien como se espera; el resultado final es impredecible (condición de competencia).

    El Ejemplo PruebaContador muestra la situación de interferencia de hilos en una ejecución con dos hilos: uno (main) incrementando 100 000 veces el contador y el otro (h) decrementando la misma cantidad de veces ¿Cuál es el resultado esperado y cuál es el que se obtiene? ¿Se generan los mismos valores o resultados en distintas ejecuciones? ¿Por qué no son cero?

Errores de consistencia de memoria.

    Este tipo de errores ocurren cuando hilos diferentes tienen vistas inconsistentes de lo que deberían ser los mismos datos. Las causas de este tipo de errores son muchas y muy variadas y su análisis queda fuera de los alcances de este blog. Por ahora basta con saber que el programador debe tener consciencia de este tipo de errores para que pueda emplear una estrategia para anularlos.

    La clave para anular este tipo de errores de consistencia de memoria es entender una relación denominada "sucede antes" (happens-before). Dicha relación es simplemente una garantía de que las escrituras de memoria realizadas por una declaración específica, son visibles para otra declaración específica. Para visualizar mejor esto, considere lo siguiente:

int contador = 0;

. . . 

Hilo A: contador++;

. . . 

Hilo B: System.out.println(contador);

    Suponga que dicho contador es compartido por dos hilos A y B, y suponga también que A incrementa el contador y que poco después B imprime en la salida estándar el contador. El valor impreso por B puede ser 0 o 1, es decir: no hay garantía de que el cambio a contador por parte del hilo A sea visible para el hilo B, a menos de que el programador establezca una relación happens-before entre estas dos sentencias. La sincronización es una de las formas de crear este tipo de relación.

    Java proporciona dos formas de sincronización:

1. Métodos sincronizados.
2. Sentencias sincronizadas.
   

     Para que un método sea sincronizado, basta con añadir la palabra reservada synchronized a su definición, tal y como se muestra en el Ejemplo ContadorSincronizado. El hacer que los métodos sean sincronizados, tiene dos efectos para las instancias de la clase:

1. No es posible el traslape para dos invocaciones de métodos sincronizados que se realicen sobre el mismo objeto. Cuando un hilo está ejecutando un método sincronizado para un objeto determinado, todos los demás hilos que invoquen métodos sincronizados para el mismo objeto se bloquean, es decir, se suspende su ejecución, hasta que el primer hilo haya terminado.
   
2. Cuando un método sincronizado termina, automáticamente establece una relación happens-before para cualquier invocación subsecuente de un método sincronizado para el mismo objeto, lo que garantiza que los cambios al estado del objeto sean visibles para todos los hilos. 

    Los constructores no pueden ser sincronizados y no tendría sentido, porque sólo el hilo que crea el objeto debería tener acceso a él. De hecho esta situación se identifica como un error de sintaxis.

    Los métodos sincronizados habilitan una estrategia simple para prevenir la interferencia de hilos y los errores de consistencia de memoria. Como regla general podría decirse que: si un objeto es visible por más de un hilo, todas las lecturas o escrituras a las variables (atributos) del objeto deberían ser por métodos sincronizados, con excepción quizá de los atributos final (los cuales no pueden ser modificados una vez que el objeto ha sido construido).

    El Ejemplo PruebaContadorSincronizado muestra cómo podría utilizarse la clase ContadorSincronizado. Analice ambas clases y compárese con sus contra partes de la sección anterior.

Candados intrínsecos y sentencias sincronizadas.

    La sincronización se construye al rededor de una entidad conocida como candado intrínseco o candado de monitor (o simplemente monitor) misma que juega un rol fundamental en dos aspectos relacionados con la sincronización:

1. Hace cumplir el acceso exclusivo al estado del objeto (exclusión mutua).
2. Establece y garantiza la relación happens-before esencial para la visibilidad y coherencia (consistencia de memoria).
   

    Cada objeto tiene asociado un candado intrínseco (lo mismo que cada clase cuando se habla de métodos estáticos). Por convención, si un hilo necesita acceso exclusivo y consistente a los campos de un objeto, tiene que apropiarse de dicho candado antes de hacerlo y liberarlo al terminar.

    Mientras un hilo posea el candado intrínseco, ningún otro hilo puede adquirirlo por lo que se bloqueará. Por otro lado, cuando un hilo libera un candado intrínseco, se establece una relación happens-before entre dicha acción y cualquier adquisición subsecuente del mismo candado.

    Cuando un hilo invoca un método sincronizado, automáticamente adquiere el candado intrínseco para dicho objeto y lo libera cuando el hilo en cuestión termina de ejecutar el método, aun cuando la terminación se dé por una excepción no atrapada.

    En este sentido, sucede que no siempre conviene que todo el método esté sincronizado debido a que se merma la concurrencia (contención de hilos); en algunos casos conviene que se sincronice sólo un bloque de código, debido a que el método podría tener también sentencias que no necesariamente acceden a datos compartidos, o que acceden a datos compartidos distintos, en cuyo caso un enfoque basado en sentencias sincronizadas sería entonces más apropiado (consulte el Ejercicio 8 de los Ejercicios selectos).

    Aunque para el ejemplo que se ha venido desarrollando en esta entrada no tendría mucho sentido utilizar las sentencias sincronizadas, con la finalidad de mostrar su uso y equivalencia para este caso particular, se propone al lector la revisión, comparación y análisis del Ejemplo ContadorSincronizado2 así como su correspondiente clase de prueba del Ejemplo PruebaContadorSincronizado2.

Conclusión.

    Como conclusión general es importante resaltar la importancia de la sincronización al trabajar con hilos y recursos compartidos por éstos.

    De los ejemplos comentados es importante también enfatizar y no perder de vista que una clase tan simple como Contador, utilizada en un contexto de hilos compitiendo por acceso a los datos puede derivar, sin la debida sincronización, en un potencial desastre respecto a la consistencia de la memoria y la coherencia de los datos derivada de la interferencia de hilos.

    Por otro lado, conviene también el tener presente que un abuso de la sincronización, pueden incurrir en la nada deseable contención de hilos, haciendo que las potenciales ventajas de la concurrencia no sólo desaparezcan sino que sean absurdas.

    Finalmente aquí, como en otras tantas instancias, se manifiestan dos de esas importantes y perennes lecciones de vida:

1. "Las nuevas soluciones traen consigo nuevos problemas".
2. "Todo viene con su precio".
   

Ejercicios selectos (Hilos).

 

1. Considere el Ejemplo HolaEjecutable2. Modifíquelo para que la línea 18 substituya a la 17, recompile y pruebe su funcionamiento. Se recomienda ampliamente al lector consultar el API de Java para documentarse acerca del uso del constructor correspondiente y asegurase de comprender su funcionamiento.
2. Considere el Ejemplo HolaHilo2. Integre la línea 17 (que aparece comentada) para que forme parte del código, recompile y pruebe su funcionamiento. Se recomienda ampliamente al lector consultar el API de Java para documentarse acerca del uso del método setName( ) de la clase Thread y asegurase de comprender su funcionamiento; así como de comprender también la similitud y diferencias con respecto al ejercicio anterior.
3. Con base en los Ejemplos HolaHilo2 y HolaEjecutable2 realice, para cada uno, lo siguiente:
1. Genere más de un hilo (al menos tres) y póngalos en ejecución.
2. Genere un arreglo con capacidad para almacenar diez hilos, creé el número de hilos correspondiente y ponga a todos en ejecución.
   
4. Asegúrese de comprender por completo el Ejemplo HilosInteractuando. Posteriormente, modifique el ejemplo para:
• Cambiar los tiempos de método join (línea 67) una vez que haya consultado el API y comprenda más a fondo su funcionamiento.
• Cambiar el nombre del hilo de main, para que en la ejecución, en lugar de ver, por ejemplo "main: Todavía esperando...", sea vea: "Padre: Todavía esperando...".
• Pruebe con argumentos en la invocación del programa para modificar el tiempo de espera (paciencia) del hilo principal (main).
  
5. Considere el Ejemplo PruebaContador. Asegúrese de probar la equivalencia de las líneas 42-43 con la línea 44.
6. Para el Ejemplo PruebaContadorSincronizado, asegúrese de probar la equivalencia de las líneas 43-44 con la línea 45.
7. En la entrada Sincronización, se hace referencia a que un constructor no puede ser sincronizado. Pruebe dicha situación generando el error de sintaxis que debería generarse.
8. Considere y analice el Ejemplo MsLunch. Asegúrese de comprender la diferencia entre éste y las distintas versiones del ejemplo comentado en la entrada Sincronización.
9. Con base en las entradas Creación de hilos, Sincronización y los ejemplos correspondientes, escriba un programa que realice lo siguiente:
• Genere 6 hilos: 3 utilizando Thread y 3 utilizando Runnable.
• Cada hilo deberá incrementar 100 000 veces el valor de un contador compartido e imprimir su valor al finalizar.
• El hilo principal (main) deberá decrementar 600 000 veces el valor del contador compartido e imprimir su valor al finalizar.
• El hilo principal deberá, antes de iniciar sus decrementos, esperar (join) a cada hilo 50 milisegundos.
• El hilo principal deberá llamarse padre y los hilos creados: hijo1, hijo2, ... hijo 6.
  
• ¿Cuál debería ser el valor final del contador en un enfoque sincronizado y por qué?
  
10. Para el Ejemplo Interbloqueo, elimine la palabra reservada synchronized de ambos métodos ¿Que piensa que sucederá y por qué? Determine su respuesta antes de volver a compilar y ejecutar.
    
11. Considere, analice y comprenda el Ejemplo Interbloqueo2 sin ejecutarlo.
• ¿Puede determinar lo que hace? 
• ¿Se comprende la diferencia con el Ejemplo Interbloqueo?
• ¿Por qué hace lo que hace?
  

Creación de hilos.

   En Java hay básicamente dos formas de generar un nuevo hilo de ejecución:

1. Crear una instancia de la clase Thread.
2. Crear una instancia de una clase que sea ejecutable, es decir, una clase que implemente la interfaz Runnable.

   En esta entrada se presentarán dos ejemplos de cada una de estas formas.

Clase Thread.
   El Ejemplo HolaHilo muestra la creación de un hilo cuando una clase (HolaHilo) hereda de la clase Thread (línea 8).

   Todas las subclases de Thread deberían sobreescribir el método run( ), ya que la definición de dicho método establece el comportamiento que tendrá el hilo creado, es decir, el conjunto de acciones a realizar por el hilo, son definidas dentro de este método (líneas 10-12) que, para este caso, consiste únicamente en imprimir un mensaje en la salida estándar.

   Observe cómo en el método main (líneas 14-17) se crea, en la línea 15 un nuevo hilo de ejecución (hilo), mismo que se hecha a andar en la línea 16 a través del método start( ).

   El método start( ) hace que el hilo receptor del mensaje inicie su ejecución, dentro de esta inicialización del hilo ocurren distintos aspectos de gestión que la máquina virtual de Java tiene que realizar para que las cosas funcionen, como la invocación al método run( ) del hilo correspondiente.

   Es importante hacer notar al lector que nunca hay un llamado explícito al método run( ), sino que ocurre un llamado implícito como parte de las gestiones y acciones que realiza el método start( ).

   Por último, el Ejemplo HolaHilo2 muestra una variación del ejemplo anterior.

   En las líneas 11 y 19 se ha hecho uso del método currentThread( ) de la clase Thread, el cuál regresa la instancia del hilo que se está ejecutando (hilo actual), esto con la finalidad de que el método getName( ) obtenga el nombre asignado a dicha instancia. Esta propiedad del hilo en cuestión es utilizada para imprimirla en la salida estándar en las líneas 12 y 20 respectivamente.

   Finalmente, la línea 17 (comentada) utiliza el método setName( ) para asignarle un nombre al hilo ("Hilo Jr."). Se deja como ejercicio para el lector descomentar dicha línea, recompilar, ejecutar y comparar las salidas de los ejemplos correspondientes y comprender la diferencia.

Interfaz Runnable.
   El Ejemplo HolaEjecutable muestra la creación de un hilo utilizando la interfaz Runnable (línea 8).

   Una interfaz en Java es básicamente un contrato que la clase que la implementa debe cumplir, es decir, la clase que implementa una interfaz se compromete a definir todos los métodos que establezca dicha interfaz.

   Para el caso de la interfaz Runnable, el único método que hay que definir es el método run( ) (líneas 10-12), cuya única misión es imprimir un mensaje en la salida estándar.

   En la línea 15 se crea una instancia de la clase HolaEjecutable (ejecutable), misma que es utilizada como argumento para el constructor del hilo creado en la línea 16.

   Si todo sale bien, en la línea 17 existen dos hilos de ejecución:

1. El de main.
2. El que se creo en la línea 16 (hilo).

   Note aquí también que nunca hay un llamado explícito al método run( ), sino que más bien hay un llamado implícito en alguna parte del método start( ) (línea 17), el cuál es el encargado de realizar la gestión necesaria para que el hilo recién creado se introduzca en el entorno de ejecución de la máquina virtual de Java. Se recomienda ampliamente al lector el consultar el API para obtener más detalles acerca de la clase Thread y de la interfaz Runnable.

   Finalmente el Ejemplo HolaEjecutable2 muestra una variación del ejemplo descrito con anterioridad. Note particularmente las líneas 11 y 20 en donde se ha hecho uso del método currentThread( ) de la clase Thread, el cuál regresa la instancia del hilo que se está ejecutando (hilo actual); por otro lado, el método getName( ) obtiene el nombre asignado a dicha instancia. Esta propiedad del hilo en cuestión es utilizada para imprimirla en la salida estándar en las líneas 12 y 21 respectivamente.

El intercambio de la líneas 17 y 18 para que mutuamente se excluyan se deja como ejercicio para el lector.

Implementación del ADT racional.

   El Ejemplo Racional muestra una posible implementación de ADT racional definido en la entrada Tipos de Datos Abstractos (ADT).

   Las líneas 7 y 8 definen los atributos de un número racional (p / q). Los detalles relacionados con los métodos de tipo set y get (líneas 25-41), ya han sido comentados en la sección Métodos y atributos de la entrada POO (mensajes y métodos) y no se repetirán aquí.

   Por otro lado, los constructores definidos (líneas 10-23) requieren de una ampliación en su explicación, ya que difieren un poco de lo hasta ahora comentado para los constructores.

   El constructor principal o base es el definido en las líneas 18-23. Observe que dicho constructor recibe dos argumentos, mismos que representan el numerador (n) y el denominador (d) del número racional que se desea inicializar. En la línea 19, el constructor realiza una verificación del denominador (cláusula de condición), de tal forma que si éste es cero, se crea (new) y lanza (throw) una excepción (consulte la sección de Excepciones de la entrada Ejemplos selectos de transición) para indicar el error a través de la clase ArithmeticException. Note también que el mismo comportamiento es considerado en las líneas 30 y 31 para el método estableceDenominador. Una posible salida del programa al presentarse la situación anteriormente planteada, se muestra en la siguiente figura:

Una salida de la excepción generada en el Ejemplo PruebaRacional al intentar crear un número racional cuyo denominador sea cero.

 

   Los constructores de las líneas 10-12 y 14-16 se apoyan del constructor base de las líneas 18-23 para realizar la inicialización del objeto a través del uso de la cláusula this. La cláusula this es una referencia que tienen todos los objetos hacia sí mismos, por lo que en el contexto de los constructores invoca al constructor sobre cargado que corresponda con el tipo y número de argumentos que envía, que para el caso de las líneas 11 y 15 corresponden con el constructor base de las líneas 18-23.

   La implementación de las operaciones de suma y producto aparecen en las líneas 43-50 y 52-59 respectivamente (la implementación de las operaciones resta y división se dejan como ejercicio para el lector). Observe que en las líneas 46 y 47 (55 y 56) se accede directamente a los atributos p y q a través del operador punto (.), es decir, sin hacer uso de los métodos de acceso set y get; ésto es así debido a que el objeto s (m) es de la misma clase que define al método suma (multiplica), por lo que el acceso es concedido sin ningún tipo de inconveniente (recuerde lo planteado en el Ejercicio 2 de la entrada Ejercicios selectos (POO) y analice la diferencia).

   Por otro lado, note también que para el objeto (this) que recibe el mensaje suma (multiplica), los atributos p y q de las líneas 46 y 47 (55 y 56) son accedidos sin ningún tipo de operador ni mensaje, es decir, son accedidos por contexto, ya que el objeto que recibe el mensaje conoce cuáles son sus propios atributos y métodos por lo que dentro del método la expresión:

p * r.obtenDenominador( )

es equivalente a la expresión:

this.p * r.obtenDenominador( )

   Por último en lo que respecta a los método suma y multiplica, es importante resaltar que ambos métodos utilizan un objeto local al método (s y m respectivamente) para almacenar el resultado que generan y poder regresarlo como valor de retorno del método, por lo que es posible deducir que si un método requiere de variables u objetos para realizar su labor, éstos pueden declarase locales al método. En este sentido, sería un error respecto al paradigma declarar dichas variables u objetos como atributos de la clase, ya que no describen alguna propiedad o característica inherente a los objetos que deriven de la clase, sino que son sólo elementos necesarios para el almacenamiento del resultado y la realización del cálculo correspondiente a la responsabilidad (comportamiento) del método. Lo anterior se aplica aún cuando se utilizara una sola variable para almacenar el resultado de cualquiera de las cuatro operaciones aritméticas.

   Finalmente el método toString (líneas 61-63) requiere una mención aparte, ya que este método sobre escribe (razón por la cual se preservó el nombre del método) y en consecuencia re define el comportamiento previamente establecido en el método la clase Object del API de Java. Dicho método tiene como responsabilidad el regresar una representación en cadena del objeto que recibe el mensaje.

   La clase de prueba del Ejemplo Racional es la del Ejemplo PruebaRacional. Una posible salida corresponde a la mostrada en la siguiente figura:

Una posible salida de la ejecución del Ejemplo PruebaRacional. 

 

   Por último, aunque el Ejemplo PruebaRacional se explica a sí mismo, se resaltarán los siguientes aspectos:

• Las líneas 8 y 9 crean los números racionales r1 y r2, donde r1 = 1 / 3 y r2 = 2 / 5.
• Las líneas 13 y 14 envían los mensajes suma y multiplica respectivamente al objeto r1. Note que el argumento de ambos métodos es r2 y que al valor de retorno de dichos métodos (un número racional), le es enviado de manera implícita el mensaje toString para obtener la representación en cadena de los resultados correspondientes. Esto último sucede también con las líneas 11 y 12 pero para los objetos r1 y r2 respectivamente.

Implementación de Herencia (Java).

   El Ejemplo Persona muestra la implementación en Java de la clase Persona mostrada en el diagrama de clases de la entrada POO (herencia). Todos los detalles de la clase Persona de dicho ejemplo ya han sido expuestos ahí, por lo que se recomienda encarecidamente al lector los revise y analice, y que los compare con lo descrito para diagrama UML correspondiente.

   Por otro lado, el Ejemplo Cientifico contiene la implementación de la clase Científico mostrada también en el diagrama de clases mencionado anteriormente. Observe que la herencia es implementada en Java a través del uso de la cláusula extends (línea 6), seguida de la clase de la que se hereda (Persona) en la definición de la clase Científico.

   Es importante que el lector note el uso de la cláusula super en los constructores (líneas 11 y 18). El uso en Java de dicha cláusula sólo puede hacerse en el contexto de constructores y sirve para delegarle al constructor correspondiente de la clase padre, los detalles de inicialización del objeto en cuestión que, para el caso de la clase Científico, corresponden a los constructores de dos y tres argumentos de la clase Persona respectivamente. Asegúrese de comprender también ésto antes de continuar.

   Al igual que antes, se deja como ejercicio de análisis para el lector tanto los detalles restantes de implementación de la clase Científico, como el asegurarse de comprender la relación del diagrama UML con el código del Ejemplo Científico.

   En este punto, es importante también que el lector ponga especial atención en los métodos mensaje del Ejemplo Persona (líneas 61-63), y del Ejemplo Científico (líneas 33-35), ya que serán fundamentales para comprender la sobre escritura (override) de métodos que se discute más adelante en la clase de prueba (Ejemplo PruebaHerencia).

   La clase de prueba para la herencia se presenta en el Ejemplo PruebaHerencia y se describe brevemente a continuación. La línea 10 define el objeto persona y genera una instancia de la clase Persona con características específicas; note que el constructor que está siendo utilizado es el definido en las líneas 24-28 del Ejemplo Persona.

   Observe cómo en las líneas 13, 15, 19 y 21 del Ejemplo PruebaHerencia se envían mensajes específicos al objeto persona para:

1. Obtener su nombre.
2. Cambiarle el nombre.
3. Volver a obtener su nombre.
4. Solicitarle comer.
5. Solicitarle un mensaje.

   La salida de lo anterior se ve expresada en las primeras cuatro líneas de la siguiente figura:

Salida del Ejemplo PruebaHerencia.

 

    Por otro lado, la línea 26 define y crea el objeto cientifico como una instancia de la clase Cientifico. Al igual que antes, note cómo el constructor utilizado es el definido en las líneas 17-20 del Ejemplo Cientifico.

   A su vez, las líneas 28 y 30 del Ejemplo PruebaHerencia realizan algo análogo a lo que se hizo con el objeto persona, es decir, envían mensajes al objeto cientifico para obtener y cambiar el nombre del científico.

   La línea 32 por su parte, cambia la especialidad del científico a través de un mensaje de tipo set.

   Finalmente, las líneas 34, 36, 38 y 40 envían mensajes específicos al objeto cientifico para:

1. Obtener su nombre.
2. Solicitarle comer.
3. Solicitarle un mensaje.
4. Solicitarle un mensaje especial.

   Note cómo para el mensaje mensaje las respuestas del objeto persona y el objeto cientifico difieren por completo, debido a que aunque el mensaje es el mismo, el objeto que los recibe responde de manera distinta a dicho mensaje; esto último fue lo que en su momento se definió como polimorfismo. En este ejemplo el polimorfismo está expresado en su forma de sobre escritura (override) de métodos.

Composición, Agregación y Asociación.

   Desde mi perspectiva, resulta no trivial el explicar la sutil diferencia que existe entre los conceptos de Composición, Agregación y Asociación. En mi experiencia, existe una tendencia muy común hacia utilizarlos de manera indistinta, sobre todo los dos primeros; por otro lado, el tratar de mostrar uno u otro tipo de relación con ejemplos aislados, en donde sólo me muestre la Composición pero no las otras dos y así con las otras combinaciones representa, al menos para mí, una tarea no muy sencilla.

   El siguiente diagrama de clases UML presenta los cuatro tipos de relaciones más comunes que se dan entre clases:

1. Herencia (entre las clases Persona y Científico, estudiada en la entrada Herencia / Generalización).
2. Composición (entre la clase Persona y las clases Pierna, Cabeza y Tórax entre otras tantas posibles).
3. Agregación (entre las clases Persona y Ropa).
4. Asociación (entre las clases Persona y Tarjeta de Crédito).

Diagrama de Clases UML para mostrar tres tipos de relaciones: Composición, Agregación y Asociación.

    Probablemente he abusado de la simplicidad para el ejemplo, pero he tratado de utilizar elementos conocidos y asequibles en lo general para evitar lo rebuscado o complejo que puede llegar a ser el modelado de un sistema más "real", en el que con toda seguridad aparecerán, de manera natural, este tipo de relaciones. Ahora bien, la generación de esta clase de diagramas se obtiene como resultado del análisis, la experiencia, y la previa comprensión de las diferencias (muchas veces sutiles e incluso subjetivas) que pretendo clarificar.

   La principal diferencia entre las relaciones radica fundamentalmente en dos cosas:

1. En el tiempo de vida de los objetos que se deriven de las clases.
2. El grado de dependencia o cohesión entre los objetos.

Herencia.
   Quizá la relación más simple y más común de las mostradas en el diagrama de clases anterior, sea la de la herencia: un Científico es una Persona, un Científico posee todas las características de una Persona (modeladas por sus atributos) más algunas características particulares a un Científico. Lo mismo sucede con sus responsabilidades y comportamiento. Para ampliar un poco más los detalles, puede el lector revisar la entrada Herencia / Generalización.

Composición.
   La Composición es un tipo de relación de alto grado de dependencia entre la clase contenedora (Persona) y las clases que la componen (Cabeza, Tórax, Pierna, etc.), es decir, cuando se crea una instancia de la clase contenedora, deben crearse, como parte de su conformación, instancias de los objetos que la componen, ya que no tendría sentido, desde el punto de vista de la instancia de Persona, conformar una persona sin cabeza o sin un tórax; por otro lado, durante toda la vida del objeto de la clase Persona debe existir el objeto de la clase Cabeza por la misma razón que antes. En este mismo sentido, tampoco tendría congruencia el tener una instancia de la clase Cabeza que nunca haya estado relacionada con una Persona.

   Algún lector inconforme podría argumentar que sí es posible que un objeto de la clase Persona deje de contener a uno de la clase Pierna por ejemplo, sin afectar la existencia de primero, y en efecto: es posible. Bastaría entonces con analizar si conviene más que la clase Pierna se modele mejor como Agregación, pero finalmente esto es sólo un ejemplo y la idea principal considero que ha sido plasmada, lo último sería más cuestión de análisis y de la conveniencia dada para un sistema determinado tal y como sucede en la vida real.

   Mi perspectiva y determinación personal sería: que se quedara como Composición.

Agregación.
   La Agregación, por otro lado, es un tipo de relación con un bajo grado de dependencia. Así por ejemplo, una instancia de la clase Persona, puede tener o no, durante su tiempo de vida (pero no es preciso que lo tenga desde su creación), un atributo de la clase Ropa sin que ello afecte su propia existencia; al mismo tiempo que un objeto de la clase Ropa podría existir independientemente de si es agregado a una Persona o a un Maniquí (clase que no aparece en el diagrama), por ejemplo.

   En este tipo de relación, la existencia de los objetos involucrados es independiente, lo mismo que su tiempo de vida: un objeto de la clase Ropa podría seguir existiendo más allá del tiempo de vida del de una Persona y viceversa, sin que ninguno de los dos se vea afectado.

Asociación.
   Una Asociación es aún menos dependiente en relación y tiempo. Espero que el lector coincida conmigo en que si bien la ropa no es imprescindible para la existencia de una persona, sí es necesaria; mientras que una tarjeta de crédito podría ser útil, en el mejor de los casos necesaria, pero en definitiva prescindible, es decir, una Persona podría pasar toda su vida sin tener la necesidad de ninguna Tarjeta de Crédito, mientras que otras podría tener muchas de ellas.

   Finalmente la relación de Asociación presentada en el diagrama, muestra que una Tarjeta de Crédito está asociada a una Persona, y que una Persona tiene ninguna (0) o varias (*) Tarjetas de Crédito.

    Finalmente, se recomienda revisar también la información expuesta en la entrada Consideraciones adicionales, en donde se presentan y contrastan ejemplos relacionados con lo aquí expuesto.

Características fundamentales de la POO.

   Alan Curtis Kay, quien es considerado por muchos (yo entre ellos) como el padre de la POO, definió un conjunto de características fundamentales para el paradigma orientado a objetos.

   Con base en lo propuesto por Kay, en la Programación Orientada a Objetos:

1. Todo es un objeto.
2. El procesamiento es llevado a cabo por objetos:
1. Los objetos se comunican unos con otros solicitando que se lleven a cabo determinadas acciones.
2. Los objetos se comunican enviando y recibiendo mensajes.
3. Un mensaje es la solicitud de una acción, la cual incluye los argumentos que son necesarios para completar la tarea.
3. Cada objeto tiene su propia memoria, misma que está compuesta de otros objetos.
4. Cada objeto es una instancia de una clase. Una clase representa un grupo de objetos similares.
5. La clase es el repositorio del comportamiento asociado con un objeto.
1. Todos los objetos que son instancias de la misma clase llevan a cabo las mismas acciones.
6. Las clases están organizadas en una estructura jerárquica de árbol denominada jerarquía de herencia.
1. La memoria y el comportamiento asociados con las instancias de una clase, están automáticamente disponibles para cualquier clase asociada con la descendencia dentro de la estructura jerárquica de árbol.

   En un intento de complementar la visión de Alan Kay, se presenta a continuación un compendio de conceptos que definen también y refuerzan las características principales de la POO:

• La abstracción denota las características esenciales de un objeto.
• El proceso de abstracción permite seleccionar las características relevantes del objeto dentro de un conjunto e identificar comportamientos comunes para definir nuevos tipos de entidades.
• La abstracción es la consideración aislada de las cualidades esenciales de un objeto en su pura esencia o noción.
• La modularidad es la propiedad que permite subdividir una aplicación en partes más pequeñas (llamadas módulos), cada una de las cuales debe ser tan independiente como sea posible de la aplicación en sí, y de las partes restantes.
• La modularidad es el grado en el que los componentes de un sistema pueden ser separados y reutilizados.
• El encapsulamiento tiene que ver con reunir todos los elementos que pueden considerarse pertenecientes a una misma entidad al mismo nivel de abstracción. Esto permite aumentar la cohesión de los módulos o componentes del sistema. La encapsulación es quizá el concepto más importante del paradigma, ya que permite agrupar las funcionalidades (métodos) y el estado (datos) de los objetos de forma cohesiva. Los métodos proporcionarán los mecanismos adecuados para modificar el estado, y en algunos casos también serán la puerta de acceso a éste.
• El principio de ocultación de información (information hiding) se refiere a que cada objeto está aislado del exterior; es un módulo independiente y cada tipo de objeto presenta una interfaz a otros objetos, la cual especifica cómo es que pueden interactuar con él.
• El aislamiento protege a las propiedades de un objeto contra su modificación por quien no tenga derecho a acceder a ellas; solamente los propios métodos internos del objeto pueden acceder a su estado. Lo anterior asegura que otros objetos no puedan cambiar el estado interno de un objeto de manera accidental o intencionada, eliminando así efectos secundarios e interacciones inesperadas.
• El polimorfismo está relacionado con el aspecto referente al de qué tipo de comportamientos diferentes asociados a objetos distintos, pueden compartir el mismo nombre.
• El polimorfismo es la capacidad que tienen los objetos de naturaleza heterogénea, de responder de manera diferente a un mismo mensaje en función de las características y responsabilidades del objeto que recibe dicho mensaje.
• La herencia organiza y facilita el polimorfismo y el encapsulamiento, permitiendo a los objetos ser definidos y creados como tipos especializados de objetos preexistentes.
• Las clases no están aisladas, sino que se relacionan entre sí formando una jerarquía de clasificación.
• Los objetos heredan las propiedades y el comportamiento de todas las clases a las que pertenecen. Así, los objetos pueden compartir y extender su comportamiento sin tener que volver a implementarlo.
• La herencia múltiple se da cuando un objeto hereda de más de una clase.

   Es sumamente importante en lo subsecuente, tener todos estos conceptos vigentes y presentes, estudiarlos, analizarlos y comprenderlos; la memorización no es recomendable, ya que el memorizar conceptos no implica necesariamente su asimilación y mucho menos su comprensión. Por otro lado, si un concepto es comprendido, es posible entonces el poder explicarlo y deducir en consecuencia su definición.

   Mi deseo es que el lector reflexione sobre este aspecto y que, con un poco de paciencia, sume a su repertorio de conocimientos el conjunto de conceptos descritos hasta aquí, los cuales se pondrán en práctica eventual y progresivamente en entradas subsecuentes del blog.

POO (Consideraciones adicionales).

Respecto al envío de mensajes.

   La sintaxis general en Java para el envío de mensajes a un objeto es la siguiente:

objeto.mensaje(lista_de_argumentos);

donde objeto es un objeto de una clase previamente definida, y mensaje es uno de los métodos públicos definidos para dicha clase. La lista_de_argumentos es una lista de argumentos separada por comas, en donde cada argumento puede ser un objeto, o un tipo de dato primitivo.

Respecto a la sobrecarga de operadores.
   Algunos lenguajes de programación soportan un concepto relacionado con sobrecarga de operadores. La idea general del concepto de sobrecarga se ha planteado en la entrada POO (mensajes y métodos). El lenguaje de programación Java no soporta la sobrecarga de operadores, y por consiguiente, se ha omitido su descripción; sin embargo, es importante que el lector conozca que el concepto de sobrecarga no es exclusivo de los métodos o constructores, ni mucho menos de un lenguaje de programación en particular.

 

    La sobrecarga de operadores en C++ sí existe. En la sección correspondiente a las consideraciones adicionales para las colas de espera, se proporcionan un par de ejemplos al respecto. Para comprenderlos se requiere tener claros los aspectos relacionados con la implementación de la herencia, el funcionamiento de las colas de espera, y su respectiva especialización en la forma de colas de prioridad.

Respecto al paradigma.
   El establecimiento de niveles de acceso como private para los atributos de una clase, así como el uso de métodos de tipo set y get están directamente relacionados con el principio de ocultación de información (information hiding).

   Ahora bien, es probable que el lector haya notado que en la descripción del Ejemplo PruebaHerencia, en distintas ocasiones se hizo referencia a los objetos persona y científico como si fueran en sí mismos personas o entidades existentes. Lo anterior se hizo de manera deliberada, ya que como se comentó en la entrada referente al paradigma orientado a objetos, ésto eleva el nivel de abstracción y permite que se haga referencia a las entidades fundamentales del paradigma (los objetos), como elementos comunes de nuestro lenguaje natural, lo cual permite que los problemas se puedan expresar, al menos en principio, de una manera más natural e intuitiva.

   En este sentido, al dotar a los objetos de una personalidad propia con características y responsabilidades, en lugar de pensar en términos de datos, variables, y funciones o procedimientos que operen sobre dichos datos, se eleva el nivel de abstracción, facilitando con ello el análisis y la comprensión, ya que el problema y su solución pueden ser expresados y analizados en términos de su propio dominio, y no en el del medio (lenguaje de programación) de la solución. Ésta es una de las formas en la que las personas abstraemos, procesamos y utilizamos la información.

   Es sumamente importante que el lector tenga presente que en el paradigma orientado a objetos no se piensa en términos de datos, sino en términos de entidades con características y responsabilidades específicas, por lo que, cuando defina una clase, puede resultar útil el plantearse al menos un par de preguntas que le permitan determinar si los objetos derivados de su clase tienen o no sentido. Adicionalmente, las preguntas pueden ayudar también a establecer o coadyuvar en la meta de mantener una alta cohesión como parte del proceso de diseño e implementación:

1. ¿Los atributos representan características o propiedades, o definen un estado para los objetos que serán instanciados?
2. ¿La clase representa en sus métodos servicios, comportamiento, acciones o responsabilidades inherentes a los objetos que deriven de ella?

   Cabe mencionar que las preguntas propuestas son sólo una guía y una sugerencia al lector, no pretenden ser de ninguna manera una lista completa y absoluta. Con estas dos sencillas preguntas, además de validar y verificar su diseño de clases, estará reforzando también el concepto de encapsulamiento.

Respecto al polimorfismo.
   El polimorfismo es la cualidad de objetos heterogéneos de responder de distinta manera a un mismo mensaje. El tipo de polimorfismo más común se da en la herencia, pero no es el único.

   El Ejemplo Heterogéneo es un conjunto de clases (Automóvil, Motocicleta, Perro, Planta, Plomero, Profesor) heterogéneas que contienen un método de servicios. La idea es que, al menos en principio, cada una de dichas entidades ofrecen servicios distintos en función de su constitución y comportamiento general.

   Por otro lado, el Ejemplo Composición contiene tres clases: Libro, Publicación y Revista, las cuales presentan un comportamiento de polimorfismo en la forma en que se auto describen (imprimen), a través del método toString( ).

   En directa relación con el párrafo anterior, el tipo de polimorfismo más común se presenta en el Ejemplo Herencia, el cual contiene también las tres clases Libro, Publicación y Revista pero con un enfoque de polimorfismo basado en la herencia para la forma en que se auto describen (imprimen) a través del método toString( ).

   Existe un concepto en programación denominado latebinding, dynamic bindig o dynamic linkage, el cual se refiere a un mecanismo de programación en el cual el método que responderá al mensaje (el método que será invocado) es determinado en tiempo de ejecución. Como un ejemplo muy simple de esto, tómese el tiempo de comparar y analizar el Ejemplo PruebaHerencia (descrito en la entrada POO (Herencia)) y el Ejemplo PruebaPolimorfismo, en donde se muestra dicho concepto de programación, así mismo, es importante comprender tanto las diferencias de dichos ejemplos como los comentarios que aparecen en el código del Ejemplo PruebaPolimorfismo.

   Considere ahora el siguiente Ejemplo de late binding y tómese el tiempo que considere necesario para comprenderlo con base en el concepto de polimorfismo y  la comprensión de todos y cada uno de los ejemplos anteriores.

 

    Finalmente, una vez que se tengan madurados y comprendidos los ejemplos enunciados y su relación con el polimorfismo, se recomienda revisar también el tema de clases abstractas e interfaces (Java) para complementar dicho concepto.

Pilas (implementación).

   La representación de una pila, como una secuencia de nodos, se muestra en la siguiente figura. Los detalles de su implementación se desarrollarán a continuación.

Abstracción de una pila como una secuencia de nodos.

 Pila primitiva.

   Esta sección describe la implementación de una pila primitiva. Se ha denominado de esta forma debido a que implementa una estructura de datos que almacena un tipo de dato primitivo: int.

   La definición de la clase fundamental para la implementación de la estructura de datos se muestra en el Ejemplo NodoPrimitivo. Los detalles de este tipo de implementación de clases autorreferidas se han discutido con anterioridad en la entrada Abstracción de estructuras de datos y no se repetirán aquí, por lo que se sugiere al lector que la revise nuevamente y se tome el tiempo necesario para comparar el Ejemplo NodoPrimitivo con el Ejemplo Nodo antes de continuar.

   La implementación de la estructura de datos pila se muestra en el Ejemplo PilaPrimitiva, y su explicación se centrará únicamente en los métodos push, pop, estaVacia e imprime.

   El método estaVacia (líneas 37-39) realiza una verificación bastante simple: si el tope de la pila es igual a null, regresa verdadero (está vacía), si no, regresa falso (existe al menos un elemento).

   El método push por su parte (líneas 18-23), recibe como argumento el elemento a insertar en la pila (elemento), y se apoya del método estaVacia y de los constructores para realizar la inserción:

• Si la pila está vacía (línea 19), se crea un nuevo nodo con el elemento correspondiente (línea 20) para el atributo dato, y null en su atributo siguiente.
• Si la pila no está vacía (línea 21), se crea un nuevo nodo con el elemento correspondiente para el atributo dato y con el tope actual en su atributo siguiente (línea 22). Así mismo, note que el tope es actualizado para hacer referencia al nodo recién creado.

   Ahora bien, observe que el método pop (líneas 26-34) posee una característica particular: el método lanza (throws) una excepción ExcepcionEDVacia (línea 26) lo cual quiere decir que, en determinadas condiciones, el método puede lanzar una excepción; para el caso del método pop, la condición consiste en intentar eliminar un elemento de la pila cuando ésta está vacía.

   La excepción ExcepcionEDVacia definida en el Ejemplo ExcepcionEDVacia es en realidad bastante simple, ya que delega toda la responsabilidad a RuntimeException que es la clase de la que deriva, y lo único que hace es establecer un identificador para la excepción a través de sus constructores, los cuales en realidad utilizan el constructor de la super clase (clase padre) a través de la cláusula super. Es importante que el lector recuerde esta excepción, ya que será la excepción que utilizarán todas las estructuras de datos que se implementan en el blog.

   Ahora bien, cuando el programador se enfrenta a la necesidad de lanzar una excepción cabe la pregunta ¿y de qué tipo? Se puede utilizar una excepción escrita por alguien más o se puede hacer una propia. Se debería hacer clases de excepción propias cuando se responda de manera afirmativa a alguna de las siguientes preguntas, de otra forma, debería usarla una excepción escrita por alguien más (vea Creating Exception Classes):

• ¿Necesita un tipo de excepción que no está representada en el API de Java?
• ¿Sus usuarios se verán beneficiados si pueden diferenciar sus excepciones de aquellas lanzadas por clases escritas por alguien más?
• ¿Su código lanza más de una excepción relacionada?
• Si utiliza una excepción escrita por alguien más, ¿sus usuarios tendrán acceso a esas excepciones?
• ¿Su paquete de clases debería ser independiente y auto contenido?

   Continuando con el Ejemplo PilaPrimitiva, el método pop verifica (línea 27) si la pila está vacía, si lo está, crea y lanza la excepción correspondiente (línea 28); en caso contrario, recupera el dato almacenado (línea 30), y desecha el nodo correspondiente al hacer que el tope haga ahora referencia al elemento siguiente del tope actual (línea 31), para finalmente regresar el dato recuperado (línea 33). En Java no hay una eliminación o liberación explícita de memoria, dicha labor es delegada al recolector de basura el cual se encarga, grosso modo, de identificar aquellos objetos que no estén siendo referidos para entonces liberar la memoria que utilizan.

   Por último, en el método imprime (líneas 42-57), si la estructura de datos está vacía (línea 43), se reporta (línea 44); en caso contrario, se realiza un recorrido por todos los nodos de la estructura para imprimir su contenido (líneas 47-54).

   La clase de prueba para la pila primitiva del Ejemplo PilaPrimitiva, se presenta en el Ejemplo PruebaPila. Observe cómo en la línea 6 se crea la pila y se utiliza un constructor sin argumentos.

   Las líneas 9-12 realizan la inserción en la pila de los números del cero al nueve; por cada inserción se imprime todo el contenido de la pila, como se muestra en la siguiente figura:

Ejemplo de inserción de elementos en la pila primitiva. Se muestra la salida del Ejemplo PruebaPila.

    Por otro lado, las líneas 15-24 realizan la eliminación de los elementos de la pila. Dicho fragmento de código intenta eliminar once elementos (líneas 17-18) de la pila (recuerde que sólo fueron insertados diez elementos, por lo que al intentar eliminar el décimo primero, se generará la excepción ExcepcionEDVacia), y dado que el método pop puede lanzar una excepción, el código involucrado en la eliminación debe estar dentro de una cláusula try-catch-finally, la cual permite atrapar (cachar) las excepciones que un método pudiera lanzar.

   Si se genera un excepción ExcepcionEDVacia, ésta es atrapada y el flujo de control se envía al ámbito de la cláusula catch en donde se realiza el correspondiente tratamiento de la excepción. Para el caso del Ejemplo PruebaPila el manejo de la excepción consiste únicamente en imprimir la secuencia de eventos (en forma de pila) que dieron lugar a la excepción; sin embargo, es importante aclarar que el manejo de una excepción puede ser tan elaborado como en un momento dado se requiera.

   La salida correspondiente a la eliminación de elementos de la pila primitiva, se muestra en la siguiente figura:

Ejemplo de eliminación de elementos en la pila primitiva. Se muestra la salida del Ejemplo PruebaPila.

Pila genérica.

   Esta sección generaliza la implementación de una pila de tal forma que la estructura de datos tenga la capacidad de almacenar objetos genéricos; es decir, objetos de cualquier clase.

   Como primer paso, es preciso que el lector se tome el tiempo que considere necesario para comparar el Ejemplo NodoPrimitivo discutido en la sección anterior, con el Ejemplo NodoG. Es importante resaltar que, aunque distintos, ambos ejemplos son esencialmente equivalentes.

La primera diferencia que salta a la vista, además del nombre de la clase, es la notación <T>. Dicha notación se utiliza en Java para especificar que la clase gestiona objetos genéricos, es decir, que el tipo o la clase de los objetos que almacena no está especificada en la definición de la misma, sino que se especifica en el momento de la instanciación del objeto (observe la línea 6 del Ejemplo PruebaPilaGenerica).

   La línea 7 del Ejemplo NodoG define que la clase del atributo dato es T, es decir, un genérico, y por lo tanto el atributo siguiente es una referencia a un objeto que almacena objetos genéricos.

   Observe cómo ahora los constructores y los métodos de tipo set reciben como argumentos objetos genéricos T (líneas 10, 14 y 19), y referencias a objetos que a su vez almacenan objetos genéricos (líneas 14 y 27); mientras que los métodos de tipo get regresan genéricos (línea 23), o referencias a objetos que almacenan objetos genéricos (línea 31).

   Ahora bien, las consideraciones hechas para el Ejemplo NodoG respecto a los genéricos, son las mismas que debe tomar en cuenta para el Ejemplo Pila, por lo que una vez más se pide encarecidamente al lector que compare este último con el Ejemplo PilaPrimitiva discutido en la sección anterior tomando en consideración lo explicado hasta este momento para los genéricos.

   Observe que en ninguna parte del Ejemplo Pila se hace explícita una clase específica para el genérico T, por lo que también aquí se hace una gestión de genéricos en directa relación con los genéricos utilizados en el Ejemplo NodoG.

   En resumen, la clase NodoG del Ejemplo NodoG define nodos que almacenan objetos genéricos (nodos genéricos), los cuales son utilizados de manera conveniente por la clase Pila del Ejemplo Pila para conformar una estructura de datos dinámica que almacena objetos o nodos genéricos en forma de pila.

   El Ejemplo PruebaPilaGenerica muestra la clase de prueba para la pila genérica del Ejemplo Pila. La línea más importante del Ejemplo PruebaPilaGenerica es la línea 6, ya que es en ella en donde finalmente se define la clase de objetos que contendrá (almacenará) la pila: Integer.

   Consulte la sección Genéricos de la entrada Ejemplos selectos de transición para ampliar un poco más la información y los detalles acerca de los genéricos en Java. En el Ejemplo PilaC se muestra la implementación alternativa de una pila utilizando un ArrayList del API de Java; mientras que en el EjemploPruebaPilaC se presenta su correspondiente clase de prueba. Adicionalmente, se proporcionan al lector dos ejemplos adicionales que utilizan colecciones (estructuras de datos) del API: Stack y ArrayDeque (Deque); tómese el tiempo de estudiarlos y revisar la información correspondiente en el API.

   Finalmente, asegúrese de comprobar que la salida del Ejemplo PruebaPilaGenerica corresponde, en esencia, con la salida del Ejemplo PruebaPila para la inserción de datos (push), y que lo correspondiente ocurre también para la eliminación de elementos (pop).

ABB (implementación).

   Esta entrada presenta la implementación de un ABB en base a dos enfoques respecto a la inserción de elementos:

1. Enfoque recursivo.
2. Enfoque iterativo.

   Para ambas implementaciones se utiliza la clase NodoABB definida en el Ejemplo NodoABB, por lo que será la primera clase que se describirá.

   La clase NodoABB define un nodo capaz de almacenar objetos genéricos. Cada nodo definido por la clase tiene la forma de cada uno de los nodos de la siguiente figura:

Árbol binario de búsqueda (ABB) conformado por objetos de la clase NodoABB.

 

    Observe además que cada objeto instanciado tendrá dos referencias a objetos como él, las cuales representarán referencias hacia el subárbol izquierdo (nodoIzquierdo) y hacia el subárbol derecho (nodoDerecho).

   Los detalles restantes deberían resultarle familiares al lector, ya que en esencia se refieren a un constructor y a los métodos de tipo set y get para cada uno de los atributos. Asegúrese de comprender el Ejemplo NodoABB en su totalidad antes de continuar.

Enfoque recursivo.

   Probablemente el enfoque más común para la implementación de un ABB debido a la naturaleza inherente a la definición de dicha estructura de datos, sea el enfoque basado en la recursividad.

   El Ejemplo ABBr muestra la definición de la clase ABBr, la cual es en esencia la implementación de la representación definida en el diagrama de clases UML presentado en la entrada ABB (representación y diseño).

   El estudio y la comprensión de la implementación de los métodos de recorrido para un árbol binario de búsqueda (líneas 34-68), se dejan como ejercicio para el lector.

   El método inserta (líneas 13-18), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, delega la responsabilidad de la inserción de elemento dentro de arbol al método privado recursivo insertaR (línea 17).

   Por su parte, la idea del método insertaR (líneas 21-32) es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:

• Si elemento es menor (línea 22), debe ser insertado en el subárbol izquierdo.
• Si el subárbol izquierdo está vacío o disponible (línea 23), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 24). Si no está vacío (línea 25), se recorre el subárbol izquierdo de manera recursiva (línea 26) para encontrar la posición apropiada para elemento dentro del subárbol.
• Si elemento es mayor (línea 27), debe ser insertado en el subárbol derecho.
• Si el subárbol derecho está vacío o disponible (línea 28), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 29). Si no está vacío (línea 30), se recorre el subárbol derecho de manera recursiva (línea 31) para encontrar la posición apropiada para elemento dentro del correspondiente subárbol.

   La clase de prueba para la clase ABBr del Ejemplo ABBr se muestra en el Ejemplo PruebaArbol.

   La clase PruebaArbol del Ejemplo PruebaArbol utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico; el cual, además de presentarse en la salida estándar (línea 15), representa el valor a ser insertado dentro del árbol binario de búsqueda (línea 16).

   Finalmente, el Ejemplo PruebaArbol realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Es ampliamente recomendable que el lector realice varias ejecuciones de la clase PruebaArbol y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.

Una posible salida de los Ejemplos PruebaArbol y Prueba ABB.

 

    Una posible salida para el Ejemplo PruebaArbol se muestra en la figura anterior.

Enfoque iterativo.

   Un enfoque alternativo para la implementación de la operación de inserción en un árbol binario de búsqueda, es utilizar un ciclo en lugar de recursividad.

   El enfoque propuesto es casi tan compacto como el recursivo pero mucho más eficiente. La implementación sin recursividad del ABB representado en el diagrama de clase de la entrada ABB (representación y diseño) se presenta en el Ejemplo ABB.

   Al igual que antes, el estudio y la comprensión de la implementación de los métodos de recorrido (líneas 34-68), se dejan como ejercicio para el lector.

   El método inserta (líneas 13-32), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, se genera una referencia alterna (línea 17) para recorrer el árbol (línea 18).

   Al igual que antes, la idea es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:

• Si elemento es menor (línea 19), debe ser insertado en el subárbol izquierdo.
• Si el subárbol izquierdo está vacío o disponible (línea 20), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 21). Si no está vacío (línea 22), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol izquierdo (línea 23) para encontrar la posición apropiada para elemento dentro del árbol.
• Si elemento es mayor (línea 24), debe ser insertado en el subárbol derecho.
• Si el subárbol derecho está vacío o disponible (línea 25), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 26). Si no está vacío (línea 27), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol derecho (línea 28) para encontrar la posición apropiada para elemento dentro del ABB.
• Finalmente, si el elemento no fue menor ni mayor, entonces por tricotomía de los números no le queda otra más que ser igual, en cuyo caso no hay nada por hacer mas que terminar (líneas 29 y 30).

   La clase de prueba para la clase ABB del Ejemplo ABB se muestra en el Ejemplo PruebaABB.

   Al igual que antes, la clase PruebaABB del Ejemplo PruebaABB utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico, el cual además de presentarse en la salida estándar (línea 15), representa el valor que será insertado dentro del árbol binario de búsqueda (línea 16).

   Finalmente, el Ejemplo PruebaABB también realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Una vez más, se recomienda ampliamente que el lector realice varias ejecuciones de la clase PruebaABB y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.

Ejercicios selectos (colas).

(a) Estado inicial para la representación de Round robin.

(b) Estado siguiente para la representación de Round robin.

1. En el Ejemplo Cola el método inserta tiene la línea 24 como comentario ¿Qué sucede si sustituye la línea 25 por la línea 24? ¿Compilará? Si sí, ¿por qué?, y si no, ¿por qué? Si compila ¿Cuál será el resultado de la ejecución? Determine sus respuestas y después corrobore las mismas con la experimentación.
2. En el Ejemplo PruebaCola se creó una cola de espera utilizando un constructor sin argumentos. Modifique dicho ejemplo para asignar un nuevo nombre a la cola por medio del constructor correspondiente, asígnele el nombre de "Mi primera cola de espera", recompile, y pruebe su funcionamiento.
3. Modifique el Ejemplo PruebaCola para que permita leer n números enteros desde la entrada estándar y los almacene en la cola de espera.
4. Modifique el Ejemplo Cola para que:
1. Agregue el método peek a la implementación. Dicha operación funciona de la siguiente manera: echa un vistazo al elemento que se encuentra en el inicio de la cola de espera, lo regresa pero no lo elimina.
2. Incorpore un atributo privado numérico (n) que lleve el control del número de elementos insertados en la cola de espera. Al respecto no olvide:
1. Inicializar explícitamente dicho atributo a cero en el constructor.
2. Proporcionar únicamente el método de tipo get para el atributo n: public int obtenN( ).
5. Tomando como referencia el Ejemplo PruebaCola, modifíquelo para que la cola de espera del Ejemplo Cola almacene otro tipo de objetos además de los de la clase Integer. Pruebe con al menos las siguientes clases:
1. Double.
2. String.
3. Persona (del Ejemplo Persona).
4. Cientifico (del Ejemplo Cientifico).
6. Utilizando una cola de espera como la del Ejemplo Cola, implemente el algoritmo de Round robin. Round robin es un método para seleccionar a todos los elementos en un grupo de manera equitativa y en orden, se comienza con el primer elemento de la cola de espera y se procesa, se continua con el segundo y así de manera progresiva hasta llegar al último elemento de la cola, para empezar nuevamente desde el primer elemento. El principio general subyacente detrás del método, consiste en que cada elemento de la cola de espera consume una parte de un elemento compartido en cantidades iguales.
1. Considere la figura anterior en su inciso (a), la cual representa el estado inicial de una cola de espera de números enteros que representan las cantidades a considerar (quantum).
2. El estado siguiente (inciso (b)) consiste en atender (restarle uno al quantum) al nodo que se encuentra al inicio de la cola y volverlo a formar al final de la misma para atender de manera análoga a los siguientes nodos.
3. Tome en consideración que, una vez que el número llega a cero, el nodo correspondientes es eliminado. 
4. El proceso anteriormente descrito continúa hasta atender o despachar a todos los nodos formados en la cola. Para ello:
1. Genere un número aleatorio entre 10 y 50, el cual representará el número de nodos que contendrá la cola de espera.
2. Por cada nodo, genere nuevamente un número aleatorio entre 1 y 500, mismo que representará el quantum asignado a cada nodo.
5. No olvide construir también una clase de prueba para su implementación. La salida de su programa puede ser en la salida estándar o en un archivo de texto (consulte el API). Es importante que compruebe el adecuado funcionamiento de su implementación, ya que se reutilizará en otros ejercicios del blog.
7. Modifique el Ejemplo PruebaColaAscendente para que la cola de prioridad ascendente del Ejemplo ColaAscendente almacene otro tipo de objetos además de los de la clase Integer. Pruebe con al menos las siguientes clases:
1. Double.
2. String.
3. Persona (del Ejemplo Persona).
4. Cientifico (del Ejemplo Cientifico).
5. Tome en cuenta que las clases Double y String del API de Java implementan la interfaz Comparable, pero que las clases Persona y Cientifico no, por lo que como primer paso, deberá hacer que dichas clases implementen la interfaz Comparable y definan el método compareTo. Para ello:
1. Realice el ordenamiento en base al atributo que representa la edad de la persona para las instancias de la clase Persona (vea 7.6).
2. Realice el ordenamiento en función del atributo que representa la especialidad del científico para las instancias de la clase Cientifico (vea 7.7).
6. Como guía adicional para el lector, la clase PersonaComparable del Ejemplo PersonaComparable realiza la implementación de la interfaz Comparable. Observe cómo dicho ejemplo es esencialmente igual al Ejemplo Persona. Compare ambos ejemplos, estúdielos, y ponga especial atención en las líneas 5 y 57-63 del Ejemplo PersonaComparable, para que pueda resolver lo planteado en este ejercicio.
7. Respecto a la clase Cientifico, la solución es un poco más elaborada:
1. Si partimos de la siguiente base: public class Persona implements Comparable<Persona>{...}. Entonces la herencia debería ser: public class Cientifico extends Persona implements Comparable<Persona>{...} y no public class Cientifico extends Persona implements Comparable<Cientifico>{...} ya que de otra forma el compilador indicará que Comparable no puede ser heredada con diferentes argumentos (Cientifico y Persona).
   
2. El método compareTo de Cientifico debe hacer un cast (conversión de tipos): public int compareTo(Persona p){   Cientifico c = (Cientifico) p; // aquí va el código que compara con los criterios para Científico.}.
3. La cola ascedente deberá indicar que almacena objetos de la clase base Persona: ColaAscendente<Persona> cola = new ColaAscendente<Persona>( ); pero insertar instancias de Cientifico (por eso es necesario el cast).
4. En este tipo de problemas recuerde siempre usar la clase base como tipo base para los datos, aunque inserte objetos de clases derivadas. El proceso de eliminación es equivalente.
   
8. Con base en las consideraciones hechas en el blog respecto de la cola de prioridad ascendente y al diseño propuesto por el diagrama de clases UML alternativo (entrada Colas de prioridad), realice la implementación de la cola de prioridad ascendente sobrescribiendo ahora el método elimina. Pruebe su propuesta con las clases y las consideraciones hechas en el Ejercicio anterior para la interfaz Comparable.
9. Realice la implementación de una cola de prioridad descendente de manera análoga a la del Ejemplo ColaAscendente. Para lo anterior, tome en cuenta las consideraciones hechas en el blog y lo expuesto en el diseño representado por el diagrama de clases UML (entrada Colas de prioridad). No olvide definir también la clase de prueba para verificar y validar su propuesta; puede basarse en la del Ejemplo PruebaColaAscendente. Para sus pruebas, tome en cuenta al menos, las clases y consideraciones propuestas en el Ejercicio 7.
10. Con base en las consideraciones hechas en el blog respecto de la cola de prioridad descendente y al diseño propuesto por el diagrama de clases UML alternativo (entrada Colas de prioridad), realice la implementación de la cola de prioridad descendente. Pruebe su propuesta con las clases y las consideraciones hechas en el Ejercicio 7 para la interfaz Comparable.
11. Considere la abstracción de la estructura de datos compuesta mostrada en la figura que aparece al final de esta entrada. La estructura de datos mostrada está compuesta por una cola de espera y varias pilas, una por cada nodo formado en la cola. Note que cada nodo de la cola de espera conserva una referencia a objetos como él, y una referencia a objetos de tipo pila. Este ejercicio consiste en hacer una representación de una fila de supermercado, en donde cada nodo formado en la cola de espera, simula un carrito de supermercado con diferentes productos almacenados en él en forma de pila (en la vida real no necesariamente es así, pero para el caso del ejercicio propuesto basta con esa suposición). Cada nodo de la pila representa un producto, por lo que se requiere que la información que almacena la pila sean cadenas que representan la descripción del producto: leche, jamón, huevos, cacahuates, etc.
1. Escriba un programa que modele e implemente la estructura de datos planteada por el diagrama de la estructura de datos.
2. Sería sumamente conveniente y recomendable para el lector que, como parte de su diseño, realizara también el diagrama de clases UML de su propuesta de solución.

Abstracción de una estructura de datos compuesta.