LRU Cache Solutions in C++

// Source : https://oj.leetcode.com/problems/lru-cache/
// Author : Hao Chen
// Date   : 2014-10-12



#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <map>
using namespace std;

// The idea here is quite simple:
//    1) A Map to index the key.  O(1) key search time-complexity.
//    2) A List to sort the cache data by accessed time.
// 
//  Considering there are too many insert/delete opreations for the List, 
//  The ouble linked list is the good data structure to performance it.

class Node {
    public:
        int key;
        int value;
        Node *next, *prev;
        Node(int k, int v) { key=k; value=v; next = prev = NULL; }
        //Node(int k, int v, Node* n=NULL, Node* p=NULL): key(k), value(v), next(n), prev(p) {}
};

// the following double linked list seems a bit commplicated.
class DoubleLinkedList {

    private:

        Node *pHead, *pTail;
        int size;


    public:

        DoubleLinkedList(){
            pHead = pTail = NULL;
            size = 0;
        }
        ~DoubleLinkedList() {
            while(pHead!=NULL){
                Node*p = pHead;
                pHead = pHead->next;
                delete p;
            }
        }

        int Size() const {
            return size;
        }

        Node* NewAtBegin(int key, int value) {
            Node *n = new Node(key, value);
            return AddAtBegin(n);
        }

        Node* NewAtEnd(int key, int value) {
            Node *n = new Node(key, value);
            return AddAtEnd(n);
        }

        Node* AddAtBegin(Node* n){
            size++;

            if (pHead==NULL) { 
                pHead = pTail = n; 
                return n; 
            }

            n->next = pHead;
            n->prev = NULL;
            pHead->prev = n;
            pHead = n;
            return n;
        }

        Node* AddAtEnd(Node* n) {
            size++;

            if (pHead==NULL) { 
                pHead = pTail = n; 
                return n; 
            }

            pTail->next = n;
            n->prev = pTail;
            n->next = NULL;
            pTail = n;
        }

        void Unlink(Node* n){
            Node* before = n->prev;
            Node* after = n->next;

            if (before){
                before->next = after;  
            }

            if (after){ 
                after->prev = before;
            }

            if(pHead == n){
                pHead = pHead->next;
            }else if(pTail == n) {
                pTail = pTail->prev;
            }

            size--;
        }

        void Delete(Node* n){
            Unlink(n);
            delete n;
        }

        void TakeToBegin(Node* n){
            Unlink(n);
            AddAtBegin(n);
        } 

        Node* GetTailNode() {
            return pTail;
        } 

        void DeleteLast() {
            Delete(pTail);
        } 

        void Print(){
            Node* p = pHead;
            while(p!=NULL) {
                cout << "(" << p->key << "," << p->value << ") ";
                p = p->next;
            }
            cout << endl;
        }
};



class LRUCache{

    private:
        //cacheList - store the date
        DoubleLinkedList cacheList;
        //cacheMap - index the date for searching
        map<int, Node*> cacheMap;
        //the max capcity of cache
        int capacity;

    public:
        LRUCache(int capacity) {
            this->capacity = capacity;    
        }
        void print(){
            cacheList.Print();
        }

        int get(int key) {
            // The accessed node must be up-to-time -- take to the front 
            if (cacheMap.find(key) != cacheMap.end() ){
                cacheList.TakeToBegin(cacheMap[key]);
                return cacheMap[key]->value;
            }
            return -1;

        }

        void set(int key, int value) {
            // key found, update the data, and take to the front 
            if (cacheMap.find(key) != cacheMap.end() ){
                Node *p = cacheMap[key];
                p->value = value;
                cacheList.TakeToBegin(cacheMap[key]);
            }else{
                // key not found, new a node to store data
                cacheMap[key] = cacheList.NewAtBegin(key, value);
                // if the capacity exceed, remove the last one.
                if( cacheList.Size() > capacity) {
                    int key = cacheList.GetTailNode()->key; 
                    cacheMap.erase(key);
                    cacheList.DeleteLast();
                }
            }
        }
};


int main(int argc, char** argv) 
{

    /*
    LRUCache c(2);
    c.set(2,1);
    c.print();
    c.set(2,2);
    c.print();
    c.get(2);
    c.print();
    c.set(1,1);
    c.print();
    c.set(4,1);
    c.print();
    c.get(2);
    c.print();

    cout << "---------" << endl;
    */
    srand(time(0));

    int capacity = 5;
    int test_loop_times = 10;
    if (argc>1){
        capacity = atoi(argv[1]);
    }
    if (argc>2){
        test_loop_times = atoi(argv[1]);
    }

    LRUCache cache(capacity);

    int v; 
    for(int i=0; i<test_loop_times; i++) {
        v = i;//rand() % capacity;
        cout << "set " << v << ": ";
        cache.set(v, v);
        cache.print();

        v = rand() % capacity;
        cout << "get " << v << ": " << cache.get(v);
        cache.print();

        cout << endl;
    }
    return 0;
}

/// Source : https://leetcode.com/problems/lru-cache/
/// Author : liuyubobobo
/// Time   : 2019-03-02

#include <iostream>
#include <unordered_map>
#include <cassert>

using namespace std;


/// HashMap + Double Linked List
/// Time Complexity: init: O(1)
///                  get: O(1)
///                  put: O(1)
/// Space Complexity: O(n)
class LRUCache {

private:
    class Node{

    public:
        int key, value;
        Node *prev, *next;

        Node(int k, int v): key(k), value(v), prev(NULL), next(NULL){}
    };

    int capacity;
    unordered_map<int, Node*> data;

    Node* dummyHead;
    Node* tail;

public:
    LRUCache(int capacity): capacity(capacity){
        dummyHead = new Node(-1, -1);
        tail = new Node(-1, -1);

        dummyHead->next = tail;
        tail->prev = dummyHead;
    }

    ~LRUCache(){
        // TODO memory
    }

    int get(int key) {
//        cout << "get " << key << endl;
        if(data.count(key)){
            moveToHead(data[key]);
            assert(dummyHead->next);
//            debug();
            return dummyHead->next->value;
        }
        return -1;
    }

    void put(int key, int value) {
//        cout << "put " << key << " " << value << endl;
        if(data.count(key)){
            data[key]->value = value;
            moveToHead(data[key]);
            return;
        }

        data[key] = new Node(key, value);
        addFirst(data[key]);
//        debug();
        if(data.size() > capacity){
            assert(data.size() == capacity + 1);
            int delKey = removeLast();
            assert(data.count(delKey));
            data.erase(delKey);
//            debug();
        }
    }

private:
    void moveToHead(Node* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;

        node->prev = node->next = NULL;
        addFirst(node);
    }

    void addFirst(Node* node){

        node->next = dummyHead->next;
        node->next->prev= node;

        node->prev = dummyHead;
        dummyHead->next = node;
    }

    int removeLast(){

        assert(tail->prev != dummyHead);
        Node* delNode = tail->prev;

        tail->prev = tail->prev->prev;
        tail->prev->next = tail;

        // TODO: delete delNode
        return delNode->key;
    }

    void debug(){

        cout << "Hash Map : sz = " << data.size() << endl;
        for(const pair<int, Node*>& p: data)
            cout << p.first << " : ( " << p.second->key << " , " << p.second->value << " )" << endl;

        cout << "Double Linked List : " << endl;
        Node* cur = dummyHead;
        while(cur)
            cout << "(" << cur->key << "," << cur->value << ") -> ", cur = cur->next;
        cout << "NULL" << endl << endl;
    }
};


int main() {

    LRUCache cache1(2);
    cache1.put(1, 1);
    cache1.put(2, 2);
    cout << cache1.get(1) << endl; // 1
    cache1.put(3, 3);
    cout << cache1.get(2) << endl; // -1
    cache1.put(4, 4);
    cout << cache1.get(1) << endl; // -1
    cout << cache1.get(3) << endl; // 3
    cout << cache1.get(4) << endl; // 4

    cout << endl;

    LRUCache cache2(2);
    cache2.put(2, 1);
    cache2.put(1, 1);
    cache2.put(2, 3);
    cache2.put(4, 1);
    cout << cache2.get(1) << endl; // -1
    cout << cache2.get(2) << endl; // 3

    return 0;
}