//data stracture project : memory pages
//seyed mohammad hoseini 871412306
///////////////////////////////////////

#include <iostream>
#include <time.h>
#include <string>
using namespace std;

template <class x> class Queue {
public:
	Queue					(int m);
	~Queue					();
	void	Enqueue			(x e);
	void	Dequeue			(x& e);
	int		QueueIsFull		();
	int		QueueIsEmpty	();
	void	QueueRetreive	(x& e);
private:
	int maxsize;
	x *p;
	int rear;
	int front;
	int n;
};

int main()
{
	cout << "data stracture project : memory pages\nseyed mohammad hoseini 871412306\n_____________________________________\n\n";
	string again;
	do{
		int p, n;
		cout << "n : ";
		cin >> n;
		cout << "p : ";
		cin >> p;
		Queue<int> q1(n), q2(n);
		int *PageSequence = new int[3*p];
		
		srand((unsigned) time(NULL));
		cout << "Page sequence : ";
		for (int i = 0; i < 3 * p; i++){
			PageSequence[i] = (int)(((float)rand()/(RAND_MAX+1)) * p) + 1;
			cout << PageSequence[i] << " ";
		}

		int fault = 0, ready = 0, e, nn = 0;
		for (int i = 0; i < 3 * p; i++)
		{
			cout << "\n\nPages available in main memory : ";
			ready = 0;
			while (!q1.QueueIsEmpty()){
				q1.Dequeue(e);
				if (e == PageSequence[i])
					ready = 1;
				q2.Enqueue(e);
				cout << e << " ";
			}
			cout << "\nrequested page : " << PageSequence[i];
			while(!q2.QueueIsEmpty()){
				q2.Dequeue(e);
				q1.Enqueue(e);
			}
			if (ready == 0){
				if (nn == n){
					q1.Dequeue(e);
					q1.Enqueue(PageSequence[i]);
					fault++;
				}
				else{
					q1.Enqueue(PageSequence[i]);
					nn++;
				}
			}
		}
		cout << "\nPages available in main memory (at end) : ";
		while (!q1.QueueIsEmpty()){
			q1.Dequeue(e);
			cout << e << " ";
		}

		cout << "\n\nPage fault : " << fault;
		cout << "\n\ntry again? (y/n) ";
		cin >> again;
		cout << "\n\n";
	}while(again == "y");

	return 0;
}

template <class x> Queue<x>::Queue(int m) {
	maxsize = m;
	p = new x[maxsize];
	rear = -1;
	front = -1;
	n = 0;
}

template <class x> Queue<x>::~Queue() {
	delete [] p;
	rear = front = -1;
}

template <class x> int Queue<x>::QueueIsFull() {
	if ((rear == maxsize - 1) && (front == -1))
		return 1;
	if ((rear == front) && (n == 1))
		return 1;
	return 0;
}

template <class x> int Queue<x>::QueueIsEmpty() {
	if ((rear == front) && (n == 0))
		return 1;
	return 0;
}

template <class x> void Queue<x>::Enqueue(x e) {
	if(!QueueIsFull()){
		rear = (rear + 1) % maxsize;
		p[rear] = e;
		n = 1;
	}
}

template <class x> void Queue<x>::Dequeue(x& e) {
	if(!QueueIsEmpty()){
		front = (front + 1) % maxsize;
		e = p[front];
		n = 0;
	}
}

template <class x> void Queue<x>::QueueRetreive(x& e){
	if(!QueueIsEmpty()){
		int k = front;
		front = (front + 1) % maxsize;
		e = p[front];
		front = k;
	}
}