//
//  Solution146.cpp
//  Algorithm
//
//  Created by Pancf on 2020/12/8.
//  Copyright © 2020 Pancf. All rights reserved.
//

#include "Solution146.hpp"

LRUCache::LRUCache(int capacity): capacity(capacity)
{
}

int LRUCache::get(int key)
{
    auto it = keyToIndex.find(key);
    if (it != keyToIndex.end()) { // find it
        keyValues.splice(keyValues.begin(), keyValues, it->second);
        return it->second->second;
    }
    return -1;
}

void LRUCache::put(int key, int value)
{
    auto it = keyToIndex.find(key);
    if (it != keyToIndex.end()) {
        it->second->second = value;
        keyValues.splice(keyValues.begin(), keyValues, it->second);
    } else {
        if (keyToIndex.size() >= capacity) {
            int keyToRemove = keyValues.back().first;
            keyToIndex.erase(keyToRemove);
            keyValues.pop_back();
        }
        keyValues.emplace_front(key, value);
        keyToIndex.insert({key, keyValues.begin()});
    }
}