#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;

  }

  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_