struct Node
{
    int key;
    int val;
};

class LRUCache
{
public:
    LRUCache(int capacity) : m_Capacity(capacity)
    {
        m_Size = 0;
    }

    int get(int key)
    {
        // empty list/hashtable / not found key -> then return -1
        if (lst.size() == 0 || hashTable.find(key) == hashTable.end())
            return -1;
        // now we need to retrieve the value to return and place this node at first spot on the list
        // using 'splice'
        std::list<Node>::iterator iteratorToKeyNode = hashTable[key];
        // now we need to move the current Node to the beginning of the lst.
        // we will do it by using splice
        lst.splice(lst.begin(), lst, iteratorToKeyNode); // using splice to move the current node to the beginning of the lst.
        return (*iteratorToKeyNode).val;
    }

    void put(int key, int value)
    {
        Node newNode = { key, value };
        // two cases:
        // A1: Key already exists
        if (hashTable.find(key) != hashTable.end())
        {
           std::list<Node>::iterator iteratorToExistedNode = hashTable[key];
           (*iteratorToExistedNode).val = value;
           lst.splice(lst.begin(), lst, iteratorToExistedNode); // using splice to move the current node to the beginning of the lst.
        }
        // B1: Key does not exist
        else
        {
            // two cases:
            // A2: there is room left in the cache:
            if (m_Size < m_Capacity)
            {
                m_Size++; // incrementing size
                // hashTable.emplace(std::make_pair(key, newNode)); // updating the hashTable
                // lst.push_front(newNode);                         // updating lst
            }
            // B2: there is no room left in the cache
            else
            {
                // we need to remove the least recently used node, which is the tail of the list
                Node nodeToBeRemoved = lst.back();
                lst.pop_back();
                hashTable.erase(nodeToBeRemoved.key);
            }
            // adding the new element
            //hashTable.emplace(std::make_pair(key, newNode)); // updating the hashTable
            lst.push_front(newNode);
            hashTable.emplace(std::make_pair(key, lst.begin()));
        }

    }

private:
    int m_Size;
    int m_Capacity;
    std::list<Node> lst;
    std::unordered_map<int, std::list<Node>::iterator> hashTable;
};

/**
 * 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);
 */