#include <stdlib.h>
#include
using namespace std;

#define QLEN 3
#define LINE_LEN 8

/*
The recentQueue class is a queue which sorts the entry based on recently processed order. The structure of each entry is as follow:
typedef struct {
int key, line;
} keyPtr;
Here, the key is provided by users and line is a pointer to a free line.

Suppose a queue has capacity equal to QLEN and the number of stored keys is num. The sorted keys should be updated after processing to maintaining the recently processed order:
C1: the keys will be stored in a continuous region, from location from 0 to num-1.
C2: the most recently processed keys are placed at sorted[num-1] and sorted[0] is the least recently processed key.

Furthermore, there are also QLEN lines of data and each sorted key has a line pointer associated with it. The recentQueue class does not model the data access of the line data. It only maintains a bool array lineUsed[QLEN] to keep track which line is already assigned to a key.

The processing types are push and remove, as explained in detailed below:

• push(int newKey): store the new key the end of the queue:
  • if num<QLEN, num++ and search for a free line to assign to the new key
  • if num==QLEN, num remains to be be QLEN and the sorted[0] is flushed. The line associated with sorted[0] is reused for the new key. Need to shift some keys to maintain condition C1 and C2
• remove(int ptr):
  remove a key at ptr, i.e. sorted[ptr]. Since the key at the removed location is invalid, shift some keys to maintain the condition C1 and C2 and free the line associated with the removed key

*/

typedef struct {
int key, line;
} keyPtr;

class recentQueue_emtpty {
int num, i;
keyPtr sorted[QLEN];
bool lineUsed[QLEN];

public:
recentQueue() {
}

bool remove(int ptr) {

}
void push(int newKey) {

}

void debug(void) {		
	cout << "num=" << num << endl; 
	cout << "key=" ; 
	for(int i=0; i<num; i++) cout << sorted[i].key << " " ; 		
	cout << endl; 
	cout << "line=" ; 
	for(int i=0; i<num; i++) cout << sorted[i].line << " " ; 		
	cout << endl; 
	
}

}

int main(void) {
recentQueue rq;
rq.push(4);
rq.push(3);
rq.push(2);
rq.debug();
rq.push(1);
rq.debug();
//rq.remove(1); //remove 3
//rq.exchange(1, 5);
rq.remove(1);
rq.push(5);
rq.debug();
cout << "search 5 =" << rq.search(5) << endl;
cout << "search 10 =" << rq.search(10) << endl;

}