class LRUCache{
private:
    class node{
    public:
        int key;
        int val;
        node* prev;
        node* next;
        node(int key, int val) {
            this->key = key;
            this->val = val;
            this->prev = NULL;
            this->next = NULL;
        }
    };
    node* head = NULL;
    node* tail = NULL;
    unordered_map<int, node*> map;
    int capacity;

    void moveToTail(node* current) {
        tail->prev->next = current;
        current->prev = tail->prev;

        current->next = tail;
        tail->prev = current;

        return;
    }

public:
    // @param capacity, an integer
    LRUCache(int capacity) {
        // write your code here
        this->capacity = capacity;
        this->head = new node(-1, -1);
        this->tail = new node(-1, -1);
        head->next = tail;
        tail->prev = head;
    }

    // @return an integer
    int get(int key) {
        // write your code here
        if (map.find(key) == map.end()) {
            return -1;
        }

        node* current = map[key];
        current->prev->next = current->next;
        current->next->prev = current->prev;
        moveToTail(current);

        return current->val;

    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    void set(int key, int value) {
        // write your code here
        if (get(key) != -1) {
            map[key]->val = value;
            return;
        }

        if (map.size() == capacity) {
            node* oldestNode = head->next;

            map.erase(oldestNode->key);

            oldestNode->next->prev = head;
            head->next = oldestNode->next;

            delete oldestNode;
        }

        node* newNode = new node(key, value);
        map.insert({key, newNode});

        moveToTail(newNode);

        return;
    }
};