06: High-Performance LRU Cache (O(1) Eviction)

use std::collections::HashMap;
use std::fmt::Display;
use std::hash::Hash;
use std::ptr::NonNull;

struct Node<K, V> {
    key: K,
    val: V,
    prev: Option<NonNull<Node<K, V>>>,
    next: Option<NonNull<Node<K, V>>>,
}

impl<K, V> Node<K, V> {
    fn new(key: K, val: V) -> Self {
        Self {
            key,
            val,
            prev: None,
            next: None,
        }
    }
}

pub struct LruCache<K, V> {
    capacity: usize,
    map: HashMap<K, NonNull<Node<K, V>>>,
    head: Option<NonNull<Node<K, V>>>,
    tail: Option<NonNull<Node<K, V>>>,
}

impl<K, V> LruCache<K, V>
where
    K: Hash + Eq + Clone + Display,
    V: Clone + Display,
{
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "A capacidade do cache precisa ser maior que zero");
        Self {
            capacity,
            map: HashMap::with_capacity(capacity),
            head: None,
            tail: None,
        }
    }

    pub fn len(&self) -> usize {
        self.map.len()
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }

    fn detach(&mut self, mut node: NonNull<Node<K, V>>) {
        unsafe {
            let node_ref = node.as_mut();

            match node_ref.prev {
                Some(mut prev) => prev.as_mut().next = node_ref.next,
                None => self.head = node_ref.next,
            }

            match node_ref.next {
                Some(mut next) => next.as_mut().prev = node_ref.prev,
                None => self.tail = node_ref.prev,
            }

            node_ref.prev = None;
            node_ref.next = None;
        }
    }

    fn attach_to_head(&mut self, mut node: NonNull<Node<K, V>>) {
        unsafe {
            let node_ref = node.as_mut();
            node_ref.next = self.head;
            node_ref.prev = None;

            match self.head {
                Some(mut old_head) => old_head.as_mut().prev = Some(node),
                None => self.tail = Some(node),
            }

            self.head = Some(node);
        }
    }

    pub fn get(&mut self, key: &K) -> Option<&V> {
        if let Some(&node_ptr) = self.map.get(key) {
            self.detach(node_ptr);
            self.attach_to_head(node_ptr);
            unsafe { Some(&(*node_ptr.as_ptr()).val) }
        } else {
            None
        }
    }

    pub fn put(&mut self, key: K, val: V) {
        if let Some(&node_ptr) = self.map.get(&key) {
            unsafe {
                (*node_ptr.as_ptr()).val = val;
            }
            self.detach(node_ptr);
            self.attach_to_head(node_ptr);
        } else {
            if self.map.len() >= self.capacity {
                self.evict_lru();
            }

            let new_box = Box::new(Node::new(key.clone(), val));
            let node_ptr = NonNull::new(Box::into_raw(new_box)).unwrap();

            self.attach_to_head(node_ptr);
            self.map.insert(key, node_ptr);
        }
    }

    fn evict_lru(&mut self) -> Option<(K, V)> {
        let lru_node = self.tail?;
        self.detach(lru_node);

        unsafe {
            let boxed = Box::from_raw(lru_node.as_ptr());
            self.map.remove(&boxed.key);
            Some((boxed.key, boxed.val))
        }
    }

    pub fn print_timeline(&self) {
        println!("   Ocupação: {}/{} slots", self.len(), self.capacity());
        print!("   [MRU / Mais Recente] -> ");

        let mut curr = self.head;
        while let Some(node) = curr {
            unsafe {
                let n = node.as_ref();
                print!("(\"{}\": {}) -> ", n.key, n.val);
                curr = n.next;
            }
        }
        println!("[LRU / Descarte Próximo]");
    }
}

impl<K, V> Drop for LruCache<K, V> {
    fn drop(&mut self) {
        let mut curr = self.head;
        while let Some(node) = curr {
            unsafe {
                let boxed = Box::from_raw(node.as_ptr());
                curr = boxed.next;
            }
        }
    }
}

fn main() {
    println!("============================================================");
    println!("🦀 RUST SYSTEMS: HIGH-PERFORMANCE LRU CACHE (O(1) GET/PUT)");
    println!("============================================================");

    println!("\n1. Inicializando Cache LRU com capacidade máxima = 3:");
    let mut cache: LruCache<String, String> = LruCache::new(3);

    println!("   -> put(\"session_user\", \"ana_dev\")");
    cache.put("session_user".to_string(), "ana_dev".to_string());
    println!("   -> put(\"auth_token\", \"token_xyz89\")");
    cache.put("auth_token".to_string(), "token_xyz89".to_string());
    println!("   -> put(\"user_role\", \"admin\")");
    cache.put("user_role".to_string(), "admin".to_string());

    println!("\n2. Estado da Linha Temporal do Cache:");
    cache.print_timeline();

    println!("\n3. Acessando chave intermediária (get):");
    println!("   -> get(\"session_user\")");
    let user = cache.get(&"session_user".to_string());
    println!("   Valor obtido: {:?}", user);
    println!("   Notice como \"session_user\" foi promovido ao topo (MRU):");
    cache.print_timeline();

    println!("\n4. Inserindo novo item para forçar Despejo (Eviction Policy):");
    println!("   O cache já está em 3/3. \"auth_token\" é atualmente o mais antigo (LRU).");
    println!("   -> put(\"cluster_id\", \"node_01\")");
    cache.put("cluster_id".to_string(), "node_01".to_string());

    println!("\n5. Estado do Cache após o Despejo Automático:");
    cache.print_timeline();

    println!("\n6. Verificando que o item antigo foi descartado:");
    println!("   get(\"auth_token\")   => {:?}", cache.get(&"auth_token".to_string()));
    println!("   get(\"cluster_id\")   => {:?}", cache.get(&"cluster_id".to_string()));
    println!("   get(\"session_user\") => {:?}", cache.get(&"session_user".to_string()));

    println!("\n7. Finalizando: Trait Drop desaloca nós órfãos sem memory leaks!");
}