Last active
March 31, 2020 05:02
-
-
Save kuriringohankamehameha/937ed14142bac455059ff10fc991ac34 to your computer and use it in GitHub Desktop.
A sample of a LRU Cache
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <map> | |
template <typename T> | |
struct CircularQueue { | |
std::pair<T, T> data; | |
size_t size; | |
CircularQueue* prev, *next; | |
CircularQueue(std::pair<T, T> data = std::make_pair(0, 0)) { this->data = data; prev = next = nullptr; size = 0; } | |
CircularQueue<T>* insert(CircularQueue* front, std::pair<T, T> data) { | |
if (!front) { | |
front = new CircularQueue(data); | |
front->size++; | |
return front; | |
} | |
if (!(front->prev)) { | |
CircularQueue* node = new CircularQueue(data); | |
node->next = node->prev = front; | |
front->next = front->prev = node; | |
node->size = front->size + 1; | |
front = node; | |
return front; | |
} | |
CircularQueue* rear = front->prev; | |
CircularQueue* node = new CircularQueue(data); | |
node->next = front; | |
node->prev = rear; | |
rear->next = node; | |
front->prev = node; | |
node->size = front->size + 1; | |
front = node; | |
return front; | |
} | |
CircularQueue<T>* remove(CircularQueue* front) { | |
CircularQueue* rear = front->prev; | |
if (!rear) { | |
front->prev = nullptr; | |
front->next = nullptr; | |
delete front; | |
return nullptr; | |
} | |
CircularQueue* tmp = rear->prev; | |
if (tmp == front) { | |
rear->prev = rear->next = nullptr; | |
delete rear; | |
front->prev = front->next = nullptr; | |
front->size--; | |
return front; | |
} | |
tmp->next = front; | |
rear->prev = nullptr; | |
front->prev = tmp; | |
rear->next = nullptr; | |
delete rear; | |
front->size--; | |
return front; | |
} | |
void print(CircularQueue* front) { | |
if (!front) | |
return; | |
size_t cap; | |
CircularQueue* head = front; | |
for (cap = front->size; cap > 0; head = head->next) { | |
std::cout << "Key: " << head->data.first << " -> "; | |
cap--; | |
} | |
std::cout << "\n"; | |
} | |
void free_queue(CircularQueue* front) { | |
if (!front) | |
return; | |
front = this->remove(front); | |
free_queue(front); | |
} | |
}; | |
template <typename T> | |
class LRUCache { | |
// The LRUCache class: Implements a Least Recently Used policy | |
public: | |
size_t capacity; | |
size_t curr = 0; | |
std::map<int, CircularQueue<T>*> hash_map; | |
CircularQueue<T> queue; | |
CircularQueue<T>* front; | |
LRUCache(size_t capacity) { | |
this->capacity = capacity; | |
std::pair<T, T> pr = std::make_pair(0, 0); | |
queue = CircularQueue<T>(pr); | |
front = nullptr; | |
} | |
int get(int key) { | |
if (hash_map.count(hash(key)) > 0) { | |
if (curr == 1) | |
return hash_map[key]->data.second; | |
CircularQueue<T>* node = hash_map[hash(key)]; | |
CircularQueue<T>* pnode = node->prev; | |
CircularQueue<T>* nnode = node->next; | |
if (pnode && pnode == nnode) { | |
front = node; | |
front->size = curr; | |
return hash_map[key]->data.second; | |
} | |
if (pnode) { | |
pnode->next = nnode; | |
} | |
if (nnode) { | |
nnode->prev = pnode; | |
} | |
node->next = front; | |
node->prev = front->prev; | |
if (front->prev) | |
front->prev->next = node; | |
CircularQueue<T>* tmp = front; | |
tmp->prev = node; | |
front = node; | |
front->size = curr; | |
//front = queue.remove(front); | |
//front = queue.insert(front, key); | |
return hash_map[key]->data.second; | |
} | |
return -1; | |
} | |
void put(int key, int value) { | |
if (hash_map.count(hash(key)) > 0) { | |
if (curr == 1) { | |
front->data.second = value; | |
return; | |
} | |
CircularQueue<T>* node = hash_map[hash(key)]; | |
CircularQueue<T>* pnode = node->prev; | |
CircularQueue<T>* nnode = node->next; | |
if (pnode && (pnode == nnode)) { | |
front = node; | |
front->size = curr; | |
front->data.second = value; | |
return; | |
} | |
if (pnode) { | |
pnode->next = nnode; | |
} | |
if (nnode) { | |
nnode->prev = pnode; | |
} | |
node->next = front; | |
node->prev = front->prev; | |
if (front->prev) | |
front->prev->next = node; | |
CircularQueue<T>* tmp = front; | |
tmp->prev = node; | |
front = node; | |
front->size = curr; | |
front->data.second = value; | |
return; | |
} | |
if (curr >= capacity) { | |
if (front->prev) | |
hash_map.erase(hash(front->prev->data.first)); | |
else | |
hash_map.erase(hash(front->data.first)); | |
front = queue.remove(front); | |
curr--; | |
} | |
std::pair<T, T> pr = std::make_pair(key, value); | |
front = queue.insert(front, pr); | |
curr++; | |
hash_map[hash(front->data.first)] = front; | |
// std::cout << "Inserted " << front->data << " to queue\n"; | |
} | |
int hash(int key) { | |
return key; | |
} | |
void print() { | |
queue.print(front); | |
} | |
~LRUCache() { | |
hash_map.clear(); | |
queue.free_queue(front); | |
} | |
}; | |
int main() { | |
LRUCache<int> cache(2); // We can choose between a vector and a map for the HashMap Table | |
cache.put(1, 1); | |
cache.put(2, 2); | |
cache.print(); | |
std::cout << cache.get(1) << std::endl; // returns 1 | |
cache.print(); | |
cache.put(3, 3); // evicts key 2 | |
std::cout << cache.get(2) << std::endl; // returns -1 | |
cache.put(4, 4); // evicts key 1 | |
std::cout << cache.get(1) << std::endl; // returns -1 (not found) | |
std::cout << cache.get(3) << std::endl; // returns 1 | |
std::cout << cache.get(4) << std::endl; // returns 1 | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment