LRUCache, C++ (gcc)

LRUCache

//Title of this code

#include <iostream>
#include <map>

using namespace std;

template <class K, class D>
struct LRUNode {
  
    K key;
    D data;
    
    LRUNode* next;
    LRUNode* perv;
    
    LRUNode(K k, D d) : key(k), data(d) {}
};

template <class K, class D, int maxEntries = 4>
class LRUCache {

map<K, LRUNode<K, D>*> lruMap;
    
    LRUNode<K, D>* head;
    LRUNode<K, D>* tail;
    
    int entriesNum;
    
  public:

LRUCache() {
        entriesNum = 0;
        head = NULL;
        tail = NULL;
    }

~LRUCache() {
        LRUNode<K, D>* cur = head;
        LRUNode<K, D>* tmp;

while (cur) {
            tmp = cur->next;
            delete cur;
            cur = tmp;
        } 
    }
    
    void put(K key, D data) {
    
        LRUNode<K, D>* node = lruMap[key];
        
        if (!node) {
            node = new LRUNode<K, D>(key, data);
            
            if (entriesNum >= maxEntries) {
                LRUNode<K, D>* tmp = tail;   
                detach(tail);
                
                lruMap.erase(tmp->key);
                delete tmp;
                
                --entriesNum;
                
            }

++entriesNum;
            
            lruMap[key] = node;
            attach(node);

} else {
            node->data = data;
            
            detach(node);
            attach(node);
        } 
    }
    
    
    D get(K key) {
        LRUNode<K, D>* node = lruMap[key];
        
        if (node) {
            //if (node != head) {
                detach(node);
                attach(node);
            //}
            return node->data;
            
        } 
        
        return 0;
    }
    
    void print() {
        LRUNode<K, D>* cur = head;
        
        while (cur) {
            cout << cur->data << ". ";
            cur = cur->next;  
        }
     
        cout << endl;  
    }
    
    
  private:
    
    void detach(LRUNode<K, D>* node) {

if (node == head && node->next)
            head = node->next;
        
        if (node == tail && node->perv)
            tail = node->perv;
            
        
        if (node->perv) {
            node->perv->next = node->next;
        }
        
        if (node->next) {
            node->next->perv = node->perv;
        }
        
    }
    
    void attach(LRUNode<K, D>* node) {
        
        if (head && head != node) {
            head->perv = node;
            node->next = head;
            node->perv = NULL;
            head = node;

} else if (!head){
            head = node;
            tail = node;
        }
        
    }

};

int main()
{
    LRUCache<int, int, 3> myCache;
    
    myCache.put(1,1); 
    myCache.put(2,2); 
    myCache.put(3,3); 
    myCache.put(4,4); myCache.get(3);
    myCache.put(5,5); myCache.get(3);
    myCache.put(6,6); myCache.get(4);
    
   
    myCache.print();

}


run \| edit \| history \| help	0