/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 */

#ifndef TEST_H
#define TEST_H

#include <stddef.h>
#include <limits.h>
#include <stream.h>
#include <stdlib.h>

#include "data_generator.H"
#include "insertion_sort.H"
#include "merge_sort.H"
#include "discrete_sort.H"
#include "quick_sort.H"
#include "heapsort.H"
#include "heapsort.other.H"
#include "partition_merge_sort.H"
#include "fun_sort.H"
#include "clock.H"
#include "video_vector.H"
#include "statistical_element.H"

#define NUMBER_OF_SORTS 20

char* titleString[] = {
    "inplace mergesort",
    "adaptive mergesort",
    "quicksort",
    "heapsort",
    "traditional heapsort",
    "insertion sort",
    "selection sort",
    "shellsort",
    "bubble sort",
    "inplace partition mergesort",
    "adaptive partition mergesort",
    "inplace discrete sort",
    "adaptive stable discrete sort",
    "inplace stable discrete sort",
    "partial heapsort",
    "partial quicksort",
    "segment quicksort",
    "quick select",
    "adaptive merge",
    "inplace merge"
    };

#define NUMBER_OF_INPUTS 9

char* inputString[] = {
    "random",
    "sorted",
    "inversely sorted",
    "hill-shaped",
    "valley-shaped",
    "double sorted",
    "inversely double sorted",
    "constant",
    "zipfian"
    };

int getSortType()
{
    int sortType = 0;
    char sortTypeString[8];

    cout << "Sort types:" << endl;
    
    for (int i = 0; i < NUMBER_OF_SORTS; i++) 
	cout << " " << i << ":   " << titleString[i] << endl ;

    cout << endl << "Enter sort type (Default: 0): ";
    cout.flush();
    cin.getline(sortTypeString, 8);
    if (sortTypeString[0])
	sortType = atoi(sortTypeString);
    if (sortType >= NUMBER_OF_SORTS || sortType < 0) exit(1);
    cout << titleString[sortType] << " selected.\n" << endl;
    return sortType;
}

int getInputType()
{
    int inputType = 0;
    char inputTypeString[8];

    cout << "Input types:" << endl;
    
    for (int i = 0; i < NUMBER_OF_INPUTS; i++) 
	cout << " " << i << ":   " << inputString[i] << endl ;

    cout << endl << "Enter input type (Default: 0): ";
    cout.flush();
    cin.getline(inputTypeString, 8);
    if (inputTypeString[0])
	inputType = atoi(inputTypeString);
    if (inputType >= NUMBER_OF_INPUTS || inputType < 0) exit(1);
    cout << inputString[inputType] << " input selected.\n" << endl;
    return inputType;

}


int getSpeed()
{
    int speed = 20;
    char speedString[8];

    cout << endl << "Enter slowdown factor (Default: 200): ";
    cout.flush();
    cin.getline(speedString, 8);
    if (speedString[0])
	speed = atoi(speedString);
    if (speed <= 0) speed = 1;
    cout << "Slowdown factor " << speed << " selected.\n" << endl;
    return speed;
}


int getSize()
{
    int size = 500;
    char sizeString[8];

    cout << endl << "Enter data size (Default: 500): ";
    cout.flush();
    cin.getline(sizeString, 8);
    if (sizeString[0])
	size = atoi(sizeString);
    if (size <= 100) size = 100;
    cout << "Data size " << size << " selected.\n" << endl;
    return size;
}


double getPercent()
{
    double percent = .25;
    char sizeString[8];

    cout << "Enter buffer ratio (Default: .25): ";
    cout.flush();
    cin.getline(sizeString, 8);
    if (sizeString[0])
	percent = atof(sizeString);
    if (percent > 1) percent = 1;
    if (percent <= 0) percent = .25;
    return percent;
}

double getCut()
{
    double percent = .5;
    char sizeString[8];

    cout << "Enter partial ratio (Default: .5): ";
    cout.flush();
    cin.getline(sizeString, 8);
    if (sizeString[0])
	percent = atof(sizeString);
    if (percent >= 1) percent = .5;
    if (percent <= 0) percent = .5;
    return percent;
}

double getPercentZipfian()
{
    double percent = .001;
    char sizeString[8];

    cout << "Enter zipfian ratio (Default: .001): ";
    cout.flush();
    cin.getline(sizeString, 8);
    if (sizeString[0])
	percent = atof(sizeString);
    if (percent > 1) percent = 1;
    if (percent <= 0) percent = .001;
    return percent;
}

template <class Buffer>
void generateInputs(Buffer* bp, int inputType, int step)
{
    switch (inputType) {
    case 0:
	randomIota(bp->begin(), bp->end(), step);
	break;
    case 1:
	iota(bp->begin(), bp->end(), 0, step);
	break;
    case 2:
	reverseIota(bp->begin(), bp->end(), 0, step);
	break;
    case 3:
	hill(bp->begin(), bp->end(), step);
	break;
    case 4:
	valley(bp->begin(), bp->end(), step);
	break;
    case 5:
	doubleIota(bp->begin(), bp->end(), step);
	break;
    case 6:
	doubleReverseIota(bp->begin(), bp->end(), step);
	break;
    case 7:
	fill(bp->begin(), bp->end(), (bp->end() - bp->begin())/2);
	break;
    case 8:
    {
	int numValues = int((bp->end() - bp->begin()) * getPercentZipfian());
	zipfian(bp->begin(), bp->end(),	numValues);
	break;
    }
    default:
	exit(1);
    }
}

template <class Buffer>
void generateInputs(Buffer* bp, int inputType, double percent)
{
    switch (inputType) {
    case 0:
	randomIota(bp->begin(), bp->end(), 1);
	break;
    case 1:
	iota(bp->begin(), bp->end(), 0, 1);
	break;
    case 2:
	reverseIota(bp->begin(), bp->end(), 0, 1);
	break;
    case 3:
	hill(bp->begin(), bp->end(), 1);
	break;
    case 4:
	valley(bp->begin(), bp->end(), 1);
	break;
    case 5:
	doubleIota(bp->begin(), bp->end(), 1);
	break;
    case 6:
	doubleReverseIota(bp->begin(), bp->end(), 1);
	break;
    case 7:
	fill(bp->begin(), bp->end(), (bp->end() - bp->begin())/2);
	break;
    case 8:
    {
	int numValues = int((bp->end() - bp->begin()) * percent);
	zipfian(bp->begin(), bp->end(),	numValues);
	break;
    }
    default:
	exit(1);
    }
}

template <class Buffer, class BufferAux>
void doSort(Buffer* bp, BufferAux* bpa, int sortType)
{
    switch (sortType) {
    case 0:
	inplaceMergeSort(bp->begin(), bp->end());
	break;
    case 1:
	mergeSortAdaptive(bp->begin(), bp->end(), 
			  size_t(bpa->end() - bpa->begin()), bpa->begin());
	break;
    case 2:
	quickSort(bp->begin(), bp->end());
	break;
    case 3:
	heapSort(bp->begin(), bp->end());
	break;
    case 4:
	traditionalHeapSort(bp->begin(), bp->end());
	break;
    case 5:
	insertionSort(bp->begin(), bp->end());
	break;
    case 6:
	selectionSort(bp->begin(), bp->end());
	break;
    case 7:
	shellSortPAP(bp->begin(), bp->end());
	break;
    case 8:
	bubbleSort(bp->begin(), bp->end());
	break;
    case 9:
	inplacePartitionMergeSort(bp->begin(), bp->end());
	break;
    case 10:
	partitionMergeSortAdaptive(bp->begin(), bp->end(),
				   size_t(bpa->end() - bpa->begin()), 
				   bpa->begin());
	break;
    case 11:
	inplaceDiscreteSort(bp->begin(), bp->end());
	break;
    case 12:
	stableDiscreteSortAdaptive(bp->begin(), bp->end(),
				   size_t(bpa->end() - bpa->begin()), 
				   bpa->begin());
	break;
    case 13:
	inplaceStableDiscreteSort(bp->begin(), bp->end());
	break;
    case 14:
	partialHeapSort(bp->begin(), 
			bp->begin() + int(getCut()*(bp->end() - bp->begin())),
			bp->end());
	break;
    case 15:
	partialQuickSort(bp->begin(), 
			bp->begin() + int(getCut()*(bp->end() - bp->begin())),
			bp->end());
	break;
    case 16:
	segmentQuickSort(bp->begin(), 
			 bp->begin() + int(getCut()*(bp->end() - bp->begin())),
			 bp->begin() + int(getCut()*(bp->end() - bp->begin())),
			 bp->end());
	break;
    case 17:
	quickSelect(bp->begin(),
		    bp->begin() + int(getCut()*(bp->end() - bp->begin())),
		    bp->end());
	break;
    case 18:
	mergeAdaptive(bp->begin(), bp->begin() + (bp->end() - bp->begin()) / 2,
		      bp->end(), size_t(bpa->end() - bpa->begin()), 
		      bpa->begin());
	break;
    case 19:
	inplaceMerge(bp->begin(), bp->begin() + (bp->end() - bp->begin()) / 2,
		     bp->end());
	break;
    default:
	exit(1);
    }
}


template <class Buffer, class BufferAux>
double timeSort(Buffer* bp, BufferAux* bpa, int sortType)
{
    Clock clock;
    clock.clear();
    doSort(bp, bpa, sortType);
    return clock.time() / 1000000;
}

template <class Buffer>
void checkSorted(Buffer* bp)
{
    cout << "isAscendinglySorted ? "
	<< (isSorted(bp->begin(), bp->end()) ? "Yes" : "No") 
	<< endl;
}    

void endTest()
{
    while(1);
}  


template <class VideoVector>
int mainVideo(int argc, char** argv, VideoVector*, int step)
{
    int size = 500;
    int speed = 200;
    if (argc > 1)
	size = atoi(argv[1]);
    if (argc > 2) {
	speed = atoi(argv[2]);
    }    
    int sortType = getSortType();
    int inputType = getInputType();
    int height = size;
    if (step == 1 && inputType > 2 && inputType != 7) height = height / 2;
    VideoVector buffer(size, height, speed, titleString[sortType]);
    VideoVector* bufferAuxP = 0;
    size_t sizeAux = 0;
    if (sortType == 1 || sortType == 10 || sortType == 12 || sortType == 18) {
	double percent = getPercent();
	sizeAux = size_t(percent * size);
	bufferAuxP = new VideoVector(sizeAux, height, speed, "buffer");
    }
    generateInputs(&buffer, inputType, step);
    buffer.setSecondaryKey();
    doSort(&buffer, bufferAuxP, sortType);
    checkSorted(&buffer);
    endTest();
    return 1;
}

template <class Vector>
int mainTime(int argc, char** argv, Vector*)
{
    int size = 100000;

    if (argc > 1)
	size = atoi(argv[1]);
    cout << "sorting " << size << " elements\n\n";
    int sortType = getSortType();
    int inputType = getInputType();

    Vector buffer(size);
    Vector* bufferAuxP = 0;
    size_t sizeAux = 0;
    if (sortType == 1 || sortType == 10 || sortType == 12 || sortType == 18) {
	double percent = getPercent();
	sizeAux = size_t(percent * size);
	bufferAuxP = new Vector(sizeAux);
    }
    generateInputs(&buffer, inputType, 1);

    cout << timeSort(&buffer, bufferAuxP, sortType) << " sec\n";
    return 1;
}

int xTHRESHOLD;

template <class Vector>
int expTime(int argc, char** argv, Vector*)
{
    int size = 100000;

    if (argc > 1)
	size = atoi(argv[1]);
    int sortType = 12;
    int inputType = 8;

    Vector buffer(size);
    Vector* bufferAuxP = new Vector(size / 100);
    
    for (xTHRESHOLD = 4; xTHRESHOLD <= 32; xTHRESHOLD++) {
	generateInputs(&buffer, inputType, 1);
	cout << "Threshold = " << xTHRESHOLD << " ";
	cout << timeSort(&buffer, bufferAuxP, sortType) << " sec\n";
    }
    return 1;
}

template <class Vector>
int mainCount(int argc, char** argv, Vector*)
{
    int size = 100000;

    if (argc > 1)
	size = atoi(argv[1]);
    cout << "sorting " << size << " elements\n\n";
    int sortType = getSortType();
    int inputType = getInputType();

    Vector buffer(size);
    Vector* bufferAuxP = 0;
    size_t sizeAux = 0;
    if (sortType == 1 || sortType == 10 || sortType == 12 || sortType == 18) {
	double percent = getPercent();
	sizeAux = size_t(percent * size);
	bufferAuxP = new Vector(sizeAux);
    }
    generateInputs(&buffer, inputType, 1);
    StatisticalElement::compCount = 0;
    StatisticalElement::moveCount = 0;
    doSort(&buffer, bufferAuxP, sortType);
    cout << "Number of comparisons: " << StatisticalElement::compCount << endl;
    cout << "Number of moves: " << StatisticalElement::moveCount << endl;
    checkSorted(&buffer);
    return 1;
}

#endif