klyff 0.1.3

use std::collections::HashMap;

pub(super) struct Cache<K, V> {
    current_tick: u64,

    /// Storage of key-value pair and the tick at which it was last used.
    values: Vec<(K, V, u64)>,
    /// Map from a key straight to an index to the node.
    map: HashMap<K, usize>,
    /// Index to prev node of each node.
    prev: Vec<Option<usize>>,
    // Index to next node of each node.
    next: Vec<Option<usize>>,
    /// Index of the most-recently-used slot (head of the list).
    head: Option<usize>,
    /// Index of the least-recently-used slot (tail of the list).
    tail: Option<usize>,
    /// Slots that have been evicted and can be reused.
    free: Vec<usize>,
}

impl<K: std::hash::Hash + Eq + Clone, V: Clone> Cache<K, V> {
    pub fn new() -> Self {
        Self {
            current_tick: 0,
            values: Vec::new(),
            map: HashMap::new(),
            prev: Vec::new(),
            next: Vec::new(),
            head: None,
            tail: None,
            free: Vec::new(),
        }
    }

    pub fn new_tick(&mut self) {
        self.current_tick += 1;
    }

    pub fn current_tick(&self) -> u64 {
        self.current_tick
    }

    /// Look up a key. Moves the entry to the MRU position.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let idx = *self.map.get(key)?;
        self.move_to_front(idx);
        Some(&self.values[idx].1)
    }

    /// Insert or update a key-value pair at the current tick.
    pub fn insert(&mut self, key: K, value: V) {
        if let Some(&idx) = self.map.get(&key) {
            // Update in-place and move to front.
            self.values[idx].1 = value;
            self.values[idx].2 = self.current_tick;
            self.move_to_front(idx);
            return;
        }

        let tick = self.current_tick;
        let idx = match self.free.pop() {
            Some(slot) => {
                self.values[slot] = (key.clone(), value, tick);
                self.prev[slot] = None;
                self.next[slot] = None;
                slot
            }
            None => {
                let slot = self.values.len();
                self.values.push((key.clone(), value, tick));
                self.prev.push(None);
                self.next.push(None);
                slot
            }
        };

        self.map.insert(key, idx);
        self.attach_front(idx);
    }

    pub fn remove(&mut self, key: &K) -> bool {
        let Some(idx) = self.map.remove(key) else {
            return false;
        };
        self.detach(idx);
        self.free.push(idx);
        true
    }

    /// Iterate over all live key-value pairs in arbitrary order.
    ///
    /// Walks the lookup map so evicted (freed) slots are skipped.
    #[cfg(feature = "serde")]
    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
        self.map.iter().map(move |(k, &idx)| (k, &self.values[idx].1))
    }

    /// Peek at the least-recently-used entry without changing the order.
    pub fn peek_lru(&self) -> Option<(&K, &V, u64)> {
        let idx = self.tail?;
        let (k, v, t) = &self.values[idx];
        Some((k, v, *t))
    }

    /// Detach slot `idx` from wherever it sits in the list.
    fn detach(&mut self, idx: usize) {
        let p = self.prev[idx];
        let n = self.next[idx];

        match p {
            Some(pi) => self.next[pi] = n,
            None => self.head = n, // idx was the head
        }
        match n {
            Some(ni) => self.prev[ni] = p,
            None => self.tail = p, // idx was the tail
        }

        self.prev[idx] = None;
        self.next[idx] = None;
    }

    /// Insert slot `idx` at the front (MRU end) of the list.
    fn attach_front(&mut self, idx: usize) {
        self.prev[idx] = None;
        self.next[idx] = self.head;

        if let Some(old_head) = self.head {
            self.prev[old_head] = Some(idx);
        } else {
            // List was empty — idx is also the tail.
            self.tail = Some(idx);
        }
        self.head = Some(idx);
    }

    /// Move an already-linked slot to the front.
    fn move_to_front(&mut self, idx: usize) {
        if self.head == Some(idx) {
            return; // already MRU
        }
        self.detach(idx);
        self.attach_front(idx);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn basic_insert_and_get() {
        let mut c: Cache<&str, i32> = Cache::new();
        c.insert("a", 1);
        c.insert("b", 2);
        c.insert("c", 3);
        assert_eq!(c.get(&"a"), Some(&1));
        assert_eq!(c.get(&"b"), Some(&2));
        assert_eq!(c.get(&"c"), Some(&3));
    }

    #[test]
    fn peek_lru_returns_tail() {
        let mut c: Cache<&str, i32> = Cache::new();
        c.insert("a", 1);
        c.insert("b", 2);
        c.insert("c", 3);
        // Order (MRU→LRU): c, b, a  — LRU is "a".
        let (k, v, _t) = c.peek_lru().unwrap();
        assert_eq!(*k, "a");
        assert_eq!(*v, 1);
    }

    #[test]
    fn tick_stored_with_entry() {
        let mut c: Cache<&str, i32> = Cache::new();
        c.insert("a", 1);
        c.new_tick();
        c.new_tick();
        c.insert("b", 2);
        // "a" was inserted at tick 0, "b" at tick 2. LRU is "a".
        let (_k, _v, tick) = c.peek_lru().unwrap();
        assert_eq!(tick, 0);
    }

    #[test]
    fn update_moves_to_front() {
        let mut c: Cache<&str, i32> = Cache::new();
        c.insert("a", 1);
        c.insert("b", 2);
        c.insert("c", 3);
        // Re-insert "a" — it should now be MRU and LRU should be "b".
        c.insert("a", 10);
        let (k, _v, _) = c.peek_lru().unwrap();
        assert_eq!(*k, "b");
        assert_eq!(c.get(&"a"), Some(&10));
    }

    #[test]
    fn remove_returns_value_and_tick() {
        let mut c: Cache<&str, i32> = Cache::new();
        c.insert("a", 1);
        c.new_tick();
        c.insert("b", 2);
        assert!(c.remove(&"a"));
        assert_eq!(c.get(&"a"), None);
    }

    #[test]
    fn remove_updates_lru_order() {
        let mut c: Cache<&str, i32> = Cache::new();
        c.insert("a", 1);
        c.insert("b", 2);
        c.insert("c", 3);
        // LRU is "a". Remove it — new LRU should be "b".
        c.remove(&"a");
        let (k, _v, _) = c.peek_lru().unwrap();
        assert_eq!(*k, "b");
    }

    #[test]
    fn remove_nonexistent_returns_none() {
        let mut c: Cache<&str, i32> = Cache::new();
        assert!(!c.remove(&"x"));
    }
}