//Memory.h
//Stephen Bassoli
//CSE 258
#include <afx.h>
#include <ctype.h>
#include <fstream.h>
#include "Token.h"

struct hole
{
	int index;
	int endIndex;
	int size;
};

struct program
{
	int index;
	int endIndex;
	int size;
	int jobID;
	int stepsLeft;
};

class Memory
{
public:
	short mem[1024];
	hole* Holes;
	program* Programs;
	program* queuedProgs;
	int numHoles;
	int currPrograms;
	int numProgsLeft;
	int stepsDone;
	ofstream outfile;


	Memory();
	Memory(CString* progs, int n, ofstream& out);
	hole& getHoleAt(int n);
	void sortHoles();
	bool insertAt(program Prog, int at);
	void deleteHole(hole n);
	void createHole(int Index, int Size);
	void removeProg(int job);
	program& getProg(int job);

	hole& getFirstHole(int minSize);
	hole& getWorstHole(int minSize);
	hole& getBestHole(int minSize);
	hole& getNextHole(int minSize, int from);
	bool firstFit(program Prog);
	bool worstFit(program Prog);
	bool bestFit(program Prog);
	bool nextFit(program Prog, int& from);
	bool loadFirstFit();
	bool loadWorstFit();
	bool loadBestFit();
	bool loadNextFit();

	program dequeueJob();
	void enqueueJob(program Prog);
	bool clockEdge();

	void printProgs();
	void printHoles();

	void fixSizes();
};

//Default Constructor
Memory::Memory()
{
	for (int i = 0 ; i < 1024 ; i++)
		mem[i] = 0;
	Holes = new hole[200];
	Programs = new program[200];
	queuedProgs = new program[200];
	Holes[0].index = 0;
	Holes[0].size = 1024;
	Holes[0].endIndex = 1023;
	numHoles = 1;
	currPrograms = 0;
	numProgsLeft = 0;
	stepsDone = 0;
}

//Constructor that is actually used
Memory::Memory(CString* progs, int n, ofstream& out)
{
	CString job, size, steps;
	outfile = out;
	for (int i = 0 ; i < 1024 ; i++)
		mem[i] = 0;
	Holes = new hole[200];
	Programs = new program[200];
	queuedProgs = new program[200];
	Holes[0].index = 0;
	Holes[0].size = 1024;
	Holes[0].endIndex = 1023;
	numHoles = 1;
	currPrograms = 0;
	numProgsLeft = n;
	stepsDone = 0;
	queuedProgs = new program[n];
	for (i = 0; i < n ; i++)
	{
		CToken tok(progs[i]);
		tok.SetToken(" ");
		tok.GetNextToken();
		job = tok.GetNextToken();
		size = tok.GetNextToken();
		steps = tok.GetNextToken();
		queuedProgs[i].index = -1;
		queuedProgs[i].endIndex = -1;
		queuedProgs[i].jobID = atoi(job);
		size.Remove('k');
		queuedProgs[i].size = atoi(size);
		queuedProgs[i].stepsLeft = atoi(steps);
	}
}

//inserts the program at a certain location in memory
bool Memory::insertAt(program Prog, int at)
{
	bool holeOnTop,holeOnBottom;
	for (int i = at; i < (Prog.size + at); i++)
	{
		if (mem[i] != 0)
			return false;
	}
	Prog.index = at;
	Prog.endIndex = at + Prog.size - 1;
	Programs[currPrograms++] = Prog;
	for (i = at; i < (Prog.size + at); i++)
		mem[i] = Prog.jobID;
	if (at == 0)
		holeOnTop = false;
	else
	{
		if (mem[at - 1] == 0)
			holeOnTop = true;
		else
			holeOnTop = false;
	}
	if (at == 1023)
		holeOnBottom = false;
	else
	{
		if (mem[Prog.endIndex + 1] == 0)
			holeOnBottom = true;
		else
			holeOnBottom = false;
	}

	if ((!holeOnTop)&&(!holeOnBottom))
		deleteHole(getHoleAt(Prog.index));
	else if ((!holeOnTop)&&(holeOnBottom))
	{
		getHoleAt(Prog.endIndex + 1).index = Prog.endIndex + 1;
		getHoleAt(Prog.endIndex + 1).size = getHoleAt(Prog.endIndex + 1).endIndex - getHoleAt(Prog.endIndex + 1).index + 1;
	}
	else if ((holeOnTop)&&(!holeOnBottom))
	{
		getHoleAt(at - 1).endIndex = at - 1;
		getHoleAt(at - 1).size = at - getHoleAt(at - 1).index + 1;
	}
	else if (holeOnTop&&holeOnBottom)
	{
		int hole1Start, hole1End, hole2Start, hole2End;
		hole1Start = getHoleAt(at).index;
		hole1End = at - 1;
		hole2Start = Prog.endIndex + 1;
		hole2End = getHoleAt(at).endIndex;
		deleteHole(getHoleAt(at));
		createHole(hole1Start,(hole1End - hole1Start + 1));
		createHole(hole2Start,(hole2End - hole2Start + 1));
	}
	outfile << "Job " << Prog.jobID << " added to memory" << endl;
	sortHoles();
	return true;
}

//returns a program as specified by the job number
program& Memory::getProg(int job)
{
	static program error;
	error.jobID = -1;
	error.size = -1;
	error.endIndex = -1;
	error.index = -1;
	error.stepsLeft = -1;
	for (int i = 0 ; i < currPrograms; i++)
	{	
		if (Programs[i].jobID == job)
			return Programs[i];
	}
	return error;
}

//removes a program from memory as specified by the job number
void Memory::removeProg(int job)
{
	int pos = 0;
	bool holeOnTop, holeOnBottom;
	for (int i = 0 ; i < currPrograms; i++)
	{	
		if (Programs[i].jobID == job)
		{
			pos = i;
			break;
		}
	}
	if (Programs[pos].index == 0)
		holeOnTop = false;
	else
	{
		if (mem[Programs[pos].index - 1] == 0)
			holeOnTop = true;
		else 
			holeOnTop = false;
	}
	if (Programs[pos].endIndex == 1023)
		holeOnBottom = false;
	else
	{
		if (mem[Programs[pos].endIndex + 1] == 0)
			holeOnBottom = true;
		else
			holeOnBottom = false;
	}

	if ((!holeOnTop)&&(!holeOnBottom))
	{
		createHole(Programs[pos].index, Programs[pos].size);	
	}
	else if ((!holeOnTop)&&(holeOnBottom)) //possible problems here
	{
		getHoleAt(Programs[pos].endIndex + 1).index = Programs[pos].index;
		getHoleAt(Programs[pos].endIndex + 1).size += Programs[pos].size;
	}
	else if ((holeOnTop)&&(!holeOnBottom))
	{
		getHoleAt(Programs[pos].index - 1).endIndex = Programs[pos].endIndex;
		getHoleAt(Programs[pos].index - 1).size += Programs[pos].size;
	}
	else if (holeOnTop&&holeOnBottom)
	{
		int holeStart, holeEnd, addSize;
		holeStart = getHoleAt(Programs[pos].index - 1).index;
		holeEnd = getHoleAt(Programs[pos].endIndex + 1).endIndex;
		addSize = getHoleAt(Programs[pos].endIndex + 1).size;
		deleteHole(getHoleAt(Programs[pos].endIndex + 1));
		getHoleAt(Programs[pos].index - 1).endIndex = holeEnd;
		getHoleAt(Programs[pos].index - 1).size += Programs[pos].size + addSize; 
	}
	for (i = Programs[pos].index ; i <= Programs[pos].endIndex ; i++)
		mem[i] = 0;
	for (i = pos ; i < (currPrograms - 1); i++)		
		Programs[i] = Programs[i+1];
	currPrograms--;
	outfile << "Job " << job << " removed from memory" << endl;
	sortHoles();
}


//returns a hole at a specified index
hole& Memory::getHoleAt(int n)
{
	static hole error;
	error.index = -1;
	error.size  = -1;
	error.endIndex = -1;
	for (int i = 0 ; i < numHoles ; i++)
	{
		if ((n >= Holes[i].index)&&(n <= (Holes[i].index + Holes[i].size - 1)))
			return Holes[i];
	}
	return error;
}

//Uses selection sort to sort the holes in the Holes[] array by their starting index
void Memory::sortHoles()
{
	int n = numHoles;
    int i, j;
	hole v;
    for(i=1;i<n;i++) 
	{
        v = Holes[i];
        j = i;
        while ( Holes[j-1].index > v.index ) 
		{
			Holes[j] = Holes[j-1]; 
			j = j-1;
			if ( j <= 0 ) 
				break;
        }
        Holes[j] = v;
	}
}

//Deletes a hole from memory
void Memory::deleteHole(hole n)
{
	int pos;
	for (int i = 0 ; i < numHoles; i++)
	{
		if (n.index == Holes[i].index)
			pos = i;
	}
	for (i = pos ; i < (numHoles - 1); i++)
		Holes[i] = Holes[i+1];
	numHoles--;
}

//Creates a hole in memory as specified by the starting index and size
void Memory::createHole(int Index, int Size)
{
	Holes[numHoles].index = Index;
	Holes[numHoles].size = Size;
	Holes[numHoles].endIndex = Index + Size - 1;
	numHoles++;
	sortHoles();
}

//returns the first hole of at least minSize
hole& Memory::getFirstHole(int minSize)
{
	static hole error;
	error.index = -1;
	error.endIndex = -1;
	error.size = -1;
	for (int i = 0 ; i < numHoles ; i++)
	{
		if (Holes[i].size >= minSize)
			return Holes[i];
	}
	return error;
}

//returns the largest hole of at least minSize
hole& Memory::getWorstHole(int minSize)
{
	static hole error;
	error.index = -1;
	error.endIndex = -1;
	error.size = -1;
	int largest = 0;
	int pos = -1;
	for (int i = 0 ; i < numHoles ; i++)
	{
		if (Holes[i].size > largest)
		{
			largest = Holes[i].size;
			pos = i;
		}
	}
	if (largest >= minSize)
		return Holes[pos];
	else
		return error;
}

//returns the hole just large enough to fit minSize
hole& Memory::getBestHole(int minSize)
{
	static hole error;
	error.index = -1;
	error.endIndex = -1;
	error.size = -1;
	int pos = -1;
	int difference = 1000000;
	for (int i = 0 ; i < numHoles ; i++)
	{
		if (((Holes[i].size - minSize) < difference)&&((Holes[i].size - minSize) >= 0))
		{
			difference = (Holes[i].size - minSize);
			pos = i;
		}
	}
	if (difference == 1000000)
		return error;
	else
		return Holes[pos];
}

//returns the first hole of at least minSize starting at index 'from'
hole& Memory::getNextHole(int minSize, int from)
{
	static hole error;
	error.index = -1;
	error.endIndex = -1;
	error.size = -1;
	int curr = getHoleAt(from).index;
	for (int i = 0 ; i < numHoles ; i++)
	{
		if ((Holes[i].size >= minSize)&&(Holes[i].index >= curr))
			return Holes[i];
		else
		{
			if (Holes[i].index > from)
				curr = Holes[i].endIndex + 1;
		}
	}
	curr = 0;
	for (i = 0 ; i < numHoles ; i++)
	{
		if ((Holes[i].size >= minSize)&&(curr < from))
			return Holes[i];
		else
			curr = Holes[i].endIndex + 1;		
	}
	return error;
}

//inserts Prog into memory using first-fit
bool Memory::firstFit(program Prog)
{
	if (getFirstHole(Prog.size).size == -1)
		return false;
	else
	{
		insertAt(Prog,getFirstHole(Prog.size).index);
		return true;
	}
}

//inserts Prog into memory using worst-fit
bool Memory::worstFit(program Prog)
{
	if (getWorstHole(Prog.size).size == -1)
		return false;
	else
	{
		insertAt(Prog,getWorstHole(Prog.size).index);
		return true;
	}	
}

//inserts Prog into memory using best-fit
bool Memory::bestFit(program Prog)
{
	if (getBestHole(Prog.size).size == -1)
		return false;
	else
	{
		insertAt(Prog,getBestHole(Prog.size).index);
		return true;
	}	
}

//inserts Prog into memory using next-fit
bool Memory::nextFit(program Prog, int& from)
{
	int temp;
	if (getNextHole(Prog.size,from).size == -1)
		return false;
	else
	{
		temp = getNextHole(Prog.size,from).endIndex;
		insertAt(Prog,getNextHole(Prog.size,from).index);
		from = temp;
		return true;
	}	
}

//returns the next program on the queue
program Memory::dequeueJob()
{
	program error;
	error.size = -1;
	error.index = -1;
	error.endIndex = -1;
	error.stepsLeft = -1;
	error.jobID = -1;
	if (numProgsLeft > 0)
	{
		program temp;
		temp = queuedProgs[0];
		for (int i = 0 ; i < (numProgsLeft - 1); i++)
			queuedProgs[i] = queuedProgs[i+1];
		numProgsLeft--;
		return temp;
	}
	else
		return error;
}

//puts a program on the queue
void Memory::enqueueJob(program Prog)
{
	//cout << Prog.size << endl;
	if (Prog.size == -1)
		return;
	for (int i = numProgsLeft ; i >= 0; i--)
		queuedProgs[i + 1] = queuedProgs[i];
	numProgsLeft++;	
	queuedProgs[0] = Prog;
}

//Decrements the steps of each program in memory and eleminates jobs that have 0 steps left
bool Memory::clockEdge()
{
	bool update = false;
	for (int i = 0; i < currPrograms ; i++)
	{
		Programs[i].stepsLeft--;
		if (Programs[i].stepsLeft == 0)
		{
			update = true;
			removeProg(Programs[i].jobID);
			i--;
		}
	}
	stepsDone++;
	return update;
}

//loads as many jobs as it can from the queue into memory using first-fit
bool Memory::loadFirstFit()
{
	if (numProgsLeft > 0)
	{
		program pending;
		int i = 0;
		pending = dequeueJob();
		if (pending.size == -1)
			return false;
		while (firstFit(pending))
		{
			pending = dequeueJob();
			if (pending.size == -1)
				return false;
			i++;
		}
		enqueueJob(pending);
		
		if (i == 0)
		{
			return false;
		}
		else
			return true;
	}
	else 
		return false;
}

//loads as many jobs as it can from the queue into memory using worst-fit
bool Memory::loadWorstFit()
{
	if (numProgsLeft > 0)
	{
		program pending;
		int i = 0;
		pending = dequeueJob();
		if (pending.size == -1)
			return false;
		while (worstFit(pending))
		{
			pending = dequeueJob();
			if (pending.size == -1)
				return false;
			i++;
		}
		enqueueJob(pending);
		
		if (i == 0)
		{
			return false;
		}
		else
			return true;
	}
	else 
		return false;
}

//loads as many jobs as it can from the queue into memory using best-fit
bool Memory::loadBestFit()
{
	if (numProgsLeft > 0)
	{
		program pending;
		int i = 0;
		pending = dequeueJob();
		if (pending.size == -1)
			return false;
		while (bestFit(pending))
		{
			pending = dequeueJob();
			if (pending.size == -1)
				return false;
			i++;
		}
		enqueueJob(pending);
		
		if (i == 0)
		{
			return false;
		}
		else
			return true;
	}
	else 
		return false;
}

//loads as many jobs as it can from the queue into memory using next-fit
bool Memory::loadNextFit()
{
	int start = 0;
	if (numProgsLeft > 0)
	{
		program pending;
		int i = 0;
		pending = dequeueJob();
		if (pending.size == -1)
			return false;
		while (nextFit(pending,start))
		{
			pending = dequeueJob();
			if (pending.size == -1)
				return false;
			i++;
		}
		enqueueJob(pending);
		
		if (i == 0)
		{
			return false;
		}
		else
			return true;
	}
	else 
		return false;
}

//outputs all programs in memory to the outfile
void Memory::printProgs()
{
	for (int i = 0 ; i < currPrograms ; i++)
		outfile << "Job " << Programs[i].jobID << " from " << Programs[i].index << " to " << Programs[i].endIndex << " with " << Programs[i].stepsLeft << " steps remaining (" << Programs[i].size << "k)" << endl;
}

//outputs all holes in memory to the outfile
void Memory::printHoles()
{
	for (int i = 0 ; i < numHoles ; i++)
		outfile << "Hole at " << Holes[i].index << " to " << Holes[i].endIndex << " (" << Holes[i].size << "k)" << endl;
}

//fixes the sizes of all programs and holes in memory
void Memory::fixSizes()
{
	for (int i = 0 ; i < numHoles ; i++)
	{
		while ((mem[Holes[i].index - 1] == 0)&&(Holes[i].index != 0))
			Holes[i].index -= 1;
		while ((mem[Holes[i].endIndex + 1] == 0)&&(Holes[i].endIndex !=1023))
			Holes[i].endIndex += 1;
		Holes[i].size = Holes[i].endIndex - Holes[i].index  + 1;
	}
	for (i = 0 ; i < currPrograms ; i++)
		Programs[i].size = Programs[i].endIndex - Programs[i].index + 1;
}