// -*- mode: c++; c-basic-offset: 2; -*-

#ifndef LRU_HH
#define LRU_HH

#include <algorithm>
#include <deque>
#include <unordered_map>

template<typename K, typename V>
class lru {
public:
  lru(size_t size)
    : size_(size) {
  }

  bool empty() const {
    return usage_.empty();
  }

  size_t size() const {
    return usage_.size();
  }

  V* get(K const& key) {
    auto it = data_.find(key);
    if (it == data_.end()) return nullptr;
    auto it2 = std::find(usage_.begin(), usage_.end(), key);
    if (it2 != usage_.begin()) {
      usage_.erase(it2);
      usage_.push_front(key);
    }
    return &it->second;
  }

  void insert(K const& key, V const& data) {
    auto pair = data_.insert(std::make_pair(key, data));
    if (pair.second) {
      usage_.push_front(key);
      shrink_to_size();
    } else {
      pair.first->second = data;
      auto it = std::find(usage_.begin(), usage_.end(), key);
      if (it != usage_.begin()) {
        usage_.erase(it);
        usage_.push_front(key);
      }
    }
  }

  void erase(K const& key) {
    if (data_.erase(key)) {
      usage_.erase(std::find(usage_.begin(), usage_.end(), key));
    }
  }

private:
  void shrink_to_size() {
    if (usage_.size() > size_) {
      data_.erase(usage_.back());
      usage_.pop_back();
    }
  }

  size_t const size_;
  std::deque<K> usage_;
  std::unordered_map<K, V> data_;
};

#endif  // LRU_HH