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


#include "heapsort.H"

 
template <class Iterator>
void heapSort1(Iterator first, Iterator last)
{
    makeHeapFromBottom(first, last);
    sortHeap(first, last);
}


template <class Iterator>
void traditionalHeapSort(Iterator first, Iterator last)
{
    makeHeap(first, last);
    sortHeapTraditional(first, last);
}


template <class Iterator>
void traditionalHeapSort1(Iterator first, Iterator last)
{
    makeHeapFromBottom(first, last);
    sortHeapTraditional(first, last);
}

template <class Iterator>
void sortHeapTraditional(Iterator first, Iterator last)
{
    if (last - first < 2) return;

    while (first != --last)  
	popHeapTraditional(first, last, *last, *last);
}

template <class Iterator, class T>
void popHeapTraditional(Iterator first, Iterator last, T value, T& result)
{
    result = *first;
    size_t len = last - first;
    size_t parent = 0;
    size_t secondChild = 2;
    
    while (secondChild < len) {
	if (*(first + secondChild) - *(first + (secondChild - 1)) < 0)
	    secondChild--;
	if (value - *(first + secondChild) < 0) {
	    *(first + parent) = *(first + secondChild);
	    parent = secondChild;
	    secondChild = 2 * (secondChild + 1);
	} else {
	    *(first + parent) = value;
	    return;
	}
    }
    if (secondChild == len) 
	if (!(*(first + (secondChild - 1)) - value < 0)) {
	    *(first + parent) = *(first + (secondChild - 1));
	    *(first + (secondChild - 1)) = value;
	    return;
	}

    *(first + parent) = value;
}

template <class Iterator>
void makeHeapFromBottom(Iterator first, Iterator last)
{
    if (last - first < 2) return;
    
    Iterator i = first;

    while (++i != last)
	pushHeap(first, i, *i);
}