/** -*- C++ -*-
 **
 **  KAI C++ Compiler
 **
 **  Copyright (C) 1996-2001 Intel Corp. All rights reserved.
 **
 **  The heap functions are split out of algorithm to speed up compilation of queue.
 **  Queue only needs the heap functions from algorithm.
 **/
/**
 **  Lib++  : The Modena C++ Standard Library,
 **           Version 2.4, October 1997
 **
 **  Copyright (c) 1995-1997 Modena Software Inc.
 **/
#ifndef __KAI_HEAP
#define __KAI_HEAP

#include <mcompile.h>

namespace __kai {

// For implementation of class priority_queue and Heap operations

template <class RandomAccessIterator, class Distance, class T>
void __push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value)
{
    Distance parent = (holeIndex - 1) / 2;
    while (holeIndex > topIndex && *(first + parent) < value) {
        *(first + holeIndex) = *(first + parent);
        holeIndex = parent;
        parent = (holeIndex - 1) / 2;
    }    
    *(first + holeIndex) = value;
}

template <class RandomAccessIterator, class Distance, class T, class Compare>
void __push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value, Compare comp)
{
    Distance parent = (holeIndex - 1) / 2;
    while (holeIndex > topIndex && comp(* (first + parent), value)) {
        *(first + holeIndex) = *(first + parent);
        holeIndex = parent;
        parent = (holeIndex - 1) / 2;
    }
    *(first + holeIndex) = value;
}

template <class RandomAccessIterator, class Distance, class T>
inline void __adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value)
{
    Distance topIndex = holeIndex;
    Distance secondChild = 2 * holeIndex + 2;
    while (secondChild < len) {
        if (*(first + secondChild) < *(first + (secondChild - 1)))
            secondChild--;
        *(first + holeIndex) = *(first + secondChild);
        holeIndex = secondChild;
        secondChild = 2 * (secondChild + 1);
    }
    if (secondChild == len) {
        *(first + holeIndex) = *(first + (secondChild - 1));
        holeIndex = secondChild - 1;
    }
    __push_heap(first, holeIndex, topIndex, value);
}

template <class RandomAccessIterator, class Distance, class T, class Compare>
void __adjust_heap (RandomAccessIterator first, Distance holeIndex,
                    Distance len, T value, Compare comp)
{
    Distance topIndex = holeIndex;
    Distance secondChild = 2 * holeIndex + 2;
    while (secondChild < len)
    {
        if (comp (* (first + secondChild), * (first + (secondChild - 1))))
            secondChild--;
        *(first + holeIndex) = *(first + secondChild);
        holeIndex = secondChild;
        secondChild = 2 * (secondChild + 1);
    }
    if (secondChild == len)
    {
        *(first + holeIndex) = *(first + (secondChild - 1));
        holeIndex = secondChild - 1;
    }
    __push_heap (first, holeIndex, topIndex, value, comp);
}

template <class RandomAccessIterator, class T>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value)
{
    typedef  typename std::iterator_traits<RandomAccessIterator>::difference_type Distance;
    *result = *first;
    __adjust_heap(first, Distance(0), Distance(last - first), value);
}

template <class RandomAccessIterator, class T, class Compare>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
		       RandomAccessIterator result, T value, Compare comp )
{
    typedef  typename std::iterator_traits<RandomAccessIterator>::difference_type Distance;
    *result = *first;
    __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
}

} // namespace __kai

namespace std {

// Section 25.3.6 -- Heap operations

// Section 25.3.6.1 -- push_heap
template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    typedef typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    typedef typename iterator_traits<RandomAccessIterator>::value_type Value;
    __kai::__push_heap(first, Distance((last - first) - 1), Distance(0), Value(* (last - 1)));
}

template <class RandomAccessIterator, class Compare>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    typedef typename iterator_traits<RandomAccessIterator>::value_type Value;
    __kai::__push_heap(first, Distance((last - first) - 1), Distance(0), Value(* (last - 1)), comp);
}

// Section 25.3.6.2 -- pop_heap
template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    typedef typename iterator_traits<RandomAccessIterator>::value_type Value;
    __kai::__pop_heap(first, last-1, last-1, Value(* (last - 1)));
}

template <class RandomAccessIterator, class Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef  typename iterator_traits<RandomAccessIterator>::value_type Value;
    __kai::__pop_heap(first, last - 1, last - 1, Value(* (last - 1)), comp);
}

// Section 25.3.6.3 -- make_heap

template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    typedef typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    typedef typename iterator_traits<RandomAccessIterator>::value_type Value;

    if (last - first < 2)
	return;
    Distance len = last - first;
    Distance parent = (len - 2)/2;
    
    while (true) {
        __kai::__adjust_heap(first, parent, len, Value(* (first + parent)));
        if (parent == 0)
	    return;
        --parent;
    }
}

template <class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    typedef typename iterator_traits<RandomAccessIterator>::value_type Value;
    if (last - first < 2)
	return;
    Distance len = last - first;
    Distance parent = (len - 2)/2;
    
    while (true) {
        __kai::__adjust_heap(first, parent, len, Value(* (first + parent)), comp);
        if (parent == 0)
	    return;
        --parent;
    }
}

// Section 25.3.6.4 -- sort_heap
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    while (last - first > 1) {
	pop_heap(first, last);
	--last;
    }
}

template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    while (last - first > 1) {
	pop_heap(first, last, comp);
	--last;
    }
}

} // namespace std

#endif /* __KAI_HEAP */