LRU Cache - doubly Linked List | Hash Map

lrucache.cpp

#include <iostream>
#include <unordered_map>
/*
capacity = 5
Head 11 8 5 1 4 Tail

tail->prev inseamna nodul cu key 7

head->next = inseamna nodul cu key 8

se folosesc doua structuri de date: Doubly Linked List si HashMap
       get(key),put(key, value)

       get(8) ===> inseamna mutam key 8 dupa head
*/
using namespace std;

class LRUCache {

      private:

      class Node {

            public:
             int key;
             int data;

             Node* next;
             Node* prev;

             Node(int key, int data) {
                 this->key = key;
                 this->data = data;
                 this->next = nullptr;
                 this->prev = nullptr;
             }
      };

      int capacity;
      // HEAD <--> MRU .... LRU<--> Tail
    //     -1                       -1
      Node *head;
      Node *tail;

      //key -> Node*
      unordered_map<int, Node*>map;

      //elimina din lista dublu inlantuita un node
      void removeNode( Node *node ) {

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

          //optimal
          node->prev = nullptr;
          node->next = nullptr;
      }

      //adauga imediat dupa santinela HEAD
      /*
         HEAD node(next, prev) node1(next, prev) node2
         head->next inseamna node1
         node->prev = santinela HEAD
      */
      void addAfterHead(Node* node) {
           node->next = head->next;
           node->prev = head;

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

      //muta nodul la inceput
      void moveToHead(Node* node) {

          removeNode(node);

          addAfterHead(node);
      }

      //eliminare LRU
      Node* removeLRU() {
         Node *lru = tail->prev;
         removeNode(lru);

         return lru;
      }

      public:
      LRUCache(int capacity) {

           this->capacity = capacity;

           //sentinel nodes

           head = new Node(-1, -1);
           tail = new Node(-1, -1);

           /*
           LRUCache
           head <-> tail
           */
           head->next = tail;
           tail->prev = head;
      }

      //destructorul clasei = eliberam memoria din zona HEAP
      ~LRUCache() {

          Node* current = head;

          while(current != NULL) {
               Node *next = current->next;
               delete current;
               current = next;
          }
      }

      int get(int key) {

          if(map.find(key) == map.end()) {

              cout<<"GET "<<key <<"--> -1 (Not Found)";

              return -1;
          }

          Node *node = map[ key ]; //Complexitate O(1)

          moveToHead( node );

          cout<<"GET "<<key<<"-->"<<node->data<<endl;

          return node->data;
      }

      void put(int key, int value) {

            //verificam daca key exista in cache
            if(map.find(key) != map.end()) {

                Node *node = map[ key ];

                node->data = value;

                moveToHead( node );

                cout<<"PUT "<<key<<"->"<<value<<" (UPDATED)";

            }  else {

              //cache plin
              if(map.size() == capacity) {

                  Node*lru = removeLRU();

                  map.erase( lru->key );

                  cout<<"PUT "<<key<<"="<<value<<" key="<<lru->key<<" "<<lru->data<<endl;

                  delete lru;

              } else {

                  cout<<"PUT "<<key<<" = "<<value<<endl;
              }

              Node * newNode = new Node(key, value);

              addAfterHead(newNode);

              map[ key ] = newNode;

            }
      }

      //head 1 2 3 4 tail
      //    /\
      //    current
      void display() {

           Node *current = head->next;

           cout<<"Cache (MRU -> LRU): ";

           while(current != tail) {

                cout<<"("<<current->key<<"="<<current->data<<")";

                current = current->next;
           }

           cout<< "| SIZE = "<<map.size()<<"/"<<capacity<<"\n";
      }
};

int main(int argc, char const *argv[]) {

  cout<<"===== LRU Cache (capacity = 3) ======";

  LRUCache cache( 3 );
  //HEAD <==> TAIL

  cache.put(1, 10);

  cache.display();

  cache.put(2, 20);
  cache.display();

  cache.put(3, 30);

  cache.display();

  cache.get(1);

  cache.display();

  cache.put(4, 40);
  cache.display();

  cache.get(1);
  cache.display();

  return 0;
}