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

/// A fixed-capacity least-recently-used cache.
///
/// `get` and `put` update recency. When inserting beyond capacity, the least
/// recently used entry is evicted.
pub struct LruCache<K, V> {
    capacity: usize,
    map: HashMap<K, usize>,
    entries: Vec<Option<Entry<K, V>>>,
    free: Vec<usize>,
    head: Option<usize>,
    tail: Option<usize>,
}

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

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

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

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

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

    pub fn contains_key(&self, key: &K) -> bool {
        self.map.contains_key(key)
    }

    /// Returns a shared value reference and marks the entry as most recently used.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let idx = *self.map.get(key)?;
        self.move_to_front(idx);
        Some(&self.entries[idx].as_ref().expect("cache index is valid").value)
    }

    /// Inserts or updates a value.
    ///
    /// Returns the old value for an updated key, or the evicted LRU entry when
    /// insertion exceeds capacity.
    pub fn put(&mut self, key: K, value: V) -> Option<(K, V)> {
        if self.capacity == 0 {
            return Some((key, value));
        }

        if let Some(&idx) = self.map.get(&key) {
            let entry = self.entries[idx].as_mut().expect("cache index is valid");
            let old_value = std::mem::replace(&mut entry.value, value);
            let old_key = entry.key.clone();
            self.move_to_front(idx);
            return Some((old_key, old_value));
        }

        let evicted = if self.len() == self.capacity {
            self.remove_lru()
        } else {
            None
        };

        let idx = self.allocate_entry(Entry {
            key: key.clone(),
            value,
            prev: None,
            next: None,
        });
        self.map.insert(key, idx);
        self.push_front(idx);

        evicted
    }

    pub fn remove(&mut self, key: &K) -> Option<V> {
        let idx = self.map.remove(key)?;
        self.unlink(idx);
        let entry = self.entries[idx].take().expect("cache index is valid");
        self.free.push(idx);
        Some(entry.value)
    }

    fn remove_lru(&mut self) -> Option<(K, V)> {
        let idx = self.tail?;
        self.unlink(idx);
        let entry = self.entries[idx].take().expect("cache index is valid");
        self.map.remove(&entry.key);
        self.free.push(idx);
        Some((entry.key, entry.value))
    }

    fn allocate_entry(&mut self, entry: Entry<K, V>) -> usize {
        if let Some(idx) = self.free.pop() {
            self.entries[idx] = Some(entry);
            idx
        } else {
            self.entries.push(Some(entry));
            self.entries.len() - 1
        }
    }

    fn move_to_front(&mut self, idx: usize) {
        if self.head == Some(idx) {
            return;
        }
        self.unlink(idx);
        self.push_front(idx);
    }

    fn push_front(&mut self, idx: usize) {
        {
            let entry = self.entries[idx].as_mut().expect("cache index is valid");
            entry.prev = None;
            entry.next = self.head;
        }

        if let Some(old_head) = self.head {
            self.entries[old_head]
                .as_mut()
                .expect("cache index is valid")
                .prev = Some(idx);
        } else {
            self.tail = Some(idx);
        }

        self.head = Some(idx);
    }

    fn unlink(&mut self, idx: usize) {
        let (prev, next) = {
            let entry = self.entries[idx].as_ref().expect("cache index is valid");
            (entry.prev, entry.next)
        };

        if let Some(prev_idx) = prev {
            self.entries[prev_idx]
                .as_mut()
                .expect("cache index is valid")
                .next = next;
        } else {
            self.head = next;
        }

        if let Some(next_idx) = next {
            self.entries[next_idx]
                .as_mut()
                .expect("cache index is valid")
                .prev = prev;
        } else {
            self.tail = prev;
        }

        let entry = self.entries[idx].as_mut().expect("cache index is valid");
        entry.prev = None;
        entry.next = None;
    }
}

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

    #[test]
    fn evicts_least_recently_used_entry() {
        let mut cache = LruCache::new(2);

        assert_eq!(cache.put("a", 1), None);
        assert_eq!(cache.put("b", 2), None);
        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 updating_existing_key_refreshes_recency() {
        let mut cache = LruCache::new(2);

        cache.put(1, "one");
        cache.put(2, "two");
        assert_eq!(cache.put(1, "ONE"), Some((1, "one")));

        assert_eq!(cache.put(3, "three"), Some((2, "two")));
        assert_eq!(cache.get(&1), Some(&"ONE"));
        assert_eq!(cache.get(&2), None);
        assert_eq!(cache.get(&3), Some(&"three"));
    }

    #[test]
    fn zero_capacity_does_not_store_entries() {
        let mut cache = LruCache::new(0);

        assert_eq!(cache.put("x", 10), Some(("x", 10)));
        assert_eq!(cache.len(), 0);
        assert_eq!(cache.get(&"x"), None);
    }
}