package lru;

import java.util.HashMap;

public class LRUCache2<K,V> {

    public final int capacity;

    class DNode{

        K key;

        V value;

        DNode next;

        DNode pre;

        public DNode(K key, V value, LRUCache2<K, V>.DNode pre, LRUCache2<K, V>.DNode next) {

            super();

            this.key = key;

            this.value = value;

            this.pre = pre;

            this.next = next;

        }

    }

    
　　//附加头结点

    DNode head=new DNode(null,null,null,null);

    DNode last=head;

    HashMap<K,DNode> map=new HashMap<>();

    public LRUCache2(int capacity) {

        this.capacity=capacity;

    }

    public V get(K key) {

        DNode node=map.get(key);

        if(node!=null) {

            moveToHead(node);

        }

        return node==null?null:node.value;

    }

    public void put(K key, V value) {

        DNode node=map.get(key);

        if(node==null) {

            if(map.size()>=capacity) {

                removeLast();

            }

            node=new DNode(key, value,head,head.next);

            if(head.next!=null)

                head.next.pre=node;

            head.next=node;

            map.put(node.key, node);

            if(last==head) last=node;

        }else {

            node.value=value;

            moveToHead(node);

        }

    }

    private void removeLast() {

        // TODO Auto-generated method stub

        if(last==null) {

            throw new IllegalArgumentException("cant remove before put");

        }

        map.remove(last.key);

        last.pre.next=null;

        last=last.pre;

    }

    private void moveToHead(LRUCache2<K, V>.DNode node) {

        // TODO Auto-generated method stub

        if(head.next==node) return;

        if(last==node) {

            last=node.pre;

        }

        node.pre.next=node.next;

        if(node.next!=null) node.next.pre=node.pre;

        node.next=head.next;

        node.pre=head;

        head.next.pre=node;

        head.next=node;

    }

}