Cómo ordenar colecciones de objetos

Ordenación de colecciones de objetos.

Revisión 1.1

Introducción.

Debido a que en los últimos tiempos esta parece ser una de las preguntas más
frecuentes que aparecen, me he decidio a escribir este pequeño ejemplo sobre
como ordenar elementos. Este ejemplo no trata de ser una guía de buena
programación, si no que trata simplemente de enseñar la manera de ordenar
fácilmente colecciones de elementos.

Como toda persona que trabaja con Java debería saber, el API de Java es muy
rico, y contiene ya mucho del código genérico que nuestra aplicación pueda
necesitar. Solo hay que saber buscarlo.

Este es el caso de la ordenación de elementos, que viene ya implementada, con
un algoritmo de los más eficientes, el mergesort. Además, date cuenta de
que, como dice el título, este artículo trata el ordenamiento de objetos,
no elementos primitivos.

Un poco de teoría: el interface java.lang.Comparable.

Gran parte de la magia en la ordenación de objetos que ofrece Java2 es
culpa del buen diseño del API Collections, que ofrece el conjunto de
funcionalidad básica para tratamientos de conjuntos de elementos. Este API es
capaz de ordenar todos los objetos de clases que implementen el interface
java.lang.Comparable, que contiene un solo método:

Method Summary
int	compareTo(Object o)           Compares this object with the specified object for order.

El entero que devuelve este método será el equivalente a
objeto1 - objeto2, es decir:

objecto1.comparteTo(objeto2);

negativo si objeto1 < objeto2
cero     si objeto1 = objeto2
positivo si objeto1 > objeto2

Lo que decida si un objeto es mayor o menor que otro es lo que tenemos que hacer
nosotros. Por supuesto gran parte de las clases básicas del API de Java, como
String, Integer, File, Date y demás, ya la implementan, con el
orden esperado (alfabético, ordinal, cronológico, etc), así que solo tendremos
que preocuparnos de este interface con nuestras clases propias más complejas,
como por ejemplo, Usuario:

class Usuario{

private String nombre;
private int edad;

Usuario(String nombre, int edad) {
this.nombre = nombre;
this.edad = edad;
}

public String getNombre() {
return nombre;
}

public int getEdad() {
return edad;
}

public String toString() {
return nombre + " (" + edad + ")";
}
}

Nosotros tendremos que decidir que hace que un Usuario
vaya antes que otro, pongamos por ejemplo el orden alfabético.

class Usuario1 implements Comparable {

private String nombre;
private int edad;

Usuario1(String nombre, int edad) {
this.nombre = nombre;
this.edad = edad;
}

public String getNombre() {
return nombre;
}

public int getEdad() {
return edad;
}

public String toString() {
return nombre + " (" + edad + ")";
}

public int compareTo(Object o) {
Usuario1 otroUsuario = (Usuario1) o;
//podemos hacer esto porque String implementa Comparable
return nombre.compareTo(otroUsuario.getNombre());
}
}

Ordenando: la clase java.util.Collections.

Como he dicho antes, muchas de las cosas más básicas (y muchas otras no tan
básicas) que podamos necesitar en nuestros programas Java ya estan
implementadas. En el caso de las colecciones de elementos se encuentran en el
paquete java.util. Allí podreís encontrar todas las clases para
mantener grupos de elementos (listas, pilas, árboles, etc), y como no, clases de
utilidad. Eso es lo que ahora necesitamos, una clase de utilidad:
java.util.Collections, no confundir con el interface
java.util.Collection, base de (casi) todas las colecciones de
objetos.

Esta clase contiene muchos métodos, para hallar el elemento más
pequeño o el más grande de una colección, para barajearlos
(cambiar su orden de forma aleatoria), para ponerlos en orden inverso al actual,
etc. Solo teneis que consultar el API.

Por supuesto esta clase tiene un método para ordenar colecciones de elementos, y
es eso lo que nos ocupa ahora.

Method Summary
static void	sort(List list)           Sorts the specified list into ascending order, according to the natural ordering of its elements.

Como veis este método puede ordenar cualquier colecion que implemente el
interface java.util.List, y ese orden natural se refiere al
orden que indican el método comparteTo que hemos visto antes.

Un ejemplo para ordenar distintos java.lang.String sería de la
siguietne forma:

ArrayList lista = new ArrayList();
lista.add("uno");
lista.add("dos");
lista.add("tres");
lista.add("cuatro");
printList(lista);
System.out.println("\n Ahora ordenados...");
Collections.sort(lista);
//metodo que imprime la lista
printList(lista);

Y para ordenar nuestros queridos Usuario haríamos algo como esto

ArrayList lista = new ArrayList();
lista.add(new Usuario1("uno", 11));
lista.add(new Usuario1("dos", 2));
lista.add(new Usuario1("tres", 3));
lista.add(new Usuario1("cuatro", 44));
printList(lista);
System.out.println("\n Ahora ordenados...");
Collections.sort(lista);
//metodo que imprime la lista
printList(lista);

Cambiando el orden: el interface java.util.Comparator.

Hasta aquí hemos visto lo fácil que era todo, pero aún nos queda la parte
complicada, ¿qué hacemos si queremos ordenar nuestros Usuario
por edad en lugar de nombre?. Eso no nos lo permite hacer el interface
java.lang.Comparable, así que consultamos la documentacion de
nuestra clase de utilidades java.util.Collections y descubrimos el
siguiente método:

Method Summary
static void	sort(List list, Comparator c)           Sorts the specified list according to the order induced by the specified comparator.

Así que nos pica la curiosidad y vamos a ver que es eso de
java.util.Comparator, y descubrimos que es otro interface que se
usa para comparar objetos, y que tiene los siguientes métodos:

Method Summary
int	compare(Object o1, Object o2)           Compares its two arguments for order.
boolean	equals(Object obj)           Indicates whether some other object is "equal to" this Comparator.

El método equals(Object obj) no nos interesa, es el que como
en la clase java.lang.Object determina si dos objetos son el mismo
o no, el que nos interesa es el otro,
compare(Object o1, Object o1).

El funcionamiento es el mismo que el visto anteriormente en el interface
comparable, solo que en esta ocasión se pasan los dos objetos a comparar como
argumentos. El resultado será:

negativo si o1 < o2
cero     si o1 = o2
positivo si o1 > o2

o al menos eso es lo que se espera, porque nosotros podemos decidir. El método
sort de la clase java.util.Collections ordenadrá en
función de este resultado, pero somos nosotros quién decide ese orden.

Podríamos hacer que nuestras clases implementasen
java.util.Comparator, pero entonces no habríamos avanzado mucho
desde el ejemplo anterior, es decir, estaríamos limitados a un orden, por lo que
lo normal será escribir distintas clases que implementen este interface para
después usar la que necesitemos en cada momento. Para ordenar nuestra clase
Usuario escribiremos dos clases, una para ordenarlos por nombre,
y otra por edad.

import java.util.Comparator;

class NombreComparator implements Comparator {

public int compare(Object o1, Object o2) {
Usuario u1 = (Usuario) o1;
Usuario u2 = (Usuario) o2;
return u1.getNombre().compareTo(u2.getNombre());
}

public boolean equals(Object o) {
return this == o;
}
}

import java.util.Comparator;

class EdadComparator implements Comparator {

public int compare(Object o1, Object o2) {
Usuario u1 = (Usuario) o1;
Usuario u2 = (Usuario) o2;
return u1.getEdad() - u2.getEdad();
}

public boolean equals(Object o) {
return this == o;
}
}

Ahora solo nos queda usarlos, nada más fácil

ArrayList lista = new ArrayList();
lista.add(new Usuario("uno", 11));
lista.add(new Usuario("dos", 2));
lista.add(new Usuario("tres", 3));
lista.add(new Usuario("cuatro", 44));
printList(lista);
System.out.println("\n Ahora ordenados por nombre...");
Collections.sort(lista, new NombreComparator());
//metodo que imprime la lista
printList(lista);
System.out.println("\n y ahora ordenados por edad...");
Collections.sort(lista, new EdadComparator());
//metodo que imprime la lista
printList(lista);

¿Y que hago con los arrays?.

Adivina adivinanza: java.util.Arrays

Código de los ejemplos.

Descargate el código con los ejemplos de los artículos de la siguiente
dirección:

http://www.javahispano.com/download/ejemplos/ordenar.zip

Anexo de Martín Pérez: Quería añadir un matiz al artículo de ordenación y en partícular a la ordenación de Strings. En el artículo no se ha tenido en cuenta que el método compareTo() para Strings realiza la ordenación basándose en los códigos ASCII. Por lo tanto la salida no será correcta ya que : No va a tratar bien los acentos ni letras como la ñ Va a ordenar mal los números Ej : 1,10,110,2,3,4,45,5,.... Las mayúsculas tienen código ASCII menor, por lo que saldrán antes que todas las entradas con minúsuculas, etc.. Por lo tanto si lo que quieres hacer es ordenar Strings yo te sugeriría algo como esto : Collator esCollator = Collator.getInstance(new Locale("es", "ES", "EURO")); // EURO es para estar al dia Arrays.sort(myArray,esCollator); Nota : Collator implementa la interfaz Comparator ¿ Ventaja frente a currarte tu propio compareTo() para ordenar Strings ? Si en vez de coger el Locale Español coges el de la máquina tu programa ordenará bien en cualquier lenguaje.

Alberto Molpeceres es ahora mismo desarrollador de aplicaciones en ámbito cliente/servidor para la empresa T-Systems - debis Systemhaus en Munich (Alemania). Cuando no está trabajando o "metiendo caña" al resto de los integrantes de javaHispano intenta pasear con su novia, buscar la desaparecida lógica del idioma alemán o intenta olvidar la pesadilla que es buscar piso en Munich. Para cualquier duda o tirón de orejas, e-mail a: al_ARROBA_javahispano.org

Diseño de software con patrones (parte 4)

Diseño de software con patrones (parte 4)

Como explicamos en capítulos anteriores, hay tres tipos fundamentales de patrones:

• patrones de creación.
  
• patrones estructurales.
  
• patrones de comportamiento.
  

En los artículos anteriores explicamos, a parte de algunos conceptos básicos e historia, algunos de los patrones de creación. En esta cuarta entrega sobre el diseño de software con patrones vamos a empezar con el siguiente tipo, los patrones estructurales, que se encargan de modelar las relaciones entre objetos para formar estructuras más o menos complejas.

Patrones estructurales

Como he dicho un par de líneas más arriba, los patrones estructurales se ocupan de la combinación de objetos para crear estructuras complejas. Esto no es del todo exacto, ya que hay patrones estructurales que se encargan de las relaciones entre clases (mayoritariamente el uso de la herencia), mientras que otros se encargan de los objetos, las instancias de las clases (normalmente composición).

Entre los patrones que tengo intención de mencionar, sin que sea una lista ya definida, pueden destacar el patrón adaptador (adapter pattern, GoF), el patrón fachada (facade pattern, GoF), el patrón proxy (proxy pattern, GoF) y el patrón puente (bridge pattern, GoF).

El patrón adaptador (Adapter pattern, GoF)

El patrón adaptador, como su propio nombre nos puede hacer ver, se usa para convertir el interface de una clase a la de otra, entendiendo en este caso interface como el conjunto de métodos que ofrece una clase para su manipulación por código, no la herramienta que usa el usuario final de nuestra aplicación. Lo que haremos será escribir métodos con nuestra interface deseada que deleguen el trabajo en los de la interface ya existente.

Las razones para querer hacer algo así pueden ser de muy distinta naturaleza, y pueden ir desde querer integrar una clase ya existente pero que no podemos modificar en una nueva jerarquía de clases, que por ejemplo implemente una nueva interfaz, podemos querer limitar el interface de una clase, hasta poder querer hacerlo simplemente porque la convención de nombres usada en la clase original, que tampoco podemos o queremos cambiar, no se ajusta a la nuestra. Esta última razón os puede parece un poco tonta, pero os aseguro que puede ser bastante frustrante recibir miles de errores de compilación por trabajar con métodos del estilo GetName en lugar de getName.

Esta adaptación la podemos realizar de dos formas:

• Por herencia.
  
• Por composición.
  

Adaptación por herencia

Si optamos por usar la herencia para adaptar una clase, haremos que la clase que implementa la nueva interface extienda de la original y añadiremos a esta los métodos que consideremos oportunos.

Supongamos que alguien un poco cazurro ha escrito la siguiente clase:

public class Usuario{

protected String nombre;
protected String password;
. . .

public Usuario (String nombre, String password){
. . .
}

public String GetNombre (){
return nombre;
}

public String GetPassword (){
return password;
}
. . .
}

Como nos hemos leido las convenciones de código de Java de nuestra empresa y estamos de acuerdo en que es bueno seguirlas, nos damos cuenta de que esas dos G de Getxxx nos dan muchos quebraderos de cabeza. El problema esta en que esa clase ya esta en sistemas productivos y por tanto no podemos hacer algo tan simple como cambiar esa letra. Es por eso que optamos por extender esa clase, de forma que el sistema siga trabajando correctamente con las clases antiguas, pero nosotros podamos evitar acordarnos de la santa madre de alguno cada vez que nos aparezcan veinte errores de compilación por algo tan tonto.

public class BuenUsuario extends Usuario{

public BuenUsuario (String nombre, String password){
super (nombre, password);
}

public String geNombre (){
return GetNombre();
}

public String getPassword (){
return GetPassword();
}
}

Además, el haberlo hecho así, aprovechándonos de las ventajas de la herencia, hace que los métodos de otras clases que usen la clase Usuario puedan seguir funcionando sin retocarlos.

Adaptación por composición

Pero ocurre que en algunos casos no podemos usar la herencia, ya sea porque queremos integrar esa clase en una jerarquía nueva y ya estemos heredando de otra clase, o ya sea por causa de modificadores de acceso como private o final que impidan que se hereden algunas características de la clase, o simplemente que no queramos que la nueva clase tenga el interface completo de la original. En ese caso tendremos que usar la composición, es decir, incluir la clase a adaptar como un atributo de la adaptadora.

Supongamos que no existe la clase java.util.Stack y que queremos crear una clase con estructura de pila para nuestros programas. Podemos, por qué no, implementar una lista enlazada nosotros mismos y crear nuestra propia pila, pero entonces deberiamos tener cuidado de muchas cosas, como por ejemplo de los accesos concurrentes. Es por eso que viendo que la clase java.util.Vector ya tiene implementado todo eso, y de forma bastante correcta, se nos ocurre que un vector sería una buena pila si no tuviera tantos métodos que podriamos usar para saltarnos el concepto de pila. Lo siguiente que se nos debe ocurrir es crear una clase adaptadora que forme una pila a partir de un vector:

public class Pila{

private Vector valores;

public Pila(){
valores = new Vector();
}

public void push (Object o){
valores.add (o);
}

public Object pop (){
Object o = valores.lastElement();
valores.remove (o);
return o;
}
}

Por supuesto habría que tener más cuidado al sacar elementos (método pop), pero en fin, el objetivo de este código no es crear una clase de utilidad real.

El patrón fachada (Facade pattern, GoF)

El patrón fachada trata de simplificar la interface entre dos sistemas o componentes de software ocultando un sistema complejo detrás de una clase que hace las veces de pantalla o fachada.

La idea principal es la de ocultar todo lo posible la complejidad de un sistema, el conjunto de clases o componentes que lo forman, de forma que solo se ofrezca un (o unos pocos) punto de entrada al sistema tapado por la fachada.

Una ventaja más de usar una clase fachada para comunicar las dos partes o componentes, es la de aislar los posibles cambios que se puedan producir en alguna de las partes. Si cambias, por porner un ejemplo, el medio de comunicación o de almacenamiento de una de las partes, la otra, que por ejemplo hace la presentación, no tiene porque enterarse, y viceversa.

Este patrón es bastante fácil de explicar en palabras (aunque no estoy seguro de haberlo conseguido), pero no tanto de poner un ejemplo, al menos no uno completo. Intentaré hacerlo basándome en un caso personal.

En el trabajo teníamos un sistema de varias capas, un servidor DMS (Document Managment System), un proxy para distintos DMS escrito en C/C++ y una aplicación web desarrollada con servlets (y motores de plantillas) como interface al usuario. El aspecto más peliagudo era la comunicación entre el proxy para DMS y nuestra aplicación Java, que se producía por medio de sockets TCP/IP y mensajes XML. Podeis imaginaros que entre las clases propias de la comunicación (sockets, streams, handlers de la comunicación, etc), las clases de proceso del XML (parsers, codificadores, conversores xml a PDF, etc) y las clases de nuestro sistema (documentos, listas de resultados, etc) resultaba un sistema bastante complejo, complejidad que no era necesario que la conociera la aplicación web.

En ese escenario creamos una clase fachada que ocultaba la complejidad de la comunicación de la siguiente forma

public class XArCFacade{

. . .

public Document getDocument (String id){
. . .
}

. . .

public HitList search (String request){
. . .
}

. . .
}

Obviamente esta clase esta reducida en cuanto al número de métodos respecto a la original, pero sigue la misma idea. Como veis, nuestra aplicación no tiene porque saber ni como ni de donde se consigue la información, nuestra aplicación web solo tenía que preocuparse de buscar la mejor manera posible de presentar dicha información, que tampoco fue fácil.

Como hemos dicho antes, esta arquitectura aisla los posibles cambios en una de la partes. En nuestro caso, se cambió la presenteción de JSP a Servlets con plantillas, y la parte de comunicación se cambió de usar una libreria escrita en C/C++ por medio de JNI a usar una pure java, de forma independiente, sin que la otra se viera afectada.

¿JDK 1.4?

Entre versiones betas, RC y demás, el lanzamiento del JDK1.4 de Sun esta siendo un poco caótico, pero al fin parece que hoy (y casi a traición) ha aparecido la versión final del JDK1.4.


Si son verdad las comparativas de rendimiento que publica Sun no tendremos mucho de que quejarnos, aunque algo siempre habrá.


Si aún no lo habeis leido, podeis leer un articulo sobre algunas de las novedades que presenta en esta misma web. Esta basado en las primeras betas, pero es aplicable al 99%.

Charlas sobre Java

El 12 de Febrero comenzaron a impartirse unas charlas online sobre Java a traves de la red de IRC Hispano.

Los temas son diversos y las charlas se extenderan a lo largo de Febrero y Marzo.

Las charlas abarcan desde los temas más sencillos hasta los más complejos.

Para obtener más información sobre como conectarse a ese servidor de irc visitar la web del IRC-Hispano.


Para obtener más información sobre las charlas podéis ir
aquí.


En el canal #java, por supuesto.

Presentado Tomcat 4.0.2

Ya se han acabado las versiones beta de Tomcat 4.0.2, así que ya podeis descargar por fin la version 4.0.2 final.


Esta nueva versión no presenta grandes novedades en cuanto a funcionalidad, no era su función, pero si hay corregido una gran cantidad de pequeños errores, alrededor de 100, que harán de Tomcat una aún mejor herramienta.