-
Notifications
You must be signed in to change notification settings - Fork 343
/
LRU Cache C++ implementation
127 lines (111 loc) · 2.65 KB
/
LRU Cache C++ implementation
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
#include <iostream>
#include <map>
using namespace std;
class Node {
public:
int key, value;
Node *prev, *next;
Node(int k, int v): key(k), value(v), prev(NULL), next(NULL) {}
};
class DoublyLinkedList {
Node *front, *rear;
bool isEmpty() {
return rear == NULL;
}
public:
DoublyLinkedList(): front(NULL), rear(NULL) {}
Node* add_page_to_head(int key, int value) {
Node *page = new Node(key, value);
if(!front && !rear) {
front = rear = page;
}
else {
page->next = front;
front->prev = page;
front = page;
}
return page;
}
void move_page_to_head(Node *page) {
if(page==front) {
return;
}
if(page == rear) {
rear = rear->prev;
rear->next = NULL;
}
else {
page->prev->next = page->next;
page->next->prev = page->prev;
}
page->next = front;
page->prev = NULL;
front->prev = page;
front = page;
}
void remove_rear_page() {
if(isEmpty()) {
return;
}
if(front == rear) {
delete rear;
front = rear = NULL;
}
else {
Node *temp = rear;
rear = rear->prev;
rear->next = NULL;
delete temp;
}
}
Node* get_rear_page() {
return rear;
}
};
class LRUCache{
int capacity, size;
DoublyLinkedList *pageList;
map<int, Node*> pageMap;
public:
LRUCache(int capacity) {
this->capacity = capacity;
size = 0;
pageList = new DoublyLinkedList();
pageMap = map<int, Node*>();
}
int get(int key) {
if(pageMap.find(key)==pageMap.end()) {
return -1;
}
int val = pageMap[key]->value;
// move the page to front
pageList->move_page_to_head(pageMap[key]);
return val;
}
void put(int key, int value) {
if(pageMap.find(key)!=pageMap.end()) {
// if key already present, update value and move page to head
pageMap[key]->value = value;
pageList->move_page_to_head(pageMap[key]);
return;
}
if(size == capacity) {
// remove rear page
int k = pageList->get_rear_page()->key;
pageMap.erase(k);
pageList->remove_rear_page();
size--;
}
// add new page to head to Queue
Node *page = pageList->add_page_to_head(key, value);
size++;
pageMap[key] = page;
}
~LRUCache() {
map<int, Node*>::iterator i1;
for(i1=pageMap.begin();i1!=pageMap.end();i1++) {
delete i1->second;
}
delete pageList;
}
};