/*************************************************************************
	> File Name: lru.cpp
	> Author:Ryan 
	> Mail: 
	> Created Time: Tue Oct 13 20:31:11 2020
    > Function :实现LRU缓存淘汰策略
 ************************************************************************/

#include<iostream>
#include<unordered_map>
using namespace std;

/*
 *双链表结点
 */ 
struct node{
    int val,key;
    node *prev,*next;
    node():prev(NULL),next(NULL){}
    node(int k,int v):key(k),val(v),prev(NULL),next(NULL){}
    
    //重载 == 号
    bool operator == (const node &p) const{
        return val==p.val&&key==p.key;
    }
 };

/*
 *双链表
 */ 
 class DoubleList{
     
     public:
        node *first;
        node *end;
        int n;

        DoubleList();
        void addFirst(node*);
        void remove(node*);
        int removeLast();
        int size();
 };
/*
 *构造函数，新建首尾节点，相连
 */ 
DoubleList::DoubleList(){
    n=0;
    first = new node();
    end = new node();
    first->next = end;
    end->prev = first;
}

/*
 *在第一位添加一个节点
 */ 
void DoubleList::addFirst(node *nd){
    n++;
    //node *tmp = new node(nd->key,nd>val);
    node *t = first->next;
    nd->next = t;
    first->next = nd;
    nd->prev = first;
    t->prev = nd;
}

/*
 *删除一个肯定存在的节点
 */
void DoubleList::remove(node *nd){
    n--;

    node *p = first;
    while(p->key!=nd->key){
        p=p->next;
    }
    node *pt = p->prev;
    node *nt = p->next;
    pt->next = nt;
    nt->prev = pt;
    delete p;
}
/*
 *删除最后一个节点
 */ 
int DoubleList::removeLast(){
    if(n>=1){
        node *tmp = end->prev;
        node *pt = tmp->prev;
    
        pt->next = end;
        end->prev = pt;

        int t = tmp->key;
        delete tmp;
        n--;
        return t;
    }
    return -1;
}

int DoubleList::size(){
    return n;
}

class LRUCache{
    private:
        unordered_map<int,node> map;
        DoubleList *lru;    
        int maxSize;

    public:
        LRUCache(){};
        LRUCache(int ms);
        int get(int key);
        void put(int key,int val);
        void show();
 };

LRUCache::LRUCache(int ms){
    maxSize = ms;
    lru = new DoubleList();
}

int LRUCache::get(int key){
    if(map.count(key)==0){
        return -1;
    }
    else{
        int val = map.find(key)->second.val;
        put(key,val);
        return val;
    }
}

void LRUCache::put(int key,int value){
    node *nd = new node(key,value);
    
    if(map.count(nd->key)==1){
        //移到前面
        lru->remove(nd);
        lru->addFirst(nd);
    }
    else{
        if(lru->n==maxSize){
            int k = lru->removeLast();
            map.erase(k);
            lru->addFirst(nd);
        }
        else{
            lru->addFirst(nd);
        }
    }
    map[key] = *nd;
}

void LRUCache::show(){
    if(lru->n==0) cout<<"empty task"<<endl;
    else{
        node *p = lru->first->next;
        cout<<"当前一共有"<<lru->n<<"个任务: "<<endl;
        for(int i=0;i<lru->n;i++){
            cout<<"第"<<i+1<<"个任务: "<<p->val<<endl;
            p=p->next;
        }
    }
}

int main(){
    LRUCache *l = new LRUCache(3);
    l->put(1,2);
    l->put(2,3);
    l->put(3,4);
    l->put(4,5);
    l->show();
}