use std::collections::HashMap;
use std::hash::Hash;

/// A least-recently-used cache with O(1) lookup and eviction.
pub struct LruCache<K, V> {
    capacity: usize,
    entries: HashMap<K, usize>,
    nodes: Vec<Option<Node<K, V>>>,
    free: Vec<usize>,
    head: Option<usize>,
    tail: Option<usize>,
}

struct Node<K, V> {
    key: K,
    value: V,
    prev: Option<usize>,
    next: Option<usize>,
}

impl<K: Eq + Hash + Clone, V> LruCache<K, V> {
    pub fn new(capacity: usize) -> Self {
        Self {
            capacity,
            entries: HashMap::with_capacity(capacity),
            nodes: Vec::with_capacity(capacity),
            free: Vec::new(),
            head: None,
            tail: None,
        }
    }

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

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

    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    /// Returns a value and marks its entry as most recently used.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let index = *self.entries.get(key)?;
        self.touch(index);
        Some(&self.nodes[index].as_ref().unwrap().value)
    }

    /// Returns a mutable value and marks its entry as most recently used.
    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        let index = *self.entries.get(key)?;
        self.touch(index);
        Some(&mut self.nodes[index].as_mut().unwrap().value)
    }

    /// Inserts or updates an entry. Returns the evicted entry, if any.
    pub fn put(&mut self, key: K, value: V) -> Option<(K, V)> {
        if let Some(&index) = self.entries.get(&key) {
            self.nodes[index].as_mut().unwrap().value = value;
            self.touch(index);
            return None;
        }

        if self.capacity == 0 {
            return Some((key, value));
        }

        let evicted = if self.entries.len() == self.capacity {
            let index = self.tail.expect("a full cache has a tail");
            Some(self.remove_index(index))
        } else {
            None
        };

        let index = if let Some(index) = self.free.pop() {
            self.nodes[index] = Some(Node {
                key: key.clone(),
                value,
                prev: None,
                next: None,
            });
            index
        } else {
            self.nodes.push(Some(Node {
                key: key.clone(),
                value,
                prev: None,
                next: None,
            }));
            self.nodes.len() - 1
        };

        self.entries.insert(key, index);
        self.attach_front(index);
        evicted
    }

    pub fn remove(&mut self, key: &K) -> Option<V> {
        let index = *self.entries.get(key)?;
        let (_, value) = self.remove_index(index);
        Some(value)
    }

    pub fn clear(&mut self) {
        self.entries.clear();
        self.nodes.clear();
        self.free.clear();
        self.head = None;
        self.tail = None;
    }

    fn touch(&mut self, index: usize) {
        if self.head == Some(index) {
            return;
        }
        self.detach(index);
        self.attach_front(index);
    }

    fn detach(&mut self, index: usize) {
        let (prev, next) = {
            let node = self.nodes[index].as_ref().unwrap();
            (node.prev, node.next)
        };

        if let Some(prev) = prev {
            self.nodes[prev].as_mut().unwrap().next = next;
        } else {
            self.head = next;
        }

        if let Some(next) = next {
            self.nodes[next].as_mut().unwrap().prev = prev;
        } else {
            self.tail = prev;
        }

        let node = self.nodes[index].as_mut().unwrap();
        node.prev = None;
        node.next = None;
    }

    fn attach_front(&mut self, index: usize) {
        let old_head = self.head;

        {
            let node = self.nodes[index].as_mut().unwrap();
            node.prev = None;
            node.next = old_head;
        }

        if let Some(old_head) = old_head {
            self.nodes[old_head].as_mut().unwrap().prev = Some(index);
        } else {
            self.tail = Some(index);
        }

        self.head = Some(index);
    }

    fn remove_index(&mut self, index: usize) -> (K, V) {
        self.detach(index);
        let node = self.nodes[index].take().unwrap();
        self.entries.remove(&node.key);
        self.free.push(index);
        (node.key, node.value)
    }
}

fn main() {}

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

    #[test]
    fn evicts_least_recently_used_entry() {
        let mut cache = LruCache::new(2);
        cache.put("a", 1);
        cache.put("b", 2);

        assert_eq!(cache.get(&"a"), Some(&1));
        assert_eq!(cache.put("c", 3), Some(("b", 2)));
        assert_eq!(cache.get(&"b"), None);
        assert_eq!(cache.get(&"a"), Some(&1));
        assert_eq!(cache.get(&"c"), Some(&3));
    }

    #[test]
    fn updates_and_removes_entries() {
        let mut cache = LruCache::new(2);
        cache.put(1, "old");
        cache.put(1, "new");

        assert_eq!(cache.len(), 1);
        assert_eq!(cache.get(&1), Some(&"new"));
        assert_eq!(cache.remove(&1), Some("new"));
        assert!(cache.is_empty());
    }
}