#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

#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()<<" ";
}

#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

#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 frontn";

}

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 backn";

}

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 existn";
        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 freedn";
}

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;
}

#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

#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;

}