learn-alg 0.1.0

// 使用rust来实现各种算法
// 本节是一个lru缓存算法
// 如何实现一个lru
// 1. 当有新数据访问链表时,从链表头开始顺序访问链表
// 2. 如果遍历发现存在对应的链表元素了,就把链表这个位置的元素移动(删除该位置,再在头部插入)到头部
// 如果没有,则分两种情况,缓存未满,则直接插入到头部,缓存已满,则删除链表尾结点元素,然后把新元素插入到头结点.
// 时间复杂度O(n),因为要完全遍历(可以通过散列表来优化)
use std::cell::{Ref, RefCell};
use std::collections::HashMap;
use std::rc::{Rc, Weak};
type PNode = Rc<RefCell<ListNode>>;

#[derive(Debug, Default)]
struct ListNode {
    key: i32,
    value: i32,
    next: Option<PNode>,
    prev: Option<Weak<RefCell<ListNode>>>,
}
impl ListNode {
    fn new(key: i32, value: i32) -> Self {
        ListNode {
            key,
            value,
            next: None,
            prev: None,
        }
    }
    fn pop(node: PNode) -> PNode {
        let prev = node.borrow_mut().prev.take().unwrap().upgrade().unwrap();
        let next = node.borrow_mut().next.take().unwrap();
        prev.borrow_mut().next = Some(Rc::clone(&next));
        next.borrow_mut().prev = Some(Rc::downgrade(&prev));
        node
    }
    fn push_after_head(node: PNode, head: PNode) {
        let next = head.borrow_mut().next.take();
        next.as_ref().unwrap().borrow_mut().prev = Some(Rc::downgrade(&node));
        node.borrow_mut().next = next;
        node.borrow_mut().prev = Some(Rc::downgrade(&head));
        head.borrow_mut().next = Some(node);
    }
}
#[derive(Debug)]
struct LRUCache {
    map: HashMap<i32, Option<PNode>>,
    head: Option<PNode>,
    tail: Option<PNode>,
    capacity: i32,
}
// impl Display for LRUCache {
//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
//         let mut node = self.head.as_ref();
//         while let Some(cur) = node{
//             write!(f, "key:{:?},value:{:?}", cur.borrow().key,cur.borrow().value).unwrap();
//             node = node.unwrap().borrow().next;
//         }
//         Ok(())
        
//     }
// }
impl LRUCache {
    fn new(capacity: i32) -> Self {
        let head_node = Rc::new(RefCell::new(ListNode::default()));
        let tail_node = Rc::new(RefCell::new(ListNode::default()));
        head_node.borrow_mut().next = Some(Rc::clone(&tail_node));
        tail_node.borrow_mut().prev = Some(Rc::downgrade(&head_node));

        LRUCache {
            map: HashMap::new(),
            head: Some(head_node),
            tail: Some(tail_node),
            capacity,
        }
    }
    fn get(&self, key: i32) -> i32 {
        if let Some(item) = self.map.get(&key) {
            let node = item.as_ref().unwrap();
            let node = ListNode::pop(Rc::clone(node));
            let value = node.borrow().value;
            ListNode::push_after_head(node, Rc::clone(self.head.as_ref().unwrap()));
            value
        } else {
            -1
        }
    }
    fn put(&mut self, key: i32, value: i32) {
        if let Some(item) = self.map.get(&key) {
            let node = item.as_ref().unwrap();
            let node = ListNode::pop(Rc::clone(node));
            node.borrow_mut().value = value;
            ListNode::push_after_head(node, Rc::clone(self.head.as_ref().unwrap()));
        } else {
            if self.map.len() >= self.capacity as usize {
                let del_node = self
                    .tail
                    .as_ref()
                    .unwrap()
                    .borrow()
                    .prev
                    .as_ref()
                    .unwrap()
                    .upgrade()
                    .unwrap();
                let del_node = ListNode::pop(del_node);
                self.map.remove(&del_node.borrow().key);
            }
            let new_node = Rc::new(RefCell::new(ListNode::new(key, value)));
            self.map.insert(key, Some(Rc::clone(&new_node)));
            ListNode::push_after_head(new_node, Rc::clone(self.head.as_ref().unwrap()));
        }
    }
}

fn main() {
    let mut lru = LRUCache::new(3);
    lru.put(1, 1);
    lru.put(2, 2);
    lru.put(3, 3);
    lru.put(4, 4);
    lru.get(1);
    println!("{:?}",lru.map);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_lru() {
        let mut lru = LRUCache::new(10);
        lru.put(1, 1);
        lru.put(2, 2);
        lru.put(3, 3);
        lru.put(4, 4);
        lru.get(1);
        println!("{:?}",lru.map);
    }
}