//
//  Solution460.hpp
//  Algorithm
//
//  Created by Pancf on 2020/12/13.
//  Copyright © 2020 Pancf. All rights reserved.
//

#ifndef Solution460_hpp
#define Solution460_hpp

#include <stdio.h>
#include <unordered_map>
#include <list>

class LFUCache {
public:
    LFUCache(int capacity): capacity(capacity) {
        freqList.emplace_back(std::pair<int, std::list<int>>(1, {}));
    }
    
    int get(int key);
    void put(int key, int value);
    
private:
    
    int capacity;
    
    struct Item {
        int val;
        std::list<std::pair<int, std::list<int>>>::iterator freqIt;
        std::list<int>::iterator timeIt;
    };
    
    std::unordered_map<int, Item> mp;
    // 二维双向链表，第一维按frequency降序，第二维按access time降序
    std::list<std::pair<int, std::list<int>>> freqList;
    
    void reorderList(Item &);
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

#endif /* Solution460_hpp */