#include <stdio.h>
#include <memory.h>
#include <fcntl.h>
#include <windows.h>
#include <sys/stat.h>
#include <string.h>
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>

#define MAX				10

#define DIR_RANDOM		1
#define DIR_REVERSE		2 // To test for worst case...

class CSort {
private:
	int Array[ MAX ] ;		// Fixed array of MAX size
	int Count ;				// Count of items... Should always be MAX

public:
	CSort( void ) ;

	void FillArray( int direction ) ;
	void DisplayArray( char *caption ) ;
	void Swap( int pos1, int pos2 ) ;
	void Test( void ) ;

	void BubbleSort( void ) ;
	void SelectionSort( void )  ;
	void QuickSort( int first, int last ) ;
} ;

//Enable this define if you want to see 'prove' that the list is sorted...
//#define SHOW_LIST

__int64 clockCycles ;

/**
 * Preformance function, counting clock cycles...
 */

__forceinline void CountCycles()
{
	__asm {
		RDTSC
		mov DWORD PTR[ clockCycles + 4 ], edx
		mov DWORD PTR[ clockCycles ], eax
	}
}

struct PreformanceCounter {
  __int64 StartCount ;
  __int64 StopCount ;

  PreformanceCounter( void ) {
	  StartCount = 0 ;
	  StopCount = 0 ;
  } ;
  void Start( void ) {
	  CountCycles();
	  StartCount = clockCycles ;
  } ;
  void Stop( void ) {
	  CountCycles();
	  StopCount = clockCycles ;
  } ;
  int Result( void ) {
	  unsigned int diff = (unsigned int)( StopCount - StartCount ) ;
	  printf( "Results: %d cycles\n", diff/100 ) ;	    
	  return diff/100 ;
  } ;

} ;

/**
 * Default constructor
 */

CSort::CSort( void ) 
{  
  Count = 0 ;	 
  memset( Array, 0, MAX ) ;
}

/**
 * Fill array with preset values
 */

void CSort::FillArray( int direction ) 
{ 
	switch ( direction ) {
	case DIR_RANDOM:
		Array[ 0 ] = 6 ;
		Array[ 1 ] = 2 ;
		Array[ 2 ] = 3 ;
		Array[ 3 ] = 1 ;
		Array[ 4 ] = 7 ;
		Array[ 5 ] = 9 ;
		Array[ 6 ] = 5 ;
		Array[ 7 ] = 4 ;
		Array[ 8 ] = 8 ;
		Array[ 9 ] = 0 ;
		break;
	default:
		for ( int i = 0 ; i < MAX ; i++ )
			Array[ i ] = MAX - i ;
		break;
    } ;
	Count = MAX ;
}

/**
 * Swap two items
 */

void CSort::Swap( int pos1, int pos2 )
{
  int temp = Array[ pos1 ] ;
  Array[ pos1 ] = Array[ pos2 ] ;
  Array[ pos2 ] = temp ;
}

/**
 * Display array on-screen
 */

void CSort::DisplayArray( char *caption ) 
{ 
	if ( Count == 0 ) {
  	  printf( "No items in list...\n" ) ;
	  return ;   
	}
	printf( "%s\n", caption ) ;
#ifdef SHOW_LIST
  for ( int i = 0 ; i < MAX ; i++ )
	  printf( "%d:  %d\n", i, Array[i] ) ;
  printf( "\n" ) ;
#endif
}

/**
 * Test array if in correct order
 */

void CSort::Test( void ) 
{
  for ( int i = 1 ; i < MAX ; i++ )
    if ( Array[ i ] < Array[ i - 1 ] )
	  printf( "FAILED...\n" ) ;
printf( "PASSED...\n" ) ;
}

/***********************************************
 * Main program                                *
 ***********************************************/

int main(int argc, char* argv[])
{
	SetPriorityClass( GetCurrentProcess( ), HIGH_PRIORITY_CLASS ) ;
	//SetThreadPriorirty( GetCurrentThread( ), THREAD_PRIORITY_HIGHEST ) ;

	PreformanceCounter count ;
	CSort sort ; 

	/* Bubble sort */
	sort.FillArray( DIR_RANDOM ) ;
	sort.DisplayArray( "Random Filled" ) ;
	count.Start( ) ;
	sort.BubbleSort( ) ;
	count.Stop( ) ;
    sort.DisplayArray( "Bubble sorted" ) ;
	sort.Test( ) ;
	count.Result( ) ;

	sort.FillArray( DIR_REVERSE ) ;
	sort.DisplayArray( "Reverse order Filled" ) ;
    count.Start( ) ;
	sort.BubbleSort( ) ;
	count.Stop( ) ;
	sort.DisplayArray( "Bubble sorted" ) ;
	sort.Test( ) ;
	count.Result( ) ;

	/* Selection sort */
	sort.FillArray( DIR_RANDOM ) ;
	sort.DisplayArray( "Random Filled" ) ;
	count.Start( ) ;
	sort.SelectionSort( ) ;
	count.Stop( ) ;
    sort.DisplayArray( "Selection sorted" ) ;
	sort.Test( ) ;
	count.Result( ) ;

	sort.FillArray( DIR_REVERSE ) ;
	sort.DisplayArray( "Reverse order Filled" ) ;
	count.Start( ) ;
	sort.SelectionSort( ) ;
	count.Stop( ) ;
	sort.DisplayArray( "Selection sorted" ) ;
	sort.Test( ) ;
	count.Result( ) ;

	/* Quick sort */
	sort.FillArray( DIR_RANDOM ) ;
	sort.DisplayArray( "Random Filled" ) ;
	count.Start( ) ;
	sort.QuickSort(0, MAX-1) ;
	count.Stop( ) ;
	sort.DisplayArray( "Quick sorted" ) ;
	sort.Test( ) ;
	count.Result( ) ;

	sort.FillArray( DIR_REVERSE ) ;
	sort.DisplayArray( "Reverse order Filled" ) ;
	count.Start( ) ;
	sort.QuickSort(0, MAX-1) ;
	count.Stop( ) ;
	sort.DisplayArray( "Quick sorted" ) ;
	sort.Test( ) ;
	count.Result( ) ;

	SetPriorityClass( GetCurrentProcess( ), NORMAL_PRIORITY_CLASS ) ;
	//SetThreadPriorirty( GetCurrentThread( ), THREAD_PRIORITY_NORMAL ) ;

	getch() ;
	return 0;
}