#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <functional>
#include <unordered_map>

template<class Key, class Value>
class ListNode {
public:
    Key key;
    Value value;

    ListNode* prev;
    ListNode* next;

    ListNode(Key k, Value v)
        : key(k), value(v), prev(nullptr), next(nullptr) {}
};

template<class Key, class Value>
class LinkedList {
private:
    ListNode<Key, Value>* head;
    ListNode<Key, Value>* tail;

    std::unordered_map<Key, ListNode<Key, Value>*> mp;

    size_t sz;

public:
    LinkedList() : sz(0) {
        head = new ListNode<Key, Value>(Key(), Value());
        tail = new ListNode<Key, Value>(Key(), Value());
        head->next = tail;
        tail->prev = head;
    }

    ~LinkedList() {
        auto cur = head;
        while (cur) {
            auto next = cur->next;
            delete cur;
            cur = next;
        }
    }

    void insert_front(Key key, Value value) {
        if (mp.count(key)) return;

        auto node = new ListNode<Key, Value>(key, value);

        node->next = head->next;
        node->prev = head;

        head->next->prev = node;
        head->next = node;

        mp[key] = node;

        ++sz;
    }

    void remove(Key key) {
        if (!mp.count(key)) return;

        auto node = mp[key];

        node->prev->next = node->next;
        node->next->prev = node->prev;

        mp.erase(key);
        delete node;

        --sz;
    }

    ListNode<Key, Value>* find(Key key) {
        if (!mp.count(key)) return nullptr;
        return mp[key];
    }

    const ListNode<Key, Value>* find(Key key) const {
        typename std::unordered_map<Key, ListNode<Key, Value>*>::const_iterator it = mp.find(key);
        if (it == mp.end()) return nullptr;
        return it->second;
    }

    void move_to_front(Key key) {
        if (!mp.count(key)) return;

        auto node = mp[key];

        // 先摘掉
        node->prev->next = node->next;
        node->next->prev = node->prev;

        // 再插到头
        node->next = head->next;
        node->prev = head;

        head->next->prev = node;
        head->next = node;
    }

    void remove_tail() {
        if (tail->prev == head) return;

        auto node = tail->prev;

        node->prev->next = tail;
        tail->prev = node->prev;

        mp.erase(node->key);
        delete node;

        --sz;
    }
    
    size_t size() const {
        return sz;
    }

    // Iterate from head -> tail (excluding sentinels)
    void for_each(const std::function<void(const Key&, const Value&)>& visitor) const {
        auto cur = head->next;
        while (cur != tail) {
            visitor(cur->key, cur->value);
            cur = cur->next;
        }
    }
};

#endif