package LRU;

/*
不使用LinkedListMap实现
 */

import java.util.HashMap;
import java.util.LinkedHashMap;

class Node{
    public int key, val;
    public Node pre, next;
    public Node(int k, int v){
        this.key = k;
        this.val = v;
    }
}

class DoubleList{
    private Node head, tail;

    private int size;

    public DoubleList(){
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.pre = head;
        size = 0;
    }

    //添加结点至队尾
    public void addLast(Node x){
        x.pre = tail.pre;
        x.next = tail;
        tail.pre.next = x;
        tail.pre = x;
        size++;
    }

    //删除目标结点
    public void remove(Node x){
        x.pre.next = x.next;
        x.next.pre = x.pre;
        size--;
    }

    //删除链表中第一个结点并返回
    public Node removeFirst(){
        if(head==null){
            return null;
        }else{
            Node first = head.next;
            remove(first);
            return first;

        }
    }

    //时间复杂度为1
    public int size(){
        return size;
    }
}

public class LRUCacheEssential {
    private HashMap<Integer, Node> map ;

    private  DoubleList cache ;

    private int cap;

    public LRUCacheEssential(int cap){
        this.cap = cap;
        map = new LinkedHashMap<>();
        cache = new DoubleList();
    }

    //将某个key提升为最近使用
    private void makeRecently(int key){
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }

    //添加最近使用的元素
    private void addRecently(int key, int val){
        Node x = new Node(key,val);
        cache.addLast(x);
        map.put(key, x);
        System.out.println("成功添加"+key+","+map.get(key).val);
    }

    //删除一个key
    private void deleteKey(int key){
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }

    //删除最久没有使用的
    private void removeLeastRecently(){
        Node x=cache.removeFirst();
        map.remove(x.key);
        System.out.println("删除数据"+x.key);
    }

    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int val){
        if(map.containsKey(key)){
            deleteKey(key);
            addRecently(key,val);
            System.out.println("更改数据");
            return;
        }
        if(cap == cache.size()){
            removeLeastRecently();
        }
        addRecently(key,val);
    }

    public static void main(String[] args) {
        LRUCacheEssential lru = new LRUCacheEssential(5);
        lru.put(0,1);
        lru.put(1,1);
        lru.put(2,1);
        lru.put(3,1);
        lru.put(4,1);

        lru.put(5,1);
        lru.put(2,3);
        lru.put(0,1);

    }
}