Árvore Rubro-Negra (Red-Black Tree)

    Árvore Rubro-Negra válida:

              [13:N]                 N = Negro
             /      \                V = Vermelho
          [8:V]    [17:V]
         /    \       \
      [1:N]  [11:N]  [25:N]
        \              /
       [6:V]        [22:V]

    Verificação da propriedade 5 (black-height = 2 para raiz):
    13 → 8 → 1 → NIL    : negros = {13, 1}     = 2 ✓
    13 → 8 → 1 → 6 → NIL: negros = {13, 1}     = 2 ✓
    13 → 8 → 11 → NIL   : negros = {13, 11}    = 2 ✓
    13 → 17 → 25 → NIL  : negros = {13, 25}    = 2 ✓
    13 → 17 → 25 → 22   : negros = {13, 25}    = 2 ✓

Caso 1 — Tio é vermelho (recoloração):

       [G:N]                    [G:V]
      /     \                  /     \
   [P:V]   [T:V]    →      [P:N]   [T:N]
   /                        /
 [X:V]                    [X:V]

 Recolore P e T para negro, G para vermelho.
 Continue verificando a partir de G.

Caso 2 — Tio é negro, X é filho interno (rotação + caso 3):

       [G:N]                    [G:N]
      /     \                  /     \
   [P:V]   [T:N]    →      [X:V]   [T:N]
      \                     /
     [X:V]               [P:V]

 Rotação à esquerda em P. Agora trata como Caso 3.

Caso 3 — Tio é negro, X é filho externo (rotação + recoloração):

       [G:N]                    [P:N]
      /     \                  /     \
   [P:V]   [T:N]    →      [X:V]   [G:V]
   /                                   \
 [X:V]                               [T:N]

 Rotação à direita em G. Troca cores de P e G.

use std::cmp::Ordering;
use std::fmt::Display;

/// Cores dos nós: vermelho ou negro
#[derive(Debug, Clone, Copy, PartialEq)]
enum Cor {
    Vermelho,
    Negro,
}

/// Nó da árvore rubro-negra
#[derive(Debug, Clone)]
struct No<T: Ord + Display + Clone> {
    valor: T,
    cor: Cor,
    esquerda: ArvoreRN<T>,
    direita: ArvoreRN<T>,
}

/// Tipo da árvore rubro-negra
type ArvoreRN<T> = Option<Box<No<T>>>;

/// Verifica se um nó é vermelho
fn eh_vermelho<T: Ord + Display + Clone>(no: &ArvoreRN<T>) -> bool {
    match no {
        Some(n) => n.cor == Cor::Vermelho,
        None => false, // NIL é negro (propriedade 3)
    }
}

/// Rotação à esquerda (link vermelho à direita vai para esquerda)
fn rotacao_esquerda<T: Ord + Display + Clone>(mut no: Box<No<T>>) -> Box<No<T>> {
    let mut novo_raiz = no.direita.take().expect("Filho direito necessário");
    no.direita = novo_raiz.esquerda.take();
    novo_raiz.cor = no.cor;
    no.cor = Cor::Vermelho;
    novo_raiz.esquerda = Some(no);
    novo_raiz
}

/// Rotação à direita (link vermelho à esquerda sobe)
fn rotacao_direita<T: Ord + Display + Clone>(mut no: Box<No<T>>) -> Box<No<T>> {
    let mut novo_raiz = no.esquerda.take().expect("Filho esquerdo necessário");
    no.esquerda = novo_raiz.direita.take();
    novo_raiz.cor = no.cor;
    no.cor = Cor::Vermelho;
    novo_raiz.direita = Some(no);
    novo_raiz
}

/// Inverte as cores do nó e seus dois filhos
fn inverter_cores<T: Ord + Display + Clone>(no: &mut Box<No<T>>) {
    no.cor = if no.cor == Cor::Vermelho {
        Cor::Negro
    } else {
        Cor::Vermelho
    };
    if let Some(ref mut esq) = no.esquerda {
        esq.cor = if esq.cor == Cor::Vermelho {
            Cor::Negro
        } else {
            Cor::Vermelho
        };
    }
    if let Some(ref mut dir) = no.direita {
        dir.cor = if dir.cor == Cor::Vermelho {
            Cor::Negro
        } else {
            Cor::Vermelho
        };
    }
}

/// Corrige violações rubro-negras (implementação Left-Leaning Red-Black Tree)
fn corrigir<T: Ord + Display + Clone>(mut no: Box<No<T>>) -> Box<No<T>> {
    // Se o filho direito é vermelho e o esquerdo não, rotaciona à esquerda
    if eh_vermelho(&no.direita) && !eh_vermelho(&no.esquerda) {
        no = rotacao_esquerda(no);
    }
    // Se o filho esquerdo e o neto esquerdo são vermelhos, rotaciona à direita
    if eh_vermelho(&no.esquerda)
        && no
            .esquerda
            .as_ref()
            .map_or(false, |e| eh_vermelho(&e.esquerda))
    {
        no = rotacao_direita(no);
    }
    // Se ambos os filhos são vermelhos, inverte as cores
    if eh_vermelho(&no.esquerda) && eh_vermelho(&no.direita) {
        inverter_cores(&mut no);
    }
    no
}

/// Árvore Rubro-Negra (Left-Leaning Red-Black Tree)
#[derive(Debug)]
struct ArvoreRubroNegra<T: Ord + Display + Clone> {
    raiz: ArvoreRN<T>,
    tamanho: usize,
}

impl<T: Ord + Display + Clone> ArvoreRubroNegra<T> {
    /// Cria uma árvore rubro-negra vazia
    fn nova() -> Self {
        ArvoreRubroNegra {
            raiz: None,
            tamanho: 0,
        }
    }

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

    /// Insere um valor na árvore
    fn inserir(&mut self, valor: T) {
        self.raiz = Self::inserir_rec(self.raiz.take(), valor);
        // Propriedade 2: a raiz é sempre negra
        if let Some(ref mut raiz) = self.raiz {
            raiz.cor = Cor::Negro;
        }
        self.tamanho += 1;
    }

    fn inserir_rec(no: ArvoreRN<T>, valor: T) -> ArvoreRN<T> {
        match no {
            None => Some(Box::new(No {
                valor,
                cor: Cor::Vermelho, // Novo nó é sempre vermelho
                esquerda: None,
                direita: None,
            })),
            Some(mut atual) => {
                match valor.cmp(&atual.valor) {
                    Ordering::Less => {
                        atual.esquerda = Self::inserir_rec(atual.esquerda.take(), valor);
                    }
                    Ordering::Greater => {
                        atual.direita = Self::inserir_rec(atual.direita.take(), valor);
                    }
                    Ordering::Equal => {
                        return Some(atual); // Duplicado ignorado
                    }
                }
                Some(corrigir(atual))
            }
        }
    }

    /// Busca um valor na árvore
    fn buscar(&self, valor: &T) -> bool {
        let mut atual = &self.raiz;
        while let Some(no) = atual {
            match valor.cmp(&no.valor) {
                Ordering::Less => atual = &no.esquerda,
                Ordering::Greater => atual = &no.direita,
                Ordering::Equal => return true,
            }
        }
        false
    }

    /// Travessia em ordem (valores ordenados)
    fn em_ordem(&self) -> Vec<T> {
        let mut resultado = Vec::new();
        Self::em_ordem_rec(&self.raiz, &mut resultado);
        resultado
    }

    fn em_ordem_rec(no: &ArvoreRN<T>, resultado: &mut Vec<T>) {
        if let Some(atual) = no {
            Self::em_ordem_rec(&atual.esquerda, resultado);
            resultado.push(atual.valor.clone());
            Self::em_ordem_rec(&atual.direita, resultado);
        }
    }

    /// Calcula a black-height (número de nós negros até uma folha)
    fn black_height(&self) -> usize {
        let mut contagem = 0;
        let mut atual = &self.raiz;
        while let Some(no) = atual {
            if no.cor == Cor::Negro {
                contagem += 1;
            }
            atual = &no.esquerda;
        }
        contagem
    }

    /// Verifica se a árvore satisfaz todas as propriedades rubro-negras
    fn verificar_propriedades(&self) -> bool {
        // Propriedade 2: raiz é negra
        if eh_vermelho(&self.raiz) {
            println!("Violação: raiz é vermelha");
            return false;
        }
        // Verifica propriedades 4 e 5 recursivamente
        Self::verificar_rec(&self.raiz).is_some()
    }

    /// Retorna Some(black_height) se válida, None se inválida
    fn verificar_rec(no: &ArvoreRN<T>) -> Option<usize> {
        match no {
            None => Some(1), // NIL é negro
            Some(atual) => {
                // Propriedade 4: vermelhos não podem ter filhos vermelhos
                if atual.cor == Cor::Vermelho {
                    if eh_vermelho(&atual.esquerda) || eh_vermelho(&atual.direita) {
                        println!("Violação: nó vermelho {} tem filho vermelho", atual.valor);
                        return None;
                    }
                }
                let bh_esq = Self::verificar_rec(&atual.esquerda)?;
                let bh_dir = Self::verificar_rec(&atual.direita)?;
                // Propriedade 5: black-height igual em ambos os lados
                if bh_esq != bh_dir {
                    println!(
                        "Violação: black-height diferente no nó {} (esq={}, dir={})",
                        atual.valor, bh_esq, bh_dir
                    );
                    return None;
                }
                let incremento = if atual.cor == Cor::Negro { 1 } else { 0 };
                Some(bh_esq + incremento)
            }
        }
    }
}

fn main() {
    let mut arvore = ArvoreRubroNegra::nova();

    // Inserção de valores em ordem crescente
    let valores = vec![10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
    println!("Inserindo em ordem crescente: {:?}", valores);

    for v in &valores {
        arvore.inserir(*v);
    }

    println!("Tamanho: {}", arvore.tamanho());
    println!("Black-height: {}", arvore.black_height());
    println!("Propriedades válidas: {}", arvore.verificar_propriedades());
    println!("Em ordem: {:?}", arvore.em_ordem());

    // Busca
    println!("\nBuscar 50: {}", arvore.buscar(&50));
    println!("Buscar 55: {}", arvore.buscar(&55));
}

use std::fmt;

/// Representa um intervalo de tempo (ex: reunião)
#[derive(Debug, Clone)]
struct Intervalo {
    inicio: u32,  // Hora de início (em minutos desde meia-noite)
    fim: u32,     // Hora de término
    descricao: String,
}

impl Intervalo {
    fn novo(inicio: u32, fim: u32, descricao: &str) -> Self {
        Intervalo {
            inicio,
            fim,
            descricao: descricao.to_string(),
        }
    }

    /// Verifica se dois intervalos se sobrepõem
    fn sobrepoe(&self, outro: &Intervalo) -> bool {
        self.inicio < outro.fim && outro.inicio < self.fim
    }

    /// Formata hora em formato HH:MM
    fn formato_hora(minutos: u32) -> String {
        format!("{:02}:{:02}", minutos / 60, minutos % 60)
    }
}

impl fmt::Display for Intervalo {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}-{} {}",
            Self::formato_hora(self.inicio),
            Self::formato_hora(self.fim),
            self.descricao
        )
    }
}

impl PartialEq for Intervalo {
    fn eq(&self, other: &Self) -> bool {
        self.inicio == other.inicio
    }
}
impl Eq for Intervalo {}

impl PartialOrd for Intervalo {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Intervalo {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.inicio.cmp(&other.inicio)
    }
}

fn main() {
    let mut agenda = ArvoreRubroNegra::nova();

    // Inserir compromissos
    agenda.inserir(Intervalo::novo(540, 600, "Reunião diária"));
    agenda.inserir(Intervalo::novo(600, 720, "Desenvolvimento"));
    agenda.inserir(Intervalo::novo(720, 780, "Almoço"));
    agenda.inserir(Intervalo::novo(840, 900, "Code review"));
    agenda.inserir(Intervalo::novo(960, 1020, "Retrospectiva"));

    println!("=== Agenda do Dia (ordenada) ===");
    for intervalo in agenda.em_ordem() {
        println!("  {}", intervalo);
    }

    // Verificar conflito com novo compromisso
    let novo = Intervalo::novo(570, 630, "Entrevista");
    println!("\nTentar agendar: {}", novo);

    let conflitos: Vec<_> = agenda
        .em_ordem()
        .iter()
        .filter(|i| i.sobrepoe(&novo))
        .cloned()
        .collect();

    if conflitos.is_empty() {
        println!("Sem conflitos! Pode agendar.");
    } else {
        println!("Conflitos encontrados:");
        for c in &conflitos {
            println!("  - {}", c);
        }
    }
}