class LRUCache : Cache
{
    private:
        // Member variable to distinguish between first 
        // element added and remaining elements
        bool m_first_node_added = false;
        // Iterator for map
        std::map<int, Node*>::iterator it;
        
        // Add new Node
        void AddNode(int key, int value);
        // Discard last item of list and add new Node
        void UpdateNewNode(int key, int value);
        // Update Cache order after a get command
        void UpdateLastHit(Node * node);
    
    public:
        // Public constructor with capacity
        LRUCache(int capacity)
        {
            cp = capacity;
        }
        
        // set new item
        void set(int key, int value);
        
        // get value from list
        int get(int key);
};

int LRUCache::get(int key)
{
    int ret_value = 0;
    try
    {
        it = mp.find(key);
        if (it != mp.end())
        {
            Node* tmp = it->second;
            ret_value = tmp->value;
            
            // Update
            UpdateLastHit(tmp);
            
            /*std::cout << "Print" << std::endl;
            // Print from tail to head
            Node* x = tail;
            for (int i = 0; i < mp.size(); i++)
            {
                std::cout <<" i - " << i << " - " <<  x->key << " - " << x->value << std::endl;
                if (x->next != nullptr)
                {
                    x = x->next; 
                }
                else 
                {
                    break;
                } 
            }*/
            
            // Print from head to tail
            /*x = head;
            for (int i = 0; i < mp.size(); i++)
            {
                std::cout <<" i - " << i << " - " <<  x->key << " - " << x->value << std::endl;
                
                if (x->prev != nullptr)
                {
                    x = x->prev; 
                }
                else 
                {
                    break;
                }  
            }*/
        }
        else 
        {
            ret_value = -1;
        }
    }
    catch (const std::out_of_range& oor) 
    {
        std::cerr << "Out of Range error: " << oor.what() << '\n';
    }

    return ret_value;
}

void LRUCache::UpdateLastHit(Node* node)
{
    // If node requested is already head
    // no update needed
    if (node->value != head->value &&
        node->key   != head->key)
    {        
        // If node is tail
        // linked list update shall be different
        if (node == tail)
        {      
            Node* next_node = node->next;
            tail = next_node;
            next_node->prev = nullptr;
        }
        else 
        {
            // Get previous and next node
            Node* prev_node = node->prev;
            Node* next_node = node->next;
            
            // Link previous and next node
            prev_node->next = next_node;
            next_node->prev = prev_node;
        }
        
        //Update head
        node->prev = head;
        node->next = nullptr;
        
        head->next = node;
        
        head = node;
    }
}

void LRUCache::set(int key, int value)
{
    if (mp.size() < cp)
    {
        //std::cout << "AddNode" << std::endl;
        AddNode(key, value);
    }
    else 
    {
        //std::cout << "Update of list is needed" << std::endl;
        UpdateNewNode(key, value); 
    }
}

void LRUCache::AddNode(int key, int value)
{
    // Create Node ptr
    Node* entry = new Node(key, value);
            
    if (!m_first_node_added)
    {
        // Since it is first Node there is no prev or next
        entry->prev = nullptr;
    }
    else 
    {
        // If is not the first Node, set prev as the current head
        entry->prev = head;
    }
    // Next will always be null since the new node is added to the head
    entry->next = nullptr;
    
    // If it is not the first node, current Head will point to new node
    // Update the next entry for the previous head
    if (m_first_node_added)
    {
        head->next = entry;
    }
    
    // Add/Update entry to map
    mp[key] = entry;
    
    // Entry is always the new head
    head = entry;
    
    // First Node added then is at same time tail and head
    if (!m_first_node_added)
    {
        tail = entry;
    }
    
    // If first node is added
    // initialize variable
    if (!m_first_node_added)
    {
        m_first_node_added = true;
    }
}

void LRUCache::UpdateNewNode(int key, int value)
{
    // Update tail first and remove current tail
    int tail_key = tail->key;
    tail = tail->next;
    tail->prev = nullptr;
    
    // remove old tail
    mp.erase(tail_key);
    
    // Add new entry as header
    // Create Node ptr
    Node* entry = new Node(key, value);
    
    // Copy next reference from current tail
    entry->prev = head;
    entry->next = nullptr;
    
    // Assign next entry to old head
    head->next = entry;
    
    // Add entry to map
    mp[key] = entry;
    
    // Set new head
    head = entry;
}

class LRUCache: public Cache {
    public:
        LRUCache(int cap) {capacity = cap;}
        void set(int key, int val) {
            map<int, Node*>::iterator it = mp.find(key);
            if(it == mp.end()) {
                // not in the cache
                Node* newNode = new Node(key, val);
                mp.emplace(key, newNode);
                if(mp.size() == 1) {
                    head = newNode;
                    tail = newNode;
                } else {
                    head->prev = newNode;
                    newNode->next = head;
                    head = newNode;
                    if(mp.size() > capacity) {
                        Node* last = tail;
                        tail = last->prev;
                        mp.erase(last->key);
                        tail->next = nullptr;
                        delete last;
                    }   
                }
            } else {
                // cache hit
                Node* node = it->second;
                node->value = val;
                if(mp.size() != 1) {
                    if(node->prev != nullptr) {
                        node->prev->next = node->next;
                        head->prev = node;
                        node->prev = nullptr;
                        head = node;
                    }
                    
                }
            }
        }
        
        int get(int key) {
            map<int, Node*>::iterator it = mp.find(key);
            return (it == mp.end() ? -1 : it->second->value);
        }
    
    private:
        int capacity;
};

struct LRUCache : Cache {
    std::vector<std::pair<int, int>> list{};
    LRUCache(int n) {
        this->cp = n;
    }
    void set(int a, int b) override {
        const auto iter = std::find_if(list.begin(), list.end(), [a](const auto& c){
            return a == c.first;
        });
        if (iter != list.end()) {          // same key found
            list.erase(iter);
        } else {
            if (this->cp == list.size()) { // max size
                list.erase(list.begin());  
            } 
        }
        list.push_back({a, b});
    }
    int get(int a) override {
        const auto iter = std::find_if(list.begin(), list.end(), [a](const auto& c){
            return a == c.first;
        });
        if (iter != list.end()) {
            return iter->second;
        }
        return -1;
    }
};

class LRUCache : Cache{
    int curc = 1;
    
    public:
    LRUCache(int c){
        cp = c;
        head = NULL;
        tail = new Node(-1,0);
        mp[-1] = tail;
    }
   
   void set(int k, int v){
       
       Node* f = NULL;
       auto itr = mp.begin();
       while(itr!= mp.end()){
           if(itr->first == k){  f = mp[k]; break;}
           itr++;
       }
       if( f ){
            if(f!=head){ f->prev->next = f->next;
            if(f!=tail){ f->next->prev = f->prev; }
            else{ tail = f->prev; tail->next=NULL;}
            f->next = head;
            head->prev = f;
            head = f;
            }
            f->value = v;
            f->prev = NULL; 
            
       }else{
           Node* n;
          if(head == NULL){ 
            n = new Node(NULL,tail,k,v); 
            head = n;
            tail->prev = n;
            mp[k] = n;
          }
          else{ 
            n = new Node(NULL,head,k,v);
            head->prev = n;
             mp[k] = n;
              head = n;
            }
          curc++; 
       }
       
       
       if(curc > cp){
           
           Node* p = tail->prev;
           
           mp.erase(tail->key);
           delete tail;
           tail = p;
           tail->next = NULL;
           //mp[p->key] = NULL;
           curc--;
       }

   } 
   
   int get(int k){ 
        int find = 0;
        Node* f;
       auto itr = mp.begin();
       while(itr!= mp.end()){
           if(itr->first == k){  f = mp[k]; find = 1; break;}
           itr++;
       }
      if(find){ set(k,f->value); 
            return f->value; }
      else return -1; 
   }
};