Listas Ligadas em Rust: Desafios e Implementações

use std::fmt;

/// Tipo auxiliar para o ponteiro para o próximo nó
type Link<T> = Option<Box<No<T>>>;

/// Nó da lista ligada
#[derive(Debug)]
struct No<T> {
    valor: T,
    proximo: Link<T>,
}

/// Lista simplesmente ligada
#[derive(Debug)]
pub struct ListaLigada<T> {
    cabeca: Link<T>,
    tamanho: usize,
}

impl<T> ListaLigada<T> {
    /// Cria uma lista vazia
    pub fn nova() -> Self {
        ListaLigada {
            cabeca: None,
            tamanho: 0,
        }
    }

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

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

    /// Insere um elemento no início da lista — O(1)
    pub fn inserir_inicio(&mut self, valor: T) {
        let novo_no = Box::new(No {
            valor,
            // O novo nó assume a propriedade (ownership) da cabeça anterior
            proximo: self.cabeca.take(),
        });
        self.cabeca = Some(novo_no);
        self.tamanho += 1;
    }

    /// Remove e retorna o elemento do início da lista — O(1)
    pub fn remover_inicio(&mut self) -> Option<T> {
        // take() substitui self.cabeca por None e retorna o valor anterior
        self.cabeca.take().map(|no| {
            self.cabeca = no.proximo;
            self.tamanho -= 1;
            no.valor
        })
    }

    /// Retorna uma referência ao primeiro elemento — O(1)
    pub fn espiar(&self) -> Option<&T> {
        self.cabeca.as_ref().map(|no| &no.valor)
    }

    /// Retorna uma referência mutável ao primeiro elemento — O(1)
    pub fn espiar_mut(&mut self) -> Option<&mut T> {
        self.cabeca.as_mut().map(|no| &mut no.valor)
    }

    /// Insere um elemento no final da lista — O(n)
    pub fn inserir_final(&mut self, valor: T) {
        let novo_no = Box::new(No {
            valor,
            proximo: None,
        });

        // Caso especial: lista vazia
        if self.cabeca.is_none() {
            self.cabeca = Some(novo_no);
            self.tamanho += 1;
            return;
        }

        // Percorre até o último nó
        let mut atual = &mut self.cabeca;
        while let Some(ref mut no) = atual {
            if no.proximo.is_none() {
                no.proximo = Some(novo_no);
                self.tamanho += 1;
                return;
            }
            atual = &mut no.proximo;
        }
    }

    /// Verifica se a lista contém um determinado valor — O(n)
    pub fn contem(&self, alvo: &T) -> bool
    where
        T: PartialEq,
    {
        let mut atual = &self.cabeca;
        while let Some(ref no) = atual {
            if &no.valor == alvo {
                return true;
            }
            atual = &no.proximo;
        }
        false
    }

    /// Converte a lista em um Vec — O(n)
    pub fn para_vec(&self) -> Vec<&T> {
        let mut resultado = Vec::with_capacity(self.tamanho);
        let mut atual = &self.cabeca;
        while let Some(ref no) = atual {
            resultado.push(&no.valor);
            atual = &no.proximo;
        }
        resultado
    }
}

/// Implementação do iterador para consumir a lista
impl<T> Iterator for ListaLigada<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.remover_inicio()
    }
}

/// Implementação do Display para visualização
impl<T: fmt::Display> fmt::Display for ListaLigada<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut atual = &self.cabeca;
        write!(f, "[")?;
        let mut primeiro = true;
        while let Some(ref no) = atual {
            if !primeiro {
                write!(f, " → ")?;
            }
            write!(f, "{}", no.valor)?;
            primeiro = false;
            atual = &no.proximo;
        }
        write!(f, "]")
    }
}

/// Libera a memória iterativamente para evitar estouro de pilha
/// em listas muito grandes (o Drop padrão seria recursivo)
impl<T> Drop for ListaLigada<T> {
    fn drop(&mut self) {
        let mut link_atual = self.cabeca.take();
        while let Some(mut no) = link_atual {
            link_atual = no.proximo.take();
            // 'no' é descartado aqui sem recursão
        }
    }
}

fn main() {
    let mut lista = ListaLigada::nova();

    // Inserções no início
    lista.inserir_inicio(30);
    lista.inserir_inicio(20);
    lista.inserir_inicio(10);
    println!("Após inserções no início: {}", lista);

    // Inserção no final
    lista.inserir_final(40);
    lista.inserir_final(50);
    println!("Após inserções no final: {}", lista);

    // Espiar o primeiro elemento
    if let Some(primeiro) = lista.espiar() {
        println!("Primeiro elemento: {}", primeiro);
    }

    // Remover do início
    let removido = lista.remover_inicio();
    println!("Removido: {:?}", removido);
    println!("Lista após remoção: {}", lista);

    // Verificar se contém
    println!("Contém 30? {}", lista.contem(&30));
    println!("Contém 99? {}", lista.contem(&99));

    // Tamanho
    println!("Tamanho: {}", lista.tamanho());

    // Converter para Vec
    println!("Como Vec: {:?}", lista.para_vec());
}

/// Iterador que empresta elementos da lista (não consome)
pub struct Iter<'a, T> {
    proximo: Option<&'a No<T>>,
}

impl<T> ListaLigada<T> {
    /// Retorna um iterador por referência imutável
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            proximo: self.cabeca.as_deref(),
        }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.proximo.map(|no| {
            self.proximo = no.proximo.as_deref();
            &no.valor
        })
    }
}

// Uso:
// for valor in lista.iter() {
//     println!("{}", valor);
// }

use std::fmt;

type Link<T> = Option<Box<No<T>>>;

struct No<T> {
    valor: T,
    proximo: Link<T>,
}

struct Pilha<T> {
    topo: Link<T>,
    tamanho: usize,
}

impl<T> Pilha<T> {
    fn nova() -> Self {
        Pilha { topo: None, tamanho: 0 }
    }

    fn empilhar(&mut self, valor: T) {
        let novo = Box::new(No {
            valor,
            proximo: self.topo.take(),
        });
        self.topo = Some(novo);
        self.tamanho += 1;
    }

    fn desempilhar(&mut self) -> Option<T> {
        self.topo.take().map(|no| {
            self.topo = no.proximo;
            self.tamanho -= 1;
            no.valor
        })
    }

    fn espiar(&self) -> Option<&T> {
        self.topo.as_ref().map(|no| &no.valor)
    }

    fn esta_vazia(&self) -> bool {
        self.tamanho == 0
    }
}

/// Representa uma ação que pode ser desfeita
#[derive(Debug, Clone)]
enum Acao {
    InserirTexto { posicao: usize, texto: String },
    RemoverTexto { posicao: usize, texto: String },
    FormatarNegrito { inicio: usize, fim: usize },
    FormatarItalico { inicio: usize, fim: usize },
    SubstituirTexto { posicao: usize, antigo: String, novo: String },
}

impl fmt::Display for Acao {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Acao::InserirTexto { posicao, texto } => {
                write!(f, "Inserir '{}' na posição {}", texto, posicao)
            }
            Acao::RemoverTexto { posicao, texto } => {
                write!(f, "Remover '{}' da posição {}", texto, posicao)
            }
            Acao::FormatarNegrito { inicio, fim } => {
                write!(f, "Negrito em [{}, {})", inicio, fim)
            }
            Acao::FormatarItalico { inicio, fim } => {
                write!(f, "Itálico em [{}, {})", inicio, fim)
            }
            Acao::SubstituirTexto { posicao, antigo, novo } => {
                write!(f, "Substituir '{}' por '{}' na posição {}", antigo, novo, posicao)
            }
        }
    }
}

/// Inverte uma ação para gerar a ação de desfazer
fn inverter_acao(acao: &Acao) -> Acao {
    match acao {
        Acao::InserirTexto { posicao, texto } => Acao::RemoverTexto {
            posicao: *posicao,
            texto: texto.clone(),
        },
        Acao::RemoverTexto { posicao, texto } => Acao::InserirTexto {
            posicao: *posicao,
            texto: texto.clone(),
        },
        Acao::FormatarNegrito { inicio, fim } => Acao::FormatarNegrito {
            inicio: *inicio,
            fim: *fim,
        },
        Acao::FormatarItalico { inicio, fim } => Acao::FormatarItalico {
            inicio: *inicio,
            fim: *fim,
        },
        Acao::SubstituirTexto { posicao, antigo, novo } => Acao::SubstituirTexto {
            posicao: *posicao,
            antigo: novo.clone(),
            novo: antigo.clone(),
        },
    }
}

/// Sistema de histórico com undo e redo
struct HistoricoEditor {
    historico_desfazer: Pilha<Acao>,
    historico_refazer: Pilha<Acao>,
}

impl HistoricoEditor {
    fn novo() -> Self {
        HistoricoEditor {
            historico_desfazer: Pilha::nova(),
            historico_refazer: Pilha::nova(),
        }
    }

    /// Registra uma nova ação (limpa o histórico de refazer)
    fn executar(&mut self, acao: Acao) {
        println!("  ✔ Executando: {}", acao);
        self.historico_desfazer.empilhar(acao);
        // Ao executar nova ação, o histórico de refazer é invalidado
        self.historico_refazer = Pilha::nova();
    }

    /// Desfaz a última ação
    fn desfazer(&mut self) -> Option<Acao> {
        self.historico_desfazer.desempilhar().map(|acao| {
            let acao_inversa = inverter_acao(&acao);
            println!("  ↩ Desfazendo: {} → Aplicando: {}", acao, acao_inversa);
            self.historico_refazer.empilhar(acao.clone());
            acao_inversa
        })
    }

    /// Refaz a última ação desfeita
    fn refazer(&mut self) -> Option<Acao> {
        self.historico_refazer.desempilhar().map(|acao| {
            println!("  ↪ Refazendo: {}", acao);
            self.historico_desfazer.empilhar(acao.clone());
            acao
        })
    }

    /// Mostra o estado atual
    fn estado(&self) {
        print!("  Estado: ");
        if let Some(ultima) = self.historico_desfazer.espiar() {
            println!("última ação = {}", ultima);
        } else {
            println!("nenhuma ação no histórico");
        }
    }
}

fn main() {
    let mut editor = HistoricoEditor::novo();

    println!("═══ Simulação de Editor de Texto ═══\n");

    // Usuário digita e formata texto
    println!("── Executando ações ──");
    editor.executar(Acao::InserirTexto {
        posicao: 0,
        texto: "Olá, ".to_string(),
    });
    editor.executar(Acao::InserirTexto {
        posicao: 5,
        texto: "mundo!".to_string(),
    });
    editor.executar(Acao::FormatarNegrito { inicio: 0, fim: 3 });
    editor.executar(Acao::SubstituirTexto {
        posicao: 5,
        antigo: "mundo".to_string(),
        novo: "Rust".to_string(),
    });

    editor.estado();

    // Desfazer duas vezes
    println!("\n── Desfazendo ──");
    editor.desfazer();
    editor.desfazer();
    editor.estado();

    // Refazer uma vez
    println!("\n── Refazendo ──");
    editor.refazer();
    editor.estado();

    // Nova ação após desfazer (invalida o refazer)
    println!("\n── Nova ação (invalida refazer) ──");
    editor.executar(Acao::FormatarItalico { inicio: 0, fim: 11 });

    // Tentar refazer (não deve funcionar)
    println!("\n── Tentando refazer ──");
    match editor.refazer() {
        Some(acao) => println!("  Refez: {}", acao),
        None => println!("  Nada para refazer (histórico foi invalidado)"),
    }
}