//+----------------------------------------------------------------------+
//|								    DAPsim								 |
//| Dean Morrison												11/30/06 |
//| University of Florida												 |
//| Department of Electrical and Computer Engineering					 |
//+----------------------------------------------------------------------+
//| Description: DAPsim is a trace-driven simulator developed in C++ for |
//| the purpose of designing, testing, and evaluating demand prepaging 	 |
//| policies.  It currently implements my proposed concept of Dynamically|
//| Adaptive Prepaging, but may be modified to evaluate many other 		 |
//| policies.															 |
//|																		 |
//| Reuse Policy: Use of this software for personal or instructional	 |
//| purposes is granted without fee provided that the source bears a	 |
//| clear and complete citation.										 |
//+----------------------------------------------------------------------+


#include "main.h"
#include "UsedPageQ.h"

int debugModeUsed = DEBUG_MODE;

UsedPageQ::UsedPageQ()
{
	size = 0;
	maxSize = DEFAULT_MAX_MEM_SIZE;
	ResidentQ.setMaxSize(maxSize);
	NonResidentQ.setMaxSize(DEFAULT_MAX_MEM_SIZE);
	clearHistogram();
}

void UsedPageQ::setMaxSize(int newMaxSize)
{
	int currentSize = getSize();
	maxSize = newMaxSize;
	ResidentQ.setMaxSize(maxSize);
	//if (debugModeUsed == DEBUG_4) cout << "Used Queue Max Size set to: " << ResidentQ.getMaxSize() << endl;

	// If New Max Size is less than old, remove extra pages
	int elementNum;
	int numOfPagesToRemove = 0;
	if (newMaxSize < currentSize) {
		numOfPagesToRemove = currentSize - newMaxSize;
		for (elementNum = 0; elementNum < numOfPagesToRemove; ++elementNum) {
			NonResidentQ.pushMRU((ResidentQ.popLRU()).getPageNumber());
		}
	}
}

void UsedPageQ::setMinSize(int newMinSize)
{
	minSize = newMinSize;
}

int UsedPageQ::getSize(void)
{
	size = ResidentQ.getSize();
	return size;
}

int UsedPageQ::getMaxSize(void)
{
	return maxSize;
}

int UsedPageQ::getMinSize(void)
{
	return minSize;
}

bool UsedPageQ::referencePage(unsigned long int pageNumber)
{
	bool pageHit = false;	// Default = Page Fault

	int elementNum = 0;
	LRU_pageQ_entry entryReferenced;
	list<LRU_pageQ_entry>::iterator position;
    for (position = ResidentQ.getQueue()->begin(); position != ResidentQ.getQueue()->end(); ++position) {
        if ((*position).getPageNumber() == pageNumber) {
			pageHit = true;
			incHistogram(elementNum);
			break;
		}
		elementNum++;
    }
	// If pageNumber not in Resident Queue, mark as Page Fault
	if (!pageHit) {
		// Check Non-Resident Queue for page
		elementNum = maxSize;
		for (position = NonResidentQ.getQueue()->begin(); position != NonResidentQ.getQueue()->end(); ++position) {
		    if ((*position).getPageNumber() == pageNumber) {
				incHistogram(elementNum);
				removeNonResidentPage((*position).getPageNumber());
				break;
			}
			elementNum++;
		}

		return pageHit;
	}
	
	entryReferenced = *position;
	ResidentQ.getQueue()->erase(position);
	ResidentQ.getQueue()->push_front(entryReferenced);

	return pageHit;
}

void UsedPageQ::addPage(unsigned long int newPage)
{
	// Check if Eviction is necessary
	if ((ResidentQ.getSize() + 1) > maxSize) {	
		//Evict LRU Page
		evictPage();
	}
	ResidentQ.pushMRU(newPage);
	// Update size
	size = ResidentQ.getSize();
}

void UsedPageQ::evictPage(void)
{
	LRU_pageQ_entry evictedPage = ResidentQ.popLRU();
	size = ResidentQ.getSize();
	NonResidentQ.pushMRU(evictedPage.getPageNumber());
}

void UsedPageQ::removeNonResidentPage(unsigned long int pageNumber)
{
	list<LRU_pageQ_entry>::iterator position;
    for (position = NonResidentQ.getQueue()->begin(); position != NonResidentQ.getQueue()->end(); ++position) {
        if ((*position).getPageNumber() == pageNumber) {
			// Remove Page
			NonResidentQ.getQueue()->erase(position);
			return;
		}
    }
}

void UsedPageQ::printQueueEntries(void)
{
	cout << "Used Page Queue:\n";
	cout << "Resident Queue:\n";
	cout << "\tPage #\tHist Value\n";
	cout << "\t------\t----------\n";
	
	int elementNum = 0;
	list<LRU_pageQ_entry>::iterator position;
    for (position = ResidentQ.getQueue()->begin(); position != ResidentQ.getQueue()->end(); ++position) {
		if (elementNum == 0) cout << "    MRU\t";
		else if (elementNum == (ResidentQ.getSize()-1)) cout << "    LRU\t";
		else cout << "\t";
		cout << (*position).getPageNumber() << "\t";
		//cout << (*position).getHistValue() << "\n";
		cout << histogram[elementNum] << "\n";
		elementNum++;
	}

	//elementNum = ResidentQ.getSize() + 1;
	elementNum = maxSize;
	cout << "Non-Resident Queue:\n";
	cout << "\tPage #\tHist Value\n";
	cout << "\t------\t----------\n";
	cout << "    MRU\t";
	for (position = NonResidentQ.getQueue()->begin(); position != NonResidentQ.getQueue()->end(); ++position) {
		if (elementNum == (NonResidentQ.getSize()-1)) cout << "    LRU\t";
		else cout << "\t";
		cout << (*position).getPageNumber() << "\t";
		//cout << (*position).getHistValue() << "\n";
		cout << histogram[elementNum] << "\n";
		elementNum++;
	}
}

void UsedPageQ::clearHistogram(void)
{
	int index;
	//int maxIndex = ResidentQ.getMaxSize() + NonResidentQ.getMaxSize();
	int maxIndex = DEFAULT_MAX_MEM_SIZE;
	for (index = 0; index < maxIndex; index++) {
		histogram[index] = 0;
	}
}

void UsedPageQ::incHistogram(int index)
{
	if (index >= DEFAULT_MAX_MEM_SIZE) {
		if (debugModeUsed == DEBUG_2) cout << "ERROR: Histogram index out of bounds!\n";
		return;
	}
	histogram[index] += 1;
}

bool UsedPageQ::pagePresentInResidentQ(unsigned long int pageNumber)
{
	bool pagePresent = false;
	list<LRU_pageQ_entry>::iterator position;
    for (position = ResidentQ.getQueue()->begin(); position != ResidentQ.getQueue()->end(); ++position) {
        if ((*position).getPageNumber() == pageNumber) {
			pagePresent = true;
			break;
		}
    }
	
	return pagePresent;
}

bool UsedPageQ::pagePresentInNonResidentQ(unsigned long int pageNumber)
{
	bool pagePresent = false;
	list<LRU_pageQ_entry>::iterator position;
    for (position = NonResidentQ.getQueue()->begin(); position != NonResidentQ.getQueue()->end(); ++position) {
        if ((*position).getPageNumber() == pageNumber) {
			pagePresent = true;
			break;
		}
    }
	
	return pagePresent;
}

long int UsedPageQ::getMRUPageNumber(void)
{
	return (ResidentQ.getMRU_entry()).getPageNumber();
}

int UsedPageQ::findHistogramIndex(unsigned long int pageNumber)
{
	int index = DEFAULT_MAX_MEM_SIZE - 1;
	list<LRU_pageQ_entry>::iterator position;
	int elementNum = ResidentQ.getMaxSize();
	for (position = NonResidentQ.getQueue()->begin(); position != NonResidentQ.getQueue()->end(); ++position) {
		if ((*position).getPageNumber() == pageNumber) {
			index = elementNum;
			return index;
		}
		elementNum++;
	}
	if (debugModeUsed == DEBUG_2) cout << "ERROR: Histogram Index not found!\n";
	return index;
}

void UsedPageQ::decayHistogram(double decayValue)
{
	int index;
	int maxIndex = DEFAULT_MAX_MEM_SIZE;
	for (index = 0; index < maxIndex; index++) {
		histogram[index] = (double)histogram[index] * decayValue;
	}
}

void UsedPageQ::printHistogram(void)
{
	cout << "Used Page Queue Histogram:\n";
	int index;
	int maxIndex = ResidentQ.getMaxSize() + NonResidentQ.getSize();
	for (index = 0; index < maxIndex; index++) {
		cout << histogram[index] << endl;
	}
}

int UsedPageQ::getHistogramEntry(int index)
{
	if (index >= DEFAULT_MAX_MEM_SIZE) {
		if (debugModeUsed >= DEBUG_2) cout << "ERROR: Histogram index out of bounds!\n";
		return -1;
	}
	return histogram[index];
}