ReactOS 0.4.16-dev-199-g898cc56
_heap.h File Reference
#include <stl/_heap.c>
Include dependency graph for _heap.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

template<class _RandomAccessIterator >
_STLP_BEGIN_NAMESPACE void push_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
 
template<class _RandomAccessIterator , class _Compare >
void push_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 
template<class _RandomAccessIterator , class _Distance , class _Tp >
void __adjust_heap (_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __val)
 
template<class _RandomAccessIterator , class _Tp , class _Distance >
void __pop_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __val, _Distance *)
 
template<class _RandomAccessIterator >
void pop_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
 
template<class _RandomAccessIterator , class _Distance , class _Tp , class _Compare >
void __adjust_heap (_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __val, _Compare __comp)
 
template<class _RandomAccessIterator , class _Tp , class _Compare , class _Distance >
void __pop_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __val, _Compare __comp, _Distance *)
 
template<class _RandomAccessIterator , class _Compare >
void pop_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 
template<class _RandomAccessIterator >
void make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
 
template<class _RandomAccessIterator , class _Compare >
void make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 
template<class _RandomAccessIterator >
_STLP_INLINE_LOOP void sort_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
 
template<class _RandomAccessIterator , class _Compare >
_STLP_INLINE_LOOP void sort_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 

Function Documentation

◆ __adjust_heap() [1/2]

template<class _RandomAccessIterator , class _Distance , class _Tp >
void __adjust_heap ( _RandomAccessIterator  __first,
_Distance  __holeIndex,
_Distance  __len,
_Tp  __val 
)

Definition at line 111 of file _heap.c.

112 {
113 _Distance __topIndex = __holeIndex;
114 _Distance __secondChild = 2 * __holeIndex + 2;
115 while (__secondChild < __len) {
116 if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
117 __secondChild--;
118 *(__first + __holeIndex) = *(__first + __secondChild);
119 __holeIndex = __secondChild;
120 __secondChild = 2 * (__secondChild + 1);
121 }
122 if (__secondChild == __len) {
123 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
124 __holeIndex = __secondChild - 1;
125 }
126 __push_heap(__first, __holeIndex, __topIndex, __val);
127}
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
_STLP_BEGIN_NAMESPACE _STLP_INLINE_LOOP void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __val)
Definition: _heap.c:42

Referenced by __make_heap(), __partial_sort_copy(), and __pop_heap().

◆ __adjust_heap() [2/2]

template<class _RandomAccessIterator , class _Distance , class _Tp , class _Compare >
void __adjust_heap ( _RandomAccessIterator  __first,
_Distance  __holeIndex,
_Distance  __len,
_Tp  __val,
_Compare  __comp 
)

Definition at line 146 of file _heap.c.

148{
149 _Distance __topIndex = __holeIndex;
150 _Distance __secondChild = 2 * __holeIndex + 2;
151 while (__secondChild < __len) {
152 if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) {
153 _STLP_VERBOSE_ASSERT(!__comp(*(__first + (__secondChild - 1)), *(__first + __secondChild)),
154 _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
155 __secondChild--;
156 }
157 *(__first + __holeIndex) = *(__first + __secondChild);
158 __holeIndex = __secondChild;
159 __secondChild = 2 * (__secondChild + 1);
160 }
161 if (__secondChild == __len) {
162 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
163 __holeIndex = __secondChild - 1;
164 }
165 __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
166}
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439

◆ __pop_heap() [1/2]

template<class _RandomAccessIterator , class _Tp , class _Compare , class _Distance >
void __pop_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_RandomAccessIterator  __result,
_Tp  __val,
_Compare  __comp,
_Distance *   
)
inline

Definition at line 74 of file _heap.h.

77{
78 *__result = *__first;
79 __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
80 __val, __comp);
81}
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __val)
Definition: _heap.c:111

◆ __pop_heap() [2/2]

template<class _RandomAccessIterator , class _Tp , class _Distance >
void __pop_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_RandomAccessIterator  __result,
_Tp  __val,
_Distance *   
)
inline

Definition at line 54 of file _heap.h.

56{
57 *__result = *__first;
58 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __val);
59}

Referenced by __partial_sort(), and __pop_heap_aux().

◆ make_heap() [1/2]

template<class _RandomAccessIterator >
void make_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last 
)

Definition at line 206 of file _heap.c.

207{
208 __make_heap(__first, __last,
209 _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
210}
_STLP_INLINE_LOOP void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *, _Distance *)
Definition: _heap.c:190
#define _STLP_VALUE_TYPE(_It, _Tp)
#define _STLP_DISTANCE_TYPE(_It, _Tp)

Referenced by __partial_sort(), __partial_sort_copy(), HeapTest::mkheap0(), HeapTest::mkheap1(), HeapTest::pheap1(), HeapTest::pheap2(), and priority_queue< _Tp, _Sequence, _Compare >::priority_queue().

◆ make_heap() [2/2]

template<class _RandomAccessIterator , class _Compare >
void make_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Compare  __comp 
)

Definition at line 233 of file _heap.c.

235{
236 __make_heap(__first, __last, __comp,
237 _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
238}

◆ pop_heap() [1/2]

template<class _RandomAccessIterator >
void pop_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last 
)

Definition at line 138 of file _heap.c.

139 {
140 __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
141}
void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *)
Definition: _heap.c:132

Referenced by HeapTest::mkheap0(), HeapTest::mkheap1(), priority_queue< _Tp, _Sequence, _Compare >::pop(), and sort_heap().

◆ pop_heap() [2/2]

template<class _RandomAccessIterator , class _Compare >
void pop_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Compare  __comp 
)

Definition at line 181 of file _heap.c.

183{
184 __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
185}

◆ push_heap() [1/2]

template<class _RandomAccessIterator >
_STLP_BEGIN_NAMESPACE void push_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last 
)

Definition at line 65 of file _heap.c.

66{
67 __push_heap_aux(__first, __last,
68 _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
69}
void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance *, _Tp *)
Definition: _heap.c:56

Referenced by HeapTest::pheap1(), HeapTest::pheap2(), and priority_queue< _Tp, _Sequence, _Compare >::push().

◆ push_heap() [2/2]

template<class _RandomAccessIterator , class _Compare >
void push_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Compare  __comp 
)

Definition at line 102 of file _heap.c.

104{
105 __push_heap_aux(__first, __last, __comp,
106 _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
107}

◆ sort_heap() [1/2]

template<class _RandomAccessIterator >
_STLP_INLINE_LOOP void sort_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last 
)

Definition at line 99 of file _heap.h.

100{
101 while (__last - __first > 1)
102 pop_heap(__first, __last--);
103}
void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
Definition: _heap.c:138

Referenced by __partial_sort(), __partial_sort_copy(), HeapTest::pheap1(), and HeapTest::pheap2().

◆ sort_heap() [2/2]

template<class _RandomAccessIterator , class _Compare >
_STLP_INLINE_LOOP void sort_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Compare  __comp 
)

Definition at line 108 of file _heap.h.

110{
111 while (__last - __first > 1)
112 pop_heap(__first, __last--, __comp);
113}