Advertisement
markyrocks

node insert/ rotate back

May 20th, 2022
534
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include<map>
  3. #include<sstream>
  4.  
  5. using namespace std;
  6. struct node {
  7.     node* prev;
  8.     node* next;
  9.     int val, key;
  10.     node(node* prev=nullptr,node* next=nullptr,int key=NULL,int val=NULL)
  11.         :prev{ prev }, next{ next }, val{ val }, key{ key } {}
  12.  
  13. };
  14.  
  15. struct cache {
  16.     int cp;
  17.     node* head;
  18.     node* tail;
  19.     map<int, node*> mp;
  20.  
  21.     cache(int capacity = NULL) : cp(capacity), head{ nullptr }, tail{ nullptr }{}
  22.  
  23.     void set(int key, int val) {
  24.         auto f = mp.find(key);
  25.         if (f != mp.end()) { mp[key]->val = val; moveToTail(mp[key]); }
  26.         else if (mp.size() < cp) {
  27.             if (!head) {
  28.                 head = new node(nullptr, nullptr, key, val);
  29.                 mp[key] = head;
  30.             }
  31.             else if (!tail) {
  32.                 tail = new node(head, head, key, val);
  33.                 head->next = tail;
  34.                 head->prev = tail;
  35.                 mp[key] = tail;
  36.             }
  37.             else {
  38.                 node* n = new node(tail, head, key, val);
  39.                 tail->next = n;
  40.                 tail = n;
  41.                 head->prev=n;
  42.                 mp[key] = n;
  43.             }//probably need a scenario where cp is only 1... but im not doing it...
  44.         }
  45.         else { //capacity is reached....shift head to the rear
  46.             auto f = mp.find(head->key);
  47.             mp.erase(f);
  48.             tail = head;
  49.             head = tail->next;
  50.             tail->key = key;
  51.             tail->val = val;
  52.             mp[key] = tail;
  53.         }
  54.  
  55.     }
  56.  
  57.     void moveToTail(node* n) {
  58.         if (n == tail) { return; }
  59.         else if (n == head) {
  60.             tail = head;
  61.             head = tail->next;
  62.         }
  63.         else {
  64.             n->prev->next = n->next; //removes itself from old positiion
  65.             n->next->prev = n->prev;
  66.  
  67.             n->next = head; //inserts itself in new postion
  68.             n->prev = tail;
  69.  
  70.             tail->next = n; //updates the nodes on both sides
  71.             head->prev = n;
  72.  
  73.             tail = n; //updates the tail
  74.         }
  75.     }
  76.  
  77.     int get(int key) { //push newest hits to the back
  78.         auto f = mp.find(key);
  79.         if (f == mp.end()) { return -1; }
  80.         moveToTail(mp[key]);
  81.         return tail->val;
  82.     }
  83.  
  84.     void printptrs() {
  85.         for (auto& n : mp) {
  86.             cout << " prev = " << n.second->prev << " current = " << n.second << " next = " << n.second->next << "\n";
  87.         }
  88.     }
  89.     void printMap() {
  90.         for (auto& m : mp) {
  91.             cout << "key = " << m.first << " val = " << m.second->val << "\n";
  92.         }
  93.     }
  94.     void printMapOrdered() {
  95.         node* n = head;
  96.         do {
  97.             cout << "key = " << n->key << " val = " << n->val << "\n";
  98.             n = n->next;
  99.         } while (n != head);
  100.  
  101.        
  102.     }
  103.  
  104. };
  105.  
  106.  
  107.  
  108. int main()
  109. {
  110.    stringstream ss;
  111.     ss << "4 0 1 2 3 4 5 6 7 8 9"; //simple test case
  112.     int n,k,v;
  113.     ss >> n;
  114.    
  115.     cache c(n);
  116.  
  117.    while(ss>>k>>v){
  118.        c.set(k, v);
  119. //printptrs();
  120.  
  121.     }
  122.    c.get(4);
  123.    c.printMap();
  124. cout << " \n\n";
  125.    c.printMapOrdered();
  126.  
  127. }
Advertisement
RAW Paste Data Copied
Advertisement