//  Test a sort algorithm for data locality
//  by counting memory faults for various page sizes.
//  Use Monitored Array class (MArray) to tabulate faults.

int p;
#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include "array.h"
#include "string.h"

void pheap(int);
void init();		// worst case input
extern const int MAX= 10000;
extern MArray a(MAX);

int main ()
{ 
 
     char str[5];
     char name[50];
     int n;

     for (n=8; n<2000; n *= 2)
     {  a.setSize (n);
        for (p=4; p<n; p *= 2)		// page size = 8,16,32,...
          {  init ();			// initialize array
	     a.reset();
             a.setFault(0);		// reset mem fault counter
	     a.setRefs(0);
	     strcpy (name,"output/pheap");		// sorting algorithm name
	     sprintf (str,"%d",n);	// concat n
	     strcat (name,str);
	     sprintf (str,"%d",p);	// concat p
	     strcat (name,str);
	     a.setName (name);		// filename, e.g.  pheap328 (n=32, p=8)
   	     pheap (n);  		// call sort algorithm

//	Counting faults
	     cout << "pheap sort, n = " ;
	     cout.width(4);
	     cout << n << " page size = " ;
	     cout.width(4);
	     cout << p << ",  faults = " ; 
	     cout.width(8) ;
	     cout << a.getFault() << "  pct = " ;
	     cout.setf (ios::fixed);
	     cout << setprecision(3)
		  << ((double) a.getFault()) / a.getRefs() * 100. << endl;
	     a.closeFile();
/*
	     out << n << " "
		 << p << " "
		 << a.getFault() << " "
		 << ((double) a.getFault()) / a.getRefs() * 100. << endl;
*/

	  }

// check to see that the numbers were sorted correctly
   a.dump();
     }

   return 0;
}