/*

*

* Copyright (c) 1994

* Hewlett-Packard Company

*

* Permission to use, copy, modify, distribute and sell this software

* and its documentation for any purpose is hereby granted without fee,

* provided that the above copyright notice appear in all copies and

* that both that copyright notice and this permission notice appear

* in supporting documentation. Hewlett-Packard Company makes no

* representations about the suitability of this software for any

* purpose. It is provided "as is" without express or implied warranty.

*

* Copyright (c) 1997

* Silicon Graphics Computer Systems, Inc.

*

* Permission to use, copy, modify, distribute and sell this software

* and its documentation for any purpose is hereby granted without fee,

* provided that the above copyright notice appear in all copies and

* that both that copyright notice and this permission notice appear

* in supporting documentation. Silicon Graphics makes no

* representations about the suitability of this software for any

* purpose. It is provided "as is" without express or implied warranty.

*/

/* NOTE: This is an internal header file, included by other STL headers.

* You should not attempt to use it directly.

*/

#ifndef __SGI_STL_INTERNAL_HEAP_H

#define __SGI_STL_INTERNAL_HEAP_H

__STL_BEGIN_NAMESPACE

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)

#pragma set woff 1209

#endif

// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.

// 插入节点后向上调整

template <class _RandomAccessIterator, class _Distance, class _Tp>

void

__push_heap(_RandomAccessIterator __first,

_Distance __holeIndex, _Distance __topIndex, _Tp __value)

{

// 父节点

_Distance __parent = (__holeIndex - 1) / 2;

// 父节点小于新值时进行调整 percolate up

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 _Tp>

inline void

__push_heap_aux(_RandomAccessIterator __first,

_RandomAccessIterator __last, _Distance*, _Tp*)

{

__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),

_Tp(*(__last - 1)));

}

template <class _RandomAccessIterator>

inline void

push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

{

__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);

__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,

_LessThanComparable);

// 调用前，新元素已置于4底部容器的最尾端

__push_heap_aux(__first, __last,

__DISTANCE_TYPE(__first), __VALUE_TYPE(__first));

}

template <class _RandomAccessIterator, class _Distance, class _Tp,

class _Compare>

void

__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,

_Distance __topIndex, _Tp __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 _Compare,

class _Distance, class _Tp>

inline void

__push_heap_aux(_RandomAccessIterator __first,

_RandomAccessIterator __last, _Compare __comp,

_Distance*, _Tp*)

{

__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),

_Tp(*(__last - 1)), __comp);

}

template <class _RandomAccessIterator, class _Compare>

inline void

push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

_Compare __comp)

{

__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);

__push_heap_aux(__first, __last, __comp,

__DISTANCE_TYPE(__first), __VALUE_TYPE(__first));

}

template <class _RandomAccessIterator, class _Distance, class _Tp>

void

__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,

_Distance __len, _Tp __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 _Tp, class _Distance>

inline void

__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

_RandomAccessIterator __result, _Tp __value, _Distance*)

{

*__result = *__first; // 取出结果

__adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);

}

template <class _RandomAccessIterator, class _Tp>

inline void

__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,

_Tp*)

{

__pop_heap(__first, __last - 1, __last - 1,

_Tp(*(__last - 1)), __DISTANCE_TYPE(__first));

//以上，根据 implicit representation heap的次序特性，pop动作的结果

//应为底部容器的第一个元素。因此，首先设定欲调整值为尾值，然后将首值调至

//尾节点（所以以上将迭代器 result设为 last-1）。然后重整 [first, last-1)，

//使之重新成㆒个合格的 heap。

}

// 取出最大值

template <class _RandomAccessIterator>

inline void pop_heap(_RandomAccessIterator __first,

_RandomAccessIterator __last)

{

__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);

__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,

_LessThanComparable);

__pop_heap_aux(__first, __last, __VALUE_TYPE(__first));

}

// 调整堆

template <class _RandomAccessIterator, class _Distance,

class _Tp, class _Compare>

void

__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,

_Distance __len, _Tp __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 _Tp, class _Compare,

class _Distance>

inline void

__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

_RandomAccessIterator __result, _Tp __value, _Compare __comp,

_Distance*)

{

*__result = *__first;

__adjust_heap(__first, _Distance(0), _Distance(__last - __first),

__value, __comp);

}

template <class _RandomAccessIterator, class _Tp, class _Compare>

inline void

__pop_heap_aux(_RandomAccessIterator __first,

_RandomAccessIterator __last, _Tp*, _Compare __comp)

{

__pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,

__DISTANCE_TYPE(__first));

}

template <class _RandomAccessIterator, class _Compare>

inline void

pop_heap(_RandomAccessIterator __first,

_RandomAccessIterator __last, _Compare __comp)

{

__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);

__pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);

}

template <class _RandomAccessIterator, class _Tp, class _Distance>

void

__make_heap(_RandomAccessIterator __first,

_RandomAccessIterator __last, _Tp*, _Distance*)

{

// 长度为0或1不用排列

if (__last - __first < 2) return;

_Distance __len = __last - __first;

//找出第一个需要重排的子树头部，以 parent标示出。由于任何叶节点都不需执行

// perlocate down，所以有以下计算。parent命名不佳，名为 holeIndex更好。

_Distance __parent = (__len - 2)/2;

while (true) {

__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));

if (__parent == 0) return;

__parent--;

}

}

// 建堆

template <class _RandomAccessIterator>

inline void

make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

{

__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);

__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,

_LessThanComparable);

__make_heap(__first, __last,

__VALUE_TYPE(__first), __DISTANCE_TYPE(__first));

}

template <class _RandomAccessIterator, class _Compare,

class _Tp, class _Distance>

void

__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

_Compare __comp, _Tp*, _Distance*)

{

if (__last - __first < 2) return;

_Distance __len = __last - __first;

_Distance __parent = (__len - 2)/2;

while (true) {

__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),

__comp);

if (__parent == 0) return;

__parent--;

}

}

template <class _RandomAccessIterator, class _Compare>

inline void

make_heap(_RandomAccessIterator __first,

_RandomAccessIterator __last, _Compare __comp)

{

__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);

__make_heap(__first, __last, __comp,

__VALUE_TYPE(__first), __DISTANCE_TYPE(__first));

}

//每执行一次 pop_heap()，极值（在 STL heap㆗为极大值）即被放在尾端。

//扣除尾端再执行一次 pop_heap()，次极值又被放在新尾端。最后即得

//排序结果。

template <class _RandomAccessIterator>

void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

{

__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);

__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,

_LessThanComparable);

while (__last - __first > 1)

pop_heap(__first, __last--);

}

template <class _RandomAccessIterator, class _Compare>

void

sort_heap(_RandomAccessIterator __first,

_RandomAccessIterator __last, _Compare __comp)

{

__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);

while (__last - __first > 1)

pop_heap(__first, __last--, __comp);

}

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)

#pragma reset woff 1209

#endif

__STL_END_NAMESPACE

#endif /* __SGI_STL_INTERNAL_HEAP_H */

// Local Variables:

// mode:C++

// End: