class LFUCache {
Public:
    // 1. capacity 크기의 캐시를 생성합니다.
    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;
}