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

Go to the source code of this file.

Macros

#define _STLP_HEAP_C
 

Functions

template<class _RandomAccessIterator , class _Distance , class _Tp >
_STLP_BEGIN_NAMESPACE _STLP_INLINE_LOOP void __push_heap (_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __val)
 
template<class _RandomAccessIterator , class _Distance , class _Tp >
void __push_heap_aux (_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance *, _Tp *)
 
template<class _RandomAccessIterator >
void push_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
 
template<class _RandomAccessIterator , class _Distance , class _Tp , class _Compare >
_STLP_INLINE_LOOP void __push_heap (_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __val, _Compare __comp)
 
template<class _RandomAccessIterator , class _Compare , class _Distance , class _Tp >
void __push_heap_aux (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Distance *, _Tp *)
 
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 >
void __pop_heap_aux (_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *)
 
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 >
void __pop_heap_aux (_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *, _Compare __comp)
 
template<class _RandomAccessIterator , class _Compare >
void pop_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 
template<class _RandomAccessIterator , class _Tp , class _Distance >
_STLP_INLINE_LOOP void __make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *, _Distance *)
 
template<class _RandomAccessIterator >
void make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
 
template<class _RandomAccessIterator , class _Compare , class _Tp , class _Distance >
_STLP_INLINE_LOOP void __make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Tp *, _Distance *)
 
template<class _RandomAccessIterator , class _Compare >
void make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 

Macro Definition Documentation

◆ _STLP_HEAP_C

#define _STLP_HEAP_C

Definition at line 27 of file _heap.c.

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 }
_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
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439

◆ __make_heap() [1/2]

template<class _RandomAccessIterator , class _Tp , class _Distance >
_STLP_INLINE_LOOP void __make_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Tp *  ,
_Distance *   
)

Definition at line 190 of file _heap.c.

192 {
193  if (__last - __first < 2) return;
194  _Distance __len = __last - __first;
195  _Distance __parent = (__len - 2)/2;
196 
197  for (;;) {
198  __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
199  if (__parent == 0) return;
200  __parent--;
201  }
202 }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __val)
Definition: _heap.c:111

Referenced by make_heap().

◆ __make_heap() [2/2]

template<class _RandomAccessIterator , class _Compare , class _Tp , class _Distance >
_STLP_INLINE_LOOP void __make_heap ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Compare  __comp,
_Tp *  ,
_Distance *   
)

Definition at line 216 of file _heap.c.

218 {
219  if (__last - __first < 2) return;
220  _Distance __len = __last - __first;
221  _Distance __parent = (__len - 2)/2;
222 
223  for (;;) {
224  __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
225  __comp);
226  if (__parent == 0) return;
227  __parent--;
228  }
229 }
_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_aux() [1/2]

template<class _RandomAccessIterator , class _Tp >
void __pop_heap_aux ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Tp *   
)
inline

Definition at line 132 of file _heap.c.

132  {
133  __pop_heap(__first, __last - 1, __last - 1,
134  _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
135 }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __val, _Distance *)
Definition: _heap.h:54
#define _STLP_DISTANCE_TYPE(_It, _Tp)

Referenced by pop_heap().

◆ __pop_heap_aux() [2/2]

template<class _RandomAccessIterator , class _Tp , class _Compare >
void __pop_heap_aux ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Tp *  ,
_Compare  __comp 
)
inline

Definition at line 171 of file _heap.c.

173 {
174  __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
175  _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
176 }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __val, _Distance *)
Definition: _heap.h:54
#define _STLP_DISTANCE_TYPE(_It, _Tp)

◆ __push_heap() [1/2]

template<class _RandomAccessIterator , class _Distance , class _Tp >
_STLP_BEGIN_NAMESPACE _STLP_INLINE_LOOP void __push_heap ( _RandomAccessIterator  __first,
_Distance  __holeIndex,
_Distance  __topIndex,
_Tp  __val 
)

Definition at line 42 of file _heap.c.

44 {
45  _Distance __parent = (__holeIndex - 1) / 2;
46  while (__holeIndex > __topIndex && *(__first + __parent) < __val) {
47  *(__first + __holeIndex) = *(__first + __parent);
48  __holeIndex = __parent;
49  __parent = (__holeIndex - 1) / 2;
50  }
51  *(__first + __holeIndex) = __val;
52 }
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656

Referenced by __adjust_heap(), and __push_heap_aux().

◆ __push_heap() [2/2]

template<class _RandomAccessIterator , class _Distance , class _Tp , class _Compare >
_STLP_INLINE_LOOP void __push_heap ( _RandomAccessIterator  __first,
_Distance  __holeIndex,
_Distance  __topIndex,
_Tp  __val,
_Compare  __comp 
)

Definition at line 76 of file _heap.c.

78 {
79  _Distance __parent = (__holeIndex - 1) / 2;
80  while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) {
81  _STLP_VERBOSE_ASSERT(!__comp(__val, *(__first + __parent)), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
82  *(__first + __holeIndex) = *(__first + __parent);
83  __holeIndex = __parent;
84  __parent = (__holeIndex - 1) / 2;
85  }
86  *(__first + __holeIndex) = __val;
87 }
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439

◆ __push_heap_aux() [1/2]

template<class _RandomAccessIterator , class _Distance , class _Tp >
void __push_heap_aux ( _RandomAccessIterator  __first,
_RandomAccessIterator  __last,
_Distance *  ,
_Tp *   
)
inline

Definition at line 56 of file _heap.c.

58 {
59  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
60  _Tp(*(__last - 1)));
61 }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_STLP_BEGIN_NAMESPACE _STLP_INLINE_LOOP void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __val)
Definition: _heap.c:42

Referenced by push_heap().

◆ __push_heap_aux() [2/2]

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

Definition at line 92 of file _heap.c.

95 {
96  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
97  _Tp(*(__last - 1)), __comp);
98 }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_STLP_BEGIN_NAMESPACE _STLP_INLINE_LOOP void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __val)
Definition: _heap.c:42

◆ 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
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
#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 }
_STLP_INLINE_LOOP void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *, _Distance *)
Definition: _heap.c:190
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
#define _STLP_VALUE_TYPE(_It, _Tp)
#define _STLP_DISTANCE_TYPE(_It, _Tp)

◆ 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
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
#define _STLP_VALUE_TYPE(_It, _Tp)

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 }
void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *)
Definition: _heap.c:132
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
#define _STLP_VALUE_TYPE(_It, _Tp)

◆ push_heap() [1/2]

template<class _RandomAccessIterator >
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
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
#define _STLP_VALUE_TYPE(_It, _Tp)
#define _STLP_DISTANCE_TYPE(_It, _Tp)

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 }
void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance *, _Tp *)
Definition: _heap.c:56
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
#define _STLP_VALUE_TYPE(_It, _Tp)
#define _STLP_DISTANCE_TYPE(_It, _Tp)