use alloc::{
    collections::{BTreeMap, LinkedList},
    vec::Vec,
};
use core::{cmp::Ord, fmt, mem};


/// Реализация политики вытеснения давно неиспользуемых данных
/// ([Least Recently Used (LRU)](https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU)).
///
/// Предполагает, что ключ `K` и значение `V` --- легковесные типы.
/// А сам кеш хранит своё содержимое где-то в другом месте.
#[derive(Clone, Debug)]
pub struct Lru<K, V>
where
    K: Clone + Copy + Ord,
    V: Clone + Copy,
{
    /// Отображение ключей в индексы, по которым хранятся узлы со значениями.
    /// То есть, значения [`Lru::map`] --- это индексы в [`Lru::nodes`].
    map: BTreeMap<K, usize>,

    /// Хранилище для узлов, отображающих ключи в значения.
    /// Эти же узлы провязаны в LRU--очередь на основе двусвязного списка.
    /// LRU--очередь перечисляет узлы в порядке их последнего использования,
    /// от дольше всего не использовавшегося до использованного последним.
    nodes: Vec<Node<K, V>>,

    /// Голова LRU--очереди --- узел, который не использовался дольше всего.
    head: Option<usize>,

    /// Хвост LRU--очереди --- узел, который использовался последним.
    tail: Option<usize>,
}


#[derive(Clone, Debug)]
/// Узел LRU--очереди.
///
/// LRU--очередь перечисляет узлы в порядке их последнего использования,
/// от дольше всего не использовавшегося до использованного последним.
struct Node<K, V> {
    /// Ключ.
    key: K,

    /// Значение.
    value: V,

    /// Предыщущий узел, он использовался последний раз перед последним использованием текущего.
    /// Хранится как индекс в [`Lru::nodes`].
    prev: Option<usize>,

    /// Следующий узел, он использовался последний раз после последнего использования текущего.
    /// Хранится как индекс в [`Lru::nodes`].
    next: Option<usize>,
}


impl<K, V> Lru<K, V>
where
    K: Clone + Copy + Ord,
    V: Clone + Copy,
{
    /// Создаёт LRU--кеш с ограничением на ёмкость `capacity`.
    ///
    /// # Panics
    ///
    /// Паникует, если ограничение на ёмкость нулевое.
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0);

        Self {
            nodes: Vec::with_capacity(capacity),
            map: BTreeMap::new(),
            head: None,
            tail: None,
        }
    }


    /// Сохраняет в кеш заданную пару ключ--значение.
    /// Обновляет время доступа к записи, если она есть.
    /// Возвращает:
    ///   - Пару ключ--значение, которую при этом пришлось вытеснить из кеша,
    ///     если до операции уже было достигнуто ограничение на его текущую ёмкость.
    ///   - [`None`], если ограничение на текущую ёмкость кеша
    ///     не было достигнуто на момент начала операции.
    pub fn insert(&mut self, key: K, value: V) -> Option<(K, V)> {
        if self.map.contains_key(&key) {
            self.get(key).unwrap();
            return None;
        }

        let mut poped = None;
        if self.nodes.len() == self.nodes.capacity() {
            poped = self.pop();
            poped.unwrap();
        }

        assert!(self.nodes.len() < self.nodes.capacity());
        let node = Node::<K, V> {
            key,
            value,
            prev: self.tail,
            next: None,
        };
        self.nodes.push(node);
        self.tail = Some(self.nodes.len() - 1);
        self.map.insert(key, self.tail.unwrap());

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

        poped
    }


    /// Возвращает значение для заданного ключа `key`,
    /// или [`None`], если соответствующей записи нет.
    /// Обновляет время доступа к записи, если она есть.
    pub fn get(&mut self, key: K) -> Option<V> {
        let maybe_id = self.map.get(&key);
        if maybe_id.is_none() {
            return None;
        }
        let id = *maybe_id.unwrap();

        self.set_next_in_prev(id, self.nodes[id].next);
        self.set_prev_in_next(id, self.nodes[id].prev);

        let old_tail = self.tail;
        {
            let node = self.nodes.get_mut(id).unwrap();
            self.tail = Some(id);
            node.prev = old_tail;
            node.next = None;
        }

        if let Some(old_tail) = old_tail {
            self.nodes.get_mut(old_tail).unwrap().next = Some(id);
        }

        Some(self.nodes[id].value)
    }


    /// Удаляет из кеша запись с заданным ключём `key`, если она есть.
    /// Возвращает:
    ///   - Значение для удалённого ключа.
    ///   - [`None`], если по ключу `key` в кеше ничего не найдено.
    pub fn remove(&mut self, key: K) -> Option<V> {
        // info!("in remove");
        let maybe_id = self.map.get(&key);
        if maybe_id.is_none() {
            return None;
        }
        let id = *maybe_id.unwrap();

        Some(self.remove_node(id).unwrap().1)
    }


    /// Удаляет из кеша запись, которая дольше всех остальных не обновлялась.
    /// Возвращает удалённую пару ключ--значение.
    fn pop(&mut self) -> Option<(K, V)> {
        if let Some(id) = self.head {
            self.remove_node(id)
        } else {
            None
        }
    }


    /// Удаляет из кеша запись по её индексу `id` в [`Lru::nodes`].
    /// Возвращает удалённую пару ключ--значение.
    fn remove_node(&mut self, id: usize) -> Option<(K, V)> {
        self.map.remove(&self.nodes[id].key).unwrap();

        self.set_next_in_prev(id, self.nodes[id].next);
        self.set_prev_in_next(id, self.nodes[id].prev);

        let sz = self.nodes.len();
        if id != sz - 1 {
            self.nodes.swap(id, sz - 1);

            self.set_next_in_prev(id, Some(id));
            self.set_prev_in_next(id, Some(id));

            self.map.insert(self.nodes[id].key, id).unwrap();

            if self.head.unwrap() == sz - 1 {
                self.head = Some(id);
            }
            if self.tail.unwrap() == sz - 1 {
                self.tail = Some(id);
            }
        }

        let node = self.nodes.pop().unwrap();

        Some((node.key, node.value))
    }


    /// Устанавливает в `next` ссылку [`Node::next`] узла,
    /// который предшествует узлу номер `id` в структуре очереди,
    /// либо обновляет [`Lru::head`], если предшествующего узла нет.
    fn set_next_in_prev(&mut self, id: usize, next: Option<usize>) {
        let node = self.nodes.get(id).unwrap();

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


    /// Устанавливает в `prev` ссылку [`Node::prev`] узла,
    /// который следует за узлом номер `id` в структуре очереди,
    /// либо обновляет [`Lru::tail`], если следующего узла нет.
    fn set_prev_in_next(&mut self, id: usize, prev: Option<usize>) {
        let node = self.nodes.get(id).unwrap();

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


    /// Проверяет внутренние инварианты LRU--кеша
    ///
    /// # Panics
    ///
    /// Паникует, если инварианты нарушены.
    pub fn validate(&self) {
        let mut curr = self.head;
        let mut prev = None;
        let mut tail = None;
        let mut count = 0;

        assert_eq!(self.nodes.len(), self.map.len());
        assert!(self.nodes.len() <= self.nodes.capacity());

        while let Some(id) = curr {
            assert!(count < self.nodes.len());
            assert!(id < self.nodes.len());

            let node = &self.nodes[id];

            assert_eq!(node.prev, prev);
            assert_eq!(self.map.get(&node.key), Some(&id));

            prev = curr;
            curr = node.next;
            if curr.is_none() {
                tail = Some(id);
            }

            count += 1;
        }

        assert_eq!(self.tail, tail);
    }
}


impl<K, V> fmt::Display for Lru<K, V>
where
    K: Clone + Copy + Ord + fmt::Display,
    V: Clone + Copy + fmt::Display,
{
    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
        write!(
            formatter,
            "head: {:?}, tail: {:?}, lru: [",
            self.head, self.tail,
        )?;

        let mut separator = "";
        let mut curr = self.head;

        while let Some(id) = curr {
            let node = &self.nodes[id];

            write!(
                formatter,
                "{}{{id: {}, key: {}, value: {}, prev: {:?}, next: {:?}}}",
                separator, id, node.key, node.value, node.prev, node.next,
            )?;

            curr = node.next;
            separator = ", ";
        }

        write!(formatter, "], map: {{")?;

        separator = "";
        for (key, id) in self.map.iter() {
            let value = &self.nodes[*id].value;
            write!(formatter, "{}{} -> {} [{}]", separator, key, value, id)?;
            separator = ", ";
        }

        write!(formatter, "}}")
    }
}