Fila (Queue): Estrutura FIFO em Rust

use std::fmt;

/// Fila genérica implementada com buffer circular
///
/// O buffer circular permite enfileirar e desenfileirar em O(1)
/// sem necessidade de mover elementos.
#[derive(Debug)]
pub struct FilaCircular<T> {
    buffer: Vec<Option<T>>,
    frente: usize,     // índice do primeiro elemento
    tamanho: usize,    // número de elementos presentes
    capacidade: usize, // tamanho total do buffer
}

impl<T> FilaCircular<T> {
    /// Cria uma fila com a capacidade especificada
    pub fn nova(capacidade: usize) -> Self {
        assert!(capacidade > 0, "Capacidade deve ser maior que zero");

        let mut buffer = Vec::with_capacity(capacidade);
        for _ in 0..capacidade {
            buffer.push(None);
        }

        FilaCircular {
            buffer,
            frente: 0,
            tamanho: 0,
            capacidade,
        }
    }

    /// Enfileira um elemento na trás da fila — O(1) amortizado
    pub fn enfileirar(&mut self, valor: T) -> Result<(), String> {
        if self.tamanho == self.capacidade {
            // Dobra a capacidade quando cheia
            self.redimensionar();
        }

        let indice_tras = (self.frente + self.tamanho) % self.capacidade;
        self.buffer[indice_tras] = Some(valor);
        self.tamanho += 1;
        Ok(())
    }

    /// Desenfileira e retorna o elemento da frente — O(1)
    pub fn desenfileirar(&mut self) -> Option<T> {
        if self.tamanho == 0 {
            return None;
        }

        let valor = self.buffer[self.frente].take();
        self.frente = (self.frente + 1) % self.capacidade;
        self.tamanho -= 1;
        valor
    }

    /// Retorna referência ao elemento da frente sem remover — O(1)
    pub fn frente(&self) -> Option<&T> {
        if self.tamanho == 0 {
            None
        } else {
            self.buffer[self.frente].as_ref()
        }
    }

    /// Retorna referência ao elemento de trás sem remover — O(1)
    pub fn tras(&self) -> Option<&T> {
        if self.tamanho == 0 {
            None
        } else {
            let indice = (self.frente + self.tamanho - 1) % self.capacidade;
            self.buffer[indice].as_ref()
        }
    }

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

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

    /// Retorna a capacidade atual do buffer
    pub fn capacidade(&self) -> usize {
        self.capacidade
    }

    /// Redimensiona o buffer dobrando a capacidade
    fn redimensionar(&mut self) {
        let nova_capacidade = self.capacidade * 2;
        let mut novo_buffer: Vec<Option<T>> = Vec::with_capacity(nova_capacidade);

        // Copia os elementos na ordem correta
        for i in 0..self.tamanho {
            let indice_antigo = (self.frente + i) % self.capacidade;
            // Usa replace para mover o valor sem clonar
            let valor = self.buffer[indice_antigo].take();
            novo_buffer.push(valor);
        }

        // Preenche o resto com None
        for _ in self.tamanho..nova_capacidade {
            novo_buffer.push(None);
        }

        self.buffer = novo_buffer;
        self.frente = 0;
        self.capacidade = nova_capacidade;
    }
}

/// Exibição formatada
impl<T: fmt::Display> fmt::Display for FilaCircular<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "Fila [")?;
        for i in 0..self.tamanho {
            if i > 0 {
                write!(f, " ← ")?;
            }
            let indice = (self.frente + i) % self.capacidade;
            if let Some(ref val) = self.buffer[indice] {
                write!(f, "{}", val)?;
            }
        }
        write!(f, "]")?;
        write!(f, " (tam: {}, cap: {})", self.tamanho, self.capacidade)
    }
}

fn main() {
    println!("═══ Fila com Buffer Circular ═══\n");

    let mut fila = FilaCircular::nova(4);

    // Enfileirando elementos
    for i in 1..=6 {
        fila.enfileirar(i * 10).unwrap();
        println!("Enfileirou {}: {}", i * 10, fila);
    }

    println!();

    // Desenfileirando
    while let Some(valor) = fila.desenfileirar() {
        println!("Desenfileirou: {} | {}", valor, fila);
    }

    // Tentando desenfileirar de fila vazia
    match fila.desenfileirar() {
        Some(v) => println!("Desenfileirou: {}", v),
        None => println!("\nFila vazia — nada para desenfileirar"),
    }
}

use std::collections::VecDeque;

fn demonstrar_vecdeque_como_fila() {
    let mut fila: VecDeque<String> = VecDeque::new();

    // Enfileirar (push_back)
    fila.push_back("Primeiro da fila".to_string());
    fila.push_back("Segundo da fila".to_string());
    fila.push_back("Terceiro da fila".to_string());

    println!("Fila: {:?}", fila);

    // Espiar a frente
    if let Some(primeiro) = fila.front() {
        println!("Próximo a ser atendido: {}", primeiro);
    }

    // Desenfileirar (pop_front)
    while let Some(pessoa) = fila.pop_front() {
        println!("Atendendo: {}", pessoa);
    }

    // Fila com capacidade pré-alocada
    let mut fila_grande: VecDeque<i32> = VecDeque::with_capacity(1000);
    for i in 0..100 {
        fila_grande.push_back(i);
    }

    println!("\nFila grande: {} elementos, capacidade: {}",
        fila_grande.len(), fila_grande.capacity());

    // Iterar sem consumir
    let soma: i32 = fila_grande.iter().sum();
    println!("Soma dos elementos: {}", soma);

    // Drenar elementos (remove e retorna iterador)
    let primeiros_cinco: Vec<i32> = fila_grande.drain(..5).collect();
    println!("Drenados: {:?}", primeiros_cinco);
    println!("Restantes: {}", fila_grande.len());
}

fn main() {
    demonstrar_vecdeque_como_fila();
}

use std::collections::BinaryHeap;

fn demonstrar_fila_prioridade() {
    let mut fila = BinaryHeap::new();

    // Insere com prioridade implícita (maior valor = maior prioridade)
    fila.push(5);
    fila.push(1);
    fila.push(10);
    fila.push(3);

    // Remove sempre o maior
    while let Some(valor) = fila.pop() {
        println!("Processando: {}", valor);
        // Saída: 10, 5, 3, 1
    }
}

fn main() {
    demonstrar_fila_prioridade();
}

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

/// Representa o estado de uma tarefa
#[derive(Debug, Clone, PartialEq)]
enum EstadoTarefa {
    Pendente,
    EmExecucao,
    Concluida,
    Bloqueada,
}

/// Representa uma tarefa no agendador
#[derive(Debug, Clone)]
struct Tarefa {
    id: usize,
    nome: String,
    duracao_restante: u32,  // unidades de tempo restantes
    prioridade: u8,         // 1-5 (5 = mais urgente)
    estado: EstadoTarefa,
    dependencias: Vec<usize>, // IDs das tarefas que precisam terminar antes
}

impl Tarefa {
    fn nova(id: usize, nome: &str, duracao: u32, prioridade: u8, deps: Vec<usize>) -> Self {
        Tarefa {
            id,
            nome: nome.to_string(),
            duracao_restante: duracao,
            prioridade,
            estado: EstadoTarefa::Pendente,
            dependencias: deps,
        }
    }
}

impl fmt::Display for Tarefa {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "[T{}] {} (restante: {}u, prio: {}, estado: {:?})",
            self.id, self.nome, self.duracao_restante, self.prioridade, self.estado
        )
    }
}

/// Agendador de tarefas round-robin com resolução de dependências
struct Agendador {
    tarefas: HashMap<usize, Tarefa>,
    fila_execucao: VecDeque<usize>,   // IDs das tarefas prontas
    fila_espera: VecDeque<usize>,     // IDs das tarefas bloqueadas
    concluidas: Vec<usize>,           // IDs das tarefas concluídas
    quantum: u32,                      // tempo por fatia
    tempo_atual: u32,
}

impl Agendador {
    fn novo(quantum: u32) -> Self {
        Agendador {
            tarefas: HashMap::new(),
            fila_execucao: VecDeque::new(),
            fila_espera: VecDeque::new(),
            concluidas: Vec::new(),
            quantum,
            tempo_atual: 0,
        }
    }

    /// Adiciona uma tarefa ao agendador
    fn adicionar_tarefa(&mut self, tarefa: Tarefa) {
        let id = tarefa.id;
        self.tarefas.insert(id, tarefa);
        self.fila_espera.push_back(id);
    }

    /// Verifica se as dependências de uma tarefa foram satisfeitas
    fn dependencias_satisfeitas(&self, id_tarefa: usize) -> bool {
        if let Some(tarefa) = self.tarefas.get(&id_tarefa) {
            tarefa.dependencias.iter().all(|dep_id| {
                self.concluidas.contains(dep_id)
            })
        } else {
            false
        }
    }

    /// Move tarefas da fila de espera para a fila de execução
    /// quando suas dependências são satisfeitas (similar a BFS)
    fn atualizar_filas(&mut self) {
        let mut prontas = Vec::new();
        let mut ainda_bloqueadas = VecDeque::new();

        while let Some(id) = self.fila_espera.pop_front() {
            if self.dependencias_satisfeitas(id) {
                prontas.push(id);
            } else {
                ainda_bloqueadas.push_back(id);
            }
        }

        self.fila_espera = ainda_bloqueadas;

        // Ordena as prontas por prioridade (maior primeiro)
        prontas.sort_by(|a, b| {
            let prio_a = self.tarefas.get(a).map(|t| t.prioridade).unwrap_or(0);
            let prio_b = self.tarefas.get(b).map(|t| t.prioridade).unwrap_or(0);
            prio_b.cmp(&prio_a)
        });

        for id in prontas {
            if let Some(tarefa) = self.tarefas.get_mut(&id) {
                tarefa.estado = EstadoTarefa::Pendente;
            }
            self.fila_execucao.push_back(id);
        }
    }

    /// Executa um ciclo do agendador round-robin
    fn executar_ciclo(&mut self) -> bool {
        self.atualizar_filas();

        if self.fila_execucao.is_empty() {
            if self.fila_espera.is_empty() {
                return false; // Tudo concluído
            }
            println!("  [t={}] Deadlock ou dependências pendentes!", self.tempo_atual);
            return false;
        }

        // Pega a próxima tarefa da frente da fila
        if let Some(id) = self.fila_execucao.pop_front() {
            if let Some(tarefa) = self.tarefas.get_mut(&id) {
                tarefa.estado = EstadoTarefa::EmExecucao;

                // Executa por no máximo 'quantum' unidades
                let execucao = tarefa.duracao_restante.min(self.quantum);
                tarefa.duracao_restante -= execucao;
                self.tempo_atual += execucao;

                println!(
                    "  [t={:>3}] Executando {} por {}u (restante: {}u)",
                    self.tempo_atual, tarefa.nome, execucao, tarefa.duracao_restante
                );

                if tarefa.duracao_restante == 0 {
                    // Tarefa concluída
                    tarefa.estado = EstadoTarefa::Concluida;
                    self.concluidas.push(id);
                    println!(
                        "         >>> {} CONCLUÍDA!",
                        tarefa.nome
                    );
                } else {
                    // Tarefa não terminou — volta para o final da fila
                    tarefa.estado = EstadoTarefa::Pendente;
                    self.fila_execucao.push_back(id);
                }
            }
        }

        true
    }

    /// Executa todas as tarefas até completar
    fn executar_tudo(&mut self) {
        println!("═══ Agendador Round-Robin (quantum: {}u) ═══\n", self.quantum);

        let mut ciclos = 0;
        let max_ciclos = 100; // prevenção contra loops infinitos

        while self.executar_ciclo() && ciclos < max_ciclos {
            ciclos += 1;
        }

        println!("\n─── Resumo ───");
        println!("Tempo total: {}u", self.tempo_atual);
        println!("Ciclos executados: {}", ciclos);
        println!("Tarefas concluídas: {}", self.concluidas.len());

        // Ordem de conclusão
        println!("\nOrdem de conclusão:");
        for (i, id) in self.concluidas.iter().enumerate() {
            if let Some(tarefa) = self.tarefas.get(id) {
                println!("  {}. [T{}] {}", i + 1, tarefa.id, tarefa.nome);
            }
        }
    }
}

/// BFS para encontrar a ordem topológica das dependências
fn ordem_bfs(tarefas: &[Tarefa]) -> Vec<usize> {
    let mut grau_entrada: HashMap<usize, usize> = HashMap::new();
    let mut adjacencias: HashMap<usize, Vec<usize>> = HashMap::new();

    // Inicializa
    for tarefa in tarefas {
        grau_entrada.entry(tarefa.id).or_insert(0);
        adjacencias.entry(tarefa.id).or_default();
    }

    // Constrói o grafo de dependências
    for tarefa in tarefas {
        for &dep in &tarefa.dependencias {
            adjacencias.entry(dep).or_default().push(tarefa.id);
            *grau_entrada.entry(tarefa.id).or_insert(0) += 1;
        }
    }

    // BFS com fila — algoritmo de Kahn
    let mut fila: VecDeque<usize> = VecDeque::new();
    let mut ordem: Vec<usize> = Vec::new();

    // Adiciona nós sem dependências
    for (&id, &grau) in &grau_entrada {
        if grau == 0 {
            fila.push_back(id);
        }
    }

    while let Some(id) = fila.pop_front() {
        ordem.push(id);

        if let Some(vizinhos) = adjacencias.get(&id) {
            for &vizinho in vizinhos {
                if let Some(grau) = grau_entrada.get_mut(&vizinho) {
                    *grau -= 1;
                    if *grau == 0 {
                        fila.push_back(vizinho);
                    }
                }
            }
        }
    }

    ordem
}

fn main() {
    // Define as tarefas de um projeto de software
    let tarefas = vec![
        Tarefa::nova(1, "Análise de Requisitos", 3, 5, vec![]),
        Tarefa::nova(2, "Design do Banco", 4, 4, vec![1]),
        Tarefa::nova(3, "Design da API", 3, 4, vec![1]),
        Tarefa::nova(4, "Implementar Backend", 8, 3, vec![2, 3]),
        Tarefa::nova(5, "Implementar Frontend", 6, 3, vec![3]),
        Tarefa::nova(6, "Testes de Integração", 4, 2, vec![4, 5]),
        Tarefa::nova(7, "Deploy", 2, 5, vec![6]),
    ];

    // Mostra a ordem de dependências via BFS
    println!("═══ Resolução de Dependências (BFS / Kahn) ═══\n");
    let ordem = ordem_bfs(&tarefas);
    println!("Ordem topológica: {:?}\n", ordem);

    for id in &ordem {
        if let Some(tarefa) = tarefas.iter().find(|t| t.id == *id) {
            let deps_str = if tarefa.dependencias.is_empty() {
                "nenhuma".to_string()
            } else {
                tarefa.dependencias.iter()
                    .map(|d| format!("T{}", d))
                    .collect::<Vec<_>>()
                    .join(", ")
            };
            println!("  T{}: {} (deps: {})", tarefa.id, tarefa.nome, deps_str);
        }
    }

    // Executa o agendador round-robin
    println!("\n");
    let mut agendador = Agendador::novo(3); // quantum de 3 unidades

    for tarefa in tarefas {
        agendador.adicionar_tarefa(tarefa);
    }

    agendador.executar_tudo();
}