#!/usr/bin/python

import argparse

parser = argparse.ArgumentParser(description='Virtual Memory Simulator')
parser.add_argument('-n', required=True, type=int, help='Number of Frames')
parser.add_argument('-a', type=str, required=True,
                          choices=['opt', 'fifo', 'aging'],
                          help='Page Replacement Algorithm')
parser.add_argument('-r', type=int, required=False, help='Refresh Amount')
parser.add_argument('filename', help='Trace file', type=str)

args = parser.parse_args()
if args.a == 'aging' and not args.r:
	print("Refresh [-r] must be specified with aging argument.")
	exit(1)

# 4KB Page Size means 12 bits will determine (2^20 = 4KB)
PAGE_SIZE_BIT_LENGTH = 12

class PageReplacementAlgorithmInterface:
	def find_frame(self, frames):
		raise NotImplementedError()

	def on_memory_access(self, frames, frame_no):
		raise NotImplementedError()

class OptimalReplacementAlgorithm(PageReplacementAlgorithmInterface):
	trace_map = {}
	def __init__(self, traces):
		for i, trace in reversed(list(enumerate(traces))):
			page_no = trace.page_no
			if page_no not in self.trace_map:
				self.trace_map[page_no] = []
			self.trace_map[page_no].append(i)

	def find_frame(self, frames):
		max_mem_access_time = -1
		maximum_index = -1
		page_no = None
		for index, page in enumerate(frames):
			current_frame_accesses = self.trace_map[page.page_no]
			if len(current_frame_accesses) == 0:
				current_frame_accesses.append(float('inf'))

			current_mem_access_time = current_frame_accesses[-1]
			if current_mem_access_time == max_mem_access_time:
				if frames[maximum_index].dirty_bit and not page.dirty_bit:
					# If there is a tie, choose this one if it is not dirty
					max_mem_access_time = -1

			if current_mem_access_time > max_mem_access_time:
				max_mem_access_time = current_mem_access_time
				maximum_index = index
				page_no = page.page_no

		return maximum_index

	def on_memory_access(self, frames, frame_no):
		page_no = frames[frame_no].page_no
		current_frames_accesses = self.trace_map[page_no]
		if len(current_frames_accesses) > 0:
			self.trace_map[page_no].pop()



class FifoReplacementAlgorithm(PageReplacementAlgorithmInterface):
	queue = []

	def find_frame(self, frames):
		frame = self.queue.pop(0)
		return frame

	def on_memory_access(self, frames, frame_no):
		if frame_no not in self.queue:
			self.queue.append(frame_no)

class PageTableEntry:
	def __init__(self, page_no, dirty_bit, refresh_bit):
		self.page_no = page_no
		self.dirty_bit = False
		self.refresh_bit = False

class PageTable:
	page_frame_table = {}
	total_memory_accesses = 0
	total_page_faults = 0
	total_writes_to_disk = 0
	new_frames_counter = 0

	def __init__(self, frames, replacement_algorithm):
		self.frames = [None] * frames
		self.replacement_algorithm = replacement_algorithm

	def find_frame(self, page_no):
		self.total_memory_accesses += 1
		if page_no in self.page_frame_table:
			# Hit
			return self.page_frame_table[page_no]

		# Page Fault
		self.total_page_faults += 1
		if self.new_frames_counter < len(self.frames):
			# Page Fault, No Eviction
			frame = self.new_frames_counter
			self.frames[self.new_frames_counter] = PageTableEntry(page_no, False, False)
			self.new_frames_counter += 1
			self.page_frame_table[page_no] = frame
			return frame

		# Page Fault, Call Page Replacement Algorithm
		frame_no = self.replacement_algorithm.find_frame(self.frames)
		del self.page_frame_table[self.frames[frame_no].page_no]

		if self.frames[frame_no].dirty_bit:
			# Evict Dirty So Need to Write to Disk
			self.total_writes_to_disk += 1

		# Evict Clean
		self.frames[frame_no] = PageTableEntry(page_no, False, False)
		self.page_frame_table[page_no] = frame_no
		return frame_no


	def store(self, page_no):
		# Find Page and Set Dirty Bit to True
		frame_no = self.find_frame(page_no)
		self.frames[frame_no].dirty_bit = True
		self.replacement_algorithm.on_memory_access(self.frames, frame_no)

	def load(self, page_no):
		frame_no = self.find_frame(page_no)
		self.replacement_algorithm.on_memory_access(self.frames, frame_no)


class MemoryAccess:
	def __init__(self, trace):
		parts = trace.strip().split()
		self.op = parts[0].upper()
		logical_address = int(parts[1], 16)
		self.page_no = logical_address >> PAGE_SIZE_BIT_LENGTH
		# Get bottom 12 bits ( & 0xFFF)
		self.offset = logical_address & ((1<<PAGE_SIZE_BIT_LENGTH)-1)
		self.cycles = int(parts[2])

	def __str__(self):
		return "{} {} {} {}".format(self.op, self.page_no, self.offset, self.cycles)


traces = []
with open(args.filename) as file:
	for line in file:
		traces.append(MemoryAccess(line))



algs = {
	"fifo": FifoReplacementAlgorithm(),
	"opt": OptimalReplacementAlgorithm(traces)
}

page_replacement_algorithm = algs[args.a]
page_table = PageTable(args.n, page_replacement_algorithm)

for mem_access in traces:
	if mem_access.op == "S":
		page_table.store(mem_access.page_no)
	else:
		page_table.load(mem_access.page_no)

def print_statistics(page_table):
	print("Algorithm: {}".format(args.a.upper()))
	print("Number of frames:       {}".format(args.n))
	print("Total memory accesses:  {}".format(page_table.total_memory_accesses))
	print("Total page faults:      {}".format(page_table.total_page_faults))
	print("Total writes to disk:   {}".format(page_table.total_writes_to_disk))

print_statistics(page_table)