#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
//////双哈希实现简单LFU算法：

// 定义对应的节点结构：

template <class K, class V>
struct Node
{
    Node() {} //表明对应的默认对象必须存在，hash[key] = Node()！！
    Node(const K& key, const V& value, int access_count)
        : key(key), value(value), access_count(access_count) {
    }

    K key;
    V value;

    // 存储对应key的访问次数：
    int access_count;
    // 对应节点的key值所在的list处的迭代器：

    // 表明是类型不是list中的成员变量：
    typename list<K>::iterator it; // 方便找到对应的list的具体位置，方便进行删除。
};

template <class K, class V>
class LFUCache
{

public:
    LFUCache(size_t capacity) : _capacity(capacity), _min_access_count(1) {}

    bool put(const K& key, const V& val)
    {
        // 1.判断容量是否为0：

        if (_capacity <= 0)
            return false;

        //进行查找：
        auto it = _hash_map.find(key);
        if (it != _hash_map.end()) {
            // 存在这个key，直接更新对应的值并根据对应LFU策略进行对应处理：
            _hash_map[key].value = val;
            // 2.更新访问次数：
            accessCountAdd(key);
            return true;
        }

        // 不存在，检查容量（根据LFU策略更新),插入新的：
        // it==_hash_map.end()

        if (_capacity <= _hash_map.size())
        {
            // 容量已满，执行LFU策略：
            // 找到访问次数最少的list，也就是是最不经常使用的那一批数据：
            auto& min_list = _access_map[_min_access_count];
            // 根据LRU策略删除最近最少使用的key：
            auto evict_key = min_list.back();
            min_list.pop_back();
            // 判断是否这个list为空了，进行删除：
            if (min_list.empty())
                _access_map.erase(_min_access_count);
            _hash_map.erase(evict_key);
        }

      

        // 不存在直接构造插入：

        // 3.插入新节点：

        auto& new_list = _access_map[1];                              // 这里是1，因为是新插入的节点，访问次数为1
        _hash_map[key] = Node<K, V>(key, val, 1); // 这里也需要告诉编译器是个类型不是变量！！
        // 4.更新访问次数hash：
        new_list.push_front(key);
        // 更新对应的key的node的迭代器
        _hash_map[key].it = new_list.begin();
        _min_access_count = 1;
        return true;
    }

    V get(const K& key)
    {

        // 先判断是否存在这个key：
        if (_hash_map.find(key) == _hash_map.end())
            return V(); //有点瑕疵，一般都是int int ，直接返回-1

        // 存在这个key，进行访问次数+1：
        accessCountAdd(key);

        return _hash_map[key].value;
    }

    // 打印当前缓存状态（用于测试）
    void printCache()
    {
        cout << "Current Cache State:" << endl;
        for (const auto& item : _hash_map)
        {
            cout << "Key: " << item.first
                << ", Value: " << item.second.value
                << ", Access Count: " << item.second.access_count << endl;
        }
        cout << "Current Cache State:" << endl;
        for (const auto& item : _hash_map)
        {
            cout << "Key: " << item.first
                << ", Value: " << item.second.value
                << ", Access Count: " << item.second.access_count << endl;
        }

        cout << "Access Lists:" << endl;
        for (const auto& pair : _access_map)
        {
            cout << "Access Count " << pair.first << ": ";
            for (int key : pair.second)
            {
                cout << key << " ";
            }
            cout << endl;
        }
        cout << "Min Access Count: " << _min_access_count << endl;
    }

private:
    // 对于put或者get后进行对应的数据的访问次数等操作进行统一处理（比如进行LFU策略删除等）
    void accessCountAdd(const K& key)
    {

        // 获取对应节点
        Node<K, V>& node = _hash_map[key];

        int old_access_cnt = node.access_count;

        list<int>& cur_list = _access_map[old_access_cnt];

        cur_list.erase(node.it);
        // 删除后进行判断，如果访问的hash对应list空了，直接删除这个hash槽即可
        if (cur_list.empty())
        {

            _access_map.erase(old_access_cnt);

            // 如果恰好是最少的，更新下最小的即可
            if (old_access_cnt == _min_access_count)
                // 如果删除完对应的之前的key所在的list后，为空了而且此时对应的min_cnt也是当前key的cnt，此时说明min_cnt必须要+1完成更新了
                _min_access_count++;
        }

        // 此时除了有可能它俩相同，就是cur_list不为空的情况，或者不等：

        // 进行更新访问次数：
        int new_access_cnt = old_access_cnt + 1;
        node.access_count = new_access_cnt;
        // 再次更新下，这里保险起见：
        _min_access_count = min(_min_access_count, new_access_cnt);

        // 把对应的key加入到新的list中：

        auto& new_list = _access_map[new_access_cnt]; // 这里需要引用，因为后续会进行修改

        new_list.push_front(node.key);

        // 务必要更新对应迭代器：

        node.it = new_list.begin();
    }

private:
    unordered_map<K, Node<K, V>> _hash_map;  // 储存对应key值与对应的上述节点的hash
    unordered_map<int, list<K>> _access_map; // 储存对应的访问次数的存放key的那个list

    size_t _capacity; // 缓存最大容量，根据它进行决定进行对应的LFU策略更新

    int _min_access_count; // 储存最少的访问次数，方便进行删除
};

int main()
{
    LFUCache<int, int> cache(3);

    cache.put(1, 10);
    cache.put(2, 20);
    cache.put(3, 30);
    cache.printCache();
    cout << endl;

    // 访问键1，增加其访问次数
    cout << "Get key 1: " << cache.get(1) << endl;
    cache.printCache();
    cout << endl;

    // 添加新键4，应淘汰访问次数最低的键2
    cache.put(4, 40);
    cache.printCache();
    cout << endl;

    // 再次访问键3，增加其访问次数
    cout << "Get key 3: " << cache.get(3) << endl;
    cache.printCache();
    cout << endl;

    // 添加新键5，应淘汰访问次数最低的键4
    cache.put(5, 50);
    cache.printCache();

    return 0;
}