#include <iostream>
#include <time.h>	/* for clock()  and CLOCKS_PER_SEC */

#include "OrderSort.h"
#include "Utilities/Random.h"
#include "Utilities/IOSmacros.h"

void fill_random(double *A, int len)
{
    int i;
    for(i=0; i<len; i++) A[i] = drandom();
}


// check that an index array correctly sorts array A
bool is_sorted(const int *index, const double *A, int length)
{
    assert(index !=NULL);
    for (int i=length-1; i>0; i--)
    {    if (A[index[i-1]]> A[index[i]]) return 0;
    }
    return 1;
}



const int MAX_SIZE=10000000;
const int NUM_TESTS=17;
int test_length[NUM_TESTS] =
    {1, 2, 3, 4, 5, 
    6, 13, 27, 55, 111, 
    223, 447, 895, 1790, 3580,
    7161, 14323
    };


int
main(void)
{
    double * master_array = new double[MAX_SIZE];
    
    int *index = OrderSort(master_array, 0);
    assert(index==NULL);
    
    for (int test=0; test<NUM_TESTS; test++)
    {	fill_random(master_array, MAX_SIZE);
        int len = test_length[test];
	int num_tries = MAX_SIZE/len;
	assert(num_tries>0);
	clock_t before = clock();
	for(int j=0; j<num_tries; j++)
	{   int *index = OrderSort(master_array+j*len, len);
	    assert(is_sorted(index,master_array+j*len, len));
	    delete [] index;
	}
	clock_t after = clock();
	double total_time = (after-before)/ static_cast<double>(CLOCKS_PER_SEC);
	cout << "OrderSort worked for length " << len 
		<< " and took " 
		<< setprecision(3) << IOSFIXED
		<< total_time/num_tries * 1.E6
		<< " microseconds per call."
		<< "\n";
    }
    
    delete [] master_array;
    return 0;
}


// CHANGE LOG:
// 10 April 2004 Kevin Karplus
//	Empty test program replaced by a genuine test
//	including approximate timing.