//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_replacer.h
//
// Identification: src/include/buffer/lru_replacer.h
//
// Copyright (c) 2015-2021, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#pragma once

#include <list>
#include <mutex>  // NOLINT
#include <vector>
#include <unordered_map>

#include "buffer/replacer.h"
#include "common/config.h"

namespace bustub {

/**
 * LRUReplacer implements the Least Recently Used replacement policy.
 */
class LRUReplacer : public Replacer {
 public:
  /**
   * Create a new LRUReplacer.
   * @param num_pages the maximum number of pages the LRUReplacer will be required to store
   */
  explicit LRUReplacer(size_t num_pages);

  /**
   * Destroys the LRUReplacer.
   */
  ~LRUReplacer() override;

  bool Victim(frame_id_t *frame_id) override;

  void Pin(frame_id_t frame_id) override;

  void Unpin(frame_id_t frame_id) override;

  size_t Size() override;

 private:
  // TODO(student): implement me!
  const int capacity_;
  std::list<frame_id_t> lruList_;
  std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> lruMap_;
  std::mutex latch_;

  frame_id_t VictimFrame();
};

}  // namespace bustub

//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_replacer.cpp
//
// Identification: src/buffer/lru_replacer.cpp
//
// Copyright (c) 2015-2019, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_replacer.h"

namespace bustub {

LRUReplacer::LRUReplacer(size_t num_pages) : capacity_(num_pages) {}

LRUReplacer::~LRUReplacer() = default;

bool LRUReplacer::Victim(frame_id_t *frame_id) {
  std::lock_guard<std::mutex> guard(latch_);
  if (lruMap_.empty()) {
    *frame_id = -1;
    return false;
  }
  *frame_id = VictimFrame();
  return true;
}

void LRUReplacer::Pin(frame_id_t frame_id) {
  std::lock_guard<std::mutex> guard(latch_);
  if (lruMap_.find(frame_id) == lruMap_.end()) {
    return;
  }
  lruList_.remove(lruMap_.find(frame_id)->second);
  lruMap_.erase(frame_id);
  return;
}

void LRUReplacer::Unpin(frame_id_t frame_id) {
  std::lock_guard<std::mutex> guard(latch_);
  if (lruMap_.find(frame_id) != lruMap_.end()) {
    return;
  }
  while (lruMap_.size() >= capacity_) {
    VictimFrame();
  }
  lruList_.push_front(frame_id);
  lruMap_[frame_id] = lruList_.begin();
}

size_t LRUReplacer::Size() {
  std::lock_guard<std::mutex> guard(latch_);
  return lruMap_.size();
}

frame_id_t LRUReplacer::VictimFrame() {
  frame_id_t victimFrame = lruList_.back();
  lruList_.pop_back();
  lruMap_.erase(victimFrame);
  return victimFrame;
}

}  // namespace bustub