/**
     * 设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
     * set(key,value)
     * get(key)
     * 某个key的set或get一旦发生，认为这个key的记录是最常用的
     * 当缓存的大小超过K，移除最不经常使用的记录,即set或get最久远的
     *
     */

public static void main(String[] args) {
        // TODO Auto-generated method stub
        Cache<String,String> cache = new Cache<>(5);
        cache.set("1", "1");
        cache.set("2", "2");
        cache.set("3", "3");
        cache.set("4", "4");
        cache.set("5", "5");
        System.out.println(cache.get("3"));;
        cache.set("3", "03");
        cache.set("5", "05");
        cache.set("6", "06");
        cache.set("7", "07");
        Node<String> node = cache.linkCache.head;
        while(node !=null) {
            System.out.println("node--"+node.value);
            node = node.next;
        }
        
    }

}

class Cache<k,v>{
    Map<k,Node<v>> map;
    Map<Node<v>,k> nodeMp;
    LinkCache<v> linkCache;
    int size;
    public Cache(int size) {
        this.map = new HashMap<>();
        this.nodeMp = new HashMap<>();
        this.size = size;
        this.linkCache = new LinkCache<>();
    }
    public void set(k key,v value) {
        Node<v> node = new Node<>(value);
        //先判断当前是否存该value
        Node<v> n = map.get(key);
        if(n !=null) {
            n.value = value;
            get(key);//将改节点置顶
        }else {
            map.put(key, node);
            nodeMp.put(node, key);
            linkCache.addHead(node);
            if(map.size()>this.size) {
                Node<v> tail = linkCache.removeTail();
                k k = nodeMp.get(tail);
                nodeMp.remove(tail);
                map.remove(k);
            }
        }
    }
    public v get(k key) {
        Node<v> node =  map.get(key);
        Node<v> pre = node.pre;
        Node<v> next = node.next;
        node.next = null;
        node.pre = null;
        if(pre !=null && next !=null) {
            pre.next = next;
            next.pre = pre;
            linkCache.addHead(node);//放入头部
        }else if(next == null) { //当前节点是尾节点
            linkCache.tail = pre;
            pre.next = null;
            linkCache.addHead(node);//放入头部
        }
        //pre == null 当前节点是head 不用处理
            
        return node.value;
    }
    
    
}

class LinkCache<T>{
    Node<T> head;
    Node<T> tail;
    public void addHead(Node<T> node) {
        if(head == null) {
            this.head = node;
            this.tail = node;
        }else {
            node.next = this.head;
            this.head.pre = node;
            this.head = node;
        }
    }
    public Node<T> removeTail() {
        if(this.tail !=null) {
            Node<T> node = tail.pre;
            if(node !=null) {
                node.next = null;
                this.tail = node;
            }else {
                this.head = null;
                this.tail = null;
            }
            return this.tail;
        }
        return null;
    }
    
}

/*
 * 作为自定义链表公共类
 */
public  class Node<T> {
     public T value;
     public Node<T> pre;
     public Node<T> next;
     public Node(T value){
         this.value = value;
     }
}