algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

lru-cache.cpp (2230B)


      1 class Node {
      2     public:
      3         Node* next;
      4         Node* prior;
      5         int value;
      6         int key;
      7 };
      8 
      9 class LRUCache {
     10 private:
     11     Node* head = nullptr;
     12     Node* tail = nullptr;
     13     int cap = 0;
     14     unordered_map<int, Node*> lookup {};
     15 
     16 public:
     17 
     18     LRUCache(int capacity) {
     19         this->cap = capacity;
     20     }
     21     
     22     int get(int key) {
     23         if(lookup.contains(key)) {
     24             Node* current = lookup[key]; 
     25 
     26             if(current != tail) {
     27                 Node* pr = current->prior;
     28                 if(pr != nullptr) {
     29                     pr->next = current->next;
     30                 } else {
     31                     head = current->next;
     32                 }
     33                 current->next->prior = pr;
     34 
     35                 current->prior = tail;
     36                 tail->next = current;
     37                 tail = current;
     38                 current->next = nullptr;
     39             }
     40             return current->value;
     41         }
     42         return -1;
     43     }
     44     
     45     void put(int key, int value) {
     46         if(lookup.contains(key)) {
     47             Node* cr = lookup[key];
     48             cr->value = value;
     49 
     50             if(cr != tail) {
     51                 if(cr->prior != nullptr) {
     52                     cr->prior->next = cr->next;
     53                 } else {
     54                     head = cr->next;
     55                 }
     56                 cr->next->prior = cr->prior;
     57 
     58                 cr->prior = tail;
     59                 tail->next = cr;
     60                 tail = cr;
     61                 cr->next = nullptr;
     62             }
     63 
     64         } else {
     65             if(lookup.size() >= cap) {
     66                 lookup.erase(head->key);
     67                 Node* nHead = head->next;
     68                 delete head;
     69                 head = nHead;
     70 
     71                 if(head != nullptr) head->prior = nullptr;
     72                 else tail = nullptr;
     73             }
     74 
     75             Node* nextNodePtr = new Node();
     76             nextNodePtr->value = value;
     77             nextNodePtr->key = key;
     78             lookup[key] = nextNodePtr;
     79 
     80             if(tail != nullptr) {
     81                 nextNodePtr->prior = tail;
     82                 tail->next = nextNodePtr;
     83                 tail = nextNodePtr;
     84             } else {
     85                 tail = nextNodePtr;
     86                 head = nextNodePtr;
     87             }
     88         }
     89     }
     90 };