Explanation : I am adding new elements in the list until the window runs out. Head will have the earliest element and tail will have the most recent element. Once the window is over, every addition requires deletion of the very first element or least used in the list which was temporally inserted a lot earlier than other elements. An access to an existing page in the list brings it to the end of the list signifying most recent use.
List end represents most recent element in the cache. List head represents earliest of all the elements in the cache.
Link.h
#ifndef LINKLIST_LINK_H
#define LINKLIST_LINK_H
#include <iosfwd>
class Link{
private:
int value;
Link* next = nullptr;
public:
Link();
explicit Link(int key);
int getValue() const;
void setValue(int value);
Link *getNext() const;
void setNext(Link *next);
friend void operator<<(std::ostream& os, const Link &link);
};
#endif //LINKLIST_LINK_H
Link.cpp
#include "Link.h"
#include <iostream>
Link::Link() {
}
Link::Link(int key) {
this->setValue(key);
}
int Link::getValue() const {
return value;
}
void Link::setValue(int value) {
Link::value = value;
}
Link *Link::getNext() const {
return next;
}
void Link::setNext(Link *next) {
Link::next = next;
}
void operator<<(std::ostream& os, const Link &link){
os<<link.getValue()<<" ";
}
LinkList.h
#ifndef LINKLIST_LINKLIST_H
#define LINKLIST_LINKLIST_H
#include <vector>
#include "Link.h"
class LinkList{
protected:
Link* head = nullptr;
Link* tail = nullptr;
std::vector<void* >linksAddresses;
public:
virtual ~LinkList();
void insert(int key);
void push_back(int key);
void push_front(int key);
bool deleteKey(int key);
bool findKey(int key);
void insert_sorted(int key);
friend void operator<<(std::ostream& os, const LinkList &linkList);
void getLinksAddresses();
void printReverse() const;
void do_reverse();
Link* delete_at_pos(int n);
};
#endif //LINKLIST_LINKLIST_H
LinkList.cpp
#include <iostream>
#include "LinkList.h"
void LinkList::insert(int key) {
push_back(key);
}
void LinkList::push_front(int key) {
Link *newNode = new Link(key);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->setNext(head);
head = newNode;
}
//std::cout << "Inserted " << key <<" address : "<<&newNode << " at front\n";
}
void LinkList::push_back(int key) {
Link *newNode = new Link(key);
if (tail == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->setNext(newNode);
tail = newNode;
}
//std::cout << "Inserted " << key << " at back\n";
}
bool LinkList::deleteKey(int key) {
Link *curr = head;
Link *prev = head;
if (head != nullptr && head->getValue() == key) {
Link *temp = head;
head = head->getNext();
if(head == nullptr)
tail = nullptr;
delete temp;
std::cout << "Deleted " << key << "\n";
return true;
}
while (curr != nullptr && curr->getValue() != key) {
prev = curr;
curr = curr->getNext();
}
if (curr == nullptr) {
std::cout << "To delete Key " << key << " doesn't exist\n";
return false;
} else {
prev->setNext(curr->getNext());
delete curr;
std::cout << "Deleted " << key << "\n";
return true;
}
}
bool LinkList::findKey(int key) {
Link *current = head;
while (current != nullptr && current->getValue() != key)
current = current->getNext();
return current != nullptr;
}
LinkList::~LinkList() {
Link *next;
Link *curr = head;
while (curr != nullptr) {
next = curr->getNext();
delete curr;
curr = next;
}
//std::cout<<"Memory freed\n";
}
void operator<<(std::ostream &os, const LinkList &linkList) {
Link *curr = linkList.head;
os << "List is : ";
while (curr != nullptr) {
os << *curr;
curr = curr->getNext();
}
os << '\n';
}
void LinkList::insert_sorted(int key) {
//TODO
}
void LinkList::getLinksAddresses() {
while (head != nullptr){
linksAddresses.push_back(&head);
std::cout<<&head<<" "<<head->getValue()<<"\n";
head = head->getNext();
}
}
void reverse(Link* head){
if(head!= nullptr){
reverse(head->getNext());
std::cout<<head->getValue()<<" ";
}
}
void LinkList::printReverse() const {
reverse(head);
std::cout<<"\n";
}
void LinkList::do_reverse() {
Link* prev = nullptr;
Link* curr = head;
Link* next = curr->getNext();
while (curr){
}
}
Link* LinkList::delete_at_pos(int n)
{
if(n <=0)
return head;
int count = 1;
Link* curr = head, *prev = nullptr;;
while(curr!=nullptr){
if(count == n)
break;
prev = curr;
curr = curr->getNext();
count++;
}
if(curr!=nullptr){
Link* temp = curr;
if(curr == head){
head = head->getNext();
}else{
prev->setNext(curr->getNext());
}
delete temp;
}
return head;
}
LRU.hpp
#ifndef LINKLIST_LRU_HPP
#define LINKLIST_LRU_HPP
#include <iostream>
#include "LinkList.h"
class LRU : public LinkList{
private:
const int MAX = 4;
int max_len = 0;
Link* findPage(int key){
Link *current = LinkList::head;
while (current != nullptr && current->getValue() != key)
current = current->getNext();
return current;
}
public:
void insert(int key) override{
if(MAX > 0) {
Link *page = findPage(key);
if (page != nullptr) {
access(page->getValue());
return;
}
if (max_len >= MAX) {
deleteKey(LinkList::head->getValue());
max_len--;
}
push_back(key);
max_len++;
}
}
bool access(int key){
Link *current = findPage(key);
if(current == nullptr)
return false;
else{
int val = current->getValue();
deleteKey(val);
max_len--;
insert(val);
return true;
}
}
};
#endif //LINKLIST_LRU_HPP
main.cpp
#include "LinkList.h"
#include "LRU.hpp"
#include <iostream>
void testingLinkedLRU();
int main() {
testingLinkedLRU();
return 0;
}
void testingLinkedLRU(){
LRU lru;
std::cout<<lru;
lru.insert(1);
std::cout<<lru;
lru.insert(2);
std::cout<<lru;
lru.insert(3);
std::cout<<lru;
lru.insert(4);
std::cout<<lru;
lru.insert(5);
std::cout<<lru;
lru.insert(6);
std::cout<<lru;
lru.access(3);
std::cout<<lru;
lru.insert(-5);
std::cout<<lru;
lru.insert(5);
std::cout<<lru;
lru.insert(50);
std::cout<<lru;
lru.access(5);
std::cout<<lru;
lru.access(1);
std::cout<<lru;
lru.access(-5);
std::cout<<lru;
}
