Interfaces SortedMap e NavigableMap. Classe TreeMap em Java

Para criar mapeamentos ordenados, o Java oferece interfaces adicionais como SortedMap e NavigableMap.

SortedMap

A interface SortedMap<K, V> estende Map<K, V> e cria um mapeamento em que todos os elementos ficam ordenados em ordem crescente de suas chaves. SortedMap adiciona métodos como:

• K firstKey(): retorna a chave do primeiro elemento do mapeamento.
• K lastKey(): retorna a chave do último elemento do mapeamento.
• SortedMap<K, V> headMap(K end): retorna um objeto SortedMap com todos os elementos do mapeamento original até a chave end, sem incluir end.
• SortedMap<K, V> tailMap(K start): retorna um objeto SortedMap com todos os elementos do mapeamento original a partir da chave start, incluindo start.
• SortedMap<K, V> subMap(K start, K end): retorna um objeto SortedMap com todos os elementos do mapeamento original de start até end, incluindo start, mas sem incluir end.

NavigableMap

A interface NavigableMap<K, V> estende SortedMap<K, V> e permite obter elementos do mapeamento em relação a outros elementos. Seus principais métodos incluem:

• Map.Entry<K, V> ceilingEntry(K key): retorna o elemento com a menor chave k maior ou igual a key (k >= key). Caso não exista, retorna null.
• Map.Entry<K, V> floorEntry(K key): retorna o elemento com a maior chave k menor ou igual a key (k <= key). Caso não exista, retorna null.
• Map.Entry<K, V> higherEntry(K key): retorna o elemento com a menor chave k maior que key (k > key). Caso não exista, retorna null.
• Map.Entry<K, V> lowerEntry(K key): retorna o elemento com a maior chave k menor que key (k < key). Caso não exista, retorna null.
• Map.Entry<K, V> firstEntry(): retorna o primeiro elemento do mapeamento.
• Map.Entry<K, V> lastEntry(): retorna o último elemento do mapeamento.
• Map.Entry<K, V> pollFirstEntry(): retorna e remove o primeiro elemento do mapeamento.
• Map.Entry<K, V> pollLastEntry(): retorna e remove o último elemento do mapeamento.
• K ceilingKey(K key): retorna a menor chave k maior ou igual a key (k >= key). Caso não exista, retorna null.
• K floorKey(K key): retorna a maior chave k menor ou igual a key (k <= key). Caso não exista, retorna null.
• K lowerKey(K key): retorna a maior chave k menor que key (k < key). Caso não exista, retorna null.
• K higherKey(K key): retorna a menor chave k maior que key (k > key). Caso não exista, retorna null.
• NavigableSet<K> descendingKeySet(): retorna um objeto NavigableSet com todas as chaves do mapeamento em ordem reversa.
• NavigableMap<K, V> descendingMap(): retorna um objeto NavigableMap com todos os elementos em ordem reversa.
• NavigableSet<K> navigableKeySet(): retorna um objeto NavigableSet com todas as chaves do mapeamento.
• NavigableMap<K, V> headMap(K upperBound, boolean incl): retorna um objeto NavigableMap com todos os elementos do mapeamento original até upperBound. O parâmetro incl, quando true, inclui upperBound.
• NavigableMap<K, V> tailMap(K lowerBound, boolean incl): retorna um objeto NavigableMap com todos os elementos do mapeamento original a partir de lowerBound. O parâmetro incl, quando true, inclui lowerBound.
• NavigableMap<K, V> subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): retorna um objeto NavigableMap com todos os elementos do mapeamento original de lowerBound até upperBound. Os parâmetros lowIncl e highIncl, quando true, incluem lowerBound e upperBound, respectivamente.

TreeMap

A classe TreeMap<K, V> representa um mapeamento em forma de árvore. Ela herda de AbstractMap e implementa NavigableMap, o que inclui também SortedMap. Diferentemente de HashMap, em TreeMap todos os objetos se ordenam automaticamente em ordem crescente de suas chaves.

TreeMap possui construtores como:

• TreeMap(): cria um mapeamento vazio em forma de árvore.
• TreeMap(Map<? extends K, ? extends V> map): cria uma árvore e adiciona todos os elementos do mapeamento map.
• TreeMap(SortedMap<K, ? extends V> smap): cria uma árvore e adiciona todos os elementos do mapeamento ordenado smap.
• TreeMap(Comparator<? super K> comparator): cria uma árvore vazia, na qual os elementos adicionados serão ordenados pelo comparador.

Um exemplo de uso da classe segue abaixo.

import java.util.*;

public class Program {

    public static void main(String[] args) {

        TreeMap<Integer, String> states = new TreeMap<>();
        states.put(10, "Germany");
        states.put(2, "Spain");
        states.put(14, "France");
        states.put(3, "Italy");

        // obtemos o objeto pela chave 2
        String valueForKey2 = states.get(2);
        System.out.println(valueForKey2);

        // percorremos os elementos
        for (Map.Entry<Integer, String> item : states.entrySet()) {
            System.out.printf("Key: %d  Value: %s \n", item.getKey(), item.getValue());
        }

        // obtemos o conjunto completo de chaves
        Set<Integer> keys = states.keySet();
        // obtemos a coleção de todos os valores
        Collection<String> values = states.values();

        // obtemos todos os objetos após a chave 4
        Map<Integer, String> afterMap = states.tailMap(4);

        // obtemos todos os objetos antes da chave 10
        Map<Integer, String> beforeMap = states.headMap(10);

        // obtemos o último elemento da árvore
        Map.Entry<Integer, String> lastItem = states.lastEntry();
        System.out.printf("Last item has key %d value %s \n", lastItem.getKey(), lastItem.getValue());

        Map<String, Person> people = new TreeMap<>();
        people.put("1240i54", new Person("Tom"));
        people.put("1564i55", new Person("Bill"));
        people.put("4540i56", new Person("Nick"));

        for (Map.Entry<String, Person> item : people.entrySet()) {
            System.out.printf("Key: %s  Value: %s \n", item.getKey(), item.getValue().getName());
        }
    }
}

class Person {
    private String name;

    public Person(String name) {
        this.name = name;
    }

    String getName() {
        return name;
    }
}

O código acima demonstra a principal característica do TreeMap: a ordenação automática pelas chaves. Mesmo que os elementos sejam inseridos na ordem de chaves 10, 2, 14, 3, ao percorrer o mapa com o for-each sobre states.entrySet(), a saída será impressa em ordem crescente das chaves: 2, 3, 10, 14.

O exemplo também ilustra o uso de métodos de NavigableMap. O método tailMap(4) retorna um novo mapa contendo todos os elementos do mapa original com chave 4 ou superior. De forma similar, headMap(10) retorna um mapa com os elementos cujas chaves são estritamente menores que 10. O método lastEntry() oferece acesso direto ao último par chave-valor do mapa ordenado. Por fim, o segundo mapa, que usa String como chave e objetos Person como valor, reforça que a ordenação é sempre baseada na ordem natural das chaves.

Resumo

• SortedMap: Interface que estende Map para mapeamentos ordenados por chaves em ordem crescente, com métodos para acessar submapeamentos.
• NavigableMap: Extensão de SortedMap que permite navegação relativa entre elementos, como ceiling, floor e submapeamentos inclusivos.
• TreeMap: Classe que implementa NavigableMap em estrutura de árvore, com ordenação automática de chaves e construtores para inicialização variada.

📝 Exercícios

Tarefa

Descrição: Você está criando um sistema de agendamento. Um TreeMap armazena os horários de compromissos (chave Integer representando a hora em formato 24h) e a descrição do evento (valor String). Sua tarefa é encontrar o próximo compromisso disponível a partir de um horário específico.

Código inicial:

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

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> agenda = new TreeMap<>();
        agenda.put(9, "Reunião de equipe");
        agenda.put(11, "Entrevista com candidato");
        agenda.put(14, "Almoço com cliente");
        agenda.put(16, "Apresentação de projeto");

        int horarioAtual = 12; // São 12:00
        Map.Entry<Integer, String> proximoCompromisso = null;

        // Use um método de NavigableMap para encontrar o primeiro compromisso
        // que ocorre em um horário maior ou igual ao 'horarioAtual'.


        if (proximoCompromisso != null) {
            System.out.println("Seu próximo compromisso é às " + proximoCompromisso.getKey() + "h: " + proximoCompromisso.getValue());
        } else {
            System.out.println("Você não tem mais compromissos hoje.");
        }
    }
}

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

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> agenda = new TreeMap<>();
        agenda.put(9, "Reunião de equipe");
        agenda.put(11, "Entrevista com candidato");
        agenda.put(14, "Almoço com cliente");
        agenda.put(16, "Apresentação de projeto");

        int horarioAtual = 12;

        // O método ceilingEntry(K key) é perfeito para encontrar o "próximo item a partir de um ponto".
        // Ele retorna o par chave-valor com a menor chave que é maior ou igual à chave fornecida.
        Map.Entry<Integer, String> proximoCompromisso = agenda.ceilingEntry(horarioAtual);

        if (proximoCompromisso != null) {
            System.out.println("Seu próximo compromisso é às " + proximoCompromisso.getKey() + "h: " + proximoCompromisso.getValue());
        } else {
            System.out.println("Você não tem mais compromissos hoje.");
        }
    }
}

Seu próximo compromisso é às 14h: Almoço com cliente