lru.cpp

lru.cpp

LRU Cache

insert -- touch the value, update the value
init -- initialize w/ capacity
get -- get the value associated w/ key. touch the value

keep track of the LRU

Assumptions
1. key is an int, value is an int


[LRU at the front]
Example:
1. Init capcity 2        []
2. insert 1, 1          [(1, 1)]
3. insert 2, 2          [(1, 1), (2, 2)]
4. insert 3, 3          [(2, 2), (3, 3)]
5. get 2                [(3, 3), (2, 2)]
6. insert 1, 1          [(2, 2), (1, 1)]


list: 
map: (1, )


struct Node {
    Node* prev;
    Node* next;
    int key;
    int val;
}


class LRUCache {
    map<int, Node*> m;
    Node* sentinel;
    int capacity

    LRUCache(int capacity) {
        sentinel->prev = nullptr;
        sentinel->next = nullptr;
        this->capacity = capacity;
    }

    void insert(int key, int value) {
        if (m.count(key)) {
            Node *node = m[key];
            node->val = value;
            removeNodeAndPutAtEnd(node);
            return;
        }
        if (m.size() >= capacity) {
            // LRU entry is the first in the list
            Node *lru_node = sentinel->next;
            removeNodeFromList(lru_node);

            auto itr = m.find(key);
            m.erase(itr);
        }
        m[key] = new Node(key, value);
        insertNodeAtEnd(m[key]);
    }

    int get(int key) {
        if (m.count(key)) {
            int result = m[key]->val;
            removeNodeAndPutAtEnd(m[key]);
            return result;
        }
        return -1;
    }
};