/**
 * https://leetcode.com/problems/lru-cache/
 * Time O(1) | Space O(N)
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.map = new Map();

        this.head = {};
        this.tail = {};

        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    removeLastUsed() {
        const [key, next, prev] = [
            this.head.next.key,
            this.head.next.next,
            this.head,
        ];

        this.map.delete(key);
        this.head.next = next;
        this.head.next.prev = prev;
    }

    put(key, value) {
        const hasKey = this.get(key) !== -1;
        const isAtCapacity = this.map.size === this.capacity;

        if (hasKey) return (this.tail.prev.value = value);
        if (isAtCapacity) this.removeLastUsed();

        const node = { key, value };
        this.map.set(key, node);
        this.moveToFront(node);
    }

    moveToFront(node) {
        const [prev, next] = [this.tail.prev, this.tail];

        this.tail.prev.next = node;
        this.connectNode(node, { prev, next });
        this.tail.prev = node;
    }

    connectNode(node, top) {
        node.prev = top.prev;
        node.next = top.next;
    }

    get(key) {
        const hasKey = this.map.has(key);
        if (!hasKey) return -1;

        const node = this.map.get(key);

        this.disconnectNode(node);
        this.moveToFront(node);

        return node.value;
    }

    disconnectNode(node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
}