class LRUCache: public Cache {
public:
    // Constructor: Initialize LRU cache with given capacity
    LRUCache(int capacity) {
        assert(capacity > 0); // Capacity must be positive
        cp = capacity;
        // Initialize sentinel nodes (dummy head and tail)
        head = new Node(-1, -1);  // Dummy head node
        tail = new Node(-1, -1);  // Dummy tail node
        // Link head and tail to form empty list
        tail->prev = head;
        head->next = tail;
    };

    // Destructor: Clean up all allocated nodes
    ~LRUCache() {
        Node* p = head->next;
        while (p != tail) {
            Node* temp = p;
            p = p->next;
            delete temp;  // Delete all nodes including sentinels
        }
        delete head;
        delete tail;
    }

    // Set key-value pair in cache
    void set(int key, int val) override {
        // Step 1: Check if key exists
        auto p = mp.find(key);
        if (p == mp.end()) {
            // Step 2: If cache is full, evict LRU item
            if (mp.size() == cp)
                popEnd();
            // Create new node and add to map
            mp[key] = new Node(key, val);
        } else {
            // Update existing value
            mp[key]->value = val;
        }
        // Step 3: Move node to front (MRU position)
        moveToFront(mp[key]);
    }
    
    // Get value by key, returns -1 if not found
    int get(int key) override {
        auto p = mp.find(key);
        if (p == mp.end())
            return -1;
        // Move accessed node to front (MRU position)
        moveToFront(mp[key]);
        return mp[key]->value;
    }

private:
    // Move node to front of list (MRU position)
    void moveToFront(Node* curr) {
        // If node is not new, remove from current position
        if (curr->prev) {
            curr->prev->next = curr->next;
            curr->next->prev = curr->prev;
        }
        // Insert node after head (new MRU position)
        Node* headNext = head->next;
        insertNode(head, headNext, curr);
    }
    
    // Helper to insert node between left and right nodes
    void insertNode(Node* left, Node* right, Node* curr) {
        left->next = curr;
        curr->prev = left;
        right->prev = curr;
        curr->next = right;
    }
    
    // Remove LRU item (node before tail)
    void popEnd() {
        Node* end = tail->prev;
        mp.erase(end->key);  // Remove from map
        // Remove from list
        end->prev->next = tail;
        tail->prev = end->prev;
        delete end;  // Free memory
    }
};