// 
// gensort.cpp
//
// Test program for generic array sorting module in sort.hpp
//
// Computer Science S-111, Harvard University
//

#include <iostream.h>
#include <iomanip.h>
#include "sort.hpp"
#include "../util/s111unx.hpp"
#include "../util/getinput.hpp"


//
// A class to represent a data item for sorting that just consists
// of a single integer key.  We benefit from using a class instead of
// a built-in int because we are able to overload the =, <, and >=
// operators so as to count the number of comparisons and data moves.
//
class sortInt {
public:
    int key;
    const sortInt& operator =(const sortInt& a);
    friend bool operator <(sortInt a, sortInt b);
    friend bool operator >=(sortInt a, sortInt b);
    friend ostream& operator <<(ostream& s, const sortInt& a);
};


// Constants
const int maxarraysize = 4096;
const int numberperline = 24;

// Global variables
bool print_it;       // should we print the array?
int compares;        // total number of comparisons
int moves;           // total number of data moves


//
// Assignment operator - counts the number of times that it is called
//
const sortInt&
sortInt::operator =(const sortInt& a)
{
    moves++;
    key = a.key;
    return *this;
}


//
// Comparison operators - also count the number of times either one of
// them is called
//
bool
operator <(sortInt a, sortInt b)
{
    compares++;
    return (a.key < b.key);
}

bool
operator >=(sortInt a, sortInt b)
{
    compares++;
    return (a.key >= b.key);
}


//
// Output operator
//
ostream&
operator <<(ostream& s, const sortInt& a)
{
    s << a.key;
    return s;
}


//
// fill_random - randomly initialize the keys of an array
// of sortInt objects
//
void fill_random(sortInt arr[], int num_items)
{
    // Reseed random-number generator.
    randomize();

    for (int i = 1; i <= num_items; i++) {
	if (print_it)
	    arr[i].key = random(100);
	else
	    arr[i].key = random(32767);
    }
}

//
// print_array - print the contents of the specified array, from
// arr[1] to arr[num_items]
//
void
print_array(sortInt arr[], int num_items)
{
    for (int i = 1; i <= num_items; i++)
	cout << setw(3) << arr[i];
    cout << "\n";
}

//
// print_stats - print the number of comparisons and data moves, and
// optionally the sorted array
//
void
print_stats(sortInt arr[], int num_items)
{
    if (print_it) {
	cout << "\nFINAL:";
	print_array(arr, num_items);
    }

    cout << setw(10) << compares << " comparisons" 
	 << setw(10) << moves << " data moves\n\n";
}

	
int
main()
{
    sortInt asave[maxarraysize], a[maxarraysize];
    int num_items;
    
    //
    // Get various parameters from the user.
    //
    do {
	num_items = ReadInteger("How many items in the array (max 4096)?");
    } while (num_items >= maxarraysize);

    if (num_items <= 24)
	print_it = GetBoolean("Show the sorted array?", NO);
    else
	print_it = NO;
    cout << endl;
    
    
    //
    // Generate the unsorted array and optionally print it.
    //
    fill_random(asave, num_items);
    if (print_it) {
	cout << "START:";
	print_array(asave, num_items);
	cout << endl;
    }

    
    //
    // Try each of the various algorithms, starting each time 
    // with a fresh copy of the initial array.
    //
    compares = moves = 0;
    memcpy(a, asave, (num_items+1) * sizeof(sortInt));
    cout << "STRAIGHT INSERTION\t";
    InsertSort(a, num_items);
    print_stats(a, num_items);

    compares = moves = 0;
    memcpy(a, asave, (num_items+1) * sizeof(sortInt));
    cout << "BINARY INSERTION\t";
    BinInsertSort(a, num_items);
    print_stats(a, num_items);

    compares = moves = 0;
    memcpy(a, asave, (num_items+1) * sizeof(sortInt));
    cout << "SELECTION SORT\t\t";
    SelectSort(a, num_items);
    print_stats(a, num_items);
	
    compares = moves = 0;
    memcpy(a, asave, (num_items+1) * sizeof(sortInt));
    cout << "BUBBLE SORT\t\t";
    BubbleSort(a, num_items);
    print_stats(a, num_items);
    
    compares = moves = 0;
    memcpy(a, asave, (num_items+1) * sizeof(sortInt));
    cout << "SHELL SORT\t\t";
    ShellSort(a, num_items);
    print_stats(a, num_items);

    compares = moves = 0;
    memcpy(a, asave, (num_items+1) * sizeof(sortInt));
    cout << "HEAPSORT\t\t";
    HeapSort(a, num_items);
    print_stats(a, num_items);

    compares = moves = 0;
    memcpy(a, asave, (num_items+1) * sizeof(sortInt));
    cout << "QUICKSORT\t\t";
    QuickSort(a, num_items);
    print_stats(a, num_items);
}
