Ordenamiento mezcla natural: cadenas binarias

1. Algoritmo original.
2. Algoritmo genérico.
3. Ordenando cadenas binarias.
4. Ordenando cadenas.
5. Ordenando enteros grandes.
6. Ordenando objetos.

Ahora veremos cómo usar el algoritmo genérico de mezcla natural con cadenas binarias. Tenemos que implementar las dos interfaces que permiten aislar los detalles de lectura y escritura de datos.

  public static class Lector implements MezclaNaturalGenerico.Lector<String> 
  public static class Escritor implements MezclaNaturalGenerico.Escritor<String>

La implementación de estas dos interfaces es bastante directa. Por ejemplo, el método next() ecapsula readUTF() y el método hasNext() encapsula dis.available() != 0. También comentaba que el algoritmo se inicializa con fábricas para generar Lectores y Escritores. Eso lo podemos ver en esta línea:

  new MezclaNaturalGenerico<>(Lector::new, Escritor::new);

Vale la pena explicar qué está pasando aquí. La forma extendida sería implementar la interface que está esperando el constructor.

  static class FabricaLectores implements
      Function<File, MezclaNaturalGenerico.Lector<String>> {
    @Override
    public MezclaNaturalGenerico.Lector apply(Object o) {
      return new Lector(o);
    }
  }

Y la usamos así:

  new MezclaNaturalGenerico<>(new FabricaLectores(), ...);

La parte principal de FabricaLectores es new Lector(o), lo demás sólo causa ruido. Dado que Function es una interface funcional, es decir, que sólo tiene un método abstracto, la podemos reemplazar con una lambda.

  new MezclaNaturalGenerico<>(o -> new Lector(o), ...)

Pero como la única instrucción de la lambda es un new, la podemos reemplazar por una referencia al constructor. Y así es cómo llegamos al resultado final.

new MezclaNaturalGenerico<>(Lector::new, ...);

Al ejecutar este ejemplo deben obtener lo siguiente:

$ javac MezclaNaturalGenerico.java MezclaNaturalEjemplo1.java
$ java MezclaNaturalEjemplo1
Error en el ordenamiento
Fusion 1
...
EL ARCHIVO ESTA ORDENADO
1) AARON
2) ABBEY
3) ABBIE
4) ABBY
5) ABDUL
...

MezclaNaturalEjemplo1.java

Ordenamiento mezcla natural: algoritmo genérico

1. Algoritmo original.
2. Algoritmo genérico.
3. Ordenando cadenas binarias.
4. Ordenando cadenas.
5. Ordenando enteros grandes.
6. Ordenando objetos.

Esta serie de posts está inspirado en uno de nuestros posts más populares: Ordenamiento externo: Mezcla Natural. En ese post recibimos algunas preguntas de cómo reusar el código para ordenar otro tipo de datos. El código original sólo maneja cadenas en formato binario. Por lo que decidí actualizarlo para manejar cualquier tipo de dato. En este post hablaré de los cambios necesarios y en los siguientes posts mostraré ejemplos de cómo usarlo. El algoritmo base no cambió, lo que tuve que aislar es el tipo de dato y la forma en la que lo leemos y escribimos.

Tipo de dato.

El tipo de dato lo podemos ver por las menciones del tipo String a lo largo del código original. Tenemos que reemplazar String con un tipo genérico. La única operación que necesitamos del tipo de dato es que lo podamos comparar. Eso lo podemos observar cuando invocamos el método compareTo. Esto nos lleva a cambiar la definición de la clase de:

public class MezclaNatural

a:

public class MezclaNaturalGenerico<T extends Comparable<T>>

Noten que exigimos que el tipo de datos genérico implemente la interface Comparable, la cual declara el método compareTo. Ahora podemos reemplazar String con el parámetro genérico. Por ejemplo:

    String actual = null;
    String anterior = null;

con:

    T actual = null;
    T anterior = null;

Lectura de datos.

Para leer datos estábamos usando los métodos available() y readUTF() de un DataInputStream. Además invocamos el método close() de este Stream cuando terminamos de usarlo. Vamos a reemplazar este DataInputStream con una interface que provea una funcionalidad similar. En lugar de crear una interface completamente nueva, decidí crear una interface que extiende dos interfaces de las librerías de Java:

  public interface Lector<T> extends Iterator<T>, Closeable { }

Un usuario tiene que implementar esta interface para que nuestro algoritmo no se preocupe de cómo leer datos. Observen cómo volvemos a usar el parámetro genérico en esta definición. Los métodos hasNext() y next() de la interface Iterator reemplazarán a los métodos available() y readUTF().

Un pequeño detalle de implementación es que nuestro algoritmo tiene que instanciar varios Lector(es) a lo largo de su ejecución. Por lo que un usuario debe proporcionar una fábrica de Lectores. Esto lo podemos ver en el siguiente parámetro de nuestro constructor:

    Function<File, Lector<T>> generaLector

La fábrica (Function) tomará como entrada un archivo abstracto e instanciará un Lector.

Escritura de datos.

Este caso es paralelo a la lectura de datos. Para escribir usamos el método writeUTF() de un DataOutputStream. Esto la abstraemos con la interface:

  public interface Escritor<T> extends Consumer<T>, Closeable { }

El método accept() de Consumer reemplazará al método writeUTF(). Y también necesitamos una fábrica de Escritores.

    Function<File, Escritor<T>> generaEscritor

Esto es todo por este post. Si lo comparan con el código original, verán que la lógica es la misma y la mayoría fueron reemplazos directos (por ejemplo: readUTF con next) En el siguiente post veremos cómo usarlo.

MezclaNaturalGenerico.java