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


#ifndef DISCRETE_SORT_H
#define DISCRETE_SORT_H

#include "assert.H"
#include "partition.H"
#include "pair.H"
#include "insertion_sort.H"
#include "pap_auxbuffer.H"

#define DISCRETE_SORT_THRESHOLD 32

template <class Iterator>
static void inplaceDiscreteSort(Iterator first, Iterator last)
{
    while (last - first > DISCRETE_SORT_THRESHOLD) {
	Pair<Iterator, Iterator> partition = threePartition
	    (first, last, *randomSelect(first, last));
	if (partition.first - first >= last - partition.second) {
	    inplaceDiscreteSort(partition.second, last);
	    last = partition.first;
	} else {
	    inplaceDiscreteSort(first, partition.first);
	    first = partition.second;
	}
    }
    ASSERT(last - first <= DISCRETE_SORT_THRESHOLD);
    insertionSort(first, last);
}

template <class Iterator>
void inplaceStableDiscreteSort(Iterator first, Iterator last)
{
    while (last - first > DISCRETE_SORT_THRESHOLD) {
	Pair<Iterator, Iterator> partition = inplaceStable3Partition
	    (first, last, *randomSelect(first, last));
	if (partition.first - first >= last - partition.second) {
	    inplaceStableDiscreteSort(partition.second, last);
	    last = partition.first;
	} else {
	    inplaceStableDiscreteSort(first, partition.first);
	    first = partition.second;
	}
    }
    insertionSort(first, last);
}

template <class Iterator, class BufferIterator>
void stableDiscreteSortAdaptive(Iterator first, Iterator last,
				size_t bufferSize, BufferIterator buffer)
{
    ASSERT(bufferSize > 0);
    while (last - first > DISCRETE_SORT_THRESHOLD) {
	Pair<Iterator, Iterator> partition = stable3PartitionAdaptive
	    (first, last, *randomSelect(first, last), bufferSize, buffer);
	if (partition.first - first >= last - partition.second) {
	    stableDiscreteSortAdaptive(partition.second, last, 
				       bufferSize, buffer);
	    last = partition.first; 
	} else {
	    stableDiscreteSortAdaptive(first, partition.first,
				       bufferSize, buffer);
	    first = partition.second;
	}
    }
    insertionSort(first, last);
}

template <class Iterator, class T>
void stableDiscreteSortAux(Iterator first, Iterator last, T&)
{
    PAP_auxBuffer<T> buffer(last - first);
    if (buffer.len > 2)
	stableDiscreteSortAdaptive(first, last, buffer.len, buffer.ptr);
    else
	inplaceStableDiscreteSort(first, last);
}

#endif