#include <unordered_map>

struct DListNode{
    int key, val;
    DListNode* pre;
    DListNode* next;
    DListNode(int k, int v): key(k), val(v), pre(nullptr), next(nullptr){};
};


class Solution {
private:
    int size = 0;
    DListNode* head;
    DListNode* tail;
    unordered_map<int, DListNode*> mp;

public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        if(k < 1) return {};
        this->size = k;
        this->head = new DListNode(0,0);
        this->tail = new DListNode(0,0);
        this->head->next = this->tail;
        this->tail->pre = this->head;

        if(operators.size() == 0) return {};

        vector<int> res;

        for(vector<int> op : operators){
            if(op[0] == 1) {
                set(op[1], op[2]);
            }
            else if(op[0] == 2){
                int value = get(op[1]);
                res.push_back(value);
            }
        }
        return res;
    }

    void set(int key, int val){
        if(mp.find(key) == mp.end()){ // hashmap 中没找到
            DListNode* node = new DListNode(key, val);
            mp[key] = node;
            if(this->size <= 0){
                removeLast();
            }
            else{
                this->size--;
            }
            insertFirst(node);
        }
        else{  // hashmap 中已经有了，也就是链表里也已经有了
            mp[key]->val = val;
            moveToHead(mp[key]);
        }
    }


    int get(int key){
        int ret = -1;
        if(mp.find(key) != mp.end()){
            ret = mp[key]->val;
            moveToHead(mp[key]);
        }
        return ret;
    }

    void moveToHead(DListNode* node){
        if(node->pre == this->head) return;
        node->pre->next = node->next;
        node->next->pre = node->pre;
        insertFirst(node);
    }


    void removeLast(){
        mp.erase(this->tail->pre->key);
        this->tail->pre->pre->next = this->tail; // remove the last node in dlist
        this->tail->pre = this->tail->pre->pre;
    }

    void insertFirst(DListNode* node){
        node->pre = this->head;
        node->next = this->head->next;
        this->head->next->pre = node;
        this->head->next = node;
    }

};