LFU Cache em Rust: Implementação com Evição por Frequência em O(1)

use std::collections::{HashMap, VecDeque};

/// LFU Cache com operações O(1) para get e put.
///
/// Combina dois HashMaps e buckets de frequência com VecDeque
/// para manter a ordem de inserção (desempate LRU).
pub struct LfuCache<K, V>
where
    K: Eq + std::hash::Hash + Clone,
{
    /// Capacidade máxima do cache.
    capacidade: usize,
    /// Frequência mínima atual (para evição O(1)).
    freq_minima: usize,
    /// HashMap principal: chave -> (valor, frequência).
    dados: HashMap<K, (V, usize)>,
    /// Buckets de frequência: frequência -> fila de chaves.
    /// A fila mantém a ordem de inserção para desempate LRU.
    buckets: HashMap<usize, VecDeque<K>>,
}

impl<K, V> LfuCache<K, V>
where
    K: Eq + std::hash::Hash + Clone + std::fmt::Debug,
    V: Clone,
{
    /// Cria um novo LFU Cache com a capacidade especificada.
    pub fn novo(capacidade: usize) -> Self {
        LfuCache {
            capacidade,
            freq_minima: 0,
            dados: HashMap::with_capacity(capacidade),
            buckets: HashMap::new(),
        }
    }

    /// Busca o valor associado à chave.
    /// Incrementa a frequência de acesso do item.
    /// Retorna None se a chave não existir.
    pub fn get(&mut self, chave: &K) -> Option<&V> {
        if !self.dados.contains_key(chave) {
            return None;
        }

        // Obtém a frequência atual
        let freq_atual = self.dados.get(chave).unwrap().1;
        let nova_freq = freq_atual + 1;

        // Remove do bucket de frequência atual
        self.remover_do_bucket(chave, freq_atual);

        // Se o bucket da freq_minima ficou vazio, incrementa freq_minima
        if freq_atual == self.freq_minima
            && self
                .buckets
                .get(&freq_atual)
                .map_or(true, |b| b.is_empty())
        {
            self.freq_minima += 1;
        }

        // Insere no bucket da nova frequência
        self.buckets
            .entry(nova_freq)
            .or_insert_with(VecDeque::new)
            .push_back(chave.clone());

        // Atualiza a frequência no HashMap principal
        self.dados.get_mut(chave).unwrap().1 = nova_freq;

        // Retorna referência ao valor
        Some(&self.dados.get(chave).unwrap().0)
    }

    /// Insere ou atualiza um par chave-valor.
    /// Se a capacidade for excedida, evicta o item com menor frequência
    /// (desempate: o mais antigo entre os de mesma frequência).
    pub fn put(&mut self, chave: K, valor: V) {
        if self.capacidade == 0 {
            return;
        }

        // Caso 1: chave já existe — atualiza valor e incrementa frequência
        if self.dados.contains_key(&chave) {
            // Atualiza o valor
            self.dados.get_mut(&chave).unwrap().0 = valor;
            // Incrementa frequência (reutiliza lógica do get)
            let freq_atual = self.dados.get(&chave).unwrap().1;
            let nova_freq = freq_atual + 1;

            self.remover_do_bucket(&chave, freq_atual);

            if freq_atual == self.freq_minima
                && self
                    .buckets
                    .get(&freq_atual)
                    .map_or(true, |b| b.is_empty())
            {
                self.freq_minima += 1;
            }

            self.buckets
                .entry(nova_freq)
                .or_insert_with(VecDeque::new)
                .push_back(chave.clone());
            self.dados.get_mut(&chave).unwrap().1 = nova_freq;
            return;
        }

        // Caso 2: chave nova — verifica capacidade
        if self.dados.len() >= self.capacidade {
            // Evicta o item com menor frequência (mais antigo no bucket)
            self.evictar();
        }

        // Insere nova entrada com frequência 1
        self.dados.insert(chave.clone(), (valor, 1));
        self.buckets
            .entry(1)
            .or_insert_with(VecDeque::new)
            .push_back(chave);
        self.freq_minima = 1;
    }

    /// Remove o item com menor frequência (evição).
    fn evictar(&mut self) {
        if let Some(bucket) = self.buckets.get_mut(&self.freq_minima) {
            if let Some(chave_evicta) = bucket.pop_front() {
                self.dados.remove(&chave_evicta);
            }
        }
    }

    /// Remove uma chave de um bucket de frequência específico.
    fn remover_do_bucket(&mut self, chave: &K, freq: usize) {
        if let Some(bucket) = self.buckets.get_mut(&freq) {
            if let Some(pos) = bucket.iter().position(|k| k == chave) {
                bucket.remove(pos);
            }
        }
    }

    /// Retorna o número de itens no cache.
    pub fn len(&self) -> usize {
        self.dados.len()
    }

    /// Verifica se o cache está vazio.
    pub fn esta_vazio(&self) -> bool {
        self.dados.is_empty()
    }

    /// Retorna a frequência de acesso de uma chave (sem incrementar).
    pub fn frequencia(&self, chave: &K) -> Option<usize> {
        self.dados.get(chave).map(|(_, freq)| *freq)
    }

    /// Exibe o estado interno do cache para depuração.
    pub fn debug_estado(&self) {
        println!("LFU Cache (cap={}, len={}, freq_min={}):",
            self.capacidade, self.dados.len(), self.freq_minima);
        println!("  Dados:");
        for (chave, (_, freq)) in &self.dados {
            println!("    {:?} -> freq={}", chave, freq);
        }
        println!("  Buckets:");
        let mut freqs: Vec<_> = self.buckets.keys().collect();
        freqs.sort();
        for freq in freqs {
            if let Some(bucket) = self.buckets.get(freq) {
                if !bucket.is_empty() {
                    let marcador = if *freq == self.freq_minima {
                        " <-- freq_minima (evição aqui)"
                    } else {
                        ""
                    };
                    println!("    freq={}: {:?}{}", freq, bucket, marcador);
                }
            }
        }
    }
}

fn main() {
    println!("=== Demonstração do LFU Cache ===\n");

    let mut cache = LfuCache::novo(3);

    // Inserções iniciais
    cache.put("A", "dados_A");
    cache.put("B", "dados_B");
    cache.put("C", "dados_C");

    // Acessos variados para criar frequências diferentes
    // A: 3 acessos, B: 2 acessos, C: 1 acesso
    cache.get(&"A");
    cache.get(&"A");
    cache.get(&"B");

    println!("Estado após acessos variados:");
    cache.debug_estado();

    // Inserir D — deve evictar C (menor frequência)
    println!("\nInserindo D (capacidade excedida)...");
    cache.put("D", "dados_D");

    println!("C evicado (freq=1): {}", cache.get(&"C").is_none());
    println!("A permanece (freq=3): {}", cache.get(&"A").is_some());
    println!("B permanece (freq=2): {}", cache.get(&"B").is_some());

    println!("\nEstado após evição:");
    cache.debug_estado();

    // Demonstração de desempate LRU
    println!("\n--- Desempate por recência ---");
    let mut cache2 = LfuCache::novo(3);
    cache2.put("X", 1);
    cache2.put("Y", 2);
    cache2.put("Z", 3);
    // Todos com frequência 1, X é o mais antigo

    println!("Todos com freq=1:");
    cache2.debug_estado();

    cache2.put("W", 4); // Deve evictar X (mais antigo com freq=1)
    println!("\nApós inserir W:");
    println!("X evicado (mais antigo com freq=1): {}", cache2.get(&"X").is_none());
    cache2.debug_estado();
}

use std::collections::HashMap;
use std::time::Instant;

/// Tipo de conteúdo servido pela CDN.
#[derive(Debug, Clone)]
enum TipoConteudo {
    Imagem,
    JavaScript,
    Css,
    Html,
    Video,
    Api,
}

impl TipoConteudo {
    fn tamanho_medio_kb(&self) -> u64 {
        match self {
            TipoConteudo::Imagem => 200,
            TipoConteudo::JavaScript => 150,
            TipoConteudo::Css => 30,
            TipoConteudo::Html => 15,
            TipoConteudo::Video => 5000,
            TipoConteudo::Api => 5,
        }
    }
}

/// Entrada no cache da CDN.
#[derive(Debug, Clone)]
struct ConteudoCdn {
    url: String,
    tipo: TipoConteudo,
    tamanho_kb: u64,
    corpo: String, // Simulado
}

/// Estatísticas do cache CDN.
#[derive(Debug, Default)]
struct EstatisticasCdn {
    total_requisicoes: u64,
    acertos_cache: u64,
    erros_cache: u64,
    bytes_servidos_cache: u64,
    bytes_servidos_origem: u64,
    evicoes: u64,
}

impl EstatisticasCdn {
    fn taxa_acerto(&self) -> f64 {
        if self.total_requisicoes == 0 {
            return 0.0;
        }
        (self.acertos_cache as f64 / self.total_requisicoes as f64) * 100.0
    }

    fn economia_banda(&self) -> f64 {
        let total = self.bytes_servidos_cache + self.bytes_servidos_origem;
        if total == 0 {
            return 0.0;
        }
        (self.bytes_servidos_cache as f64 / total as f64) * 100.0
    }

    fn exibir(&self) {
        println!("\n  === Estatísticas da CDN ===");
        println!("  Requisições totais:    {}", self.total_requisicoes);
        println!("  Acertos (cache hit):   {}", self.acertos_cache);
        println!("  Erros (cache miss):    {}", self.erros_cache);
        println!("  Taxa de acerto:        {:.1}%", self.taxa_acerto());
        println!("  Economia de banda:     {:.1}%", self.economia_banda());
        println!("  Evições realizadas:    {}", self.evicoes);
        println!(
            "  Bytes servidos cache:  {} KB",
            self.bytes_servidos_cache
        );
        println!(
            "  Bytes servidos origem: {} KB",
            self.bytes_servidos_origem
        );
    }
}

/// Cache CDN usando política LFU.
struct CacheCdn {
    capacidade: usize,
    itens: HashMap<String, (ConteudoCdn, usize)>, // url -> (conteudo, frequencia)
    frequencias: HashMap<usize, Vec<String>>,       // freq -> lista de urls
    freq_minima: usize,
    stats: EstatisticasCdn,
}

impl CacheCdn {
    fn novo(capacidade: usize) -> Self {
        CacheCdn {
            capacidade,
            itens: HashMap::new(),
            frequencias: HashMap::new(),
            freq_minima: 0,
            stats: EstatisticasCdn::default(),
        }
    }

    /// Processa uma requisição HTTP.
    fn requisicao(&mut self, url: &str, tipo: TipoConteudo) -> bool {
        self.stats.total_requisicoes += 1;

        if self.itens.contains_key(url) {
            // Cache HIT
            self.stats.acertos_cache += 1;
            let tamanho = self.itens.get(url).unwrap().0.tamanho_kb;
            self.stats.bytes_servidos_cache += tamanho;

            // Incrementa frequência
            let freq_atual = self.itens.get(url).unwrap().1;
            let nova_freq = freq_atual + 1;

            // Remove do bucket antigo
            if let Some(bucket) = self.frequencias.get_mut(&freq_atual) {
                bucket.retain(|u| u != url);
                if bucket.is_empty() && freq_atual == self.freq_minima {
                    self.freq_minima += 1;
                }
            }

            // Adiciona ao novo bucket
            self.frequencias
                .entry(nova_freq)
                .or_insert_with(Vec::new)
                .push(url.to_string());
            self.itens.get_mut(url).unwrap().1 = nova_freq;

            true
        } else {
            // Cache MISS — busca na origem e armazena
            self.stats.erros_cache += 1;
            let tamanho = tipo.tamanho_medio_kb();
            self.stats.bytes_servidos_origem += tamanho;

            let conteudo = ConteudoCdn {
                url: url.to_string(),
                tipo,
                tamanho_kb: tamanho,
                corpo: format!("[conteúdo de {}]", url),
            };

            // Evicta se necessário
            if self.itens.len() >= self.capacidade {
                self.evictar();
            }

            // Insere com frequência 1
            self.frequencias
                .entry(1)
                .or_insert_with(Vec::new)
                .push(url.to_string());
            self.itens.insert(url.to_string(), (conteudo, 1));
            self.freq_minima = 1;

            false
        }
    }

    fn evictar(&mut self) {
        if let Some(bucket) = self.frequencias.get_mut(&self.freq_minima) {
            if let Some(url_evicta) = bucket.first().cloned() {
                bucket.retain(|u| u != &url_evicta);
                self.itens.remove(&url_evicta);
                self.stats.evicoes += 1;
            }
        }
    }

    fn exibir_cache(&self) {
        println!("\n  Conteúdo em cache ({}/{}):", self.itens.len(), self.capacidade);
        let mut itens: Vec<_> = self.itens.iter().collect();
        itens.sort_by(|a, b| b.1 .1.cmp(&a.1 .1)); // Ordena por frequência
        for (url, (conteudo, freq)) in itens {
            println!(
                "    freq={:3} | {:6} KB | {:?} | {}",
                freq, conteudo.tamanho_kb, conteudo.tipo, url
            );
        }
    }
}

fn main() {
    println!("=== Simulação de Cache CDN com LFU ===\n");

    let mut cdn = CacheCdn::novo(5);

    // Simula padrão de tráfego realista
    // Conteúdo popular (acessado muitas vezes)
    let requisicoes = vec![
        ("/img/logo.png", TipoConteudo::Imagem, 20),     // Popular
        ("/css/main.css", TipoConteudo::Css, 15),         // Popular
        ("/js/app.js", TipoConteudo::JavaScript, 10),     // Moderado
        ("/api/dados", TipoConteudo::Api, 5),             // Pouco popular
        ("/index.html", TipoConteudo::Html, 3),           // Pouco popular
        ("/video/intro.mp4", TipoConteudo::Video, 2),     // Raro
        ("/img/banner.png", TipoConteudo::Imagem, 1),     // Único
        ("/img/promo.png", TipoConteudo::Imagem, 1),      // Único
    ];

    println!("Simulando tráfego web...\n");

    for (url, tipo, repeticoes) in &requisicoes {
        for _ in 0..*repeticoes {
            let acertou = cdn.requisicao(url, tipo.clone());
            // Apenas exibe os primeiros acessos
        }
        let freq = cdn.itens.get(*url).map(|(_, f)| *f).unwrap_or(0);
        println!(
            "  {} -> {} acessos (freq no cache: {})",
            url, repeticoes, freq
        );
    }

    cdn.exibir_cache();
    cdn.stats.exibir();

    // Mostra que conteúdo popular sobrevive a rajadas
    println!("\n--- Rajada de conteúdo novo ---");
    for i in 0..5 {
        let url = format!("/api/temp/{}", i);
        cdn.requisicao(&url, TipoConteudo::Api);
    }

    println!("\nApós rajada de 5 URLs únicos:");
    cdn.exibir_cache();
    println!(
        "\n  /img/logo.png ainda no cache: {}",
        cdn.itens.contains_key("/img/logo.png")
    );
    println!(
        "  /css/main.css ainda no cache: {}",
        cdn.itens.contains_key("/css/main.css")
    );
}