class LFUCache {
Public:
    // 1. 容量サイズのキャッシュを構築する
    LFUCache(int capacity) {}
    // 1. キーに対応する値を取得する
    // 2. 見つからない場合は-1を返す
    int get(int key) {}
    // 1. キーと値のペアをキャッシュに格納する
    // 2. キャッシュがいっぱいの場合は、最も使用頻度の低いデータを削除する
    // 3. 同じ頻度のデータが複数ある場合は、最も最近使用されていないものを削除する
    void put(int key, int val) {}
}

#include <list>
#include <random>
#include <iostream>
#include <unordered_map>

using namespace std;

struct Node
{
    int key;
    int value;
    int freqeuncy;
    Node(int k, int v, int f) : key(k), value(v), freqeuncy(f) {}
};

class LFUCache
{
private:
    int minFreq;                                        // キャッシュの最小頻度
    int capacity;                                       // キャッシュの最大容量
    unordered_map<int, list<Node>::iterator> key_table; // キーとイテレータのマッピングテーブル
    unordered_map<int, list<Node>> freq_table;          // 頻度とリストのマッピングテーブル

public:
    int HIT = 0;
    int MISS = 0;

    LFUCache(int capacity){
        this->capacity = capacity;
        minFreq = 0;
        key_table.clear();
        freq_table.clear();
    }

    int get(const int &key)
    {
        // 容量が0の場合は-1を返す
        if (capacity == 0)
        {
            return -1;
        }
        // ノードのイテレータを探す
        auto it = key_table.find(key);
        // ノードが見つからない場合は-1を返す
        if (it == key_table.end())
        {
            MISS++;
            return -1;
        }
        list<Node>::iterator node = it->second;
        int value = node->value;
        int freq = node->freqeuncy;
        freq_table[freq].erase(node);
        // リストが空の場合、マップから削除し、最小頻度を更新する
        if (freq_table[minFreq].size() == 0)
        {
            freq_table.erase(freq);
            // 最小頻度が現在の頻度と等しい場合、min_freqを増やす
            if (minFreq == freq)
                minFreq++;
        }
        // ノードをfreq + 1の位置に挿入する
        freq_table[freq + 1].push_front(Node(key, value, freq + 1));
        // マップ内のイテレータを更新する
        key_table[key] = freq_table[freq + 1].begin();
        HIT++;
        return value;
    }

    void put(int key, int value)
    {
        // 容量が0の場合は戻る
        if (capacity == 0)
            return;
        // ノードのイテレータを探す
        auto it = key_table.find(key);
        if (it == key_table.end())
        {
            // キーがキャッシュにない場合、挿入する
            // 最初に容量を確認する
            if (key_table.size() == capacity)
            {
                // キャッシュがいっぱいの場合、最も使用頻度の低いノードを削除する
                // 最小頻度で最後のノードを取得する
                auto minNode = freq_table[minFreq].back();
                key_table.erase(minNode.key);
                // 新しいノードを挿入する
                freq_table[minFreq].pop_back();
                if (freq_table[minFreq].size() == 0)
                {
                    // リストが空の場合、マップから削除する
                    freq_table.erase(minFreq);
                }
            }
            // マップ内のイテレータを更新する
            minFreq = 1;
            freq_table[minFreq].push_front(Node(key, value, minFreq));
            key_table[key] = freq_table[minFreq].begin();
        }
        else
        {
            // キーがキャッシュにある場合、頻度を更新する
            list<Node>::iterator node = it->second;
            int freq = node->freqeuncy;
            freq_table[freq].erase(node);
            if (freq_table[freq].size() == 0)
            {
                // 古い頻度を削除する
                freq_table.erase(freq);
                // min_freq == cur_freqの場合、min_freqを更新する
                if (minFreq == freq)
                    minFreq++;
            }
            // ノードをfreq + 1の位置に挿入する
            freq_table[freq + 1].push_front(Node(key, value, freq + 1));
            // マップ内のイテレータを更新する
            key_table[key] = freq_table[freq + 1].begin();
        }
    }

    void clear()
    {
        key_table.clear();
        freq_table.clear();
        minFreq = 0;
        HIT = 0;
        MISS = 0;
    }
};

void testCase(){
    // leetcodeの例から
    LFUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 1を返す
    cache.put(3, 3);              // キー2を追い出す
    cout << cache.get(2) << endl; // -1を返す (見つからない)
    cout << cache.get(3) << endl; // 3を返す
    cache.put(4, 4);              // キー1を追い出す
    cout << cache.get(1) << endl; // -1を返す (見つからない)
    cout << cache.get(3) << endl; // 3を返す
    cout << cache.get(4) << endl; // 4を返す
}

int main()
{
    // testCase();

    const int CAPACITY = 200;
    const int NUM = 1000;

    LFUCache cache(CAPACITY);

    // シーケンシャルアクセス
    cout << "Sequential Access" << endl;
    cache.clear();
    for (int i = 0; i < NUM; ++i)
    {
        if (cache.get(i) == -1)
        {
            cache.put(i, i);
        }
    }
    cout << "HIT: " << cache.HIT << "\t\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;

    // 一様分布によるランダムアクセス
    cout << "Random Access with Uniform Distribution" << endl;
    cache.clear();
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, NUM);
    for (int i = 0; i < NUM; ++i)
    {
        int key = dis(gen);
        if (cache.get(key) == -1)
        {
            cache.put(key, key);
        }
    }
    
    cout << "HIT: " << cache.HIT << "\t\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;


    // 正規分布によるランダムアクセス
    cout << "Random Access with Normal Distribution" << endl;
    cache.clear();
    int mu = NUM / 2;
    int sigma = NUM / 6;
    normal_distribution<> ndis(mu, sigma);
    for (int i = 0; i < NUM*10; ++i)
    {
        int key = ndis(gen);
        if (cache.get(key) == -1)
        {
            cache.put(key, key);
        }
    }

    cout << "HIT: " << cache.HIT << "\t\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;

    return 0;
}