/*
1. 需求: 
1.1 非功能性需求:读写性能O(1)
1.2 功能性需求:读写时更新缓存优先级为最高,达到容量后有新值写入时删除优先级最低的

2.设计
2.1 使用HashMap 进行读写存储
2.2 使用双向链表维护优先级, 读写时将对应节点放入链表尾部, 回收时删除链表头部的值

3. 头尾节点都需要访问且可变,所有需要虚拟节点代替
*/


class LRUCache {

    class Node{
        int key, value;
        Node prev, next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            prev = null;
            next = null;
        }
    }

    Map<Integer, Node> mapping;
    Node head, tail;
    int capacity, size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        mapping = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!this.mapping.containsKey(key)) return -1;

        Node node = this.mapping.get(key);
        flush(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (this.mapping.containsKey(key)){
            Node node = this.mapping.get(key);
            node.value = value;
            flush(node);
        } else {
            garbageCollect();
            Node node = new Node(key, value);
            this.mapping.put(key, node);
            append(node);
            this.size++;
        }
    }

    private void poll(Node node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    private void append(Node node){
        node.prev = this.tail.prev;
        node.next = this.tail;
        this.tail.prev.next = node;
        this.tail.prev = node;
    }

    private void garbageCollect(){
        while (this.size >= this.capacity){
            Node node = this.head.next;
            poll(node);
            mapping.remove(node.key);
            this.size--;
        }
    }

    private void flush(Node node){
        poll(node);
        append(node);
    }   
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */