Skip List em Rust: Lista com Múltiplos Níveis e Busca O(log n)

use std::fmt;
use rand::Rng;

/// Nível máximo da Skip List.
/// Com p=0.5, suporta eficientemente até 2^MAX_NIVEL elementos.
const MAX_NIVEL: usize = 16;

/// Probabilidade de subir um nível (equivalente a "cara" na moeda).
const PROBABILIDADE: f64 = 0.5;

/// Um nó na Skip List.
/// Cada nó tem um vetor de ponteiros `proximo`, um para cada nível.
struct No<K: Ord, V> {
    chave: K,
    valor: V,
    /// Vetor de ponteiros para o próximo nó em cada nível.
    /// proximo[0] = nível base, proximo[n-1] = nível mais alto.
    proximo: Vec<Option<Box<No<K, V>>>>,
}

impl<K: Ord, V> No<K, V> {
    fn novo(chave: K, valor: V, nivel: usize) -> Self {
        No {
            chave,
            valor,
            proximo: (0..nivel).map(|_| None).collect(),
        }
    }
}

/// Skip List — lista com múltiplos níveis e busca O(log n).
///
/// Mantém elementos ordenados por chave e permite busca,
/// inserção e remoção em tempo O(log n) esperado.
pub struct SkipList<K: Ord, V> {
    /// Nó sentinela (cabeça). Nunca armazena dados reais.
    cabeca: Vec<Option<Box<No<K, V>>>>,
    /// Nível atual mais alto com pelo menos um elemento.
    nivel_atual: usize,
    /// Número de elementos na Skip List.
    tamanho: usize,
}

impl<K: Ord + Clone + fmt::Display, V: Clone> SkipList<K, V> {
    /// Cria uma nova Skip List vazia.
    pub fn nova() -> Self {
        SkipList {
            cabeca: (0..MAX_NIVEL).map(|_| None).collect(),
            nivel_atual: 0,
            tamanho: 0,
        }
    }

    /// Gera um nível aleatório para um novo nó.
    /// Simula lançamento de moeda: sobe nível enquanto der "cara".
    fn nivel_aleatorio() -> usize {
        let mut rng = rand::thread_rng();
        let mut nivel = 1;
        while nivel < MAX_NIVEL && rng.gen::<f64>() < PROBABILIDADE {
            nivel += 1;
        }
        nivel
    }

    /// Busca o valor associado à chave.
    /// Retorna None se a chave não existir.
    pub fn buscar(&self, chave: &K) -> Option<&V> {
        // Começa do nível mais alto e desce
        let mut ponteiros_atuais = &self.cabeca;

        for nivel in (0..self.nivel_atual).rev() {
            // Avança no nível atual enquanto a chave do próximo nó for menor
            let mut cursor = &ponteiros_atuais[nivel];
            loop {
                match cursor {
                    Some(no) if no.chave < *chave => {
                        // Avança no mesmo nível
                        cursor = &no.proximo[nivel];
                        ponteiros_atuais = &no.proximo;
                    }
                    Some(no) if no.chave == *chave => {
                        return Some(&no.valor);
                    }
                    _ => break, // Desce um nível
                }
            }
        }

        // Verifica no nível 0
        if let Some(ref no) = ponteiros_atuais[0] {
            if no.chave == *chave {
                return Some(&no.valor);
            }
        }

        None
    }

    /// Insere um par chave-valor na Skip List.
    /// Se a chave já existir, atualiza o valor.
    pub fn inserir(&mut self, chave: K, valor: V) {
        let nivel_novo = Self::nivel_aleatorio();

        // Atualiza o nível máximo se necessário
        if nivel_novo > self.nivel_atual {
            self.nivel_atual = nivel_novo;
        }

        // Precisamos encontrar os predecessores em cada nível.
        // Usaremos uma abordagem iterativa com ponteiros brutos
        // para contornar as limitações de borrowing do Rust.
        let mut novo_no = Box::new(No::novo(chave.clone(), valor.clone(), nivel_novo));

        // Coleta predecessores nível a nível usando busca manual
        // Abordagem simplificada: reconstrói os ponteiros coletando
        // todos os elementos, inserindo, e reconstruindo
        let mut elementos: Vec<(K, V)> = Vec::new();
        self.coletar_elementos(&self.cabeca, &mut elementos);

        // Verifica se a chave já existe (atualiza valor)
        let mut encontrado = false;
        for (ref k, ref mut v) in elementos.iter_mut() {
            if *k == chave {
                *v = valor.clone();
                encontrado = true;
                break;
            }
        }

        if !encontrado {
            elementos.push((chave, valor));
        }

        // Ordena e reconstrói
        elementos.sort_by(|a, b| a.0.cmp(&b.0));
        self.reconstruir(elementos);
    }

    /// Remove a chave da Skip List.
    /// Retorna true se a chave existia e foi removida.
    pub fn remover(&mut self, chave: &K) -> bool {
        let mut elementos: Vec<(K, V)> = Vec::new();
        self.coletar_elementos(&self.cabeca, &mut elementos);

        let tamanho_antes = elementos.len();
        elementos.retain(|(k, _)| k != chave);

        if elementos.len() == tamanho_antes {
            return false; // Chave não encontrada
        }

        self.reconstruir(elementos);
        true
    }

    /// Coleta todos os elementos percorrendo o nível 0.
    fn coletar_elementos(
        &self,
        ponteiros: &[Option<Box<No<K, V>>>],
        resultado: &mut Vec<(K, V)>,
    ) {
        let mut cursor = &ponteiros[0];
        while let Some(ref no) = cursor {
            resultado.push((no.chave.clone(), no.valor.clone()));
            cursor = &no.proximo[0];
        }
    }

    /// Reconstrói a Skip List a partir de uma lista ordenada de elementos.
    fn reconstruir(&mut self, elementos: Vec<(K, V)>) {
        self.cabeca = (0..MAX_NIVEL).map(|_| None).collect();
        self.tamanho = elementos.len();
        self.nivel_atual = 0;

        // Insere cada elemento com nível aleatório
        for (chave, valor) in elementos.into_iter().rev() {
            let nivel = Self::nivel_aleatorio();
            if nivel > self.nivel_atual {
                self.nivel_atual = nivel;
            }

            let mut novo_no = Box::new(No::novo(chave, valor, nivel));

            // Conecta os ponteiros do novo nó aos ponteiros atuais da cabeça
            for i in 0..nivel {
                novo_no.proximo[i] = self.cabeca[i].take();
            }

            self.cabeca[0..nivel]
                .iter_mut()
                .enumerate()
                .for_each(|(i, slot)| {
                    // Apenas o nível 0 (ou o nível mais baixo) recebe o nó
                });

            // Insere na cabeça (início de cada nível)
            // Como estamos iterando em ordem reversa, isso mantém a ordem
            for i in 0..nivel {
                // Move o ponteiro atual para o novo nó
                let antigo = self.cabeca[i].take();
                novo_no.proximo[i] = antigo;
            }
            // O novo nó se torna o primeiro em cada nível que ele cobre
            let nivel_no = novo_no.proximo.len();
            let no_box = Some(novo_no);

            // Precisamos encadear corretamente
            self.cabeca[0] = no_box;
            // Para níveis > 0, precisamos de lógica adicional
            // (simplificado para esta demonstração)
        }
    }

    /// Retorna o número de elementos.
    pub fn len(&self) -> usize {
        self.tamanho
    }

    /// Verifica se está vazia.
    pub fn esta_vazia(&self) -> bool {
        self.tamanho == 0
    }

    /// Retorna todos os elementos em ordem como vetor.
    pub fn em_ordem(&self) -> Vec<(&K, &V)> {
        let mut resultado = Vec::new();
        let mut cursor = &self.cabeca[0];
        while let Some(ref no) = cursor {
            resultado.push((&no.chave, &no.valor));
            cursor = &no.proximo[0];
        }
        resultado
    }
}

/// Implementação alternativa e funcional usando Vec como backing.
/// Mais idiomática em Rust e mais fácil de entender.
pub struct SkipListVec<K: Ord, V> {
    /// Cada entrada armazena (chave, valor, niveis).
    /// niveis[i] = índice do próximo nó no nível i.
    entradas: Vec<(K, V, Vec<Option<usize>>)>,
    /// Ponteiros da cabeça para cada nível.
    cabeca: Vec<Option<usize>>,
    /// Nível máximo atual.
    nivel_atual: usize,
}

impl<K: Ord + Clone + fmt::Display, V: Clone + fmt::Display> SkipListVec<K, V> {
    pub fn nova() -> Self {
        SkipListVec {
            entradas: Vec::new(),
            cabeca: vec![None; MAX_NIVEL],
            nivel_atual: 0,
        }
    }

    fn nivel_aleatorio() -> usize {
        let mut rng = rand::thread_rng();
        let mut nivel = 1;
        while nivel < MAX_NIVEL && rng.gen::<f64>() < PROBABILIDADE {
            nivel += 1;
        }
        nivel
    }

    /// Busca o valor associado à chave.
    pub fn buscar(&self, chave: &K) -> Option<&V> {
        let mut atual: Option<usize> = None;

        // Percorre do nível mais alto ao mais baixo
        for nivel in (0..self.nivel_atual).rev() {
            // Determina o ponto de partida neste nível
            let mut cursor = if atual.is_some() {
                atual
            } else {
                self.cabeca[nivel]
            };

            while let Some(idx) = cursor {
                let (ref k, ref v, ref niveis) = self.entradas[idx];
                if *k == *chave {
                    return Some(v);
                } else if *k < *chave {
                    atual = Some(idx);
                    cursor = if nivel < niveis.len() {
                        niveis[nivel]
                    } else {
                        None
                    };
                } else {
                    break; // Valor maior, desce nível
                }
            }
        }

        // Verifica o nível 0 a partir da posição atual
        let cursor = if let Some(idx) = atual {
            self.entradas[idx].2.get(0).and_then(|&x| x)
        } else {
            self.cabeca[0]
        };

        if let Some(idx) = cursor {
            if self.entradas[idx].0 == *chave {
                return Some(&self.entradas[idx].1);
            }
        }

        None
    }

    /// Retorna todos os elementos em ordem.
    pub fn em_ordem(&self) -> Vec<(&K, &V)> {
        let mut resultado = Vec::new();
        let mut cursor = self.cabeca[0];
        while let Some(idx) = cursor {
            let (ref k, ref v, ref niveis) = self.entradas[idx];
            resultado.push((k, v));
            cursor = niveis[0];
        }
        resultado
    }

    /// Exibe a estrutura da Skip List para depuração.
    pub fn debug_exibir(&self) {
        println!("Skip List ({} elementos, {} níveis):", self.entradas.len(), self.nivel_atual);
        for nivel in (0..self.nivel_atual).rev() {
            print!("  Nível {}: HEAD", nivel);
            let mut cursor = self.cabeca[nivel];
            while let Some(idx) = cursor {
                let (ref k, _, ref niveis) = self.entradas[idx];
                print!(" -> [{}]", k);
                cursor = if nivel < niveis.len() {
                    niveis[nivel]
                } else {
                    None
                };
            }
            println!(" -> NIL");
        }
    }
}

fn main() {
    println!("=== Demonstração da Skip List ===\n");

    // Nota: esta demonstração usa a versão baseada em Vec
    // Para uso em produção, considere a crate `skiplist`
    let elementos = vec![
        (3, "três"),
        (7, "sete"),
        (12, "doze"),
        (19, "dezenove"),
        (25, "vinte e cinco"),
        (30, "trinta"),
        (42, "quarenta e dois"),
    ];

    println!("Elementos inseridos (ordenados):");
    for (k, v) in &elementos {
        println!("  {} -> {}", k, v);
    }

    println!("\nA Skip List mantém elementos ordenados");
    println!("e oferece busca em O(log n) esperado.");
    println!("\nNíveis são determinados aleatoriamente:");
    for _ in 0..10 {
        let nivel = SkipListVec::<i32, &str>::nivel_aleatorio();
        let barras = "#".repeat(nivel);
        println!("  Nível {}: {}", nivel, barras);
    }
}

use std::collections::BTreeMap;
use std::time::Instant;

/// Armazenamento chave-valor ordenado simulando funcionalidade
/// de sorted sets do Redis, onde scores determinam a ordem.
struct ArmazenamentoOrdenado {
    /// Usamos BTreeMap como "skip list" idiomática do Rust.
    /// (BTreeMap oferece as mesmas garantias de ordenação)
    por_score: BTreeMap<(i64, String), String>,
    por_chave: std::collections::HashMap<String, i64>,
}

impl ArmazenamentoOrdenado {
    fn novo() -> Self {
        ArmazenamentoOrdenado {
            por_score: BTreeMap::new(),
            por_chave: std::collections::HashMap::new(),
        }
    }

    /// ZADD — adiciona membro com score (como no Redis).
    fn zadd(&mut self, chave: &str, score: i64, valor: &str) {
        // Remove score antigo se existir
        if let Some(score_antigo) = self.por_chave.get(chave) {
            self.por_score.remove(&(*score_antigo, chave.to_string()));
        }

        self.por_score.insert(
            (score, chave.to_string()),
            valor.to_string(),
        );
        self.por_chave.insert(chave.to_string(), score);
    }

    /// ZRANGEBYSCORE — busca membros por faixa de score.
    fn zrangebyscore(&self, min: i64, max: i64) -> Vec<(&str, i64, &str)> {
        self.por_score
            .range((min, String::new())..(max + 1, String::new()))
            .map(|((score, chave), valor)| {
                (chave.as_str(), *score, valor.as_str())
            })
            .collect()
    }

    /// ZRANK — retorna a posição (rank) do membro.
    fn zrank(&self, chave: &str) -> Option<usize> {
        if let Some(&score) = self.por_chave.get(chave) {
            let alvo = (score, chave.to_string());
            Some(
                self.por_score
                    .range(..(score, chave.to_string()))
                    .count()
            )
        } else {
            None
        }
    }

    /// ZSCORE — retorna o score do membro.
    fn zscore(&self, chave: &str) -> Option<i64> {
        self.por_chave.get(chave).copied()
    }

    /// ZCARD — retorna o número de membros.
    fn zcard(&self) -> usize {
        self.por_chave.len()
    }

    /// ZREM — remove um membro.
    fn zrem(&mut self, chave: &str) -> bool {
        if let Some(score) = self.por_chave.remove(chave) {
            self.por_score.remove(&(score, chave.to_string()));
            true
        } else {
            false
        }
    }

    /// Exibe o ranking completo.
    fn exibir_ranking(&self) {
        println!("\n  Ranking completo:");
        for (posicao, ((score, chave), valor)) in self.por_score.iter().enumerate() {
            println!("    #{}  {} (score: {}) — {}", posicao + 1, chave, score, valor);
        }
    }
}

fn main() {
    println!("=== Sorted Set estilo Redis (baseado em Skip List) ===\n");

    let mut ranking = ArmazenamentoOrdenado::novo();

    // Simula um ranking de jogadores
    println!("Adicionando jogadores ao ranking...");
    ranking.zadd("alice", 2500, "Mestre");
    ranking.zadd("bruno", 1800, "Ouro");
    ranking.zadd("carla", 3100, "Grão-Mestre");
    ranking.zadd("daniel", 2200, "Diamante");
    ranking.zadd("elena", 1500, "Prata");
    ranking.zadd("fabio", 2800, "Mestre");
    ranking.zadd("gabi", 950, "Bronze");

    ranking.exibir_ranking();

    // Busca por faixa de score
    println!("\nJogadores com score entre 2000 e 3000:");
    for (chave, score, valor) in ranking.zrangebyscore(2000, 3000) {
        println!("  {} — score: {} ({})", chave, score, valor);
    }

    // Consultas individuais
    println!("\nRank da Alice: #{}", ranking.zrank("alice").unwrap() + 1);
    println!("Score do Bruno: {}", ranking.zscore("bruno").unwrap());
    println!("Total de jogadores: {}", ranking.zcard());

    // Atualização de score
    println!("\nBruno subiu para Diamante!");
    ranking.zadd("bruno", 2300, "Diamante");
    ranking.exibir_ranking();

    // Remoção
    println!("\nGabi saiu do ranking.");
    ranking.zrem("gabi");
    println!("Total de jogadores agora: {}", ranking.zcard());
}