// LRU缓存机制可以通过哈希表辅以双向链表实现
// 使用双向链表的理由：方便删除节点，O(1)时间
// 双向链表中存储key的理由：size > capcity 时可以O(1)的时间删除哈希表中的键值对
// O(1)的get和put，用hashmap实现
// 基础还是链表的增删改查，只是这里是双向链表作为hashmap的value
// 链表的中节点的移动和删除修改通过双向链表可以在O(1)的时间内实现
// 每访问一个节点都要将其移动链表头。整个过程分为两步:1.双向链表中删除该节点，2.添加到头部
// 链表中的元素个数超过capcity后需要删除链表尾的节点
class LRUCache { 
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        DLinkedNode() {}
        DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private int size;
    private int capacity;
    private DLinkedNode head = new DLinkedNode();
    private DLinkedNode tail = new DLinkedNode();
    private HashMap<Integer, DLinkedNode> hs = new HashMap<>();
    LRUCache(int capacity) {
        size = 0;
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    public int get (int key) {
        DLinkedNode node = hs.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    public void put(int key, int value) {
        DLinkedNode node = hs.get(key);
        if (node == null) {
            node = new DLinkedNode(key, value);
            hs.put(key, node);
            addToHead(node);
            size++;
            if (size > capacity) {
               DLinkedNode tail =  removeTail();
               hs.remove(tail.key);
               --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
            
        }
    }
    public void addToHead(DLinkedNode node) { // 添加到头结点,意味着新建了一个节点
       node.next =  head.next;
       node.prev = head;
       head.next.prev = node;
       head.next = node; 
    }
    public void removeNode(DLinkedNode node) { // 删除节点
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    public void moveToHead(DLinkedNode node) { // 节点已经存在，改变他的值，需要将该节点移动到头的位置
        removeNode(node);
        addToHead(node);
    }
    public DLinkedNode removeTail() { // size > capacity 需要删除末尾节点
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }
}

// java自带的LinkedHashMap已经实现了LRU缓存
// class LRUCache extends LinkedHashMap<Integer, Integer> {
//     private int capacity;
//     public LRUCache(int capacity) {
//         super(capacity, 0.75F, true); //调用父类的构造方法
//         this.capacity = capacity;
//     }
//     public int get(int key) {
//         return super.getOrDefault(key, -1);
//     }
//     public void put(int key, int value) {
//         super.put(key, value);
//     }
//     @Override
//     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
//         return size() > capacity;
//     }
  
// }


/**
 * 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);
 */