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

/// A least-recently-used cache with fixed capacity.
///
/// Lookups and insertions are expected O(1). Keys are cloned only to maintain
/// the internal linked list.
pub struct LruCache<K, V> {
    capacity: usize,
    entries: HashMap<K, Entry<K, V>>,
    head: Option<K>,
    tail: Option<K>,
}

struct Entry<K, V> {
    value: V,
    newer: Option<K>,
    older: Option<K>,
}

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

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

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

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

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

    /// Returns a value and marks its key as most recently used.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        if !self.entries.contains_key(key) {
            return None;
        }

        self.promote(key);
        Some(&self.entries.get(key).expect("entry must exist").value)
    }

    /// Returns a mutable value and marks its key as most recently used.
    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        if !self.entries.contains_key(key) {
            return None;
        }

        self.promote(key);
        Some(&mut self.entries.get_mut(key).expect("entry must exist").value)
    }

    /// Inserts a value, returning the old value when the key already existed.
    ///
    /// If insertion exceeds capacity, the least recently used entry is evicted.
    pub fn put(&mut self, key: K, value: V) -> Option<V> {
        if self.capacity == 0 {
            return None;
        }

        if self.entries.contains_key(&key) {
            self.promote(&key);
            let entry = self.entries.get_mut(&key).expect("entry must exist");
            return Some(std::mem::replace(&mut entry.value, value));
        }

        let old_head = self.head.clone();
        self.entries.insert(
            key.clone(),
            Entry {
                value,
                newer: None,
                older: old_head.clone(),
            },
        );

        if let Some(head) = old_head {
            self.entries
                .get_mut(&head)
                .expect("head must exist")
                .newer = Some(key.clone());
        } else {
            self.tail = Some(key.clone());
        }

        self.head = Some(key);

        if self.entries.len() > self.capacity {
            self.evict_lru();
        }

        None
    }

    /// Removes a key and returns its value.
    pub fn remove(&mut self, key: &K) -> Option<V> {
        if !self.entries.contains_key(key) {
            return None;
        }

        self.unlink(key);
        self.entries.remove(key).map(|entry| entry.value)
    }

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

    fn promote(&mut self, key: &K) {
        if self.head.as_ref() == Some(key) {
            return;
        }

        self.unlink(key);

        let old_head = self.head.clone();
        {
            let entry = self.entries.get_mut(key).expect("entry must exist");
            entry.newer = None;
            entry.older = old_head.clone();
        }

        if let Some(head) = old_head {
            self.entries
                .get_mut(&head)
                .expect("head must exist")
                .newer = Some(key.clone());
        } else {
            self.tail = Some(key.clone());
        }

        self.head = Some(key.clone());
    }

    fn unlink(&mut self, key: &K) {
        let (newer, older) = {
            let entry = self.entries.get(key).expect("entry must exist");
            (entry.newer.clone(), entry.older.clone())
        };

        if let Some(ref newer_key) = newer {
            self.entries
                .get_mut(newer_key)
                .expect("neighbor must exist")
                .older = older.clone();
        } else {
            self.head = older.clone();
        }

        if let Some(ref older_key) = older {
            self.entries
                .get_mut(older_key)
                .expect("neighbor must exist")
                .newer = newer.clone();
        } else {
            self.tail = newer.clone();
        }

        let entry = self.entries.get_mut(key).expect("entry must exist");
        entry.newer = None;
        entry.older = None;
    }

    fn evict_lru(&mut self) {
        if let Some(key) = self.tail.clone() {
            self.unlink(&key);
            self.entries.remove(&key);
        }
    }
}

#[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));

        cache.put("c", 3);

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

    #[test]
    fn updates_and_zero_capacity_work() {
        let mut cache = LruCache::new(1);
        assert_eq!(cache.put("a", 1), None);
        assert_eq!(cache.put("a", 2), Some(1));
        assert_eq!(cache.get(&"a"), Some(&2));

        let mut disabled = LruCache::new(0);
        disabled.put("x", 10);
        assert!(disabled.is_empty());
        assert_eq!(disabled.get(&"x"), None);
    }
}