//  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"

void pheap (int);
void init();		// worst case input
extern const int MAX= 10000;
extern MArray a(MAX);
ofstream out ("pheap.out", ios::out);

void main ()
{ int n;
  for (n=8; n<5000; n *= 2)
     {  a.setSize (n);
        for (p=4; p<n; p *= 2)		// page size = 8,16,32,...
          {  
	     init ();			// initialize the array
	     a.setFault(0);		// reset mem fault counter
	     a.setRefs(0);
	     a.setPrev(-1);		// first ref causes a fault
   	     pheap  (n);  		// call sort algorithm
	     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;
	     out << n << " "
		 << p << " "
		 << a.getFault() << " "
		 << ((double) a.getFault()) / a.getRefs() * 100. << endl;
	  }
     }
a.dump();
}