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


#ifndef QUICK_SORT_H
#define QUICK_SORT_H

#include <stddef.h>
#include "utilities.H"
#include "sort_utilities.H"
#include "insertion_sort.H"

#define THRESHOLD 16

template <class Iterator>
void finalInsertionSort(Iterator first, Iterator last)
{
    if (last - first > THRESHOLD) {
	insertionSort(first, first + THRESHOLD);
	unguardedInsertionSort(first + THRESHOLD, last);
    } else
	insertionSort(first, last);
}

template <class Iterator, class Compare>
void finalInsertionSort(Iterator first, Iterator last, Compare comp)
{
    if (last - first > THRESHOLD) {
	insertionSort(first, first + THRESHOLD, comp);
	unguardedInsertionSort(first + THRESHOLD, last, comp);
    } else
	insertionSort(first, last, comp);
}

template <class Iterator, class T>
inline Iterator unguardedPartition(Iterator first, Iterator last, T pivot)
{
    while (1) {
	while (*first - pivot < 0) first++;
	last--;
	while (*last - pivot > 0) last--;
	if (last <= first) return first;
	swap(*first, *last);
	first++;
    }
}    

template <class Iterator, class T, class Compare>
inline Iterator unguardedPartition(Iterator first, Iterator last, 
				   T pivot, Compare comp)
{
    while (1) {
	while (comp(*first, pivot) < 0) first++;
	last--;
	while (comp(*last, pivot) > 0) last--;
	if (last <= first) return first;
	swap(*first, *last);
	first++;
    }
}    

template <class Iterator>
static void quickSortLoop(Iterator first, Iterator last)
{
    while (last - first > THRESHOLD) {
	Iterator partition = unguardedPartition
	    (first, last, *medianOf3Select(first, last));
	if (partition - first >= last - partition) {
	    quickSortLoop(partition, last);
	    last = partition;
	} else {
	    quickSortLoop(first, partition);
	    first = partition;
	}
    }
}

template <class Iterator, class Compare>
static void quickSortLoop(Iterator first, Iterator last, Compare comp)
{
    while (last - first > THRESHOLD) {
	Iterator partition = unguardedPartition
	    (first, last, *medianOf3Select(first, last, comp), comp);
	if (partition - first >= last - partition) {
	    quickSortLoop(partition, last, comp);
	    last = partition;
	} else {
	    quickSortLoop(first, partition, comp);
	    first = partition;
	}
    }
}

template <class Iterator>
void quickSort(Iterator first, Iterator last)
{
   quickSortLoop(first, last);
   finalInsertionSort(first, last);
}

template <class Iterator, class Compare>
void quickSort(Iterator first, Iterator last, Compare comp)
{
   quickSortLoop(first, last, comp);
   finalInsertionSort(first, last, comp);
}

template <class Iterator>
void partialQuickSort(Iterator first, Iterator cut, Iterator last)
{
    ASSERT(first < cut && cut <= last);

    while (last - first > THRESHOLD) {
	Iterator partition = unguardedPartition
	    (first, last, *medianOf3Select(first, last));
	if (partition >= cut) 
	    last = partition;
	else {
	    quickSort(first, partition);
	    first = partition;
	}
    }
    insertionSort(first, last);
}

template <class Iterator, class Compare>
void partialQuickSort(Iterator first, Iterator cut, Iterator last, 
		      Compare comp)
{
    ASSERT(first < cut && cut <= last);

    while (last - first > THRESHOLD) {
	Iterator partition = unguardedPartition
	    (first, last, *medianOf3Select(first, last, comp), comp);
	if (partition >= cut) 
	    last = partition;
	else {
	    quickSort(first, partition, comp);
	    first = partition;
	}
    }
    insertionSort(first, last, comp);
}

template <class Iterator>
void segmentQuickSort(Iterator first, Iterator firstCut, 
		      Iterator secondCut, Iterator last)
{
    ASSERT(first <= firstCut && firstCut < secondCut && secondCut <= last);
    while (last - first > THRESHOLD) {
	Iterator partition = unguardedPartition
	    (first, last, *medianOf3Select(first, last));
	if (partition <= firstCut)
	    first = partition;
	else if (partition >= secondCut) 
	    last = partition;
	else {
	    partialQuickSort(partition, secondCut, last);
	    secondCut = partition;
	    last = partition;
	}
    }
    insertionSort(first, last);
}

template <class Iterator, class Compare>
void segmentQuickSort(Iterator first, Iterator firstCut, 
		      Iterator secondCut, Iterator last, Compare comp)
{
    ASSERT(first <= firstCut && firstCut < secondCut && secondCut <= last);
    while (last - first > THRESHOLD) {
	Iterator partition = unguardedPartition
	    (first, last, *medianOf3Select(first, last, comp), comp);
	if (partition <= firstCut)
	    first = partition;
	else if (partition >= secondCut) 
	    last = partition;
	else {
	    partialQuickSort(partition, secondCut, last, comp);
	    secondCut = partition;
	    last = partition;
	}
    }
    insertionSort(first, last, comp);
}

template <class Iterator>
void quickSelect(Iterator first, Iterator result, Iterator last)
{
    ASSERT(first <= result && result <= last);
    while (last - first > THRESHOLD) {
	Iterator partition = unguardedPartition
	    (first, last, *medianOf3Select(first, last));
	if (partition <= result)
	    first = partition;
	else 
	    last = partition;
    }
    insertionSort(first, last);
}

template <class Iterator, class Compare>
void quickSelect(Iterator first, Iterator result, Iterator last, Compare comp)
{
    ASSERT(first <= result && result <= last);
    while (last - first > THRESHOLD) {
	Iterator partition = unguardedPartition
	    (first, last, *medianOf3Select(first, last, comp), comp);
	if (partition <= result)
	    first = partition;
	else 
	    last = partition;
    }
    insertionSort(first, last, comp);
}

#endif