#pragma once

#include "../include/paging.hpp"

#include <algorithm>
#include <limits>
#include <ranges>
#include <unordered_map>

namespace paging {

int32_t paging::optimal_replacer::run(const std::vector<int32_t> &pages) {
  int32_t faults = 0;
  std::vector<int32_t> frames;
  frames.reserve(static_cast<size_t>(this->_frames));
  for (size_t i : std::views::iota(size_t(0), pages.size())) {
    int32_t p = pages[i];
    if (std::find(frames.begin(), frames.end(), p) != frames.end())
      continue;
    ++faults;
    if (static_cast<int32_t>(frames.size()) < this->_frames) {
      frames.push_back(p);
    } else {
      int32_t idx_to_replace = 0;
      size_t farthest = 0;
      for (int32_t j : std::views::iota(0, this->_frames)) {
        size_t k = i + 1;
        while (k < pages.size() && pages[k] != frames[j])
          ++k;
        size_t dist =
            (k < pages.size() ? k : std::numeric_limits<size_t>::max());
        if (dist > farthest) {
          farthest = dist;
          idx_to_replace = j;
        }
      }
      frames[idx_to_replace] = p;
    }
  }
  return faults;
}

int32_t paging::clock_replacer::run(const std::vector<int32_t> &pages) {
  int32_t faults = 0;
  struct entry {
    int32_t page;
    bool ref;
  };
  std::vector<entry> frames;
  frames.reserve(static_cast<size_t>(this->_frames));
  int32_t hand = 0;

  for (int32_t p : pages) {
    bool hit = false;
    for (auto &e : frames) {
      if (e.page == p) {
        e.ref = true;
        hit = true;
        break;
      }
    }
    if (hit)
      continue;
    ++faults;
    if (static_cast<int32_t>(frames.size()) < this->_frames) {
      frames.push_back({p, true});
    } else {
      while (true) {
        if (!frames[hand].ref) {
          frames[hand] = {p, true};
          hand = (hand + 1) % this->_frames;
          break;
        }
        frames[hand].ref = false;
        hand = (hand + 1) % this->_frames;
      }
    }
  }
  return faults;
}

int32_t paging::lru_replacer::run(const std::vector<int32_t> &pages) {
  int32_t faults = 0;
  std::vector<int32_t> frames;
  std::unordered_map<int32_t, int32_t> last_used;
  frames.reserve(static_cast<size_t>(this->_frames));

  for (int32_t i : std::views::iota(0, static_cast<int32_t>(pages.size()))) {
    int32_t p = pages[i];
    if (std::find(frames.begin(), frames.end(), p) != frames.end()) {
      last_used[p] = i;
      continue;
    }
    ++faults;
    if (static_cast<int32_t>(frames.size()) < this->_frames) {
      frames.push_back(p);
    } else {
      int32_t lru_page = frames[0];
      int32_t min_idx = last_used[lru_page];
      for (int32_t q : frames) {
        if (last_used[q] < min_idx) {
          min_idx = last_used[q];
          lru_page = q;
        }
      }
      auto it = std::find(frames.begin(), frames.end(), lru_page);
      if (it != frames.end())
        *it = p;
    }
    last_used[p] = i;
  }
  return faults;
}

} // namespace paging
