package com.freetymekiyan.algorithms.level.hard;

import java.util.HashMap;
import java.util.Map;

/**
 * Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following
 * operations: get and set.
 * <p>
 * get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
 * set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it
 * should invalidate the least recently used item before inserting a new item.
 * <p>
 * Company Tags: Google, Uber, Facebook, Twitter, Zenefits, Amazon, Microsoft, Snapchat, Yahoo, Bloomberg, Palantir
 * Tags: Design
 * <p>
 * Use 2 data structures to implement an LRU Cache:
 * 1. A queue which is implemented by a doubly linked list. The max size of the queue will be equal to cache size. Put
 * least recently used at the tail.
 * 2. A hash map with Node's value as key and the Node as value.
 * 3. A dummy head and a dummy tail of the queue. So that we can access both head and tail fairly quick.
 */
class LRUCache {

    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head;
    private final Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        moveToHead(node);
        return node.val;
    }

    public void set(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.val = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            addNode(newNode);
            cache.put(key, newNode);
            if (cache.size() > capacity) {
                Node last = tail.prev;
                removeNode(last);
                cache.remove(last.key);
            }
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

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

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

    class Node {

        Node prev;
        Node next;
        int key;
        int val;

        public Node() {
        }

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}

@@ -1234,24 +1234,114 @@
 Node tail;%0A%0A
+    /**%0A     * Remember capacity.%0A     * Create cache map and double linked list.%0A     */%0A
     public L
@@ -1356,32 +1356,32 @@
 int capacity) %7B%0A
-
         this.cap
@@ -1536,32 +1536,179 @@
  = head;%0A    %7D%0A%0A
+    /**%0A     * Check key in cache.%0A     * If not in cache, return -1.%0A     * If in cache, get the node, move it to head, return its value.%0A     */%0A
     public int g
@@ -1883,24 +1883,334 @@
 val;%0A    %7D%0A%0A
+    /**%0A     * If key already in cache:%0A     * %7C Get the node, update its value, move to head.%0A     * If key is not in cache:%0A     * %7C Create a new node.%0A     * %7C Add it to list and cache.%0A     * %7C If cache size exceeds capacity:%0A     * %7C   Get the last node.%0A     * %7C   Remove it from list and cache.%0A     */%0A
     public v
@@ -2689,32 +2689,97 @@
        %7D%0A    %7D%0A%0A
+    /**%0A     * Remove node from list and add it to head.%0A     */%0A
     private void
@@ -2851,32 +2851,94 @@
 e(node);%0A    %7D%0A%0A
+    /**%0A     * Remove a node from double linked list.%0A     */%0A
     private void
@@ -3037,24 +3037,70 @@
 rev;%0A    %7D%0A%0A
+    /**%0A     * Add a node after head.%0A     */%0A
     private 
@@ -3242,24 +3242,126 @@
 ode;%0A    %7D%0A%0A
+    /**%0A     * Double linked list node.%0A     * With previous node, next node, key, and value.%0A     */%0A
     class No

update lru cache