HashMap em Rust: Tabela Hash com Swiss Table

use std::collections::HashMap;

fn main() {
    // Criando um HashMap vazio
    let mut notas: HashMap<String, f64> = HashMap::new();

    // Inserindo pares chave-valor
    notas.insert(String::from("Maria"), 9.5);
    notas.insert(String::from("João"), 8.0);
    notas.insert(String::from("Ana"), 9.8);

    // Acessando valores
    if let Some(nota) = notas.get("Maria") {
        println!("Nota da Maria: {}", nota);
    }

    // Verificando existência
    println!("João existe? {}", notas.contains_key("João"));

    // Iterando sobre o HashMap
    for (nome, nota) in &notas {
        println!("{}: {:.1}", nome, nota);
    }

    // Removendo um elemento
    notas.remove("João");
    println!("Após remoção: {:?}", notas);
}

use std::collections::HashMap;

fn main() {
    // A partir de vetores de tuplas
    let times = vec![
        ("Flamengo", 71),
        ("Palmeiras", 70),
        ("Atlético-MG", 65),
    ];

    let classificacao: HashMap<&str, i32> = times.into_iter().collect();
    println!("{:?}", classificacao);

    // A partir de dois vetores com zip
    let chaves = vec!["a", "b", "c"];
    let valores = vec![1, 2, 3];

    let mapa: HashMap<&str, i32> = chaves.into_iter().zip(valores).collect();
    println!("{:?}", mapa);
}

use std::collections::HashMap;

fn main() {
    let mut contagem: HashMap<&str, i32> = HashMap::new();

    // ❌ Sem Entry API: duas buscas (contains_key + insert)
    let palavra = "rust";
    if contagem.contains_key(palavra) {
        *contagem.get_mut(palavra).unwrap() += 1;
    } else {
        contagem.insert(palavra, 1);
    }

    // ✅ Com Entry API: uma única busca
    *contagem.entry("rust").or_insert(0) += 1;

    // or_default() — usa Default::default() (0 para i32)
    *contagem.entry("cargo").or_default() += 1;

    // or_insert_with() — closure executada somente se a chave não existir
    contagem.entry("crate").or_insert_with(|| {
        println!("Calculando valor inicial...");
        42
    });

    // and_modify() — modifica valor existente
    contagem
        .entry("rust")
        .and_modify(|v| *v += 10)
        .or_insert(1);

    println!("{:?}", contagem);
}

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

/// Representa um ponto em coordenadas 2D
#[derive(Debug, Eq, PartialEq)]
struct Ponto {
    x: i32,
    y: i32,
}

// Implementando Hash manualmente
// REGRA: se a == b, então hash(a) == hash(b)
impl Hash for Ponto {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.x.hash(state);
        self.y.hash(state);
    }
}

fn main() {
    let mut mapa_pontos: HashMap<Ponto, String> = HashMap::new();

    mapa_pontos.insert(
        Ponto { x: 0, y: 0 },
        String::from("Origem"),
    );
    mapa_pontos.insert(
        Ponto { x: 3, y: 4 },
        String::from("Ponto A"),
    );

    let busca = Ponto { x: 3, y: 4 };
    if let Some(nome) = mapa_pontos.get(&busca) {
        println!("Encontrado: {}", nome);
    }
}

// Para cenários onde a proteção contra DoS não é necessária
// (ex: compiladores, ferramentas offline), use FxHash:
//
// Cargo.toml:
// [dependencies]
// rustc-hash = "2"

use rustc_hash::FxHashMap;

fn exemplo_fxhash() {
    let mut mapa: FxHashMap<i32, &str> = FxHashMap::default();
    mapa.insert(1, "um");
    mapa.insert(2, "dois");

    // FxHash é ~2-5x mais rápido que SipHash para chaves inteiras
    println!("{:?}", mapa);
}

use std::collections::HashMap;

/// Conta a frequência de cada palavra em um texto.
/// Normaliza para minúsculas e remove pontuação.
fn contar_palavras(texto: &str) -> HashMap<String, usize> {
    let mut frequencia: HashMap<String, usize> = HashMap::new();

    for palavra in texto.split_whitespace() {
        // Normaliza: minúsculas e remove pontuação
        let limpa: String = palavra
            .to_lowercase()
            .chars()
            .filter(|c| c.is_alphanumeric())
            .collect();

        if !limpa.is_empty() {
            *frequencia.entry(limpa).or_insert(0) += 1;
        }
    }

    frequencia
}

/// Retorna as N palavras mais frequentes, ordenadas por contagem.
fn top_n_palavras(frequencia: &HashMap<String, usize>, n: usize) -> Vec<(&String, &usize)> {
    let mut pares: Vec<_> = frequencia.iter().collect();
    pares.sort_by(|a, b| b.1.cmp(a.1)); // Ordena por frequência decrescente
    pares.into_iter().take(n).collect()
}

/// Sistema de cache simples usando HashMap
struct Cache {
    dados: HashMap<String, String>,
    capacidade: usize,
}

impl Cache {
    fn novo(capacidade: usize) -> Self {
        Cache {
            dados: HashMap::with_capacity(capacidade),
            capacidade,
        }
    }

    /// Busca no cache, retorna None se não encontrar
    fn buscar(&self, chave: &str) -> Option<&String> {
        self.dados.get(chave)
    }

    /// Insere no cache. Retorna false se o cache estiver cheio.
    fn inserir(&mut self, chave: String, valor: String) -> bool {
        if self.dados.len() >= self.capacidade && !self.dados.contains_key(&chave) {
            return false; // Cache cheio
        }
        self.dados.insert(chave, valor);
        true
    }

    /// Busca ou calcula o valor usando a função fornecida
    fn buscar_ou_calcular<F>(&mut self, chave: &str, calcular: F) -> &String
    where
        F: FnOnce() -> String,
    {
        // Usa Entry API para evitar busca dupla
        self.dados
            .entry(chave.to_string())
            .or_insert_with(calcular)
    }
}

fn main() {
    // === Contador de Palavras ===
    let texto = "Rust é seguro. Rust é rápido. Rust é moderno. \
                 Programar em Rust é produtivo e divertido. \
                 A comunidade Rust é acolhedora e ativa.";

    let frequencia = contar_palavras(texto);

    println!("=== Frequência de Palavras ===");
    let top = top_n_palavras(&frequencia, 5);
    for (palavra, contagem) in &top {
        let barra = "#".repeat(**contagem);
        println!("  {:<12} {:>2} {}", palavra, contagem, barra);
    }

    // === Cache Simples ===
    println!("\n=== Cache Simples ===");
    let mut cache = Cache::novo(100);

    // Simula busca com cache
    let resultado = cache.buscar_ou_calcular("fibonacci_40", || {
        println!("  Calculando fibonacci(40)... (operação custosa)");
        String::from("102334155")
    });
    println!("  Resultado: {}", resultado);

    // Segunda busca: vem do cache (sem recalcular)
    let resultado = cache.buscar_ou_calcular("fibonacci_40", || {
        println!("  Isso NÃO deve aparecer!");
        String::from("erro")
    });
    println!("  Resultado do cache: {}", resultado);

    // === Agrupamento com HashMap ===
    println!("\n=== Agrupamento por Inicial ===");
    let nomes = vec!["Ana", "Bruno", "Alice", "Bianca", "Carlos", "Amanda"];
    let mut por_inicial: HashMap<char, Vec<&str>> = HashMap::new();

    for nome in nomes {
        let inicial = nome.chars().next().unwrap();
        por_inicial.entry(inicial).or_default().push(nome);
    }

    for (inicial, grupo) in &por_inicial {
        println!("  {}: {:?}", inicial, grupo);
    }
}

// Dica: ordene as letras de cada palavra para criar uma "chave de anagrama"
// "amor" e "roma" ambas geram a chave "amor"
fn agrupar_anagramas(palavras: Vec<String>) -> Vec<Vec<String>> {
    // Sua implementação aqui
    todo!()
}

// Teste:
// agrupar_anagramas(vec!["amor", "roma", "mora", "carro", "corta", "crota"])
// => [["amor", "roma", "mora"], ["carro"], ["corta", "crota"]]

fn duas_somas(nums: &[i32], alvo: i32) -> Option<(usize, usize)> {
    // Dica: para cada número, verifique se (alvo - num) já foi visto
    todo!()
}

// Teste:
// duas_somas(&[2, 7, 11, 15], 9) => Some((0, 1))
// duas_somas(&[3, 2, 4], 6) => Some((1, 2))

struct LruSimples<K, V> {
    capacidade: usize,
    mapa: HashMap<K, V>,
    ordem: Vec<K>, // ordem de acesso (mais recente no final)
}

impl<K: Eq + Hash + Clone, V> LruSimples<K, V> {
    fn novo(capacidade: usize) -> Self { todo!() }
    fn buscar(&mut self, chave: &K) -> Option<&V> { todo!() }
    fn inserir(&mut self, chave: K, valor: V) { todo!() }
}