#ifndef SRC_LRU_CACHE_INL_H_
#define SRC_LRU_CACHE_INL_H_

#include <list>
#include <unordered_map>
#include <utility>

template <typename key_t, typename value_t>
class LRUCache {
 public:
  using key_value_pair_t = typename std::pair<key_t, value_t>;
  using iterator = typename std::list<key_value_pair_t>::iterator;
  using const_iterator = typename std::list<key_value_pair_t>::const_iterator;

  const_iterator begin() const { return lru_list_.begin(); }
  const_iterator end() const { return lru_list_.end(); }

  explicit LRUCache(size_t capacity) : capacity_(capacity) {}

  void Put(const key_t& key, const value_t& value) {
    auto it = lookup_map_.find(key);
    if (it != lookup_map_.end()) {
      lru_list_.erase(it->second);
      lookup_map_.erase(it);
    }

    lru_list_.push_front(std::make_pair(key, value));
    lookup_map_[key] = lru_list_.begin();

    if (lookup_map_.size() > capacity_) {
      auto last = lru_list_.end();
      last--;
      lookup_map_.erase(last->first);
      lru_list_.pop_back();
    }
  }

  value_t& Get(const key_t& key) {
    auto it = lookup_map_.find(key);
    lru_list_.splice(lru_list_.begin(), lru_list_, it->second);
    return it->second->second;
  }

  // The entry for `key`, or nullptr when there is none.
  value_t* GetIf(const key_t& key) {
    auto it = lookup_map_.find(key);
    if (it == lookup_map_.end()) return nullptr;
    lru_list_.splice(lru_list_.begin(), lru_list_, it->second);
    return &it->second->second;
  }

  void Erase(const key_t& key) {
    auto it = lookup_map_.find(key);
    if (it != lookup_map_.end()) {
      lru_list_.erase(it->second);
      lookup_map_.erase(it);
    }
  }

  bool Exists(const key_t& key) const { return lookup_map_.count(key) > 0; }

  size_t Size() const { return lookup_map_.size(); }

  size_t Capacity() const { return capacity_; }

  void Clear() {
    lru_list_.clear();
    lookup_map_.clear();
  }

 private:
  std::list<key_value_pair_t> lru_list_;
  std::unordered_map<key_t, iterator> lookup_map_;
  size_t capacity_;
};

#endif  // SRC_LRU_CACHE_INL_H_