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