import java.util.Comparator;

/** Ordena por artista y, entre canciones del mismo artista, por título. */
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());
    }
}

import java.util.Comparator;

/** Ordena canciones de la más corta a la más larga. */
public class ByDuration implements Comparator<Song> {

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

import java.util.Objects;

/** Un código de asiento mutable, con equals y hashCode que usan sus campos. */
public class MutableKey {

    private char row;
    private int number;

    public MutableKey(char row, int number) {
        this.row = row;
        this.number = number;
    }

    public void moveTo(char newRow, int newNumber) {
        row = newRow;
        number = newNumber;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof MutableKey k && k.row == row && k.number == number;
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, number);
    }

    @Override
    public String toString() {
        return "" + row + number;
    }
}

import java.util.HashMap;
import java.util.Map;

/** Una clave que cambia después de entrar al HashMap ya no se encuentra. */
public class MutableKeyDemo {

    public static void main(String[] args) {
        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());
    }
}

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Los enteros desde from (incluido) hasta to (excluido), de step en step.
 * No guarda los números: el iterador los calcula a medida que se piden.
 */
public class NumberRange implements Iterable<Integer> {

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

    public NumberRange(int from, int to, int step) {
        if (step <= 0) {
            throw new IllegalArgumentException("step debe ser positivo: " + step);
        }
        this.from = from;
        this.to = to;
        this.step = step;
    }

    @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;
        }
    }
}

import java.util.ArrayList;
import java.util.List;

/** Un comparador que resta da un orden incorrecto cuando la resta produce un overflow. */
public class OverflowDemo {

    public static void main(String[] args) {
        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);
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * Una lista de reproducción que no admite canciones repetidas.
 * Invariante: songs no tiene dos canciones iguales (según equals).
 */
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);
    }

    public int size() {
        return songs.size();
    }

    /** Recorrer la lista con for-each, sin exponerla. */
    @Override
    public Iterator<Song> iterator() {
        return songs().iterator();
    }
}

import java.util.Iterator;

/** Una colección propia en un for-each, y lo que el for-each hace por dentro. */
public class RangeDemo {

    public static void main(String[] args) {
        NumberRange odds = new NumberRange(1, 10, 2);
        StringBuilder line = new StringBuilder("for-each:");
        for (int n : odds) {
            line.append(' ').append(n);
        }
        IO.println(line);

        // Lo mismo, escrito como lo traduce el compilador.
        line = new StringBuilder("iterador:");
        Iterator<Integer> it = odds.iterator();
        while (it.hasNext()) {
            int n = it.next();
            line.append(' ').append(n);
        }
        IO.println(line);

        // Dos recorridos a la vez: cada iterador tiene su propio cursor.
        int pairs = 0;
        for (int a : odds) {
            for (int b : odds) {
                if (a < b) {
                    pairs++;
                }
            }
        }
        IO.println("pares a < b: " + pairs);
    }
}

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;

/** Borrar durante un recorrido: mal con for-each, bien con el iterador. */
public class RemoveDemo {

    public static void main(String[] args) {
        List<Song> songs = Songs.sample();
        try {
            for (Song s : songs) {
                if (s.seconds() < 200) {
                    songs.remove(s);                // modifica la lista por fuera del iterador
                }
            }
        } catch (ConcurrentModificationException e) {
            IO.println("for-each + remove: " + e.getClass().getName());
        }

        songs = Songs.sample();
        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()
            }
        }
        IO.println("Quedan " + songs.size() + ":");
        for (Song s : songs) {
            IO.println("  " + s.seconds() + "  " + s.title());
        }
    }
}

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

/** Las tres implementaciones de Set con los mismos datos. */
public class SetDemo {

    public static void main(String[] args) {
        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);
        }
        IO.println("visitas:       " + visits.length);
        IO.println("HashSet:       " + hash);
        IO.println("LinkedHashSet: " + linked);
        IO.println("TreeSet:       " + tree);

        boolean added = tree.add("Lima");
        IO.println("¿add(\"Lima\") otra vez? " + added + ", size = " + tree.size());
        IO.println("¿contains(\"Puno\")? " + hash.contains("Puno"));
    }
}

/**
 * Una canción: título, artista y duración en segundos.
 * El orden natural es por título; si empatan, por artista y luego por duración.
 * Así compareTo da 0 solo cuando equals da true (es consistente con equals).
 */
public record Song(String title, String artist, int seconds) implements Comparable<Song> {

    @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);
    }
}

import java.util.ArrayList;
import java.util.List;

/** La lista de canciones de ejemplo (inventadas) que usan las demostraciones. */
public final class Songs {

    private Songs() {
    }

    /** Devuelve una lista nueva (modificable) con seis canciones. */
    public static List<Song> sample() {
        List<Song> songs = new ArrayList<>();
        songs.add(new Song("Garúa", "Costa Verde", 220));
        songs.add(new Song("Puente de piedra", "Los Andinos", 245));
        songs.add(new Song("Malecón", "Costa Verde", 190));
        songs.add(new Song("Arena", "Duna", 185));
        songs.add(new Song("Cumbre", "Los Andinos", 190));
        songs.add(new Song("Brisa", "Duna", 210));
        return songs;
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeSet;

/** Orden natural, órdenes con comparadores y un TreeSet que pierde canciones. */
public class SortDemo {

    static void print(String title, Iterable<Song> songs) {
        IO.println(title);
        for (Song s : songs) {
            IO.println("  " + s.seconds() + "  " + s.artist() + " - " + s.title());
        }
    }

    public static void main(String[] args) {
        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);

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

        List<Song> copy = new ArrayList<>(songs);
        Collections.reverse(copy);
        IO.println("La más larga: " + Collections.max(copy, new ByDuration()).title());
    }
}

import java.util.Comparator;

/** MAL: compara restando. Con números grandes la resta produce un overflow. */
public class SubtractionOrder implements Comparator<Integer> {

    @Override
    public int compare(Integer a, Integer b) {
        return a - b;
    }
}

import java.util.List;

/** Colecciones inmutables, vistas no modificables y copias. */
public class ViewDemo {

    public static void main(String[] args) {
        List<String> fixed = List.of("do", "re", "mi");
        try {
            fixed.add("fa");
        } catch (UnsupportedOperationException e) {
            IO.println("List.of no admite add: " + e.getClass().getSimpleName());
        }

        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());
        for (Song s : playlist) {
            IO.println("  " + s.title());
        }
    }
}

import java.util.Map;
import java.util.TreeMap;

/** Cuenta cuántas veces aparece cada palabra de un texto. */
public final class WordCount {

    private WordCount() {
    }

    /** Separa el texto en palabras (en minúsculas) y las cuenta, en orden alfabético. */
    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;
    }
}

import java.util.List;
import java.util.Map;
import java.util.Set;

/** Contar palabras con un Map y armar un índice con un Map de conjuntos. */
public class WordDemo {

    public static void main(String[] args) {
        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());
            }
        }

        List<String> lines = List.of(
                "el puente y el río",
                "el río baja al mar",
                "un puente de piedra");
        Map<String, Set<Integer>> index = WordIndex.index(lines);
        IO.println("río -> " + index.get("río") + ", puente -> " + index.get("puente")
                + ", el -> " + index.get("el"));
        IO.println(index.size() + " palabras distintas: " + index.keySet());
    }
}

import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

/** Un índice de palabras: para cada palabra, el conjunto de líneas donde aparece. */
public final class WordIndex {

    private WordIndex() {
    }

    /** Las líneas se numeran desde 1. Palabras y números de línea salen ordenados. */
    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;
    }
}

import static org.junit.jupiter.api.Assertions.assertEquals;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

import org.junit.jupiter.api.Test;

class ComparatorsTest {

    private static List<String> titles(List<Song> songs) {
        List<String> result = new ArrayList<>();
        for (Song s : songs) {
            result.add(s.title());
        }
        return result;
    }

    @Test
    void byDurationSortsShortestFirstAndKeepsTiesInOrder() {
        List<Song> songs = Songs.sample();
        songs.sort(new ByDuration());
        // Malecón y Cumbre duran 190: el orden es estable, quedan como estaban.
        assertEquals(List.of("Arena", "Malecón", "Cumbre", "Brisa", "Garúa", "Puente de piedra"),
                titles(songs));
    }

    @Test
    void byArtistThenTitleBreaksTiesByTitle() {
        List<Song> songs = Songs.sample();
        songs.sort(new ByArtistThenTitle());
        assertEquals(List.of("Garúa", "Malecón", "Arena", "Brisa", "Cumbre", "Puente de piedra"),
                titles(songs));
    }

    @Test
    void treeSetWithByDurationDropsSongsWithTheSameDuration() {
        TreeSet<Song> set = new TreeSet<>(new ByDuration());
        set.addAll(Songs.sample());
        assertEquals(5, set.size());
    }
}

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertThrows;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import org.junit.jupiter.api.Test;

class NumberRangeTest {

    private static List<Integer> collect(Iterable<Integer> numbers) {
        List<Integer> out = new ArrayList<>();
        for (int n : numbers) {
            out.add(n);
        }
        return out;
    }

    @Test
    void forEachVisitsEveryStep() {
        assertEquals(List.of(0, 3, 6, 9), collect(new NumberRange(0, 10, 3)));
    }

    @Test
    void emptyRangeHasNoElements() {
        Iterator<Integer> it = new NumberRange(5, 5, 1).iterator();
        assertFalse(it.hasNext());
        assertThrows(NoSuchElementException.class, () -> it.next());
    }

    @Test
    void eachIteratorHasItsOwnCursor() {
        NumberRange r = new NumberRange(1, 4, 1);
        Iterator<Integer> a = r.iterator();
        a.next();
        Iterator<Integer> b = r.iterator();
        assertEquals(2, a.next());
        assertEquals(1, b.next());
    }

    @Test
    void stepMustBePositive() {
        assertThrows(IllegalArgumentException.class, () -> new NumberRange(0, 10, 0));
    }
}

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTrue;

import java.util.List;

import org.junit.jupiter.api.Test;

class PlaylistTest {

    private final Song arena = new Song("Arena", "Duna", 185);

    @Test
    void doesNotAcceptTheSameSongTwice() {
        Playlist p = new Playlist();
        assertTrue(p.add(arena));
        assertFalse(p.add(new Song("Arena", "Duna", 185)));
        assertEquals(1, p.size());
    }

    @Test
    void songsViewCannotBeModified() {
        Playlist p = new Playlist();
        p.add(arena);
        List<Song> view = p.songs();
        assertThrows(UnsupportedOperationException.class, () -> view.add(arena));
        assertEquals(1, p.size());
    }

    @Test
    void viewSeesLaterChanges() {
        Playlist p = new Playlist();
        List<Song> view = p.songs();
        p.add(arena);
        assertEquals(List.of(arena), view);
    }
}

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

import org.junit.jupiter.api.Test;

class SongTest {

    private final Song arena = new Song("Arena", "Duna", 185);
    private final Song brisa = new Song("Brisa", "Duna", 210);

    @Test
    void naturalOrderIsByTitle() {
        assertTrue(arena.compareTo(brisa) < 0);
        assertTrue(brisa.compareTo(arena) > 0);
    }

    @Test
    void sameTitleIsOrderedByArtist() {
        Song other = new Song("Arena", "Costa Verde", 300);
        assertTrue(other.compareTo(arena) < 0);
    }

    @Test
    void compareToIsZeroExactlyWhenEquals() {
        Song copy = new Song("Arena", "Duna", 185);
        Song longer = new Song("Arena", "Duna", 186);
        assertEquals(0, arena.compareTo(copy));
        assertEquals(arena, copy);
        assertTrue(arena.compareTo(longer) != 0);
        assertTrue(!arena.equals(longer));
    }
}

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertTrue;

import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.jupiter.api.Test;

class WordCountTest {

    @Test
    void countsIgnoringCaseAndPunctuation() {
        Map<String, Integer> counts = WordCount.count("Lima, lima. LIMA y Cusco");
        assertEquals(3, counts.get("lima"));
        assertEquals(1, counts.get("cusco"));
        assertNull(counts.get("Lima"));             // las claves quedan en minúsculas
    }

    @Test
    void emptyTextGivesEmptyMap() {
        assertTrue(WordCount.count("").isEmpty());
        assertTrue(WordCount.count(" ... ").isEmpty());
    }

    @Test
    void keysComeOutInAlphabeticalOrder() {
        Map<String, Integer> counts = WordCount.count("río mar arena mar");
        assertEquals(List.of("arena", "mar", "río"), List.copyOf(counts.keySet()));
    }

    @Test
    void indexKeepsEachLineOnceAndSorted() {
        Map<String, Set<Integer>> index = WordIndex.index(List.of("el río", "el mar, el río", "mar"));
        assertEquals(Set.of(1, 2), index.get("el"));
        assertEquals(List.of(2, 3), List.copyOf(index.get("mar")));
        assertNull(index.get("sol"));
    }
}

package lab;

/**
 * Laboratorio de la semana 11: el stack acotado genérico de la semana 10, ahora iterable.
 * Esqueleto con las mismas firmas y el mismo contrato que code/week-10/BoundedStack.java:
 * copien aquí su implementación de la semana 10 (con su invariante y sus pruebas, en
 * BoundedStackTest.java) o complétenla ahora.
 * Parte 4: hacerlo Iterable<E> (del tope hacia el fondo) con una clase interna que
 * implemente Iterator<E>, y recorrerlo con for-each.
 */
public class BoundedStack<E> {

    /** Crea un stack vacío con capacidad para capacity elementos (capacity > 0). */
    public BoundedStack(int capacity) {
        // TODO: validar capacity y crear el arreglo interno (ver los apuntes: new E[n] no compila)
    }

    /** Pone x arriba. Lanza IllegalStateException si el stack está lleno. */
    public void push(E x) {
        throw new UnsupportedOperationException("por implementar");
    }

    /** Saca y devuelve el elemento de arriba. Lanza IllegalStateException si está vacío. */
    public E pop() {
        throw new UnsupportedOperationException("por implementar");
    }

    /** El elemento de arriba, sin sacarlo. Lanza IllegalStateException si está vacío. */
    public E peek() {
        throw new UnsupportedOperationException("por implementar");
    }

    public int size() {
        throw new UnsupportedOperationException("por implementar");
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean isFull() {
        throw new UnsupportedOperationException("por implementar");
    }
}

package lab;

import java.util.List;
import java.util.Map;

/**
 * Laboratorio, parte 1: cinco problemas cortos. Para cada uno, elijan la interfaz
 * y la implementación, escriban en un comentario por qué (qué operaciones se usan
 * y cuánto cuestan), impleméntenlo y escriban sus pruebas en ChoicesTest.java.
 * Pueden cambiar los tipos de retorno si su elección lo pide.
 */
public final class Choices {

    private Choices() {
    }

    /** 1. Los elementos sin repetidos, en el orden en que aparecieron por primera vez. */
    public static List<String> withoutDuplicates(List<String> items) {
        throw new UnsupportedOperationException("por implementar");
    }

    /** 2. Cuántas veces aparece cada elemento. */
    public static Map<String, Integer> frequencies(List<String> items) {
        throw new UnsupportedOperationException("por implementar");
    }

    // 3. Buscar un alumno por su código: una clase Registry con add(code, name) y find(code).
    // 4. Un ranking de puntajes que siempre se recorre de mayor a menor, sin ordenar cada vez.
    // 5. Una cola de atención: llegan clientes y se atiende primero al que llegó primero.
}

package lab;

import java.util.ArrayList;
import java.util.List;

/**
 * Laboratorio, parte 2: mide, sin pretender precisión, cuánto tarda contains.
 * Ya mide un ArrayList; agreguen la misma medición con un HashSet y comparen.
 * Ejecutar con: java -cp build lab.ContainsTiming
 */
public class ContainsTiming {

    static final int N = 100_000;
    static final int LOOKUPS = 1_000;

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(i);
        }

        long start = System.nanoTime();
        int found = 0;
        for (int i = 0; i < LOOKUPS; i++) {
            if (list.contains(N - 1 - i)) {         // cerca del final: el peor caso de la lista
                found++;
            }
        }
        long micros = (System.nanoTime() - start) / 1_000;
        IO.println("ArrayList: " + LOOKUPS + " contains en " + micros + " µs (" + found + " encontrados)");

        // TODO: lo mismo con un HashSet<Integer> con los mismos N números.
    }
}

# Semana 11: colecciones, Comparable, Comparator e iteradores.
#   make         compila todo a build/ (incluido el código inicial del laboratorio, en lab/)
#   make test    corre las demostraciones y las pruebas JUnit
#   make clean   borra build/
JAVAC  = javac
JFLAGS = -Xlint:all -Werror
SRC    = $(shell find . -name '*.java' -not -path './build/*')
DEMOS  = SetDemo WordDemo ViewDemo MutableKeyDemo SortDemo OverflowDemo RemoveDemo RangeDemo

all: build/.stamp

build/.stamp: $(SRC)
	mkdir -p build
	$(JAVAC) $(JFLAGS) -cp $(JUNIT_JAR) -d build $(SRC)
	touch $@

test: all
	@for d in $(DEMOS); do echo "== $$d"; java -cp build $$d || exit 1; done
	java -jar $(JUNIT_JAR) execute --class-path build --scan-class-path \
	  --disable-banner --disable-ansi-colors --details=tree

clean:
	rm -rf build

.PHONY: all test clean