#ifndef CMSC202_SORT_METRICS_H
#define CMSC202_SORT_METRICS_H

//  SortMetrics.H - Header file for CMSC 202 Project 2
//
//  Original Author:  	J. Kukla
//  Last Modified by:	J. Kukla	

#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <iostream.h>

//  Included for compatibility with the sort routines
//  from the class notes
typedef int data;
typedef int index;

class SortMetrics 
{
public:
	//  Default constructor and destructor for
	//  class SortMetrics
	SortMetrics();
	~SortMetrics();

	//  All times are in milliseconds
	time_t getWallTime() const;
	clock_t getCPUTime() const;

	long getNumCompares() const;
	long getNumSwaps() const;

	//  Returns the last value "n" that was used in 
	//  any sort run by this instance
	long   getNumElements() const;

	//  This routine calls the sort specified by which_sort (see below)
	//  on the array A with indices [low,high].
	//  An example call to sort would look like:
	//
	// 	mySorter.sort(A, 0, n-1, SortMetrics::QUICKSORT);
	//
	void sort(data A[], index low, index high, int which_sort);

	//  These are "class constants" to identify which_sort in the 
	//  sort() method.  To use one of these values, you say:
	//
	//     			SortMetrics::MERGESORT
	//
	//  and may use this identifier in any program that uses 
	//  the SortMetrics class.
	//
	//  These must be defined in SortMetrics.C by saying:
	//
	//  const int SortMetrics::MERGESORT = 0;
	//  const int SortMetrics::QUICKSORT = 1;
	//  const int SortMetrics::SELECTIONSORT = 2;
	//
	//  These are defined in the .C file (rather than in this file) to 
	//  avoid linker warnings about multiple definition of these 
	//  constants.
	const static int MERGESORT;
	const static int QUICKSORT;
	const static int SELECTIONSORT;

private:
	long    _ncompares, _nswaps, _last_n;
	time_t  _time;
	clock_t _clocks;
	
	//  Temporary "global" array for mergesort
	data * temp;

	//  The routines below come straight from the web page notes
	//  and are implemented here as private class methods.  This 
	//  forces users to use the public interface to the class to 
	//  call the sorting routines.
	void mergesort(data A[], index low, index high);
	void merge(data A[], index low1, index high1, index low2, index high2);

	void quicksort(data A[], index low, index high);
	index partition(data A[], index low, index high);

	void selectionsort(data A[], index low, index high);

};

ostream & operator << (ostream &, const SortMetrics & s);


#endif