#include <iostream>
#include <list>
#include <string>
using namespace std;

struct MemPCB
{
	int pageId;                    //process_id
	bool accessed;					//whether is accessed
	bool modified;					//whether is modified
};

void DisplayMemPagestate(list<MemPCB>* tmpList, list<MemPCB>::iterator tmpIt);
void UpdateAccess(list<MemPCB>* tmpList, int* tmpAccessArray, int access_count);
void UpdateModify(list<MemPCB>* tmpList, int* tmpAccessArray, int modify_count);
void PageInvoke(list<MemPCB>* tmpList, int tmpPageID, list<MemPCB>::iterator& tmpIt);

void main()
{
	int pageArrayCount = 0;
	int mempageArrayPtrCount = 0;	
	int cirTmp = 0;
	char cmdStr[20];
	int ginvokePosition= 0;			//global variable indicate the position of the page will be invoked

	int* pageArrayPtr = NULL;	
	list<MemPCB> memPageList;
	list<MemPCB>::iterator it = NULL;     //global iteratoe points to the current position of the mem pages

    /*****************************************input the page sequence******************************************/
	cout << "please input the counts of the pages: ";
	cin >> pageArrayCount;
	pageArrayPtr = new int[pageArrayCount];
	cout << "please input the page invoking sequence: \n";
	for(cirTmp = 0; cirTmp < pageArrayCount; cirTmp ++)
	{
		cin >> pageArrayPtr[cirTmp];
	}
	
	/*************************************input the page sequence end******************************************/
	cout << "please input the page count the mem can hold:";
	cin >> mempageArrayPtrCount;
	
	/*********************************************************************************************************/
	cout << "PageArray:  { ";
	for(cirTmp = 0; cirTmp < pageArrayCount; cirTmp++)
	{
		 cout << pageArrayPtr[cirTmp] << " ";
	}
	cout << "}\n";
	/**********************************************************************************************************/
	
	for(cirTmp = 0; cirTmp < mempageArrayPtrCount; cirTmp++)
	{
		MemPCB tmpPageInfo = {pageArrayPtr[ginvokePosition],0,0};
		ginvokePosition++;		
		memPageList.push_back(tmpPageInfo);
	}
	DisplayMemPagestate(&memPageList,memPageList.begin());

	cout << "pageID:-----pageAccess------pageModify\n";
	while(1)
	{
		cout << "input the commands:\n";
		cin >> cmdStr;

		if(strcmp(cmdStr,"access") == 0)
		{
			int access_count = 0;
			cout << "input the access num:\n";
			cin >> access_count;
			int* access_array = new int[access_count];
			cout << "modified pages:\n";
			for(int cirTmp = 0; cirTmp < access_count; cirTmp++)
			{
				cin >> access_array[cirTmp];
			}
			UpdateAccess(&memPageList,access_array,access_count);
			DisplayMemPagestate(&memPageList,memPageList.begin());
		}

		if(strcmp(cmdStr,"modify") == 0)
		{
			int modify_count = 0;
			cout << "input the modified num:\n";
			cin >> modify_count;
			int* modify_array = new int[modify_count];
			cout << "modified pages:\n";
			for(int cirTmp = 0; cirTmp < modify_count; cirTmp++)
			{
				cin >> modify_array[cirTmp];
			}
			UpdateModify(&memPageList,modify_array,modify_count);
			DisplayMemPagestate(&memPageList,memPageList.begin());
		}
		
		if(strcmp(cmdStr,"step") == 0)
		{
			PageInvoke(&memPageList,pageArrayPtr[ginvokePosition],it);
			DisplayMemPagestate(&memPageList,it);
			ginvokePosition++;
			if(ginvokePosition == pageArrayCount)
			{
				cout << "approach the ending! \n";
				break;
			}
		}
	}
	
}

/****************************************show the mem state******************************************************/
void DisplayMemPagestate(list<MemPCB>* tmpList, list<MemPCB>::iterator tmpIt)
{
	list<MemPCB>::iterator it = tmpIt;

	cout << "the current iterator points to " 
		<< (*it).pageId << " "
		<< (*it).accessed<< " "
		<< (*it).modified<<endl;

	cout << "the mem page state is: \n";
	for(int cirTmp = 0; cirTmp <= tmpList->size(); cirTmp++)
	{
		if(it != tmpList->end())
		{		
			cout << (*it).pageId << " "
				<< (*it).accessed << " "
				<< (*it).modified << endl;
			it++;
		}
		else
			it++;
	}
}

/******************************************************************************************************************/
void UpdateAccess(list<MemPCB>* tmpList, int* tmpAccessArray, int access_count)
{
	while(access_count--)
	{
		for(list<MemPCB>::iterator it = tmpList->begin(); it != tmpList->end(); it++)
		{
			if((*it).pageId == tmpAccessArray[access_count])
				(*it).accessed = !(*it).accessed;
		}
	}
}

void UpdateModify(list<MemPCB>* tmpList, int* tmpAccessArray, int modify_count)
{
	while(modify_count--)
	{
		for(list<MemPCB>::iterator it = tmpList->begin(); it != tmpList->end(); it++)
		{
			if((*it).pageId == tmpAccessArray[modify_count])
				(*it).modified = !(*it).modified;
		}
	}
}

/*******************************************************************************************************************/
void PageInvoke(list<MemPCB>* tmpList, int tmpPageID, list<MemPCB>::iterator& tmpIt)
{
	//meaning of the parameter: the pointer to the mem page list, the invoking pageID, the current circle pointer
	int cirTmp = 0;

	if(tmpIt == NULL)
		tmpIt = tmpList->begin();
	while(1)
	{
		for(cirTmp = 0; cirTmp <= tmpList->size(); cirTmp++)
		{
			if(tmpIt != tmpList->end())
			{
				if( !((*tmpIt).accessed) && !((*tmpIt).modified))
				{
					(*tmpIt).pageId = tmpPageID;          //do not change the access pos at the first time
					return;				
				}
				tmpIt++;
			}
			else
				tmpIt++;
		}

		// when the using the above method failed it runs next
		for(cirTmp = 0; cirTmp <= tmpList->size(); cirTmp++)
		{
			if(tmpIt != tmpList->end())
			{
				if((*tmpIt).accessed == 0)
					(*tmpIt).pageId = tmpPageID;
				(*tmpIt).accessed = false;
				return;
			}
			else
				tmpIt++;
		}

		//when failed runs next
		
		list<MemPCB>::iterator it = tmpList->begin();
		for(cirTmp = 0; cirTmp <= tmpList->size(); cirTmp++)
		{
			if(it != tmpList->end())
				(*it).accessed = false;
			else
				it++;
		}
		PageInvoke(tmpList,tmpPageID, tmpIt);
	}
}