#include <stdio.h>

// pick a page replacement strategy by un-commenting the relevant define
// if you use other than OPT - you must define the header fault.h
//     fault.h must define: int PageTable :: fault(unsigned int vpage)

#define OPT
//#define FIFO
//#define LRU
//#define CHANCE2
//#define NRU

#define NFRAMES 4
#define MAXNREFS 50
#define MAXNPAGES 100	// virtual memory max

typedef struct {         // data type for table entry dependent on alg
unsigned int 	Ref,
		Mod,
#ifdef FIFO
		LoadT,
#endif
#ifdef LRU
		RefT,
#endif
		Page
		;
} PageTableEntry;

void clearEntry (PageTableEntry & p) {
p.Ref=0;
p.Mod=0;
#ifdef FIFO
  p.LoadT=0;
#endif
#ifdef LRU
  p.RefT=0;
#endif
p.Page=MAXNPAGES+1;
}

void printEntry (PageTableEntry p) {
printf("%1d,", p.Ref);
printf("%1d,", p.Mod);
#ifdef FIFO
printf("%1d,", p.LoadT);
#endif
#ifdef LRU
printf("%1d,", p.RefT);
#endif
printf("%1d ", p.Page);
}

/// globals to control simulation
unsigned int Clock=0;
int Write=0;  // global i.e. 'CPU' write signal

int refString[MAXNREFS][2];
#define REF 0
#define WRITE 1
int nRefs=0;


//-- page table class and functions
class PageTable {
public:
   PageTable();
   unsigned int lookUp(unsigned int vpage);
   void setMod(int n) { table[n].Mod=1; }
   void setRef(int n) { table[n].Ref=1; }
#ifdef LRU
   void setRefT(int n) { table[n].RefT=Clock; }
#endif
   void printTable();
private:
   int fault(unsigned int vpage);
   void loadPage(unsigned int frame, unsigned int vpage);
   void writePage(unsigned int frame);
   int nFramesUsed;
   PageTableEntry * table;
};

#define IsUnusedEntry(i) table[i].Page>=MAXNPAGES

void PageTable :: printTable() {
int i, j;

printf("\n Clock:%2u Table: ", Clock);
for (i=0; i<NFRAMES; i++){
    printf(" %1u:", i);
    if (IsUnusedEntry(i)) printf(" -  ");
       else printf("%u  ", table[i].Page);
    }
}

PageTable :: PageTable() {
int i=0;

table=new PageTableEntry[NFRAMES];
for (i=0;i<NFRAMES;i++) clearEntry(table[i]);
nFramesUsed=0;
for (i=0;i<NFRAMES; i++) 
    table[i].Page=MAXNPAGES;	// initialize to impossible value
}

void PageTable :: loadPage(unsigned int frame, unsigned int vpage) {
//printf(" loadPage %u to %u  ", vpage, frame);
clearEntry(table[frame]);
#ifdef FIFO
table[frame].LoadT=Clock;
#endif
table[frame].Mod=0;
table[frame].Ref=0;
table[frame].Page=vpage;
}

void PageTable :: writePage(unsigned int frame) {
printf(" write %u from %u to memory ... ", table[frame].Page, frame);
}

//#define isUnused(i)  table[i].Page>=MAXNPAGES

unsigned int PageTable :: lookUp(unsigned int vpage) {
unsigned int frame;
//printf("  lookup %u", vpage);

for (frame=0; frame<=NFRAMES; frame++)
  if (table[frame].Page==vpage)
     return frame; 
return fault(vpage);
}

#ifdef OPT
int PageTable :: fault(unsigned int vpage) {   // select a replace ment page & do it
unsigned int farthestOff, farthestOffDistance, distanceOff;
int time, frame;

printf("   Fault(OPT):%u  ", vpage);
farthestOff=0; 
farthestOffDistance=0;

for (frame=0; frame<NFRAMES; frame++) {
    if (IsUnusedEntry(frame)) {farthestOff=frame; break; }
    for (time=Clock+1;
         time<nRefs && table[frame].Page!=(int)refString[time][REF];
         time++);
    distanceOff=time-Clock;
    if (distanceOff>farthestOffDistance) {
      farthestOffDistance = distanceOff;
      farthestOff=frame;
      }
   }
//printf("Farthest off is page: %u  ", farthestOff);
if (table[farthestOff].Mod) writePage(farthestOff);
loadPage(farthestOff,vpage);
return farthestOff;
}
#else
#include "fault.h"
#endif



// ref strings are sequences of digits - if a digit has a w in front
//    eg: w5     it is a write, otherwise it is a read

void read_refString(){
char inpt[20];
int count=0;

printf("Enter referencestring (# for read ref, w# for write ref,EOF to halt)nRefs=0\n");
while (scanf("%s", inpt)==1&& count++<MAXNREFS) {
  if (*inpt=='w' || *inpt=='W') {
     refString[nRefs][WRITE]=1;
     sscanf(inpt+1,"%u",&refString[nRefs][REF]);
     }
  else {
     refString[nRefs][WRITE]=0;
     sscanf(inpt,"%u",&refString[nRefs][REF]);
     }
  nRefs++;
  }
}

main(){
// simulate CPU processing a reference string
PageTable pt;
int time;
unsigned int vpage, frame;

read_refString();
pt.printTable();

for (Clock=0; Clock<nRefs; Clock++) {
  Write= refString[Clock][WRITE];
  vpage= refString[Clock][REF];
  printf("\n\nvpage: %5u ", vpage);
  frame=pt.lookUp(vpage);
  #ifdef LRU
  pt.setRef(frame);
  #endif
  printf(" frame: %5d", frame);
  if (Write) pt.setMod(frame);
  pt.printTable();
  }

return 0;
}