import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.stream.IntStream;


class LRUCache {

    /*
      Our internal definition of a doubly linked list
      node, put in this class for convenience since
      this is submitted in one file on Leetcode
    */
    private class DNode {
        int key;
        int value;
        DNode prev;
        DNode next;
    }

    private Map<Integer, DNode> hashtable = new HashMap<>();
    private DNode head, tail;
    private int totalItemsInCache;
    private int maxCapacity;
    private ReadWriteLock lock = new ReentrantReadWriteLock();


    public LRUCache(int maxCapacity) {

        // Cache starts empty and capacity is set by client
        totalItemsInCache = 0;
        this.maxCapacity = maxCapacity;

        // Initialize the dummy head of the cache
        head = new DNode();
        head.prev = null;

        // Init the dummy tail of the cache
        tail = new DNode();
        tail.next = null;

        // Wire the head and tail together
        head.next = tail;
        tail.prev = head;
    }

    public int getSize() {
        return totalItemsInCache;
    }

    /*
      Retrieve an item from the cache
    */
    // make get operation thread safe. Could use a reentrant read lock here for finer control.
    public synchronized int get(int key) {

        DNode node = hashtable.get(key);
        boolean itemFoundInCache = node != null;

        // Empty state check. Should raise exception here.
        if (!itemFoundInCache) {
            return -1;
        }

        // Item has been accessed. Move to the front of the list.
        moveToHead(node);

        return node.value;
    }

    /*
      Add an item to the cache if it is not already there,
      if it is already there update the value and move it
      to the front of the cache
    */
    public synchronized void put(int key, int value) {

            DNode node = hashtable.get(key);
            boolean itemFoundInCache = node != null;

            if(!itemFoundInCache){

                // Create a new node
                DNode newNode = new DNode();
                newNode.key = key;
                newNode.value = value;

                // Add to the hashtable and the doubly linked list
                hashtable.put(key, newNode);
                addNode(newNode);

                // We just added an item to the cache
                totalItemsInCache++;

                // If over capacity evict an item with LRU cache eviction policy
                if(totalItemsInCache > maxCapacity){
                    removeLRUEntryFromStructure();
                }

            } else {
                // If item is in cache just update and move it to the head
                node.value = value;
                moveToHead(node);
            }
        }

    /*
      Remove the least used entry from the doubly linked
      list as well as the hashtable. Hence it is evicted
      from the whole LRUCache structure
    */
    // don't think I need to make it  here right if I have made the helper methods thread safe?
    private  void removeLRUEntryFromStructure() {
        DNode tail = popTail();
        hashtable.remove(tail.key);
        --totalItemsInCache;
    }

    /*
      Insertions to the doubly linked list will always
      be right after the dummy head
    */
    private  void addNode(DNode node){

        // Wire the node being inserted
        node.prev = head;
        node.next = head.next;

        // Re-wire the head's old next
        head.next.prev = node;

        // Re-wire the head to point to the inserted node
        head.next = node;
    }

    /*
      Remove the given node from the doubly linked list
    */
    private  void removeNode(DNode node){

        // Grab reference to the prev and next of the node
        DNode savedPrev = node.prev;
        DNode savedNext = node.next;

        // Cut out going forwards
        savedPrev.next = savedNext;

        // Cut out going backards
        savedNext.prev = savedPrev;
    }

    /*
      Move a node to the head of the doubly linked lsit
    */
    // don't think I need to make it  here right if I have made the helper methods thread safe?
    private  void moveToHead(DNode node){
        removeNode(node);
        addNode(node);
    }

    /*
      Pop the last item from the structure
    */
    private  DNode popTail(){
        DNode itemBeingRemoved = tail.prev;
        removeNode(itemBeingRemoved);
        return itemBeingRemoved;
    }

    public static void main(String[] args) {
       import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.stream.IntStream;


class LRUCache {

    /*
      Our internal definition of a doubly linked list
      node, put in this class for convenience since
      this is submitted in one file on Leetcode
    */
    private class DNode {
        int key;
        int value;
        DNode prev;
        DNode next;
    }

    private Map<Integer, DNode> hashtable = new HashMap<>();
    private DNode head, tail;
    private int totalItemsInCache;
    private int maxCapacity;
    private ReadWriteLock lock = new ReentrantReadWriteLock();


    public LRUCache(int maxCapacity) {

        // Cache starts empty and capacity is set by client
        totalItemsInCache = 0;
        this.maxCapacity = maxCapacity;

        // Initialize the dummy head of the cache
        head = new DNode();
        head.prev = null;

        // Init the dummy tail of the cache
        tail = new DNode();
        tail.next = null;

        // Wire the head and tail together
        head.next = tail;
        tail.prev = head;
    }

    public int getSize() {
        return totalItemsInCache;
    }

    /*
      Retrieve an item from the cache
    */
    // make get operation thread safe. Could use a reentrant read lock here for finer control.
    public synchronized int get(int key) {

        DNode node = hashtable.get(key);
        boolean itemFoundInCache = node != null;

        // Empty state check. Should raise exception here.
        if (!itemFoundInCache) {
            return -1;
        }

        // Item has been accessed. Move to the front of the list.
        moveToHead(node);

        return node.value;
    }

    /*
      Add an item to the cache if it is not already there,
      if it is already there update the value and move it
      to the front of the cache
    */
    public synchronized void put(int key, int value) {

            DNode node = hashtable.get(key);
            boolean itemFoundInCache = node != null;

            if(!itemFoundInCache){

                // Create a new node
                DNode newNode = new DNode();
                newNode.key = key;
                newNode.value = value;

                // Add to the hashtable and the doubly linked list
                hashtable.put(key, newNode);
                addNode(newNode);

                // We just added an item to the cache
                totalItemsInCache++;

                // If over capacity evict an item with LRU cache eviction policy
                if(totalItemsInCache > maxCapacity){
                    removeLRUEntryFromStructure();
                }

            } else {
                // If item is in cache just update and move it to the head
                node.value = value;
                moveToHead(node);
            }
        }

    /*
      Remove the least used entry from the doubly linked
      list as well as the hashtable. Hence it is evicted
      from the whole LRUCache structure
    */
    // don't think I need to make it  here right if I have made the helper methods thread safe?
    private  void removeLRUEntryFromStructure() {
        DNode tail = popTail();
        hashtable.remove(tail.key);
        --totalItemsInCache;
    }

    /*
      Insertions to the doubly linked list will always
      be right after the dummy head
    */
    private void addNode(DNode node){

        // Wire the node being inserted
        node.prev = head;
        node.next = head.next;

        // Re-wire the head's old next
        head.next.prev = node;

        // Re-wire the head to point to the inserted node
        head.next = node;
    }

    /*
      Remove the given node from the doubly linked list
    */
    private  void removeNode(DNode node){

        // Grab reference to the prev and next of the node
        DNode savedPrev = node.prev;
        DNode savedNext = node.next;

        // Cut out going forwards
        savedPrev.next = savedNext;

        // Cut out going backards
        savedNext.prev = savedPrev;
    }

    /*
      Move a node to the head of the doubly linked lsit
    */
    // don't think I need to make it  here right if I have made the helper methods thread safe?
    private  void moveToHead(DNode node){
        removeNode(node);
        addNode(node);
    }

    /*
      Pop the last item from the structure
    */
    private  DNode popTail(){
        DNode itemBeingRemoved = tail.prev;
        removeNode(itemBeingRemoved);
        return itemBeingRemoved;
    }

    public static void main(String[] args) {
        final LRUCache cache = new LRUCache(10);
        ExecutorService e = Executors.newFixedThreadPool(1000);
        for (int i = 0; i < 500000; i++) {
            e.submit(new Runnable() {
                @Override
                public void run() {
                    int r = ThreadLocalRandom.current().nextInt();
                    cache.put(Math.toIntExact(Thread.currentThread().getId()), Math.toIntExact(Thread.currentThread().getId()));
                    int key = Math.toIntExact(Thread.currentThread().getId());
                    if (cache.get(key) != key) {
                        System.out.println("Get value for key " + key + " : " + cache.get(key));
                    }
                }
            });
        }
        e.shutdown();
//        final Integer targetKey = 100; // 65 535
//        final Integer targetValue = 2;
//        cache.put(targetKey, targetValue);
//
//        new Thread(() -> {
//            IntStream.range(0, targetKey).forEach(key -> cache.put(key, key+1));
//        }).start();
//
//
//        while (true) {
//            if (!targetValue.equals(cache.get(targetKey))) {
//                throw new RuntimeException("HashMap is not thread safe.");
//            }
//        }
        // Create 10 Threads
//        for (int i = 0; i < 10; i++) {
//            Thread thread = new Thread(() -> {
//
//                // Let Each thread insert 3000 Items
//                for (int j = 0; j < 3000; j++) {
//                    cache.put(j,j);
//                }
//
//            });
//            thread.start();
//        }
//
//        System.out.println("Count should be 30000, actual is : " + cache.getSize());
       //  System.out.println("Size of cache is " + cache.size());
    }

}

}