//  Count memory faults, as a function of memory allocation.
//  Use the LRU page depth vectors as input.
//  sdb   August 2003

//  First tabulate faults as a function of memory allocation (in pages)
//  Then form a cumulative sum.
//  The nth sum is the number of faults with memory allocation of n pages.

#include <iostream.h>
#include <fstream.h>
#include <assert.h>
  
    const int MaxP = 512;	// Merge sort requires 2n/p
				// Pheap sort requires more than n/p, less than 2n/p
				// All others require n/p.
    long faults[MaxP];		// faults[i] stores faults for mem alloc i

void init(int);

int main(int argc, char * argv[])
// arg is algorithm name
{   ifstream in;
    ofstream out;
    char name[100];
    char str[100];
    int n,p,i,depth,max;
    for (n=8; n<2000; n = 2*n)
    	for (p=4; p<=n/2; p = 2*p)
          {	cout << "n=" << n << " p=" << p << endl;
		strcpy (name,  "output/");
		strcpy (str, argv[1]);
		strcat (name, str);		// e.g.   "output/merge"
		sprintf (str,"%d",n);
		strcat (name,str);		// concat n to name
		sprintf (str,"%d",p);
		strcat (name,str);		// concat p to name
		in.open (name);
    		if (!in) cout << "input file failed to open" << endl;
		   else cout << "opened " << name << " for input" << endl;
		
    		max = n/p;
		// merge sort and pheap sort require extra space.
		if (strcmp(argv[1],"merge")==0 || strcmp(argv[1],"pheap")==0) 
			max = 2*max;
    
    		init (max);			// initialize the array faults

    		while (in>>depth)
  		   {  assert (depth < max);
			if (depth>0) faults[depth]++;
     		   }
    		in.close();
    
    		for (i=max-2; i>0; i--)
     		    faults[i] = faults[i] + faults[i+1];

    		strcat (name, "FV");
		out.open (name);
		if (!out) cout << "output file failed to open" << endl;
		  else cout << "opened " << name << " for output " << endl;
    		for (i=1; i<max; i++)
			out << faults[i] << endl;
    		out.close();
	   }
}

// initialize the array faults
void init(int max)
{  int i;
   for (i=0; i<max; i++)
	faults[i] = 0;
}