hashlru 0.11.1

// // Copyright (C) 2024 Christian Mauduit <ufoot@ufoot.org>

// Heavily inspired from:
// https://github.com/jeromefroe/lru-rs/blob/b1d858a61f332424a666959a7a5e604cc62c91d1/src/lib.rs

use crate::dump::Dump;
use crate::iter::*;
use alloc::borrow::Borrow;
use alloc::boxed::Box;
use core::marker::PhantomData;
use core::mem;
use core::ptr::{self, NonNull};
use core::usize;
use std::collections::HashMap;
use std::fmt;
use std::hash::{Hash, Hasher};

#[cfg(feature = "hashbrown")]
use hashbrown::HashMap as HashMapData;
#[cfg(not(feature = "hashbrown"))]
use std::collections::HashMap as HashMapData;

extern crate alloc;

// Struct used to hold a reference to a key
pub(crate) struct KeyRef<K> {
    k: *const K,
}

impl<K: Hash> Hash for KeyRef<K> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        unsafe { (*self.k).hash(state) }
    }
}

impl<K: PartialEq> PartialEq for KeyRef<K> {
    fn eq(&self, other: &KeyRef<K>) -> bool {
        unsafe { (*self.k).eq(&*other.k) }
    }
}

impl<K: Eq> Eq for KeyRef<K> {}

impl<K> Borrow<K> for KeyRef<K> {
    fn borrow(&self) -> &K {
        unsafe { &*self.k }
    }
}

pub(crate) struct Node<K, V> {
    pub(crate) key: mem::MaybeUninit<K>,
    pub(crate) value: mem::MaybeUninit<V>,
    pub(crate) prev: *mut Node<K, V>,
    pub(crate) next: *mut Node<K, V>,
}

impl<K, V> Node<K, V> {
    fn new(key: K, val: V) -> Self {
        Node {
            key: mem::MaybeUninit::new(key),
            value: mem::MaybeUninit::new(val),
            prev: ptr::null_mut(),
            next: ptr::null_mut(),
        }
    }

    fn new_sigil() -> Self {
        Node {
            key: mem::MaybeUninit::uninit(),
            value: mem::MaybeUninit::uninit(),
            prev: ptr::null_mut(),
            next: ptr::null_mut(),
        }
    }
}

/// LRU cache which aims at being a drop-in replacement for a hash map.
///
/// The typical use case is: you have a hash map, but know it is going to grow
/// and be too large at some point, so you need to drop the old elements.
///
/// Many implementations of LRU cache rely on double-linked lists, which are
/// not the most simple thing to implement in Rust. However, this very naive
/// implementation does not use a linked list. Instead it stores nodes in a
/// hash map, each node containing the actual value of type V plus the key
/// of type K of the previous and next items. This replaces the double-linked
/// list at the cost, indeed, of a few more hash map lookups. OTOH there's no
/// need for refs, pointers or other complex constructs.
///
/// In most cases this implementation tries to be as close as possible
/// to the [standard collections HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html)
/// however there are a few differences:
///
/// - keys must have the Clone trait
/// - get requires a mutable object
/// - no iterator on mutables
/// - some other hashmap features are not implemented
///
/// # Examples
///
/// ```
/// use hashlru::Cache;
///
/// let mut cache = Cache::new(4);
/// cache.insert("key1", 10);
/// cache.insert("key2", 20);
/// cache.insert("key3", 30);
/// cache.insert("key4", 40);
/// cache.insert("key5", 50);
/// // key1 has been dropped, size is limited to 4
/// assert_eq!(Some(&"key2"), cache.lru());
/// assert_eq!(Some(&20), cache.get(&"key2"));
/// // getting key2 has made key3 the least recently used item
/// assert_eq!(Some(&"key3"), cache.lru());
/// assert_eq!(Some(&40), cache.get(&"key4"));
/// // getting key4 makes it the most recently used item
/// assert_eq!("[key3: 30, key5: 50, key2: 20, key4: 40]", format!("{}", cache));
/// ```
// #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Cache<K, V>
where
    K: Eq + Hash,
{
    data: HashMapData<KeyRef<K>, NonNull<Node<K, V>>>,
    capacity: usize,

    // head and tail are sigil nodes to facilitate inserting entries
    head: *mut Node<K, V>,
    tail: *mut Node<K, V>,
}

// Compiler can not derive Send as implementation has pointers.
// However, they are properly encapsulated, so we declare it Send/Sync.
unsafe impl<K: Send, V: Send> Send for Cache<K, V> where K: Eq + Hash {}
unsafe impl<K: Sync, V: Sync> Sync for Cache<K, V> where K: Eq + Hash {}

/// URL to report bugs.
///
/// This is used internally to provide context when something unexpected happens,
/// so that users can find find out which piece of software fails,
/// and how to contact author(s).
///
/// Alternatively, send a direct email to <ufoot@ufoot.org>.
pub const BUG_REPORT_URL: &str = "https://gitlab.com/liberecofr/hashlru/-/issues";

impl<K, V> fmt::Debug for Cache<K, V>
where
    K: fmt::Debug + Hash + Eq,
    V: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut comma = false;
        write!(f, "Cache [")?;
        if self.len() == 0 {
            return write!(f, "]");
        } else {
            write!(f, " ")?;
        }
        let iter = self.iter();
        for kv in iter {
            if comma {
                write!(f, ", ")?;
            } else {
                comma = true;
            }
            write!(f, "({:?}, {:?})", kv.0, kv.1)?;
        }
        write!(f, " ]")
    }
}

/// Pretty-print cache content.
///
/// Prints key-value pairs as if it was an ordered list.
/// Which is, what it is, conceptually, even if implementation
/// details differ and there is no array backing the store.
///
/// # Examples
///
/// ```
/// use hashlru::Cache;
///
/// let mut a = Cache::new(900);
/// a.insert(1, "a");
/// a.insert(2, "b");
/// a.insert(3, "c");
/// assert_eq!("[1: a, 2: b, 3: c]", format!("{}", a));
/// for i in 10..1000 {
///      a.insert(i, "more");
/// }
/// // If there are too many keys, just print a few.
/// assert_eq!("[100: more, 101: more, ..., 999: more]", format!("{}", a));
/// ```
impl<K, V> fmt::Display for Cache<K, V>
where
    K: fmt::Display + Hash + Eq + Clone,
    V: fmt::Display,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let items = if self.len() <= 5 {
            self.iter()
                .map(|x| format!("{}: {}", x.0, x.1))
                .collect::<Vec<String>>()
        } else {
            let mut acc = self
                .iter()
                .take(2)
                .map(|x| format!("{}: {}", x.0, x.1))
                .collect::<Vec<String>>();
            acc.push("...".to_string());
            let mru = self.peek_mru().unwrap();
            acc.push(format!("{}: {}", mru.0, mru.1));
            acc
        };
        write!(f, "[{}]", items.join(", "))
    }
}

impl<K, V> Cache<K, V>
where
    K: Eq + Hash,
{
    /// Returns the number of elements in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut a = Cache::new(10);
    /// assert_eq!(a.len(), 0);
    /// a.insert(1, "a");
    /// assert_eq!(a.len(), 1);
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        self.data.len()
    }

    /// Returns the max number of elements in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let a: Cache::<u32,String> = Cache::new(10);
    /// assert_eq!(a.capacity(), 10);
    /// ```
    #[inline]
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// Returns true if cache is empty
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut a: Cache::<u32,String> = Cache::new(10);
    /// assert!(a.is_empty());
    /// a.insert(0, String::from("hello"));
    /// assert!(!a.is_empty());
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    /// Returns true if cache is full
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut a: Cache::<usize,usize> = Cache::new(10);
    /// assert!(!a.is_full());
    /// for i in 0..10 {
    ///     a.insert(i, i);
    /// }
    /// assert!(a.is_full());
    /// ```
    #[inline]
    pub fn is_full(&self) -> bool {
        self.data.len() >= self.capacity
    }

    /// Clears the LRU cache, drops all data.
    /// Keeps the current capacity setting.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    ///
    /// lru.clear();
    /// assert_eq!(0, lru.len());
    /// assert_eq!(10, lru.capacity());
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        while self.pop_lru().is_some() {}
    }

    /// Resizes the LRU cache. Drops least recently used entries
    /// in priority when size is reduced below current length.
    ///
    /// Returns the number of dropped entries, if any.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    /// lru.insert("z", 100);
    /// lru.insert("t", 1000);
    /// lru.insert("u", 10000);
    ///
    /// assert_eq!(2, lru.resize(3));
    /// assert_eq!(3, lru.len());
    /// assert_eq!(3, lru.capacity());
    /// ```
    pub fn resize(&mut self, capacity: usize) -> usize {
        if capacity == self.capacity {
            return 0;
        }

        if capacity > self.capacity {
            self.data.reserve(capacity - self.capacity);
        }
        let mut dropped = 0;
        while self.len() > capacity {
            self.pop_lru();
            dropped += 1;
        }
        self.data.shrink_to_fit();

        self.capacity = capacity;
        dropped
    }

    /// Crate a new LRU. The `capacity` needs to be specified,
    /// as a 0-sized LRU can hold no data at all.
    ///
    /// It is possible to resize it later.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let lru: Cache<String, usize> = Cache::new(100);
    /// ```
    pub fn new(capacity: usize) -> Cache<K, V> {
        let cache = Cache {
            data: HashMapData::with_capacity(capacity),
            capacity,
            head: Box::into_raw(Box::new(Node::new_sigil())),
            tail: Box::into_raw(Box::new(Node::new_sigil())),
        };

        unsafe {
            (*cache.head).next = cache.tail;
            (*cache.tail).prev = cache.head;
        }

        cache
    }

    fn insert_non_0(&mut self, k: K, mut v: V) -> Option<V> {
        let node_ref = self.data.get_mut(&KeyRef { k: &k });

        match node_ref {
            Some(node_ref) => {
                // if the key is already in the cache just update its value and move it to the
                // front of the list
                let node_ptr: *mut Node<K, V> = node_ref.as_ptr();

                // gets a reference to the node to perform a swap and drops it right after
                let node_ref = unsafe { &mut (*(*node_ptr).value.as_mut_ptr()) };
                mem::swap(&mut v, node_ref);
                let _ = node_ref;

                self.detach(node_ptr);
                self.attach(node_ptr);
                Some(v)
            }
            None => {
                let (_replaced, node) = self.replace_or_create_node(k, v);
                let node_ptr: *mut Node<K, V> = node.as_ptr();

                self.attach(node_ptr);

                let keyref = unsafe { (*node_ptr).key.as_ptr() };
                self.data.insert(KeyRef { k: keyref }, node);

                None
            }
        }
    }

    /// Inserts a key-value pair into the map.
    ///
    /// If the key already exists, returns the
    /// previous value for this key.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    /// let mut lru = Cache::new(10);
    ///
    /// assert_eq!(None, lru.insert(1, "a"));
    /// assert!(lru.contains_key(&1));
    /// assert!(!lru.contains_key(&2));
    /// assert_eq!(Some("a"), lru.insert(1, "b"));
    /// assert_eq!(Some(&"b"), lru.get(&1));
    /// ```
    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
        if self.capacity == 0 {
            return None;
        }
        self.insert_non_0(k, v)
    }

    fn remove_first(&mut self) -> Option<Box<Node<K, V>>> {
        let prev = unsafe { (*self.head).next };
        if prev != self.head {
            let old_key = KeyRef {
                k: unsafe { &(*(*(*self.head).next).key.as_ptr()) },
            };
            let old_node = self.data.remove(&old_key).unwrap();
            let node_ptr: *mut Node<K, V> = old_node.as_ptr();
            self.detach(node_ptr);
            unsafe { Some(Box::from_raw(node_ptr)) }
        } else {
            None
        }
    }

    fn remove_last(&mut self) -> Option<Box<Node<K, V>>> {
        let prev = unsafe { (*self.tail).prev };
        if prev != self.tail {
            let old_key = KeyRef {
                k: unsafe { &(*(*(*self.tail).prev).key.as_ptr()) },
            };
            let old_node = self.data.remove(&old_key).unwrap();
            let node_ptr: *mut Node<K, V> = old_node.as_ptr();
            self.detach(node_ptr);
            unsafe { Some(Box::from_raw(node_ptr)) }
        } else {
            None
        }
    }

    fn detach(&mut self, node: *mut Node<K, V>) {
        unsafe {
            (*(*node).prev).next = (*node).next;
            (*(*node).next).prev = (*node).prev;
        }
    }

    fn attach(&mut self, node: *mut Node<K, V>) {
        unsafe {
            (*node).next = (*self.head).next;
            (*node).prev = self.head;
            (*self.head).next = node;
            (*(*node).next).prev = node;
        }
    }

    fn replace_or_create_node(&mut self, k: K, v: V) -> (Option<(K, V)>, NonNull<Node<K, V>>) {
        if self.len() == self.capacity() {
            // if the cache is full, remove the last entry so we can use it for the new key
            let old_key = KeyRef {
                k: unsafe { &(*(*(*self.tail).prev).key.as_ptr()) },
            };
            let old_node = self.data.remove(&old_key).unwrap();
            let node_ptr: *mut Node<K, V> = old_node.as_ptr();

            // read out the node's old key and value and then replace it
            let replaced = unsafe {
                (
                    mem::replace(&mut (*node_ptr).key, mem::MaybeUninit::new(k)).assume_init(),
                    mem::replace(&mut (*node_ptr).value, mem::MaybeUninit::new(v)).assume_init(),
                )
            };

            self.detach(node_ptr);

            (Some(replaced), old_node)
        } else {
            // if the cache is not full allocate a new Node
            // Safety: We allocate, turn into raw, and get NonNull all in one step.
            (None, unsafe {
                NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(k, v))))
            })
        }
    }

    fn push_non_0(&mut self, k: K, mut v: V) -> Option<(K, V)> {
        let node_ref = self.data.get_mut(&KeyRef { k: &k });

        match node_ref {
            Some(node_ref) => {
                // if the key is already in the cache just update its value and move it to the
                // front of the list
                let node_ptr: *mut Node<K, V> = node_ref.as_ptr();

                // gets a reference to the node to perform a swap and drops it right after
                let node_ref = unsafe { &mut (*(*node_ptr).value.as_mut_ptr()) };
                mem::swap(&mut v, node_ref);
                let _ = node_ref;

                self.detach(node_ptr);
                self.attach(node_ptr);
                None
            }
            None => {
                let (replaced, node) = self.replace_or_create_node(k, v);
                let node_ptr: *mut Node<K, V> = node.as_ptr();

                self.attach(node_ptr);

                let keyref = unsafe { (*node_ptr).key.as_ptr() };
                self.data.insert(KeyRef { k: keyref }, node);

                replaced
            }
        }
    }

    /// Pushes a key-value pair into the map.
    ///
    /// If one entry needs to be removed because the
    /// cache is full, return the entry that was removed.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    /// let mut lru = Cache::new(10);
    ///
    /// lru.push(1, "a");
    /// assert_eq!(lru.contains_key(&1), true);
    /// assert_eq!(lru.contains_key(&2), false);
    /// ```
    pub fn push(&mut self, k: K, v: V) -> Option<(K, V)> {
        if self.capacity == 0 {
            return None;
        }

        self.push_non_0(k, v)
    }

    /// Returns true if there is a value for the specified key.
    ///
    /// It does not alter the order of items, and is a read-only operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert(421, true);
    /// assert!(lru.contains_key(&421));
    /// assert!(!lru.contains_key(&33));
    /// ```
    pub fn contains_key(&self, k: &K) -> bool {
        self.data.contains_key(k)
    }

    /// Returns a reference to the value corresponding to the key.
    ///
    /// This is different from a standard get, it will not alter
    /// the order of items, and is a read-only operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert(1, "a");
    /// assert_eq!(lru.peek(&1), Some(&"a"));
    /// assert_eq!(lru.peek(&2), None);
    /// ```
    pub fn peek(&self, k: &K) -> Option<&V> {
        self.data
            .get(k)
            .map(|node| unsafe { &*node.as_ref().value.as_ptr() })
    }

    /// Returns a mutable reference to the value corresponding to the key.
    ///
    /// This is different from a standard get, it will not alter
    /// the order of items, and is a read-only operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert(1, "a");
    /// let handle = lru.peek_mut(&1).unwrap();
    /// *handle = &"b";
    /// assert_eq!(lru.peek(&1), Some(&"b"));
    /// ```
    pub fn peek_mut(&mut self, k: &K) -> Option<&mut V> {
        if let Some(node) = self.data.get(k) {
            let node_ptr: *mut Node<K, V> = node.as_ptr();
            Some(unsafe { &mut *(*node_ptr).value.as_mut_ptr() })
        } else {
            None
        }
    }

    /// Returns a reference to the value corresponding to the key,
    /// along with the key itself.
    ///
    /// This is different from a standard get_key_value, it will not alter
    /// the order of items, and is a read-only operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert(1, "a");
    /// assert_eq!(Some((&1, &"a")), lru.peek_key_value(&1));
    /// assert_eq!(None, lru.peek(&2));
    /// ```
    pub fn peek_key_value(&self, k: &K) -> Option<(&K, &V)> {
        self.data
            .get(k)
            .map(|node| unsafe { (&*node.as_ref().key.as_ptr(), &*node.as_ref().value.as_ptr()) })
    }

    /// Returns a reference to the value corresponding to the key.
    ///
    /// Since this is a LRU, reading alters the order of the items
    /// and will place this one first, as it is now the most recently used.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache = Cache::new(10);
    /// cache.insert(1, "a");
    /// cache.insert(2, "b");
    /// assert_eq!(Some(&1), cache.lru());
    /// assert_eq!(cache.get(&1), Some(&"a"));
    /// assert_eq!(Some(&2), cache.lru());
    /// assert_eq!(cache.get(&3), None);
    /// ```
    pub fn get(&mut self, k: &K) -> Option<&V> {
        if let Some(node) = self.data.get(k) {
            let node_ptr: *mut Node<K, V> = node.as_ptr();

            self.detach(node_ptr);
            self.attach(node_ptr);

            Some(unsafe { &*(*node_ptr).value.as_ptr() })
        } else {
            None
        }
    }

    /// Returns a mutable reference to the value corresponding to the key.
    ///
    /// Since this is a LRU, reading alters the order of the items
    /// and will place this one first, as it is now the most recently used.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache = Cache::new(10);
    /// cache.insert(1, "a");
    /// cache.insert(2, "b");
    /// assert_eq!(Some(&1), cache.lru());
    /// let handle = cache.get_mut(&1).unwrap();
    /// *handle = &"c";
    /// assert_eq!(cache.get(&1), Some(&"c"));
    /// assert_eq!(Some(&2), cache.lru());
    /// ```
    pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {
        if let Some(node) = self.data.get(k) {
            let node_ptr: *mut Node<K, V> = node.as_ptr();

            self.detach(node_ptr);
            self.attach(node_ptr);

            Some(unsafe { &mut *(*node_ptr).value.as_mut_ptr() })
        } else {
            None
        }
    }

    /// Returns a reference to the value corresponding to the key,
    /// along with the key itself.
    ///
    /// Since this is a LRU, reading alters the order of the items
    /// and will place this one first, as it is now the most recently used.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert(1, "a");
    /// assert_eq!(Some((&1, &"a")), lru.get_key_value(&1));
    /// assert_eq!(None, lru.get(&2));
    /// ```
    pub fn get_key_value(&mut self, k: &K) -> Option<(&K, &V)> {
        self.get(k); // re-order the cache [TODO] replace by bump
        self.peek_key_value(k) // re-use peek command
    }

    /// Bumps a key, making it the most recently used key (MRU).
    ///
    /// This is similar to doing a get() and ignore the value.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache = Cache::new(10);
    /// cache.insert(1, "a");
    /// cache.insert(2, "b");
    /// assert_eq!(Some(&1), cache.lru());
    /// cache.bump(&1);
    /// assert_eq!(Some(&2), cache.lru());
    /// ```
    pub fn bump(&mut self, k: &K) {
        if let Some(node) = self.data.get_mut(k) {
            let node_ptr: *mut Node<K, V> = node.as_ptr();
            self.detach(node_ptr);
            self.attach(node_ptr);
        }
    }

    /// Removes a key, returning the (key,value) pair if there
    /// was already something for this key.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("abc", true);
    /// lru.insert("def", true);
    /// lru.insert("ghi", false);
    /// assert_eq!(Some(("def", true)), lru.pop(&"def"));
    /// assert!(lru.contains_key(&"abc"));
    /// assert!(!lru.contains_key(&"def"));
    /// assert!(lru.contains_key(&"ghi"));
    /// ```
    pub fn pop(&mut self, k: &K) -> Option<(K, V)> {
        match self.data.remove(k) {
            None => None,
            Some(old_node) => {
                let mut old_node = unsafe { *Box::from_raw(old_node.as_ptr()) };

                self.detach(&mut old_node);

                let Node { key, value, .. } = old_node;
                unsafe { Some((key.assume_init(), value.assume_init())) }
            }
        }
    }

    /// Removes a key, returning the value of the key if the
    /// key was previously in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("abc", true);
    /// lru.insert("def", true);
    /// lru.insert("ghi", false);
    /// assert_eq!(Some(true), lru.remove(&"def"));
    /// assert!(lru.contains_key(&"abc"));
    /// assert!(!lru.contains_key(&"def"));
    /// assert!(lru.contains_key(&"ghi"));
    /// ```
    pub fn remove(&mut self, k: &K) -> Option<V> {
        match self.data.remove(k) {
            None => None,
            Some(old_node) => {
                let mut old_node = unsafe { *Box::from_raw(old_node.as_ptr()) };

                self.detach(&mut old_node);

                let Node { key: _, value, .. } = old_node;
                unsafe { Some(value.assume_init()) }
            }
        }
    }

    /// Delete a key, return nothing, just ensure key is gone.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("abc", true);
    /// lru.insert("def", true);
    /// lru.insert("ghi", false);
    /// lru.delete(&"def");
    /// assert!(lru.contains_key(&"abc"));
    /// assert!(!lru.contains_key(&"def"));
    /// assert!(lru.contains_key(&"ghi"));
    /// ```
    pub fn delete(&mut self, k: &K) {
        if let Some(old_node) = self.data.remove(k) {
            let mut old_node = unsafe { *Box::from_raw(old_node.as_ptr()) };

            self.detach(&mut old_node);

            let Node {
                key: _, value: _, ..
            } = old_node;
        }
    }

    /// Returns the least recently used key (LRU).
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// assert_eq!(None, lru.lru());
    /// lru.push("abc", true);
    /// assert_eq!(Some(&"abc"), lru.lru());
    /// lru.push("def", false);
    /// assert_eq!(Some(&"abc"), lru.lru());
    /// lru.get(&"abc");
    /// assert_eq!(Some(&"def"), lru.lru());
    /// ```
    pub fn lru(&self) -> Option<&K> {
        if self.len() > 0 {
            let key = unsafe { &(*(*(*self.tail).prev).key.as_ptr()) };
            Some(key)
        } else {
            None
        }
    }

    /// Pops the least recently used key, returning its value if
    /// the cache was non-empty.
    ///
    /// After it has been popped, it is no more in the cache.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// assert_eq!(None, lru.pop_lru());
    /// lru.push("abc", true);
    /// lru.push("def", false);
    /// assert_eq!(Some(("abc", true)), lru.pop_lru());
    /// assert_eq!(1, lru.len());
    /// ```
    pub fn pop_lru(&mut self) -> Option<(K, V)> {
        if self.len() == 0 {
            return None;
        }
        let node = self.remove_last()?;
        let node = *node;
        let Node { key, value, .. } = node;
        unsafe { Some((key.assume_init(), value.assume_init())) }
    }

    /// Peeks the least recently used key, returning its value if
    /// the cache was non-empty.
    ///
    /// This does not alter the order of the cache.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// assert_eq!(None, lru.peek_lru());
    /// lru.push("abc", true);
    /// lru.push("def", false);
    /// assert_eq!(Some((&"abc", &true)), lru.peek_lru());
    /// assert_eq!(2, lru.len());
    /// assert_eq!(Some(&"abc"), lru.lru());
    /// ```
    pub fn peek_lru(&self) -> Option<(&K, &V)> {
        match self.lru() {
            Some(tail) => self.peek_key_value(&tail),
            None => None,
        }
    }

    /// Gets the least recently used key, returning its value if
    /// the cache was non-empty.
    ///
    /// After it is returned, it becomes the most recently used
    /// item, so a next call to get_lru() would return a different value.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// assert_eq!(None, lru.pop_lru());
    /// lru.push("abc", true);
    /// lru.push("def", false);
    /// assert_eq!(Some((&"abc", &true)), lru.get_lru());
    /// assert_eq!(2, lru.len());
    /// assert_eq!(Some(&"def"), lru.lru());
    /// ```
    pub fn get_lru(&mut self) -> Option<(&K, &V)> {
        if self.len() == 0 {
            return None;
        }
        let node_ptr = unsafe { (*self.tail).prev };

        self.detach(node_ptr);
        self.attach(node_ptr);

        Some(unsafe { (&*(*node_ptr).key.as_ptr(), &*(*node_ptr).value.as_ptr()) })
    }

    /// Returns the most recently used key (MRU).
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// assert_eq!(None, lru.mru());
    /// lru.push("abc", true);
    /// assert_eq!(Some(&"abc"), lru.mru());
    /// lru.push("def", false);
    /// assert_eq!(Some(&"def"), lru.mru());
    /// lru.get(&"abc");
    /// assert_eq!(Some(&"abc"), lru.mru());
    /// ```
    pub fn mru(&self) -> Option<&K> {
        if self.len() > 0 {
            let key = unsafe { &(*(*(*self.head).next).key.as_ptr()) };
            Some(key)
        } else {
            None
        }
    }

    /// Pops the most recently used key, returning its value if
    /// the cache was non-empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// assert_eq!(None, lru.pop_mru());
    /// lru.push("abc", true);
    /// lru.push("def", false);
    /// assert_eq!(Some(("def", false)), lru.pop_mru());
    /// assert_eq!(1, lru.len());
    /// ```
    pub fn pop_mru(&mut self) -> Option<(K, V)> {
        if self.len() == 0 {
            return None;
        }
        let node = self.remove_first()?;
        let node = *node;
        let Node { key, value, .. } = node;
        unsafe { Some((key.assume_init(), value.assume_init())) }
    }

    /// Peeks the most recently used key.
    /// Returns its key and value.
    ///
    /// There is no need for a get_mru, as getting the
    /// most recently used key does not alter order,
    /// so peek and get are equivalent.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// assert_eq!(None, lru.peek_mru());
    /// lru.push("abc", true);
    /// lru.push("def", false);
    /// assert_eq!(Some((&"def", &false)), lru.peek_mru());
    /// assert_eq!(2, lru.len());
    /// assert_eq!(Some(&"def"), lru.mru());
    /// ```
    pub fn peek_mru(&self) -> Option<(&K, &V)> {
        match self.mru() {
            Some(mru) => self.peek_key_value(&mru),
            None => None,
        }
    }

    /// Creates an iterator over all the entries.
    ///
    /// Iteration starts with the oldest key.
    /// The last key processed is the newest.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    /// lru.insert("z", 100);
    ///
    /// let sum=lru.iter().map(|x| x.1).sum();
    /// assert_eq!(111, sum);
    /// ```
    pub fn iter(&self) -> Iter<'_, K, V> {
        Iter {
            done: 0,
            len: self.len(),
            forward: unsafe { (*self.head).next },
            backward: unsafe { (*self.tail).prev },
            phantom: PhantomData,
        }
    }

    /// Creates an iterator over mutable entries.
    ///
    /// Iteration starts with the oldest key.
    /// The last key processed is the newest.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    /// lru.insert("z", 100);
    ///
    /// let sum=lru.iter().map(|x| x.1).sum();
    /// assert_eq!(111, sum);
    /// ```
    pub fn iter_mut(&self) -> IterMut<'_, K, V> {
        IterMut {
            done: 0,
            len: self.len(),
            forward: unsafe { (*self.head).next },
            backward: unsafe { (*self.tail).prev },
            phantom: PhantomData,
        }
    }

    /// An iterator over the keys of a LRU cache.
    ///
    /// The order of the iterated entries is guaranteed, it starts
    /// from the oldest (LRU) entry, and finishes by the most recent (MRU) entry.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    /// lru.insert("z", 100);
    ///
    /// let keys: Vec<&&str> = lru.keys().collect();
    /// assert_eq!(vec![&"x", &"y", &"z"], keys);
    /// ```
    pub fn keys(&self) -> Keys<'_, K, V> {
        self.iter().keys()
    }

    /// An iterator over the values of a LRU cache.
    ///
    /// The order of the iterated entries is guaranteed, it starts
    /// from the oldest (LRU) entry, and finishes by the most recent (MRU) entry.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru: Cache<&str, usize> = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    /// lru.insert("z", 100);
    ///
    /// let values: Vec<&usize> = lru.values().collect();
    /// assert_eq!(vec![&1, &10, &100], values);
    /// ```
    pub fn values(&self) -> Values<'_, K, V> {
        self.iter().values()
    }

    /// An iterator over the keys of a LRU cache, taking ownership.
    ///
    /// The order of the iterated entries is guaranteed, it starts
    /// from the oldest (LRU) entry, and finishes by the most recent (MRU) entry.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    /// lru.insert("z", 100);
    ///
    /// let values: Vec<&str> = lru.into_keys().collect();
    /// assert_eq!(vec!["x", "y", "z"], values);
    /// ```
    pub fn into_keys(self) -> IntoKeys<K, V> {
        self.into_iter().keys()
    }

    /// An iterator over the values of a LRU cache, taking ownership.
    ///
    /// The order of the iterated entries is guaranteed, it starts
    /// from the oldest (LRU) entry, and finishes by the most recent (MRU) entry.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru: Cache<&str, usize> = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    /// lru.insert("z", 100);
    ///
    /// let values: Vec<usize> = lru.into_values().collect();
    /// assert_eq!(vec![1, 10, 100], values);
    /// ```
    pub fn into_values(self) -> IntoValues<K, V> {
        self.into_iter().values()
    }

    /// Import data from an iterator, typically the iterator returned by into_iter().
    ///
    /// The data is not cleared before import, so values add to the existing ones.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache1 = Cache::new(5);
    /// cache1.insert("a", 0);
    /// cache1.insert("b", 1);
    /// cache1.insert("c", 2);
    /// let mut cache2 = Cache::new(10);
    /// cache2.insert("d", 3);
    /// cache2.import(cache1.into_iter());
    /// assert_eq!(4, cache2.len());
    /// assert_eq!("[d: 3, a: 0, b: 1, c: 2]", format!("{}", &cache2));
    /// ```
    pub fn import<I>(&mut self, iter: I) -> usize
    where
        I: Iterator<Item = (K, V)>,
    {
        for i in iter {
            self.insert(i.0, i.1);
        }
        self.len()
    }
}

impl<K, V> Cache<K, V> where K: Hash + Eq + Clone {}

impl<K, V> std::iter::IntoIterator for Cache<K, V>
where
    K: Eq + Hash,
{
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;

    /// Creates an iterator over all the keys.
    /// Iteration starts with the oldest key.
    /// The last key processed is the newest.
    ///
    /// Takes ownership.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut lru = Cache::new(10);
    /// lru.insert("x", 1);
    /// lru.insert("y", 10);
    /// lru.insert("z", 100);
    ///
    /// let sum=lru.into_iter().map(|x| x.1).sum();
    /// assert_eq!(111, sum);
    /// ```
    fn into_iter(self) -> IntoIter<K, V> {
        IntoIter {
            len: self.len(),
            cache: self,
        }
    }
}

impl<K, V> FromIterator<(K, V)> for Cache<K, V>
where
    K: Eq + Hash + Clone,
{
    /// Creates a new cache from an iterator.
    ///
    /// With this, you can use collect() to build a cache.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    /// use std::collections::HashMap;
    ///
    /// let mut src: HashMap<usize, &str> = HashMap::new();
    /// src.insert(1, "two");
    /// src.insert(2, "four");
    /// src.insert(3, "eight");
    ///
    /// let mut cache = src.into_iter().filter(|x| x.0 != 2).collect::<Cache<usize, &str>>();
    /// assert_eq!(2, cache.len());
    /// assert_eq!(Some(&"two"), cache.get(&1));
    /// assert_eq!(Some(&"eight"), cache.get(&3));
    /// ```
    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
        let mut c = Cache::new(0);

        for i in iter {
            c.resize(c.len() + 1);
            c.push(i.0, i.1);
        }

        c
    }
}

impl<K, V> Cache<K, V>
where
    K: Hash + Eq + Clone,
    V: Clone,
{
    /// Creates a dump of all keys and values, provided
    /// both have the Clone trait.
    ///
    /// The dump has a complete copy of all data, with ownership.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::{Cache, Dump};
    ///
    /// let mut cache = Cache::new(10);
    /// cache.insert("x", 1);
    /// cache.insert("y", 10);
    /// cache.insert("z", 100);
    ///
    /// let dump = cache.dump();
    /// assert_eq!("Dump { capacity: 10, data: [(\"x\", 1), (\"y\", 10), (\"z\", 100)] }", format!("{:?}", &dump));
    /// // another way to make a dump, taking ownership
    /// let final_dump = Dump::from(cache);
    /// ```
    pub fn dump(&self) -> Dump<K, V> {
        Dump {
            capacity: self.capacity(),
            data: self.to_vec(),
        }
    }

    /// Restores data from a dump. Clears the data before
    /// importing the dump.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::{Cache, Dump};
    ///
    /// let dump = Dump {
    ///     capacity: 10,
    ///     data: vec![("x", 1), ("y", 10), ("z", 100)],
    /// };
    /// let mut cache = Cache::new(2);
    /// assert_eq!(2, cache.capacity());
    /// cache.insert("a", 0);
    /// cache.insert("b", 1);
    /// cache.insert("c", 2);
    /// assert_eq!(2, cache.len());
    /// assert_eq!(3, cache.restore(&dump));
    /// assert_eq!(10, cache.capacity());
    /// assert_eq!("[x: 1, y: 10, z: 100]", format!("{}", &cache));
    /// // another way to restore, taking ownership
    /// let other_cache = Cache::from(dump);
    /// ```
    pub fn restore(&mut self, dump: &Dump<K, V>) -> usize {
        self.clear();
        self.resize(dump.capacity);
        for i in dump.data.iter() {
            self.insert(i.0.clone(), i.1.clone());
        }
        self.len()
    }

    /// Import data from an iterator, typically the iterator returned by iter().
    ///
    /// The data is not cleared before import, so values add to the existing ones.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache1 = Cache::new(5);
    /// cache1.insert("a", 0);
    /// cache1.insert("b", 1);
    /// cache1.insert("c", 2);
    /// let mut cache2 = Cache::new(10);
    /// cache2.insert("d", 3);
    /// cache2.import_iter(cache1.iter());
    /// assert_eq!(4, cache2.len());
    /// assert_eq!("[a: 0, b: 1, c: 2]", format!("{}", &cache1));
    /// assert_eq!("[d: 3, a: 0, b: 1, c: 2]", format!("{}", &cache2));
    /// ```
    pub fn import_iter<'a, I>(&mut self, iter: I) -> usize
    where
        K: 'a,
        V: 'a,
        I: Iterator<Item = (&'a K, &'a V)>,
    {
        for i in iter {
            self.insert(i.0.clone(), i.1.clone());
        }
        self.len()
    }

    /// Exports all items as a map.
    ///
    /// Does not preserve order.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache = Cache::new(10);
    /// cache.insert("x", 1);
    /// cache.insert("y", 10);
    /// cache.insert("z", 100);
    ///
    /// let map = cache.to_map();
    /// assert_eq!(3, map.len());
    /// assert_eq!(Some(&1), map.get(&"x"));
    /// assert_eq!(Some(&10), map.get(&"y"));
    /// assert_eq!(Some(&100), map.get(&"z"));
    /// ```
    pub fn to_map(&self) -> HashMap<K, V> {
        let mut map: HashMap<K, V> = HashMap::with_capacity(self.len());
        for i in self.iter() {
            map.insert(i.0.clone(), i.1.clone());
        }
        map
    }

    /// Exports all items as a vec.
    ///
    /// Preserves order, LRU has index 0.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache = Cache::new(10);
    /// cache.insert("x", 1);
    /// cache.insert("y", 10);
    /// cache.insert("z", 100);
    ///
    /// let vec = cache.to_vec();
    /// assert_eq!(vec![("x", 1), ("y", 10), ("z", 100)], vec);
    /// ```
    pub fn to_vec(&self) -> Vec<(K, V)> {
        let mut vec: Vec<(K, V)> = Vec::with_capacity(self.len());
        for i in self.iter() {
            vec.push((i.0.clone(), i.1.clone()));
        }
        vec
    }
}

impl<K, V> Clone for Cache<K, V>
where
    K: Hash + Eq + Clone,
    V: Clone,
{
    /// Clones a LRU cache, provided the values have the Clone trait.
    ///
    /// This is a costly operation, duplicates all underlying data.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache1 = Cache::new(10);
    /// cache1.insert("a", "Alice");
    /// cache1.insert("b", "Bob");
    /// let cache2 = cache1.clone();
    /// assert_eq!(&cache1, &cache2);
    /// cache1.insert("o", "Oscar");
    /// assert_ne!(&cache1, &cache2);
    /// ```
    fn clone(&self) -> Self {
        let mut cloned = Cache::new(self.capacity);
        cloned.import_iter(self.iter());
        cloned
    }
}

impl<K, V> PartialEq<Cache<K, V>> for Cache<K, V>
where
    K: Hash + Eq + Clone,
    V: PartialEq,
{
    /// Compares two caches. Capacity, content and order must match.
    ///
    /// # Examples
    ///
    /// ```
    /// use hashlru::Cache;
    ///
    /// let mut cache1 = Cache::new(10);
    /// cache1.insert("a", "Alice");
    /// cache1.insert("b", "Bob");
    /// let mut cache2 = Cache::new(10);
    /// cache2.insert("a", "Alice");
    /// cache2.insert("b", "Bob");
    /// cache2.insert("o", "Oscar");
    /// assert_ne!(&cache1, &cache2);
    /// cache2.remove(&"o");
    /// assert_eq!(&cache1, &cache2);
    /// cache1.get(&"a"); // changes order
    /// assert_ne!(&cache1, &cache2);
    /// ```
    fn eq(&self, other: &Self) -> bool {
        if self.capacity != other.capacity {
            return false;
        }
        if self.len() != other.len() {
            return false;
        }
        let mut iter_other = other.iter();
        for self_v in self.iter() {
            match iter_other.next() {
                Some(other_v) => {
                    if self_v != other_v {
                        return false;
                    }
                }
                None => return false,
            }
        }
        true
    }
}

impl<K, V> Eq for Cache<K, V>
where
    K: Hash + Eq + Clone,
    V: Eq,
{
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::Rng;
    use std::collections::HashSet;
    use std::fmt::Debug;
    use std::hash::Hash;

    impl<K, V> Cache<K, V>
    where
        K: Hash + Eq + Clone + Debug,
    {
        fn check_order(&self) {
            let n = self.len();
            if n > 0 {
                let mut keys = HashSet::new();
                let mut iter_keys = self.keys();
                for _ in 0..n {
                    let k = iter_keys.next().unwrap();
                    keys.insert(k);
                }
                assert_eq!(n, keys.len());

                keys.clear();
                let mut iter_keys = self.keys();
                for _ in 0..n {
                    let k = iter_keys.next_back().unwrap();
                    keys.insert(k);
                }
                assert_eq!(n, keys.len());
            }
        }
    }

    #[test]
    fn test_debug() {
        let mut lru = Cache::<i32, &str>::new(7);
        lru.insert(1, "abc");
        lru.insert(2, "def");
        lru.insert(3, "fgh");

        let debug = format!("{:?}", lru);
        assert_eq!("Cache [ (1, \"abc\"), (2, \"def\"), (3, \"fgh\") ]", debug);

        let mut iter = lru.iter();
        iter.next();
        iter.next();
        let mut debug_iter = format!("{:?}", iter);
        assert_eq!(
            "Iter { done: 2, len: 3, next: 3, next_back: 3 }",
            debug_iter
        );
        iter.next();
        debug_iter = format!("{:?}", iter);
        assert_eq!("Iter { done: 3, len: 3 }", debug_iter);
    }

    #[test]
    fn test_display() {
        let mut lru = Cache::<i32, &str>::new(7);
        lru.insert(1, "abc");
        lru.insert(2, "def");
        lru.insert(3, "fgh");

        let display = format!("{}", lru);
        assert_eq!("[1: abc, 2: def, 3: fgh]", display);

        let mut iter = lru.iter();
        iter.next();
        let display_iter = format!("{}", iter);
        assert_eq!("1/3, next: 2, next_back: 3", display_iter);
    }

    #[test]
    fn test_standard_map() {
        let mut lru = Cache::new(1000); // 1000 means no limit, for the sake of this test
        assert_eq!(None, lru.insert(1, "one"));
        lru.check_order();
        assert_eq!(None, lru.insert(2, "two"));
        lru.check_order();
        assert_eq!(None, lru.insert(3, "three"));
        lru.check_order();
        assert_eq!(3, lru.len());
        assert_eq!(Some("one"), lru.insert(1, "ONE"));
        assert_eq!(None, lru.remove(&4));
        assert_eq!(Some("ONE"), lru.remove(&1));
        lru.check_order();
        assert_eq!(Some("two"), lru.remove(&2));
        lru.check_order();
        assert_eq!(Some("three"), lru.remove(&3));
        lru.check_order();
        assert_eq!(None, lru.remove(&1));
    }

    #[test]
    fn test_pop() {
        let mut cache: Cache<usize, usize> = Cache::new(10);
        assert_eq!(None, cache.insert(1, 10));
        assert_eq!(None, cache.insert(2, 20));
        assert_eq!(None, cache.insert(3, 30));
        assert_eq!(10, cache.capacity());
        assert_eq!(3, cache.len());
        assert_eq!(Some((2, 20)), cache.pop(&2));
        assert_eq!(None, cache.pop(&2));
        assert_eq!(Some(&1), cache.lru());
        assert_eq!(Some(&3), cache.mru());
        assert_eq!(Some((1, 10)), cache.pop(&1));
        assert_eq!(Some((3, 30)), cache.pop(&3));
        assert_eq!(0, cache.len());
        assert_eq!(None, cache.pop(&3));
    }

    #[test]
    fn test_lru0() {
        let mut lru = Cache::new(0);
        assert_eq!(0, lru.len());
        assert_eq!(0, lru.capacity());
        assert_eq!(None, lru.insert(1, "one"));
        assert_eq!(0, lru.len());
        assert_eq!(0, lru.capacity());
        assert_eq!(None, lru.pop_lru());
        assert_eq!(None, lru.remove(&1));
        assert_eq!("Cache []", format!("{:?}", lru));
        assert_eq!("[]", format!("{}", lru));
    }

    #[test]
    fn test_lru1() {
        let mut lru = Cache::new(1);
        assert_eq!(0, lru.len());
        assert_eq!(1, lru.capacity());
        assert_eq!(None, lru.push(1, "two"));
        assert_eq!(1, lru.len());
        assert_eq!(Some(&"two"), lru.peek(&1));
        assert_eq!(Some(&"two"), lru.get(&1));
        assert_eq!(None, lru.push(1, "one")); // nothing returned because we push same key
        assert_eq!(Some("one"), lru.insert(1, "ONE")); // previous value for one returned
        assert_eq!(Some((1, "ONE")), lru.push(2, "two")); // lru value returned because cache full
        assert_eq!(None, lru.insert(1, "one")); // nothing returned because we push new key
        assert_eq!(1, lru.len());
        assert_eq!("Cache [ (1, \"one\") ]", format!("{:?}", lru));
        assert_eq!("[1: one]", format!("{}", lru));
    }

    #[test]
    fn test_lru5() {
        let mut lru = Cache::new(5);
        assert_eq!(None, lru.insert(1, "one"));
        assert_eq!(None, lru.insert(2, "two"));
        assert_eq!(None, lru.insert(3, "three"));
        assert_eq!(Some("three"), lru.insert(3, "THREE"));
        assert_eq!(None, lru.insert(4, "four"));
        assert_eq!(None, lru.insert(5, "five"));
        assert_eq!(None, lru.insert(6, "six"));
        assert_eq!(5, lru.len());
        assert_eq!(None, lru.get(&1));
        assert_eq!(None, lru.insert(7, "seven"));
        assert_eq!(5, lru.len());
        assert_eq!(Some(&"seven"), lru.get(&7));
        assert_eq!(5, lru.len());
        assert_eq!(None, lru.get(&1));
        assert_eq!(None, lru.get(&2));
        lru.check_order();
        assert_eq!(Some(&"THREE"), lru.get(&3));
        lru.check_order();
        assert_eq!(Some(&"four"), lru.get(&4));
        assert_eq!(None, lru.insert(8, "eight"));
        assert_eq!(None, lru.insert(9, "nine"));
        assert_eq!(None, lru.insert(10, "ten"));
        assert_eq!(None, lru.insert(11, "eleven"));
        assert_eq!(5, lru.len());
        assert_eq!(
            "Cache [ (4, \"four\"), (8, \"eight\"), (9, \"nine\"), (10, \"ten\"), (11, \"eleven\") ]",
            format!("{:?}", lru)
        );
        assert_eq!(
            "[4: four, 8: eight, 9: nine, 10: ten, 11: eleven]",
            format!("{}", lru)
        );
        assert_eq!(Some(&"four"), lru.get(&4));
        assert_eq!(None, lru.get(&3));
        assert_eq!(Some("eight"), lru.remove(&8));
        assert_eq!(Some("nine"), lru.remove(&9));
        assert_eq!(Some("ten"), lru.remove(&10));
        assert_eq!(Some("eleven"), lru.remove(&11));
        assert_eq!(Some("four"), lru.remove(&4));
        assert_eq!(0, lru.len());
    }

    #[test]
    fn test_lru100() {
        let mut lru = Cache::new(100);
        for i in 0..1000 {
            lru.push(i, format!("value_{}", i));
            lru.check_order();
        }
        assert_eq!(100, lru.len());
        assert!(format!("{:?}", lru).starts_with("Cache [ (900, \"value_900\"), "));
        assert_eq!(
            "[900: value_900, 901: value_901, ..., 999: value_999]",
            format!("{}", lru)
        );

        assert_eq!(Some(&"value_950".to_string()), lru.get(&950));
        assert_eq!(
            Some((&950, &"value_950".to_string())),
            lru.get_key_value(&950)
        );
        assert_eq!(Some((&950, &"value_950".to_string())), lru.peek_mru());
        assert_eq!(Some(&950), lru.mru());
        assert_eq!(Some((&900, &"value_900".to_string())), lru.get_lru());
        assert_eq!(Some((&901, &"value_901".to_string())), lru.get_lru());
        assert_eq!(Some((&902, &"value_902".to_string())), lru.peek_lru());
        assert_eq!(Some((&902, &"value_902".to_string())), lru.peek_lru());
        assert_eq!(
            "[902: value_902, 903: value_903, ..., 901: value_901]",
            format!("{}", lru)
        );
        assert_eq!(Some(&902), lru.lru());
        assert_eq!(Some((&901, &"value_901".to_string())), lru.peek_mru());
        assert_eq!(Some(&901), lru.mru());
    }

    #[derive(Debug, Eq, PartialEq, Clone)]
    struct Coord {
        x: i64,
        y: i64,
    }

    #[test]
    fn test_monkey() {
        let mut cache: Cache<String, Coord> = Cache::new(50);
        let mut rng = rand::thread_rng();
        let mut dummy: i64 = 0;
        for i in 0..1_000_000 {
            if i % 1000 == 0 {
                print!(".");
            }
            if i % 100_000 == 0 {
                cache.clear();
                continue;
            }
            let dice = rng.gen_range(0..=100);
            if dice < 20 {
                let key = format!("key_{}", i % 100);
                let value = Coord {
                    x: i % 89,
                    y: i % 97,
                };
                cache.insert(key, value);
                continue;
            }
            if dice < 40 {
                let key = format!("key_{}", i % 100);
                let value = Coord {
                    x: i % 89,
                    y: i % 97,
                };
                cache.push(key, value);
                continue;
            }
            if dice < 50 {
                let key = format!("key_{}", i % 10);
                cache.get(&key);
                continue;
            }
            if dice < 60 {
                let key = format!("key_{}", i % 10);
                cache.peek(&key);
                continue;
            }
            if dice < 70 {
                let key = format!("key_{}", i % 10);
                cache.pop(&key);
                continue;
            }
            if dice < 80 {
                let key = format!("key_{}", i % 10);
                cache.remove(&key);
                continue;
            }
            if dice < 81 {
                let dump = cache.dump();
                let mut other: Cache<String, Coord> = Cache::new(100);
                other.restore(&dump);
            }
            if dice < 83 {
                for kv in cache.iter() {
                    dummy += kv.1.x * kv.1.y;
                }
            }
            if dice < 85 {
                for v in cache.values() {
                    dummy += v.x * v.y;
                }
            }
        }
        assert_ne!(0, dummy);
    }
}