/**
 * Lfu class
 */
class Lfu {
	java.util.Vector stack;
	int[] distanceString;
/**
 * Lfu constructor
 */
public Lfu() {
	super();
	stack = new java.util.Vector();
	distanceString = new int[65];

	// 64 different string space
	// distanceString[64] for page that have 
	// not been referenced, distance infinity
	for (int i=0; i<65; i++) {
		distanceString[i] = 0;
	} 
}
/**
 * To check is the page already in stack
 * yes: return the position
 * no: return -1
 */
public int isInStack(int referencePage) {
	Page page;
	for (int j = 0; j < stack.size(); j++) {
		page = (Page) stack.elementAt(j);
		if (referencePage == page.getId()) {
			// reference page is j position away from
			// the top of the stack 
			distanceString[j] ++;
			return j;
		}
	}
	return -1;
}
/**
 * For testing: to print out the contents in stack
 */
public void printStack() {
	Page page;
	for (int j=0; j<stack.size(); j++) {
		page = (Page) stack.elementAt(j);
		System.out.print("|" + page.getId() + ", " + page.getCount() + "|");
	}
	System.out.println("");
}
/**
 * Lfu run: return number of page fault
 */
public double[] run(int[] pageReference) {
	int i = 0;
	int j;
	double[] pageFault = new double[3];
	boolean bRc;
	int[] memorySize = {6, 10, 16};
	Page page;
	
	while (pageReference[i] != -1) {
		if ((j = isInStack(pageReference[i])) >= 0){
			page = (Page) stack.elementAt(j);
			// increment the page count
			int count = page.getCount();
			count++;
			page.setCount(count);
			// remove the page and push it on top of the stack
			stack.removeElementAt(j);
			stack.insertElementAt(page, 0);
			// sort the rest of the stack
			sortStack(1, j);
		}
		else { 
			// add the page on the top of the stack
			page = new Page(pageReference[i], 1);
			stack.insertElementAt(page, 0);
			// sort the rest of the stack
			sortStack(1, stack.size()-1);
			// page have not been referenced, distance infinity
			distanceString[64]++;
		}
		//printStack();
		i++;
	}
	// calculate page fault
	for (j=0; j<memorySize.length; j++) {
		for (i=memorySize[j]; i<65; i++) {
			pageFault[j] = pageFault[j] + distanceString[i];
		}
	}
	return pageFault;
}
/**
 * Sort the Stack according the reference count of 
 * the page from the largest to smallest except the
 * page on the top of stack
 */
public void sortStack(int start, int end) {
	Page page;
	Page tmp;
	boolean bEnd;
		
	// stack only has two element, no need to sort
	if (stack.size() <= 2) {
		return;
	} 

	for (int i=start; i<end; i++) {
		bEnd = true;
		page = (Page) stack.elementAt(i);
		stack.removeElementAt(i);
		for (int j=i; j<end; j++) {
			tmp = (Page) stack.elementAt(j);
	    if (page.getCount() >= tmp.getCount()) {
	   		stack.insertElementAt(page, j);
	   		bEnd = false;
	   		break; 
		  }
		}
		if (bEnd) {
			stack.insertElementAt(page, end);
		} 
	} 
}
}