class LRUCache
{
public:
   LRUCache(int capacity) : _capacity(capacity)
   {
      _dummy_head = new Node(-1, -1);
      _dummy_tail = new Node(-1, -1);
      _dummy_head->_next = _dummy_tail;
      _dummy_tail->_prev = _dummy_head;
   }

   ~LRUCache()
   {
      delete _dummy_head;
      delete _dummy_tail;
   }

   int get(int key)
   {
      int result = -1;
      // two options:
      // case A: key exists
      // if (this->_map.contains(key))
      if (this->_map.find(key) != this->_map.end())
      {
         Node *resNode = this->_map[key];

         // first remove it
         this->removeNode(resNode);
         this->addNode(resNode);
         this->_map[key] = this->_dummy_head->_next;

         result = this->_map[key]->_value;
      }
      // case B: key is missing
      return result;
   }

   void put(int key, int value)
   {
      // Case A:
      // key is already here
      if (this->_map.find(key) != this->_map.end())
      {
         Node *currentNode = this->_map[key];
         removeNode(currentNode);
      }
      // Case B:
      // map is full and we need to delete the last node [remember, head and tail are dummy head / tail...]
      else if (this->_map.size() == _capacity)
      {
         this->_map.erase(this->_dummy_tail->_prev->_key);
         removeNode(this->_dummy_tail->_prev);
      }
      this->addNode(new Node(key, value));
      this->_map[key] = this->_dummy_head->_next;
   }

private:
   struct Node
   {
      Node *_prev;
      Node *_next;
      int _key;
      int _value;
      Node(int key, int value) : _key(key), _value(value) {}
   };

   void addNode(Node *newNode)
   {
      Node *tmp = this->_dummy_head->_next;
      this->_dummy_head->_next = newNode;
      newNode->_next = tmp;
      tmp->_prev = newNode;
      newNode->_prev = this->_dummy_head;
   }

   void removeNode(Node *delNode)
   {
      Node *prevNode = delNode->_prev;
      Node *nextNode = delNode->_next;

      prevNode->_next = nextNode;
      nextNode->_prev = prevNode;
   }

   std::unordered_map<int, Node *> _map;
   int _capacity;
   Node *_dummy_head;
   Node *_dummy_tail;
};
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
Console