class LRUCache: public Cache{ public: LRUCache(int c){cp = c; tail = nullptr; head = nullptr;} virtual void set(int key, int value) override{ map::iterator it = mp.find(key); Node* node = nullptr; if(it == mp.end()){ node =new Node(nullptr, head, key, value); if(mp.size() >= cp){ tail = tail->prev; tail->next->prev = nullptr; mp.erase(tail->next->key); delete tail->next; tail->next = nullptr; }else{ } if(tail == nullptr) tail = node; if(head) head->prev = node; head = node; mp[key] = node; }else{ it->second->value = value; node = it->second; if(node != head){ if(head->next == tail){ /* replace the order for head and tail*/ head = head->next; tail = tail->prev; tail->next = nullptr; head->prev = nullptr; head->next = tail; tail->prev = head; }else{ if(node == tail){ /* put the tail as a head*/ tail = tail->prev; tail->next = nullptr; node->prev = nullptr; node->next = head; head->prev = node; head = node; }else{ /* put the middle node as a head*/ node->prev->next = node->next; node->next->prev = node->prev; node->next = head; node->prev = nullptr; head->prev = node; head = node; } } }else{ /* no change in order*/ } } }

virtual int get(int key)override{
    int value = -1;
    map<int,Node*>::iterator it = mp.find(key);
    if(it != mp.end()){
        value = it->second->value;
        Node* node = it->second;
        if(node != head){
            if(head->next == tail){
                /* replace the order for head and tail*/
                head = head->next;
                tail =  tail->prev;
                tail->next = nullptr;
                head->prev = nullptr;
                head->next = tail;
                tail->prev = head;
            }else{
                if(node == tail){
                    /* put the tail as a head*/
                    tail = tail->prev;
                    tail->next = nullptr;
                    node->prev = nullptr;
                    node->next = head;
                    head->prev = node;
                    head = node;
                }else{
                   /* put the middle node as a head*/
                   node->prev->next = node->next;
                   node->next->prev = node->prev;
                   node->next = head;
                   node->prev = nullptr; 
                   head->prev = node;
                   head = node;
                }
            }
        }else{
            /* no change in order*/
        }
    }
    return value;
}

};