Bloom Filter em Rust: Estrutura Probabilística

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

/// Bloom Filter: estrutura probabilística para teste de pertinência.
/// Garante ZERO falsos negativos, mas permite falsos positivos.
struct BloomFilter {
    /// Array de bits representado como vetor de booleanos
    bits: Vec<bool>,
    /// Tamanho do array de bits
    tamanho: usize,
    /// Número de funções hash
    num_hashes: usize,
    /// Contador de elementos inseridos
    contagem: usize,
}

impl BloomFilter {
    /// Cria um novo Bloom Filter com o tamanho e número de hashes especificados.
    fn novo(tamanho_bits: usize, num_hashes: usize) -> Self {
        BloomFilter {
            bits: vec![false; tamanho_bits],
            tamanho: tamanho_bits,
            num_hashes,
            contagem: 0,
        }
    }

    /// Cria um Bloom Filter otimizado para a quantidade esperada de elementos
    /// e taxa de falsos positivos desejada.
    fn com_taxa_erro(num_elementos: usize, taxa_falso_positivo: f64) -> Self {
        // m = -n * ln(p) / (ln(2))^2
        let m = (-(num_elementos as f64) * taxa_falso_positivo.ln()
            / (2.0_f64.ln().powi(2)))
        .ceil() as usize;

        // k = (m / n) * ln(2)
        let k = ((m as f64 / num_elementos as f64) * 2.0_f64.ln()).ceil() as usize;

        BloomFilter::novo(m.max(1), k.max(1))
    }

    /// Gera k posições de hash para um dado item.
    /// Usa a técnica de double hashing: h(i) = h1 + i * h2
    fn posicoes_hash<T: Hash>(&self, item: &T) -> Vec<usize> {
        let mut posicoes = Vec::with_capacity(self.num_hashes);

        // Hash primário
        let mut hasher1 = DefaultHasher::new();
        item.hash(&mut hasher1);
        let h1 = hasher1.finish();

        // Hash secundário (usa seed diferente)
        let mut hasher2 = DefaultHasher::new();
        item.hash(&mut hasher2);
        // Perturba com uma constante para obter hash diferente
        (h1.wrapping_mul(6364136223846793005)).hash(&mut hasher2);
        let h2 = hasher2.finish();

        for i in 0..self.num_hashes {
            let pos = h1.wrapping_add((i as u64).wrapping_mul(h2)) % self.tamanho as u64;
            posicoes.push(pos as usize);
        }

        posicoes
    }

    /// Insere um elemento no Bloom Filter.
    fn inserir<T: Hash>(&mut self, item: &T) {
        for pos in self.posicoes_hash(item) {
            self.bits[pos] = true;
        }
        self.contagem += 1;
    }

    /// Consulta se um elemento POSSIVELMENTE pertence ao conjunto.
    /// - Retorna false: DEFINITIVAMENTE não está no conjunto.
    /// - Retorna true: PROVAVELMENTE está no conjunto (pode ser falso positivo).
    fn possivelmente_contem<T: Hash>(&self, item: &T) -> bool {
        self.posicoes_hash(item).iter().all(|&pos| self.bits[pos])
    }

    /// Calcula a taxa teórica de falsos positivos com base no estado atual.
    fn taxa_falso_positivo_estimada(&self) -> f64 {
        let m = self.tamanho as f64;
        let k = self.num_hashes as f64;
        let n = self.contagem as f64;
        (1.0 - (-k * n / m).exp()).powf(k)
    }

    /// Retorna a proporção de bits definidos como 1.
    fn ocupacao(&self) -> f64 {
        let definidos = self.bits.iter().filter(|&&b| b).count();
        definidos as f64 / self.tamanho as f64
    }

    /// Exibe o estado interno do Bloom Filter (para fins didáticos).
    fn exibir_estado(&self) {
        println!("Bloom Filter: {} bits, {} hashes, {} elementos",
            self.tamanho, self.num_hashes, self.contagem);
        println!("Ocupação: {:.1}%", self.ocupacao() * 100.0);
        println!("Taxa estimada de falso positivo: {:.4}%",
            self.taxa_falso_positivo_estimada() * 100.0);

        if self.tamanho <= 64 {
            let visual: String = self.bits
                .iter()
                .map(|&b| if b { '█' } else { '░' })
                .collect();
            println!("Bits: [{}]", visual);
        }
    }
}

/// Versão otimizada que usa bits reais em vez de Vec<bool>
/// (cada bool ocupa 1 byte; com bitvec, cada bit ocupa 1 bit)
struct BloomFilterCompacto {
    bits: Vec<u64>,       // Cada u64 armazena 64 bits
    tamanho_bits: usize,  // Total de bits
    num_hashes: usize,
    contagem: usize,
}

impl BloomFilterCompacto {
    fn novo(tamanho_bits: usize, num_hashes: usize) -> Self {
        let num_palavras = (tamanho_bits + 63) / 64; // Arredonda para cima
        BloomFilterCompacto {
            bits: vec![0u64; num_palavras],
            tamanho_bits,
            num_hashes,
            contagem: 0,
        }
    }

    /// Define o bit na posição especificada
    fn definir_bit(&mut self, pos: usize) {
        let palavra = pos / 64;
        let bit = pos % 64;
        self.bits[palavra] |= 1u64 << bit;
    }

    /// Verifica se o bit na posição especificada está definido
    fn obter_bit(&self, pos: usize) -> bool {
        let palavra = pos / 64;
        let bit = pos % 64;
        (self.bits[palavra] >> bit) & 1 == 1
    }

    fn posicoes_hash<T: Hash>(&self, item: &T) -> Vec<usize> {
        let mut hasher = DefaultHasher::new();
        item.hash(&mut hasher);
        let h1 = hasher.finish();

        let mut hasher2 = DefaultHasher::new();
        h1.wrapping_mul(0x517cc1b727220a95).hash(&mut hasher2);
        let h2 = hasher2.finish();

        (0..self.num_hashes)
            .map(|i| {
                (h1.wrapping_add((i as u64).wrapping_mul(h2)) % self.tamanho_bits as u64) as usize
            })
            .collect()
    }

    fn inserir<T: Hash>(&mut self, item: &T) {
        for pos in self.posicoes_hash(item) {
            self.definir_bit(pos);
        }
        self.contagem += 1;
    }

    fn possivelmente_contem<T: Hash>(&self, item: &T) -> bool {
        self.posicoes_hash(item).iter().all(|&pos| self.obter_bit(pos))
    }
}

use std::collections::hash_map::DefaultHasher;
use std::collections::HashSet;
use std::hash::{Hash, Hasher};

/// Bloom Filter (reutilizando a implementação anterior)
struct BloomFilter {
    bits: Vec<bool>,
    tamanho: usize,
    num_hashes: usize,
    contagem: usize,
}

impl BloomFilter {
    fn novo(tamanho_bits: usize, num_hashes: usize) -> Self {
        BloomFilter {
            bits: vec![false; tamanho_bits],
            tamanho: tamanho_bits,
            num_hashes,
            contagem: 0,
        }
    }

    fn posicoes_hash<T: Hash>(&self, item: &T) -> Vec<usize> {
        let mut hasher = DefaultHasher::new();
        item.hash(&mut hasher);
        let h1 = hasher.finish();
        let mut hasher2 = DefaultHasher::new();
        h1.wrapping_mul(0x517cc1b727220a95).hash(&mut hasher2);
        let h2 = hasher2.finish();
        (0..self.num_hashes)
            .map(|i| (h1.wrapping_add((i as u64).wrapping_mul(h2)) % self.tamanho as u64) as usize)
            .collect()
    }

    fn inserir<T: Hash>(&mut self, item: &T) {
        for pos in self.posicoes_hash(item) {
            self.bits[pos] = true;
        }
        self.contagem += 1;
    }

    fn possivelmente_contem<T: Hash>(&self, item: &T) -> bool {
        self.posicoes_hash(item).iter().all(|&pos| self.bits[pos])
    }
}

/// Simulação de um web crawler com deduplicação por Bloom Filter.
struct WebCrawler {
    /// Bloom Filter para verificação rápida (pode ter falsos positivos)
    filtro: BloomFilter,
    /// Fila de URLs a serem processadas
    fila: Vec<String>,
    /// URLs processadas com sucesso
    processadas: usize,
    /// URLs ignoradas pelo filtro (possivelmente duplicadas)
    ignoradas: usize,
}

impl WebCrawler {
    fn novo(urls_esperadas: usize) -> Self {
        // 10 bits por URL, 7 funções hash -> ~0.82% de falso positivo
        let tamanho = urls_esperadas * 10;
        WebCrawler {
            filtro: BloomFilter::novo(tamanho, 7),
            fila: Vec::new(),
            processadas: 0,
            ignoradas: 0,
        }
    }

    /// Adiciona uma URL à fila se ela provavelmente não foi visitada
    fn adicionar_url(&mut self, url: &str) {
        if self.filtro.possivelmente_contem(&url) {
            self.ignoradas += 1;
            // URL provavelmente já foi visitada (ou falso positivo)
        } else {
            self.filtro.inserir(&url);
            self.fila.push(url.to_string());
        }
    }

    /// Processa a próxima URL da fila
    fn processar_proxima(&mut self) -> Option<String> {
        if let Some(url) = self.fila.pop() {
            self.processadas += 1;
            Some(url)
        } else {
            None
        }
    }

    /// Exibe estatísticas do crawler
    fn estatisticas(&self) {
        println!("╔═══════════════════════════════════════╗");
        println!("║     Estatísticas do Web Crawler       ║");
        println!("╠═══════════════════════════════════════╣");
        println!("║ URLs processadas:   {:>6}             ║", self.processadas);
        println!("║ URLs na fila:       {:>6}             ║", self.fila.len());
        println!("║ URLs ignoradas:     {:>6}             ║", self.ignoradas);
        println!("║ Memória do filtro:  {:>6} bits        ║", self.filtro.tamanho);
        println!("╚═══════════════════════════════════════╝");
    }
}

fn main() {
    // === Web Crawler ===
    println!("=== Simulação de Web Crawler ===\n");

    let mut crawler = WebCrawler::novo(10_000);

    // Simulando descoberta de URLs (com duplicatas)
    let urls = vec![
        "https://rustlang.com.br/",
        "https://rustlang.com.br/tutoriais/",
        "https://rustlang.com.br/blog/",
        "https://rustlang.com.br/tutoriais/", // duplicata
        "https://rustlang.com.br/",           // duplicata
        "https://doc.rust-lang.org/",
        "https://crates.io/",
        "https://rustlang.com.br/blog/",      // duplicata
        "https://docs.rs/",
        "https://crates.io/",                 // duplicata
    ];

    for url in &urls {
        println!("Tentando adicionar: {}", url);
        crawler.adicionar_url(url);
    }

    println!();
    crawler.estatisticas();

    // Processando a fila
    println!("\nProcessando URLs:");
    while let Some(url) = crawler.processar_proxima() {
        println!("  Processando: {}", url);
    }

    // === Verificador de palavras (spell checker) ===
    println!("\n=== Verificador Ortográfico Simples ===\n");

    // Dicionário com 100k palavras -> Bloom Filter com ~120KB
    let mut dicionario = BloomFilter::novo(1_000_000, 7);

    // Simulando inserção de um dicionário
    let palavras_validas = vec![
        "rust", "programação", "linguagem", "sistema",
        "memória", "segurança", "concorrência", "compilador",
        "variável", "função", "struct", "enum", "trait",
    ];

    for palavra in &palavras_validas {
        dicionario.inserir(palavra);
    }

    // Verificando palavras
    let texto_teste = vec![
        "rust", "progrmaação", "linguagem", "sistma",
        "memória", "segurnça", "xyz123",
    ];

    for palavra in &texto_teste {
        let existe = dicionario.possivelmente_contem(palavra);
        let status = if existe { "OK" } else { "ERRO?" };
        println!("  {:20} -> {}", palavra, status);
    }

    // === Comparação de memória ===
    println!("\n=== Comparação de Memória ===");
    println!("Para 1 milhão de strings (média 20 bytes):");
    println!("  HashSet: ~48 MB (string + hash + ponteiros)");
    println!("  Bloom Filter (1% erro): ~1.2 MB (apenas bits)");
    println!("  Economia: ~97.5% de memória!");
}

struct CountingBloomFilter {
    contadores: Vec<u8>,
    tamanho: usize,
    num_hashes: usize,
}

impl CountingBloomFilter {
    fn novo(tamanho: usize, num_hashes: usize) -> Self { todo!() }
    fn inserir<T: Hash>(&mut self, item: &T) { todo!() }
    fn remover<T: Hash>(&mut self, item: &T) { todo!() }
    fn possivelmente_contem<T: Hash>(&self, item: &T) -> bool { todo!() }
}

fn medir_falsos_positivos() -> (f64, f64) {
    // Retorna (taxa_empirica, taxa_teorica)
    todo!()
}

struct ScalableBloomFilter {
    filtros: Vec<BloomFilter>,
    taxa_erro_alvo: f64,
    elementos_por_filtro: usize,
}

impl ScalableBloomFilter {
    fn novo(taxa_erro: f64, capacidade_inicial: usize) -> Self { todo!() }
    fn inserir<T: Hash>(&mut self, item: &T) { todo!() }
    fn possivelmente_contem<T: Hash>(&self, item: &T) -> bool { todo!() }
}