Colecciones, orden e iteradores

La semana pasada escribimos clases genéricas: una Box<T>, un stack acotado BoundedStack<E>, métodos como <T extends Comparable<T>> T max(List<T> list). Vimos que el type parameter deja que el compilador revise lo que entra y lo que sale de una colección. Esta semana usamos esa idea a escala: el Collections Framework de Java es un conjunto de interfaces y clases genéricas que resuelven, ya probadas y optimizadas, casi todas las formas de guardar muchos objetos: en orden, sin repetidos, por clave.

El capítulo tiene dos partes. En la primera recorremos las interfaces Collection, List, Set y Map, sus implementaciones principales y el costo de cada operación, porque elegir bien la colección es la mitad del trabajo. En la segunda vemos cómo se ordenan los objetos (Comparable y Comparator) y cómo se recorren (iteradores), y terminamos haciendo iterable una colección propia.

Lectura. Este capítulo acompaña a Eck, Introduction to Programming Using Java (versión 9): las subsecciones 10.1.4 The Java Collection Framework, 10.1.5 Iterators and for-each Loops y 10.1.6 Equality and Comparison; la sección 10.2 Lists and Sets; la 10.3 Maps; y las subsecciones 10.4.1 a 10.4.3 de la 10.4. En la 10.4.3 Eck escribe el comparador con una lambda: lean la idea; aquí lo escribimos como una clase y la sintaxis de lambdas llega la próxima semana. Para la clase interna del iterador, la subsección 5.8.2 Inner Classes. El código del capítulo está en code/week-11 y se prueba con make test dentro del contenedor del curso.

Ruta de lectura.

• Antes de clase (obligatorio, 15–20 min): La jerarquía de colecciones y List: orden y posiciones.
• En clase: en la sesión A, Set: sin repetidos, Map: de una clave a un valor con Ejemplo resuelto: contar palabras y Cómo encuentra un HashMap una clave, Colecciones inmutables y vistas y Elegir la colección; en la sesión B, Orden natural: Comparable, Otros órdenes: Comparator e Iteradores.
• Después de clase: Ejemplo resuelto: un índice de palabras, Empates en un TreeSet, Una colección propia que se puede recorrer, el Resumen y los Ejercicios. Para ampliar, las secciones de Eck de la nota Lectura.

La jerarquía de colecciones

El Collections Framework está organizado en interfaces, que dicen qué se puede hacer, e implementaciones, clases que dicen cómo se hace. Es la idea de la semana 7 aplicada a la biblioteca estándar.

• Collection<E> es un grupo de elementos. Define lo que tienen todas: add, remove, contains, size, isEmpty, clear, addAll. Y como extiende Iterable<E>, toda colección se puede recorrer con for-each.
• List<E> agrega posiciones: los elementos tienen un orden y un índice (get(i), set(i, x), add(i, x)), y puede haber repetidos.
• Set<E> es un conjunto: no admite repetidos. No agrega métodos a Collection; lo que cambia es el contrato de add, que no agrega un elemento si ya hay uno igual.
• Queue<E> es una cola: los elementos esperan su turno y se sacan por un extremo (offer, poll, peek).
• Map<K, V> asocia claves con valores: cada clave aparece una sola vez y tiene un valor. No es una Collection, porque no guarda elementos sueltos sino pares.

Idea clave. Se programa contra la interfaz: el tipo de la variable es la interfaz y la clase concreta aparece solo en el new.

List<Song> songs = new ArrayList<>();
Map<String, Integer> counts = new TreeMap<>();

El resto del código solo usa métodos de List o de Map. Si mañana conviene otra implementación, se cambia una línea. Lo mismo vale para los parámetros y los tipos de retorno: un método que recibe List<Song> acepta cualquier lista; uno que recibe ArrayList<Song> obliga a quien lo llama a usar esa clase.

Los ejemplos del capítulo usan canciones. Song.java es un record (semana 3) con los mismos componentes que el de la semana 4: título, artista y duración en segundos (seconds):

public record Song(String title, String artist, int seconds) implements Comparable<Song> {
    // compareTo, más abajo
}

Al ser un record, equals y hashCode ya comparan los tres campos (semana 5). Eso va a importar mucho en Set y Map. Songs.java arma una lista de ejemplo con seis canciones inventadas de tres artistas.

List: orden y posiciones

Ya conocen ArrayList desde la semana 4. Hay otra implementación de List en la biblioteca, LinkedList, y la diferencia está en cómo guardan los elementos.

• ArrayList guarda las referencias en un arreglo interno más grande de lo necesario (la capacidad). get(i) calcula dónde está la casilla y va directo. Agregar al final casi siempre es inmediato; cuando el arreglo se llena, ArrayList crea otro más grande y copia todo, pero eso pasa pocas veces. Insertar o borrar al inicio o en el medio obliga a correr todos los elementos que siguen.
• LinkedList guarda cada elemento en un nodo con referencias al anterior y al siguiente. Insertar o borrar en un extremo es cambiar un par de flechas. Pero get(i) tiene que recorrer nodo por nodo desde un extremo.

El costo se resume así, con n el número de elementos:

En Java. En la práctica, ArrayList gana casi siempre, incluso en casos en que la tabla parece favorecer a LinkedList: el arreglo está contiguo en memoria y el procesador lo recorre muy rápido, mientras que los nodos están dispersos por el heap y cada uno ocupa más memoria. Si lo que necesitan es una cola (sacar por un extremo y meter por el otro), la clase adecuada es ArrayDeque, no LinkedList. La guía de dev.java Choosing the Right Implementation Between ArrayList and LinkedList lo discute con detalle; está enlazada en la guía del laboratorio.

Fíjense en la última fila: contains recorre la lista entera en las dos implementaciones, porque una lista no sabe dónde está un elemento sin compararlo con todos. Si el programa pregunta mucho “¿está este elemento?”, la respuesta no es una lista sino un conjunto.

Set: sin repetidos

Un Set no guarda dos elementos iguales. Qué significa iguales depende de la implementación. HashSet y LinkedHashSet usan una tabla hash: dos elementos son iguales según equals, y hashCode decide dónde buscarlos. Por eso el contrato de la semana 5 (si a.equals(b), entonces a.hashCode() == b.hashCode()) no es un detalle: un HashSet de objetos que lo violan deja entrar repetidos. TreeSet, en cambio, no llama a equals: dos elementos son iguales si al compararlos el resultado es 0, como se ve en la segunda parte del capítulo.

Hay tres implementaciones de uso diario, y la diferencia es el orden en que se recorren. SetDemo.java mete las mismas ciudades, con repetidos, en las tres:

String[] visits = {"Lima", "Cusco", "Arequipa", "Lima", "Puno", "Cusco", "Ica"};

Set<String> hash = new HashSet<>();
Set<String> linked = new LinkedHashSet<>();
Set<String> tree = new TreeSet<>();
for (String city : visits) {
    hash.add(city);
    linked.add(city);
    tree.add(city);
}

$ java -cp build SetDemo
visitas:       7
HashSet:       [Puno, Lima, Ica, Arequipa, Cusco]
LinkedHashSet: [Lima, Cusco, Arequipa, Puno, Ica]
TreeSet:       [Arequipa, Cusco, Ica, Lima, Puno]
¿add("Lima") otra vez? false, size = 5
¿contains("Puno")? true

• HashSet guarda los elementos en una tabla hash. add, remove y contains cuestan un tiempo constante en promedio, sin importar cuántos elementos haya. A cambio, el orden del recorrido no está especificado: depende de los hashCode y del tamaño de la tabla, y puede cambiar si se agregan elementos. No hay que escribir código que dependa de él.
• LinkedHashSet es un HashSet que además recuerda el orden de inserción. Casi igual de rápido.
• TreeSet mantiene los elementos ordenados (en un árbol de búsqueda balanceado). Sus operaciones cuestan un tiempo proporcional a log n: más que un HashSet, pero mucho menos que una lista. Para ordenar necesita comparar, y eso lo vemos en la segunda parte del capítulo.

add devuelve false cuando el elemento ya estaba: el conjunto no cambió.

Map: de una clave a un valor

Un Map<K, V> responde preguntas del tipo “dado esto, ¿qué le corresponde?”: de un código a un alumno, de una palabra a su número de apariciones, de un asiento a quien lo reservó. Las operaciones principales:

Las implementaciones son paralelas a las de Set (de hecho, HashSet está implementado con un HashMap por dentro): HashMap (tiempo constante, sin orden), LinkedHashMap (orden de inserción) y TreeMap (claves ordenadas).

Ejemplo resuelto: contar palabras

WordCount.java cuenta cuántas veces aparece cada palabra de un texto. La idea: para cada palabra, leer cuántas llevamos (0 si es la primera vez) y guardar una más.

public static Map<String, Integer> count(String text) {
    Map<String, Integer> counts = new TreeMap<>();
    for (String word : text.toLowerCase().split("[^\\p{L}]+")) {
        if (word.isEmpty()) {
            continue;
        }
        int before = counts.getOrDefault(word, 0);
        counts.put(word, before + 1);
    }
    return counts;
}

split("[^\\p{L}]+") corta el texto en cada tramo de caracteres que no son letras (espacios, comas, puntos), y \p{L} incluye las letras con tilde. Elegimos TreeMap para que las palabras salgan en orden alfabético: con un HashMap, el resultado sería el mismo pero el orden al imprimir no estaría especificado. Para recorrer un mapa se usa entrySet(), que da cada par como un Map.Entry<K, V> con getKey() y getValue() (WordDemo.java):

String text = "La garúa cae en Lima. En Lima la garúa no moja, pero la garúa cae.";
Map<String, Integer> counts = WordCount.count(text);
IO.println(counts);
IO.println("garúa: " + counts.get("garúa") + ", sol: " + counts.get("sol")
        + ", sol con getOrDefault: " + counts.getOrDefault("sol", 0));

for (Map.Entry<String, Integer> e : counts.entrySet()) {
    if (e.getValue() >= 2) {
        IO.println("  " + e.getKey() + " x" + e.getValue());
    }
}

$ java -cp build WordDemo
{cae=2, en=2, garúa=3, la=3, lima=2, moja=1, no=1, pero=1}
garúa: 3, sol: null, sol con getOrDefault: 0
  cae x2
  en x2
  garúa x3
  la x3
  lima x2
...

get de una clave que no está devuelve null. Si el resultado se guarda en un int, el unboxing de null lanza NullPointerException (semana 10); por eso el conteo usa getOrDefault.

Ejemplo resuelto: un índice de palabras

Ahora queremos, para cada palabra, en qué líneas aparece, sin repetir una línea aunque la palabra salga dos veces en ella y con las líneas en orden. Es un mapa cuyo valor es un conjunto: Map<String, Set<Integer>> (WordIndex.java):

public static Map<String, Set<Integer>> index(List<String> lines) {
    Map<String, Set<Integer>> index = new TreeMap<>();
    for (int i = 0; i < lines.size(); i++) {
        for (String word : lines.get(i).toLowerCase().split("[^\\p{L}]+")) {
            if (word.isEmpty()) {
                continue;
            }
            Set<Integer> where = index.get(word);
            if (where == null) {                // primera vez: se crea su conjunto
                where = new TreeSet<>();
                index.put(word, where);
            }
            where.add(i + 1);
        }
    }
    return index;
}

El patrón “buscar; si no está, crear y guardar; después usar” aparece cada vez que el valor de un mapa es una colección. Noten que where.add(i + 1) modifica el conjunto que ya está dentro del mapa: el mapa guarda una referencia a él, no una copia, así que no hace falta volver a hacer put.

$ java -cp build WordDemo
...
río -> [1, 2], puente -> [1, 3], el -> [1, 2]
10 palabras distintas: [al, baja, de, el, mar, piedra, puente, río, un, y]

La palabra el aparece dos veces en la línea 1 (el puente y el río), pero el TreeSet guarda el 1 una sola vez.

En Java. La semana que viene veremos Map.merge y Map.computeIfAbsent, que hacen cada uno de estos dos patrones en una sola línea. Reciben una lambda, por eso esperamos.

Cómo encuentra un HashMap una clave

Un HashMap es un arreglo de buckets, casillas donde se guardan los pares. Para guardar un par, toma el hashCode() de la clave, lo mezcla y reduce el resultado a un índice del arreglo; con una tabla de 16 buckets, el índice son los últimos 4 bits del hash ya mezclado. La mezcla, en OpenJDK, es h ^ (h >>> 16): los 16 bits altos se combinan con los bajos para que también influyan en el bucket. El par se guarda en ese bucket. Para buscar una clave, calcula el mismo índice, va a ese bucket y, entre lo que haya ahí, busca un par cuya clave sea igual según equals. Por eso un get no recorre todo el mapa: va directo a un bucket.

De ahí sale un error difícil de encontrar.

Error común. Usar como clave un objeto mutable y modificarlo después de guardarlo. MutableKey.java es un código de asiento con fila y número, con equals y hashCode correctos que usan los dos campos, y un método moveTo que los cambia (MutableKeyDemo.java):

Map<MutableKey, String> seats = new HashMap<>();
MutableKey seat = new MutableKey('A', 7);
seats.put(seat, "alice");
seats.put(new MutableKey('B', 3), "bob");
IO.println("get(A7) = " + seats.get(new MutableKey('A', 7)));

seat.moveTo('C', 2);                        // se modifica la clave ya guardada
IO.println("mapa = " + seats);
IO.println("get(C2) = " + seats.get(new MutableKey('C', 2)));
IO.println("get(A7) = " + seats.get(new MutableKey('A', 7)));
IO.println("containsKey(seat) = " + seats.containsKey(seat) + ", size = " + seats.size());

$ java -cp build MutableKeyDemo
get(A7) = alice
mapa = {B3=bob, C2=alice}
get(C2) = null
get(A7) = null
containsKey(seat) = false, size = 2

El mapa imprime C2=alice, pero ni C2 ni A7 la encuentran, y ni siquiera el mismo objeto seat. La entrada sigue ahí, ocupando memoria, inalcanzable.

La animación muestra los números reales: Objects.hash('A', 7) es 2983, que cae en el bucket 7; Objects.hash('C', 2) es 3040, que cae en el 0. (Estos hash codes son menores que 65 536, así que sus 16 bits altos son cero y la mezcla no los cambia.) La regla que se deduce: las claves de un mapa (y los elementos de un conjunto) deben ser inmutables, o al menos no cambiar mientras estén adentro. String, los wrappers como Integer y los records con campos inmutables son buenas claves. Es otra razón para preferir objetos inmutables (semana 3).

Colecciones inmutables y vistas

List.of, Set.of, Map.of

Para crear una colección pequeña que no va a cambiar, las interfaces tienen static factory methods, métodos estáticos que fabrican la colección:

List<String> notes = List.of("do", "re", "mi");
Set<Integer> primes = Set.of(2, 3, 5, 7);
Map<String, Integer> stock = Map.of("pan", 40, "leche", 12);

Las colecciones que devuelven son inmutables: add, set, put, remove lanzan UnsupportedOperationException.

jshell> List<Integer> nums = List.of(3, 1, 2)
nums ==> [3, 1, 2]

jshell> nums.set(0, 9)
|  Exception java.lang.UnsupportedOperationException
|        at ImmutableCollections.uoe (ImmutableCollections.java:159)
|        at ImmutableCollections$AbstractImmutableList.set (ImmutableCollections.java:281)
|        at (#5:1)

Tampoco admiten null como elemento, y Set.of y Map.of rechazan los repetidos al crearse. Son las colecciones ideales para constantes y para datos de prueba.

Devolver una colección sin romper el encapsulamiento

En la semana 4, una Playlist encapsulaba su ArrayList<Song>. ¿Qué devuelve un getter de la lista? Si devuelve el campo tal cual, quien lo recibe puede hacer add, remove o clear sobre la lista interna y saltarse todas las reglas de la clase. En Playlist.java la regla es que no haya canciones repetidas:

public class Playlist implements Iterable<Song> {

    private final List<Song> songs = new ArrayList<>();

    /** Agrega la canción si no estaba; devuelve si se agregó. */
    public boolean add(Song song) {
        if (songs.contains(song)) {
            return false;
        }
        return songs.add(song);
    }

    /** Una vista de solo lectura: refleja los cambios, pero no permite hacerlos. */
    public List<Song> songs() {
        return Collections.unmodifiableList(songs);
    }
    // ...
}

Collections.unmodifiableList(songs) no copia nada: devuelve una vista, un objeto que envuelve a la lista original, deja leerla y lanza UnsupportedOperationException ante cualquier intento de modificarla. Como es una vista, ve los cambios que la Playlist haga después. Si lo que se quiere es una foto fija, List.copyOf(lista) hace una copia inmutable (ViewDemo.java):

Playlist playlist = new Playlist();
playlist.add(new Song("Arena", "Duna", 185));
List<Song> view = playlist.songs();
List<Song> copy = List.copyOf(view);
try {
    view.add(new Song("Arena", "Duna", 185));      // rompería el invariante
} catch (UnsupportedOperationException e) {
    IO.println("La vista no admite add: " + e.getClass().getSimpleName());
}

playlist.add(new Song("Brisa", "Duna", 210));
IO.println("vista: " + view.size() + " canciones, copia: " + copy.size());

$ java -cp build ViewDemo
List.of no admite add: UnsupportedOperationException
La vista no admite add: UnsupportedOperationException
vista: 2 canciones, copia: 1
  Arena
  Brisa

Error común. Creer que una vista no modificable protege también a los elementos. Protege la lista: nadie puede agregar ni quitar. Pero si los elementos son mutables, quien recibe la vista puede modificar cada uno. Con Song, que es un record inmutable, el problema no existe; con una clase mutable, sí.

Elegir la colección

La pregunta para elegir no es “¿cuál me gusta?”, sino “¿qué operaciones va a hacer el programa y cuántas veces?”.

En el laboratorio de esta semana justifican con esta tabla la elección para cinco problemas cortos y miden la diferencia entre contains en una lista y en un conjunto.

Orden natural: Comparable

Para ordenar una lista o guardar elementos en un TreeSet, Java necesita saber, dados dos objetos, cuál va primero. Los números y los String lo saben de fábrica. Una clase propia lo dice implementando Comparable<T>, la interfaz que conocimos en la semana 7, con un solo método:

int compareTo(T other);

El resultado se lee por su signo: negativo si this va antes que other, cero si van en el mismo lugar, positivo si va después. El valor exacto no importa. El orden que define compareTo se llama orden natural de la clase. El de String es el alfabético (más exactamente, por código de cada carácter); el de Integer, el numérico.

En Song.java el orden natural es por título y, si dos títulos empatan, por artista y luego por duración:

@Override
public int compareTo(Song other) {
    int byTitle = title.compareTo(other.title);
    if (byTitle != 0) {
        return byTitle;
    }
    int byArtist = artist.compareTo(other.artist);
    if (byArtist != 0) {
        return byArtist;
    }
    return Integer.compare(seconds, other.seconds);
}

Con eso, Collections.sort(songs) ordena la lista y un TreeSet<Song> la mantiene ordenada.

El contrato de compareTo

Ordenar funciona solo si compareTo es coherente. La documentación de Comparable pide, en resumen:

1. Antisimetría: el signo de a.compareTo(b) es el contrario del de b.compareTo(a). Si a va antes que b, b va después que a.
2. Transitividad: si a va antes que b y b antes que c, entonces a va antes que c.
3. Empates coherentes: si a.compareTo(b) == 0, entonces a y b se comparan igual con cualquier tercer objeto.

Y recomienda con fuerza una cuarta: que sea consistente con equals, es decir, que a.compareTo(b) == 0 exactamente cuando a.equals(b). Nuestro Song lo cumple porque compara los mismos tres campos que usa el equals del record. Ya veremos qué pasa cuando no se cumple.

Error común. Comparar restando:

return this.price - other.price;            // MAL

Parece correcto, porque el signo de la resta es el que pide el contrato. Pero si los valores son grandes, la resta produce un overflow (semana 1) y el signo se invierte. OverflowDemo.java lo muestra con un comparador que resta, SubtractionOrder.java:

int a = -2_000_000_000;
int b = 2_000_000_000;
IO.println("a - b = " + (a - b) + "   Integer.compare(a, b) = " + Integer.compare(a, b));

List<Integer> amounts = new ArrayList<>(List.of(b, a, 0));
amounts.sort(new SubtractionOrder());
IO.println("con resta:           " + amounts);
amounts.sort(null);                         // null = orden natural de Integer
IO.println("con Integer.compare: " + amounts);

$ java -cp build OverflowDemo
a - b = 294967296   Integer.compare(a, b) = -1
con resta:           [2000000000, -2000000000, 0]
con Integer.compare: [-2000000000, 0, 2000000000]

−2 000 000 000 menos 2 000 000 000 da −4 000 000 000, que no cabe en un int y da la vuelta a un número positivo: el comparador dice que a va después de b. Se usa siempre Integer.compare(x, y) (o Long.compare, Double.compare), que no resta.

Error común. Meter en un TreeSet objetos que no son Comparable, sin darle un comparador. Compila (el tipo TreeSet<E> no exige que E sea comparable), pero falla al primer add:

jshell> record Pen(String color) {}
jshell> var set = new java.util.TreeSet<Pen>()
jshell> set.add(new Pen("azul"))
|  Exception java.lang.ClassCastException: class REPL.$JShell$2$Pen cannot be cast to class java.lang.Comparable (...)
|        at TreeMap.compare (TreeMap.java:1605)
...

Otros órdenes: Comparator

Una clase tiene un orden natural, pero un programa suele necesitar varios: la misma lista de canciones por título, por duración, por artista. Para eso está Comparator<T>, una interfaz con el método

int compare(T a, T b);

con el mismo significado del signo que compareTo. La diferencia es que el comparador es otro objeto, separado de la clase que se ordena: se pueden escribir todos los que hagan falta, sin tocar Song. Por ahora los escribimos como clases (ByDuration.java):

public class ByDuration implements Comparator<Song> {

    @Override
    public int compare(Song a, Song b) {
        return Integer.compare(a.seconds(), b.seconds());
    }
}

Un orden con varios criterios compara por el primero y, solo si empata, pasa al siguiente (ByArtistThenTitle.java):

public class ByArtistThenTitle implements Comparator<Song> {

    @Override
    public int compare(Song a, Song b) {
        int byArtist = a.artist().compareTo(b.artist());
        if (byArtist != 0) {
            return byArtist;
        }
        return a.title().compareTo(b.title());
    }
}

El comparador se pasa a quien ordena: Collections.sort(lista, comparador), lista.sort(comparador), new TreeSet<>(comparador), new TreeMap<>(comparador), Collections.max(colección, comparador). SortDemo.java ordena la misma lista de tres maneras:

List<Song> songs = Songs.sample();

Collections.sort(songs);                    // orden natural: compareTo
print("Por título (Comparable):", songs);

songs.sort(new ByDuration());               // un orden alternativo
print("Por duración (ByDuration):", songs);

songs.sort(new ByArtistThenTitle());        // dos criterios
print("Por artista y título:", songs);

$ java -cp build SortDemo
Por título (Comparable):
  185  Duna - Arena
  210  Duna - Brisa
  190  Los Andinos - Cumbre
  220  Costa Verde - Garúa
  190  Costa Verde - Malecón
  245  Los Andinos - Puente de piedra
Por duración (ByDuration):
  185  Duna - Arena
  190  Los Andinos - Cumbre
  190  Costa Verde - Malecón
  210  Duna - Brisa
  220  Costa Verde - Garúa
  245  Los Andinos - Puente de piedra
Por artista y título:
  220  Costa Verde - Garúa
  190  Costa Verde - Malecón
  185  Duna - Arena
  210  Duna - Brisa
  190  Los Andinos - Cumbre
  245  Los Andinos - Puente de piedra
...

Cumbre y Malecón duran 190 segundos: para ByDuration empatan. ¿Por qué salió Cumbre primero? Porque la lista venía ordenada por título, y el ordenamiento de List.sort es estable: dos elementos que empatan quedan en el orden relativo en que estaban. Esa garantía permite ordenar en dos pasadas (primero por el criterio secundario, después por el principal), aunque es más claro escribir un comparador con los dos criterios.

Idea clave. Comparable es el orden de la clase, uno solo, escrito dentro de ella. Comparator es un orden externo, un objeto aparte; puede haber muchos, y se pueden escribir para clases que no son nuestras. Un comparador es un ejemplo de lo que en la semana 14 llamaremos el patrón Strategy: un algoritmo (cómo comparar) encapsulado en un objeto que se pasa a otro (el que ordena).

Empates en un TreeSet

Para un TreeSet, dos elementos son “el mismo” cuando el comparador da 0. No usa equals. Al final de SortDemo:

TreeSet<Song> byDuration = new TreeSet<>(new ByDuration());
byDuration.addAll(songs);
IO.println("Lista: " + songs.size() + " canciones; TreeSet(ByDuration): "
        + byDuration.size());

Lista: 6 canciones; TreeSet(ByDuration): 5

Malecón y Cumbre son canciones distintas (equals da false), pero para el comparador empatan, y el TreeSet se queda con la primera que llegó. Este es el problema de un orden inconsistente con equals: el conjunto deja de comportarse como un Set según equals. La solución es desempatar con más criterios hasta que el comparador dé 0 solo para elementos iguales, como hace el compareTo de Song.

Iteradores

Qué hace un for-each

Todo for-each sobre una colección usa un iterador (iterator), un objeto que recorre la colección de a un elemento. La interfaz Iterator<E> tiene tres métodos:

• hasNext(): si quedan elementos.
• next(): devuelve el siguiente y avanza.
• remove(): borra de la colección el último elemento que devolvió next(). Es opcional: las colecciones inmutables lanzan UnsupportedOperationException.

Y la interfaz Iterable<E> tiene un método, iterator(), que fabrica un iterador nuevo. El compilador traduce

for (Song s : songs) {
    // cuerpo
}

como

Iterator<Song> it = songs.iterator();
while (it.hasNext()) {
    Song s = it.next();
    // cuerpo
}

Así que for-each funciona con cualquier objeto que implemente Iterable (y con los arreglos, que el compilador trata aparte). Conviene imaginar el iterador como un cursor entre dos elementos: al empezar está antes del primero; next() salta un elemento y lo devuelve.

Borrar durante un recorrido

Supongamos que queremos quitar de la lista las canciones de menos de 200 segundos. Lo primero que se le ocurre a cualquiera (RemoveDemo.java):

for (Song s : songs) {
    if (s.seconds() < 200) {
        songs.remove(s);                    // modifica la lista por fuera del iterador
    }
}

$ java -cp build RemoveDemo
for-each + remove: java.util.ConcurrentModificationException
...

El for-each tiene un iterador escondido. songs.remove(s) cambia la lista sin que el iterador se entere, y en el siguiente next() el iterador detecta que la lista fue modificada por otro camino y lanza ConcurrentModificationException. (El nombre confunde: no hace falta ningún hilo; basta con modificar la colección mientras se la recorre.) El iterador falla a propósito y de inmediato, en lugar de seguir con un cursor que ya no sabe dónde está.

La forma correcta es usar el iterador explícitamente y borrar a través de él, con it.remove():

Iterator<Song> it = songs.iterator();
while (it.hasNext()) {
    Song s = it.next();
    if (s.seconds() < 200) {
        it.remove();                        // borra el último elemento que devolvió next()
    }
}

Quedan 3:
  220  Garúa
  245  Puente de piedra
  210  Brisa

En Java. La semana que viene veremos songs.removeIf(...), que hace exactamente este bucle en una línea, con una lambda que dice qué borrar.

Una colección propia que se puede recorrer

Para que una clase propia funcione en un for-each, basta con implementar Iterable<E>. Si la clase guarda sus elementos en una colección de la biblioteca, puede delegar en ella. Es lo que hace Playlist:

@Override
public Iterator<Song> iterator() {
    return songs().iterator();
}

Devolvemos el iterador de la vista no modificable, y no el de la lista interna, para que nadie pueda usar remove() del iterador para saltarse el invariante.

Cuando la clase guarda sus datos de otra forma, hay que escribir el iterador. NumberRange.java representa los enteros de from a to (sin incluirlo) de step en step, como 1, 3, 5, 7, 9. No guarda los números en ningún lado: el iterador los va calculando.

public class NumberRange implements Iterable<Integer> {

    private final int from;
    private final int to;
    private final int step;

    // constructor: valida que step sea positivo

    @Override
    public Iterator<Integer> iterator() {
        return new RangeIterator();
    }

    /** Clase interna: cada iterador tiene su propio cursor y ve los campos del rango. */
    private class RangeIterator implements Iterator<Integer> {

        private int next = from;

        @Override
        public boolean hasNext() {
            return next < to;
        }

        @Override
        public Integer next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            int current = next;
            next += step;
            return current;
        }
    }
}

RangeIterator es una clase interna (inner class): está declarada dentro de NumberRange y sin static. Cada objeto RangeIterator está ligado al NumberRange que lo creó y puede leer sus campos from, to y step como si fueran propios. Es private porque nadie de afuera necesita saber que existe: los demás solo ven un Iterator<Integer>.

Dos detalles del contrato de Iterator: next() sin elementos debe lanzar NoSuchElementException (no devolver null), y no implementamos remove(), así que se hereda el método default de la interfaz, que lanza UnsupportedOperationException. Como cada llamada a iterator() crea un iterador nuevo con su propio cursor, se pueden hacer dos recorridos a la vez (RangeDemo.java):

NumberRange odds = new NumberRange(1, 10, 2);
int pairs = 0;
for (int a : odds) {
    for (int b : odds) {
        if (a < b) {
            pairs++;
        }
    }
}

$ java -cp build RangeDemo
for-each: 1 3 5 7 9
iterador: 1 3 5 7 9
pares a < b: 10

Con cinco números hay 10 pares con a < b. Si los dos bucles compartieran un solo cursor, el bucle interno lo agotaría en la primera vuelta. En el laboratorio aplican esta misma estructura al BoundedStack<E> de la semana 10.

El código de la semana y make test

Además de los programas de arriba, la carpeta trae las pruebas: SongTest (orden natural y consistencia con equals), ComparatorsTest (los dos comparadores, incluidos los empates, y el TreeSet que pierde una canción), WordCountTest, PlaylistTest y NumberRangeTest. En lab/ está el código inicial del laboratorio; su BoundedStack<E> es el mismo esqueleto de la semana 10, con las mismas firmas, para que copien ahí su versión y sus pruebas. Dentro del contenedor:

$ cd code/week-11
$ make test
...
== SortDemo
Por título (Comparable):
...
╷
├─ JUnit Platform Suite ✔
├─ JUnit Jupiter ✔
│  ├─ NumberRangeTest ✔
│  │  ├─ emptyRangeHasNoElements() ✔
│  │  ├─ stepMustBePositive() ✔
│  │  ├─ forEachVisitsEveryStep() ✔
│  │  └─ eachIteratorHasItsOwnCursor() ✔
│  ├─ PlaylistTest ✔
...
│  ├─ ComparatorsTest ✔
│  │  ├─ byDurationSortsShortestFirstAndKeepsTiesInOrder() ✔
│  │  ├─ treeSetWithByDurationDropsSongsWithTheSameDuration() ✔
│  │  └─ byArtistThenTitleBreaksTiesByTitle() ✔
...
[        17 tests successful      ]
[         0 tests failed          ]

Una prueba de un comparador debe incluir empates: es donde se esconden los errores. ComparatorsTest verifica el orden completo de la lista, con Malecón y Cumbre en el lugar que dicta el ordenamiento estable.

Resumen

• El Collections Framework separa interfaces (Collection, List, Set, Queue, Map) de implementaciones. Se programa contra la interfaz.
• List: orden y repetidos. ArrayList (arreglo; get(i) inmediato) casi siempre; LinkedList (nodos) rara vez. contains en una lista recorre todo.
• Set: sin repetidos. HashSet (rápido, sin orden) y LinkedHashSet (orden de inserción) comparan con equals y hashCode; TreeSet (ordenado), con la comparación: iguales si da 0.
• Map<K, V>: put, get, getOrDefault, containsKey, entrySet. HashMap, LinkedHashMap, TreeMap. Un mapa de conjuntos sirve para índices.
• Un HashMap elige el bucket con hashCode: una clave que cambia después del put se pierde. Las claves deben ser inmutables.
• List.of, Set.of, Map.of crean colecciones inmutables; Collections.unmodifiableList da una vista de solo lectura, ideal para un getter; List.copyOf, una copia.
• Comparable<T>: el orden natural, con compareTo. Contrato: antisimetría, transitividad, empates coherentes; mejor si es consistente con equals. Nunca restar: Integer.compare.
• Comparator<T>: órdenes externos, tantos como hagan falta; varios criterios dentro de compare. List.sort es estable. Un TreeSet trata como iguales a los que el comparador empata.
• For-each usa un Iterator (hasNext, next, remove). Modificar la colección por fuera del iterador durante el recorrido lanza ConcurrentModificationException; se borra con it.remove().
• Una clase propia es iterable si implementa Iterable<E>, delegando o con una clase interna que implementa Iterator<E>.

Ejercicios

1. Para cada caso, digan qué interfaz e implementación usarían y por qué, en términos de las operaciones que se repiten: (a) los DNI de las personas que ya votaron en una mesa, para rechazar a quien intente votar dos veces; (b) el historial de páginas visitadas, con “atrás”; (c) el precio de cada producto por su código; (d) las notas de un curso, para imprimirlas de mayor a menor.

2. Sin ejecutarlo, digan qué imprime este fragmento. Después compruébenlo en jshell:

   Set<String> s = new TreeSet<>(List.of("pera", "Uva", "manzana", "uva"));
   IO.println(s + " " + s.size());

3. Escriban un método Map<Character, Integer> letterCount(String text) que cuente las letras de un texto, sin distinguir mayúsculas, con las letras en orden alfabético. Escriban sus pruebas, incluido el texto vacío.

4. Usando WordIndex, escriban un programa que lea las líneas de un texto corto y muestre las palabras que aparecen en todas las líneas. ¿Qué operación de Set les sirve? Busquen en la documentación de Set el método retainAll.

5. Explíquenle a un compañero, con un dibujo de los buckets, por qué en MutableKeyDemo ni get(A7) ni get(C2) encuentran la entrada. Luego modifiquen MutableKey para que sea inmutable (final en los campos, sin moveTo). ¿Cómo se “mueve” ahora a alguien de asiento en el mapa?

6. Escriban un comparador ByDurationDesc que ordene de la más larga a la más corta y, a igual duración, por título. Prueben el orden completo de Songs.sample().

7. Un compañero escribe return (int) (this.average - other.average); para comparar por promedio, con average de tipo double. Den dos ejemplos de pares de valores para los que el resultado es incorrecto. Escriban la versión correcta.

8. Agreguen a Song una canción con el mismo título y artista que otra, pero con distinta duración. Con el compareTo actual, ¿cuántos elementos tiene un TreeSet<Song> con las dos? ¿Y si compareTo comparara solo título y artista? Relacionen la respuesta con la consistencia con equals.

9. Reescriban el bucle de RemoveDemo para que, en lugar de borrar las canciones cortas, las copie a otra lista shortOnes sin tocar songs. ¿Hace falta el iterador explícito en ese caso? ¿Por qué?

10. Prueben en jshell qué pasa al llamar it.remove() dos veces seguidas sin next() entre ellas, y al llamarlo antes del primer next(). Lean la documentación de Iterator.remove y expliquen el comportamiento.

11. Escriban una clase Countdown implements Iterable<Integer> que recorra de n a 0, con una clase interna para el iterador. Escriban una prueba que verifique que dos for-each anidados sobre el mismo Countdown funcionan.

12. ¿Por qué Playlist.iterator() devuelve songs().iterator() y no songs.iterator()? Escriban una prueba que fallaría con la segunda versión.