#include <bits/stdc++.h>

using namespace std;

//*********************************************************
// HackerRank Prepare C++: Abstract Classes - Polymorphism
//*********************************************************

struct Node {
    Node* prev;    
    Node* next;
    int key;    
    int value;
    Node(Node* p, Node* n, int k, int val)
        : prev(p),next(n),key(k),value(val)
    {};
    Node(int k, int val)
        : prev(NULL),next(NULL),key(k),value(val){};
};

class Cache
{
protected: 
    map<int,Node*> mp; // map the key to the node in the linked list
    int cp;  // capacity
    Node* tail; // double linked list tail pointer
    Node* head; // double linked list head pointer
    virtual void set(int, int) = 0; //set function
    virtual int get(int) = 0; //get function
};

struct LRUCache : public Cache
{
    LRUCache(int capacity)
    {
        cp = capacity;
        tail = nullptr;
        head = nullptr;
    }

    Node* getHead() { return head; }
    
    void insertHead(Node* newnode)
    {
        if (head == nullptr && tail == nullptr)
        {
            head = newnode;
            head->prev = nullptr;
            head->next = nullptr;
            tail = head;
        }
        else
        {
            Node* nextnode = head;
            head = newnode;
            head->prev = nullptr;
            head->next = nextnode;
            nextnode->prev = head;
        }

        mp.insert(pair<int, Node*>{head->key, head});

        cout << "---- mp ----" << endl;        
        for (auto& i: mp)
            cout << i.first << " " << i.second << endl;
        cout << "------------" << endl;        

        if ((int)mp.size() > cp)
            removeTail();
    }

    void removeTail()
    {
        if (tail == head) // case where capacity == 1
            return;
        
        Node* tmp = tail;
        tail = tail->prev;
        tail->next = nullptr;
        mp.erase(tmp->key);
        cout << "removeTail: " << hex << tail << " prev: " << tail->prev << " next: " << tail->next
             << " newTail: " << tail << " prev: " << tail->prev << " next: " << tail->next << endl;
        delete tmp;
    }

    Node* removeNode(Node* node)
    {
        return nullptr;        
    }
    
    void printList(Node* head)
    {
        if (head == nullptr)
            return;
        
        cout << hex << head << dec << " key: " << head->key << " value: " << head->value << " next: " << hex << head->next << " prev: " << head->prev << dec << endl;
        
        return printList(head->next);
    }

    // Set/insert the value of the key, if present, otherwise add the
    // key as the most recently used key. If the cache has reached its
    // capacity, it should replace the least recently used key with a
    // new key.    
    virtual void set(int key, int value)
    {
        auto iter = mp.find(key);
        if ( iter != mp.end())
        {
            Node* node = iter->second;
            node->value = value;
        }
        else
        {
            Node* node = new Node(key, value);
            insertHead(node);
        }
    }

    // Get the value (will always be positive) of the key if the key
    // exists in the cache, otherwise return -1.
    virtual int get(int key)
    {
        auto iter = mp.find(key);
        if (iter != mp.end())
            return iter->second->value;
        else
            return -1;
    }
};

int main() {
    vector<tuple<int,int,vector<string>,vector<int>>> testCases = {
        {3, 1, {"set 1 2", "get 1", "get 2"}, {2, -1}},
        {8, 4, {"set 4 2", "set 2 7", "get 2", "set 1 8", "set 5 9", "set 6 15", "get 4", "get 5"}, {7, -1, 9}},
    };

    for (auto& tc: testCases)
    {
        int n = get<0>(tc);
        int capacity = get<1>(tc);        
        LRUCache l(capacity);

        cout << "n: " << n << " cap: " << capacity << " commands: ";        
        for (auto& command: get<2>(tc))
            cout << command << ", ";
        cout << " expected: ";
        for (auto& expected: get<3>(tc))
            cout << expected << " ";
        cout << endl;

        //size_t getIndex = 0;
        
        for (auto& command: get<2>(tc))
        {
            if (command.substr(0, 3) == "get")
            {
                regex re(R"(^(get )([0-9]*)$)");
                smatch base_match;                
                regex_match(command, base_match, re);
                ssub_match base_sub_match = base_match[2];
                
                int key = atoi(base_sub_match.str().c_str());
                cout << "get key: " << key << endl;
                cout << l.get(key) << endl;
            }
            else if(command.substr(0, 3) == "set")
            {
                regex re(R"(^(set )([0-9]*)( )([0-9]*)$)");
                smatch base_match;                
                regex_match(command, base_match, re);
                ssub_match base_sub_match1 = base_match[2];
                ssub_match base_sub_match2 = base_match[4];                
            
                int key = atoi(base_sub_match1.str().c_str());
                int value = atoi(base_sub_match2.str().c_str());

                cout << "set key: " << key << " value: " << value << endl;
                l.set(key,value);
                cout << "------- printList -----" << endl;                
                l.printList(l.getHead());
                cout << "-----------------------" << endl;                
            }
        }
        cout << "---------------------" << endl;        
    }
    
    return 0;
}