146. LRU Cache

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Rust Solution

use std::cell::RefCell;
use std::collections::HashMap;
use std::fmt::Debug;
use std::fmt::Error;
use std::fmt::Formatter;
use std::rc::{Rc, Weak};

type NodeRef = Rc<RefCell<Node>>;
type Link = Option<NodeRef>;

#[derive(Debug, Clone)]
struct Element {
    key: i32,
    val: i32,
}

impl Element {
    fn new(key: i32, val: i32) -> Self {
        Element { key, val }
    }
}

#[derive(Debug)]
struct Node {
    element: Element,
    prev: Link,
    next: Link,
}

impl Node {
    fn new(element: Element) -> Self {
        Node {
            element,
            prev: None,
            next: None,
        }
    }
    fn into_ref(self) -> NodeRef {
        Rc::new(RefCell::new(self))
    }
}

#[derive(Default)]
struct List {
    head: Link,
    tail: Link,
}

impl List {
    fn new() -> Self {
        List {
            head: None,
            tail: None,
        }
    }

    fn push_back(&mut self, new_node_ref: NodeRef) {
        new_node_ref.borrow_mut().prev = self.tail.clone();
        match self.tail.clone() {
            None => self.head = Some(new_node_ref.clone()),
            Some(last_node_ref) => last_node_ref.borrow_mut().next = Some(new_node_ref.clone()),
        }
        self.tail = Some(new_node_ref);
    }

    fn pop_front(&mut self) -> Option<Element> {
        self.head.clone().map(|node_ref| {
            let mut node = node_ref.borrow_mut();
            if let Some(next_node_ref) = node.next.take() {
                let mut next_node = next_node_ref.borrow_mut();
                next_node.prev = None;
                self.head = Some(next_node_ref.clone());
            } else {
                self.head = None;
                self.tail = None;
            }
            node.element.clone()
        })
    }

    fn unlink_node(&mut self, node_ref: NodeRef) -> Element {
        let mut node = node_ref.borrow_mut();
        let prev = node.prev.take();
        let next = node.next.take();
        match prev.clone() {
            Some(prev_node_ref) => prev_node_ref.borrow_mut().next = next.clone(),
            None => self.head = next.clone(),
        }
        match next {
            Some(next_node_ref) => next_node_ref.borrow_mut().prev = prev,
            None => self.tail = prev,
        }
        node.element.clone()
    }
    fn iter(&self) -> ListIter {
        ListIter::new(self.head.clone(), self.tail.clone())
    }
}

impl Debug for List {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
        f.debug_list().entries(self.iter()).finish()
    }
}

impl Drop for List {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

struct ListIter {
    head: Link,
    tail: Link,
}

impl ListIter {
    fn new(head: Link, tail: Link) -> Self {
        ListIter { head, tail }
    }
}

impl Iterator for ListIter {
    type Item = Element;
    fn next(&mut self) -> Option<Self::Item> {
        self.head.clone().map(|node_ref| {
            let node = node_ref.borrow();
            self.head = node.next.clone();
            node.element.clone()
        })
    }
}

#[derive(Debug)]
struct LRUCache {
    hash_map: HashMap<i32, Weak<RefCell<Node>>>,
    list: List,
    length: usize,
    capacity: usize,
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        let hash_map: HashMap<i32, Weak<RefCell<Node>>> = HashMap::new();
        let list: List = List::new();
        let length = 0;
        let capacity = capacity as usize;
        LRUCache {
            hash_map,
            list,
            length,
            capacity,
        }
    }

    fn get(&mut self, key: i32) -> i32 {
        if let Some(element) = self.get_element(key) {
            element.val
        } else {
            -1
        }
    }

    fn put(&mut self, key: i32, val: i32) {
        if self.put_element(key, val).is_none() {
            self.length += 1;
        }
        if self.length > self.capacity {
            self.pop_element();
            self.length -= 1;
        }
    }

    fn pop_element(&mut self) -> Option<Element> {
        if let Some(element) = self.list.pop_front() {
            self.hash_map.remove(&element.key);
            Some(element)
        } else {
            None
        }
    }

    fn put_element(&mut self, key: i32, val: i32) -> Option<Element> {
        if let Some(node_ref) = self.get_ref(key) {
            let old_element = self.list.unlink_node(node_ref);
            let new_element = Element::new(key, val);
            let new_node_ref = Node::new(new_element).into_ref();
            self.hash_map.insert(key, Rc::downgrade(&new_node_ref));
            self.list.push_back(new_node_ref);
            Some(old_element)
        } else {
            let new_element = Element::new(key, val);
            let new_node_ref = Node::new(new_element).into_ref();
            self.hash_map.insert(key, Rc::downgrade(&new_node_ref));
            self.list.push_back(new_node_ref);
            None
        }
    }

    fn get_element(&mut self, key: i32) -> Option<Element> {
        if let Some(node_ref) = self.get_ref(key) {
            let old_element = self.list.unlink_node(node_ref);
            let new_element = Element::new(old_element.key, old_element.val);
            let new_node_ref = Node::new(new_element).into_ref();
            self.hash_map.insert(key, Rc::downgrade(&new_node_ref));
            self.list.push_back(new_node_ref);
            Some(old_element)
        } else {
            None
        }
    }

    fn get_ref(&mut self, key: i32) -> Option<NodeRef> {
        if let Some(weak) = self.hash_map.remove(&key) {
            if let Some(node_ref) = weak.upgrade() {
                Some(node_ref)
            } else {
                None
            }
        } else {
            None
        }
    }
}

#[test]
fn test() {
    let mut obj = LRUCache::new(2);
    assert_eq!(obj.get(2), -1);
    obj.put(2, 6);
    assert_eq!(obj.get(1), -1);
    obj.put(1, 5);
    obj.put(1, 2);
    assert_eq!(obj.get(1), 2);
    assert_eq!(obj.get(2), 6);

    let mut obj = LRUCache::new(3);
    obj.put(1, 1);
    obj.put(2, 2);
    obj.put(3, 3);
    obj.put(4, 4);
    assert_eq!(obj.get(4), 4);
    assert_eq!(obj.get(3), 3);
    assert_eq!(obj.get(2), 2);
    assert_eq!(obj.get(1), -1);
    obj.put(5, 5);
    assert_eq!(obj.get(1), -1);
    assert_eq!(obj.get(2), 2);
    assert_eq!(obj.get(3), 3);
    assert_eq!(obj.get(4), -1);
    assert_eq!(obj.get(5), 5);
}