NavigableSet/NavigableMap

1. Introdução

A biblioteca padrão do Java tem diversas coleções, mas quando o assunto é intervalos, busca de elementos “mais próximos”, priorização e trabalho com slots de horário, entram em cena as interfaces NavigableSet e NavigableMap.

NavigableSet estende SortedSet, adicionando métodos para buscar elementos em relação a um valor dado (menor, maior, mais próximo etc.), além de trabalhar com intervalos.
NavigableMap estende SortedMap, adicionando métodos semelhantes para busca por chaves e trabalho com intervalos.

As implementações mais conhecidas: TreeSet e TreeMap.

Quando usar NavigableSet/NavigableMap?

• Quando é importante não apenas armazenar elementos/chaves únicos em ordem, mas também encontrar rapidamente os “vizinhos” (por exemplo, o próximo horário livre, a tarefa prioritária, o intervalo de valores).
• Quando é preciso trabalhar com intervalos: “todos os elementos entre X e Y”, “todas as chaves maiores/menores que a fornecida”, “encontrar a chave mais próxima”.

2. Intervalos: subSet, headSet, tailSet

Métodos para trabalhar com intervalos

NavigableSet e NavigableMap permitem obter visões “vivas” (view) de subconjuntos da coleção:

• subSet(fromElement, fromInclusive, toElement, toInclusive) — elementos no intervalo [fromElement; toElement], inclusivo/exclusivo.
• headSet(toElement, inclusive) — todos os elementos menores que (ou menores ou iguais a) toElement.
• tailSet(fromElement, inclusive) — todos os elementos maiores que (ou maiores ou iguais a) fromElement.

Exemplo:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

// Intervalo de 15 (inclusivo) até 45 (exclusivo)
NavigableSet<Integer> sub = set.subSet(15, true, 45, false); // [20, 30, 40]
System.out.println(sub); // [20, 30, 40]

// Todos os elementos <= 30
NavigableSet<Integer> head = set.headSet(30, true); // [10, 20, 30]

// Todos os elementos > 20
NavigableSet<Integer> tail = set.tailSet(20, false); // [30, 40, 50]

Inclusivo/exclusivo:

• true — inclusivo (o elemento entra no intervalo)
• false — exclusivo (o elemento não entra)

Para NavigableMap os métodos são análogos, mas operam sobre chaves.

3. Operações de valores próximos: floor, ceiling, lower, higher; pollFirst/Last

Busca de elementos mais próximos

NavigableSet:

• lower(E e) — o maior elemento < e (estritamente menor)
• floor(E e) — o maior elemento ≤ e (menor ou igual)
• ceiling(E e) — o menor elemento ≥ e (maior ou igual)
• higher(E e) — o menor elemento > e (estritamente maior)

Exemplo:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

System.out.println(set.lower(30));   // 20
System.out.println(set.floor(30));   // 30
System.out.println(set.ceiling(25)); // 30
System.out.println(set.higher(40));  // 50

pollFirst() / pollLast()

• pollFirst() — remove e retorna o menor elemento (ou null, se vazio)
• pollLast() — remove e retorna o maior elemento

Exemplo:

System.out.println(set.pollFirst()); // 10
System.out.println(set.pollLast());  // 50
System.out.println(set);             // [20, 30, 40]

NavigableMap: métodos análogos para chaves — lowerKey, floorKey, ceilingKey, higherKey, além de pollFirstEntry, pollLastEntry.

4. Visões: descendingSet/descendingMap; views e sua “vivacidade”

Ordem inversa: descendingSet/descendingMap

• descendingSet() — retorna uma visão do conjunto em ordem inversa.
• descendingMap() — retorna uma visão do mapa em ordem inversa de chaves.

Exemplo:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> desc = set.descendingSet();
System.out.println(desc); // [50, 40, 30, 20, 10]

Importante: isto não é uma cópia, mas uma visão “viva” (view) dos mesmos dados. Alterações em uma se refletem na outra.

Visões (view) e sua “vivacidade”

• Os métodos subSet, headSet, tailSet, descendingSet, descendingMap retornam uma view — uma visão “viva” da coleção original.
• Qualquer alteração na view se reflete na coleção original e vice-versa.
• Se você remover um elemento do subSet, ele também desaparecerá do conjunto original.

Exemplo:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> sub = set.subSet(20, true, 40, true); // [20, 30, 40]
sub.remove(30);
System.out.println(set); // [10, 20, 40, 50]

Cuidado: se você modificar a coleção original de modo que um elemento “saia” do intervalo da view, no próximo acesso à view você receberá ConcurrentModificationException.

5. Casos de uso de NavigableSet/NavigableMap

1. Slots de horário/agenda

Tarefa: encontrar o slot de horário livre mais próximo para uma reunião.

NavigableSet<LocalTime> slots = new TreeSet<>(List.of(
    LocalTime.of(9, 0),
    LocalTime.of(10, 0),
    LocalTime.of(11, 0),
    LocalTime.of(14, 0)
));

LocalTime requested = LocalTime.of(10, 30);
LocalTime nextSlot = slots.ceiling(requested); // 11:00
System.out.println("Horário mais próximo: " + nextSlot);

2. Priorização (fila com prioridade)

Tarefa: obter sempre rapidamente o elemento com a maior/menor prioridade.

NavigableSet<Task> tasks = new TreeSet<>(Comparator.comparingInt(Task::priority));
tasks.add(new Task("Correio", 2));
tasks.add(new Task("Ligação", 1));
tasks.add(new Task("Relatório", 3));

Task next = tasks.pollFirst(); // Tarefa com a prioridade mais alta (1)

3. “Chave mais próxima” (por exemplo, para buscar um intervalo em Map)

Tarefa: encontrar o intervalo de valores por uma chave, ou a chave mais próxima.

NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(50, "Insatisfatório");
grades.put(65, "Satisfatório");
grades.put(75, "Bom");
grades.put(85, "Excelente");

int score = 78;
int key = grades.floorKey(score); // 75
System.out.println("Conceito: " + grades.get(key)); // Bom

6. Prática: mini-exemplos

Exemplo 1: Intervalo de datas

NavigableSet<LocalDate> holidays = new TreeSet<>(List.of(
    LocalDate.of(2024, 1, 1),
    LocalDate.of(2024, 5, 1),
    LocalDate.of(2024, 12, 31)
));
LocalDate from = LocalDate.of(2024, 1, 1);
LocalDate to = LocalDate.of(2024, 6, 1);
NavigableSet<LocalDate> spring = holidays.subSet(from, true, to, false);
System.out.println(spring); // [2024-01-01, 2024-05-01]

Exemplo 2: Busca do valor mais próximo

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));
int x = 25;
System.out.println("Menor: " + numbers.lower(x));              // 20
System.out.println("Menor ou igual: " + numbers.floor(x));     // 20
System.out.println("Maior ou igual: " + numbers.ceiling(x));   // 30
System.out.println("Maior: " + numbers.higher(x));             // 30

7. Erros típicos e nuances

Erro nº 1: Confundir inclusivo/exclusivo em subSet/headSet/tailSet.
Sempre preste atenção aos parâmetros inclusive — por padrão, em versões antigas do Java, os intervalos eram exclusivos; em NavigableSet/NavigableMap é possível indicar explicitamente inclusivo/exclusivo.

Erro nº 2: Esperar que a view seja uma cópia.
A view é uma representação “viva”, não uma cópia! Alterações na view se refletem na coleção original.

Erro nº 3: ConcurrentModificationException ao modificar a coleção original fora da view.
Se você modificar a coleção original de modo que um elemento “saia” do intervalo da view, no próximo acesso à view receberá a exceção.

Erro nº 4: Usar NavigableSet/NavigableMap sem Comparable ou Comparator.
Essas coleções exigem que os elementos (ou chaves) sejam comparáveis (Comparable) ou que seja fornecido um Comparator. Caso contrário, você obterá ClassCastException.

Erro nº 5: Esperar que pollFirst/pollLast não modifiquem a coleção.
Esses métodos removem elementos! Se você precisar apenas visualizar — use first()/last().