package LRU;

/*
不使用LinkedListMap實(shí)現(xiàn)
 */

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

    //添加結(jié)點(diǎn)至隊(duì)尾
    public void addLast(Node x){
        x.pre = tail.pre;
        x.next = tail;
        tail.pre.next = x;
        tail.pre = x;
        size++;
    }

    //刪除目標(biāo)結(jié)點(diǎn)
    public void remove(Node x){
        x.pre.next = x.next;
        x.next.pre = x.pre;
        size--;
    }

    //刪除鏈表中第一個(gè)結(jié)點(diǎn)并返回
    public Node removeFirst(){
        if(head==null){
            return null;
        }else{
            Node first = head.next;
            remove(first);
            return first;

        }
    }

    //時(shí)間復(fù)雜度為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();
    }

    //將某個(gè)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);
    }

    //刪除一個(gè)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("刪除數(shù)據(jù)"+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("更改數(shù)據(jù)");
            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);

    }
}