ReactOS  0.4.14-dev-606-g14ebc0b
_heap.c
Go to the documentation of this file.
1 /*
2  *
3  *
4  * Copyright (c) 1994
5  * Hewlett-Packard Company
6  *
7  * Copyright (c) 1996,1997
8  * Silicon Graphics Computer Systems, Inc.
9  *
10  * Copyright (c) 1997
11  * Moscow Center for SPARC Technology
12  *
13  * Copyright (c) 1999
14  * Boris Fomitchev
15  *
16  * This material is provided "as is", with absolutely no warranty expressed
17  * or implied. Any use is at your own risk.
18  *
19  * Permission to use or copy this software for any purpose is hereby granted
20  * without fee, provided the above notices are retained on all copies.
21  * Permission to modify the code and to distribute modified code is granted,
22  * provided the above notices are retained, and a notice that the code was
23  * modified is included with the above copyright notice.
24  *
25  */
26 #ifndef _STLP_HEAP_C
27 #define _STLP_HEAP_C
28 
29 #ifndef _STLP_INTERNAL_HEAP_H
30 # include <stl/_heap.h>
31 #endif
32 
33 #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
34 # include <stl/_iterator_base.h>
35 #endif
36 
38 
39 template <class _RandomAccessIterator, class _Distance, class _Tp>
41 void
42 __push_heap(_RandomAccessIterator __first,
43  _Distance __holeIndex, _Distance __topIndex, _Tp __val)
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 }
53 
54 template <class _RandomAccessIterator, class _Distance, class _Tp>
55 inline void
56 __push_heap_aux(_RandomAccessIterator __first,
57  _RandomAccessIterator __last, _Distance*, _Tp*)
58 {
59  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
60  _Tp(*(__last - 1)));
61 }
62 
63 template <class _RandomAccessIterator>
64 void
65 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
66 {
67  __push_heap_aux(__first, __last,
68  _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
69 }
70 
71 
72 template <class _RandomAccessIterator, class _Distance, class _Tp,
73  class _Compare>
75 void
76 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
77  _Distance __topIndex, _Tp __val, _Compare __comp)
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 }
88 
89 template <class _RandomAccessIterator, class _Compare,
90  class _Distance, class _Tp>
91 inline void
92 __push_heap_aux(_RandomAccessIterator __first,
93  _RandomAccessIterator __last, _Compare __comp,
94  _Distance*, _Tp*)
95 {
96  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
97  _Tp(*(__last - 1)), __comp);
98 }
99 
100 template <class _RandomAccessIterator, class _Compare>
101 void
102 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
103  _Compare __comp)
104 {
105  __push_heap_aux(__first, __last, __comp,
106  _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
107 }
108 
109 template <class _RandomAccessIterator, class _Distance, class _Tp>
110 void
111 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
112  _Distance __len, _Tp __val) {
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 }
128 
129 
130 template <class _RandomAccessIterator, class _Tp>
131 inline void
132 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) {
133  __pop_heap(__first, __last - 1, __last - 1,
134  _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
135 }
136 
137 template <class _RandomAccessIterator>
138 void pop_heap(_RandomAccessIterator __first,
139  _RandomAccessIterator __last) {
140  __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
141 }
142 
143 template <class _RandomAccessIterator, class _Distance,
144  class _Tp, class _Compare>
145 void
146 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
147  _Distance __len, _Tp __val, _Compare __comp)
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 }
167 
168 
169 template <class _RandomAccessIterator, class _Tp, class _Compare>
170 inline void
171 __pop_heap_aux(_RandomAccessIterator __first,
172  _RandomAccessIterator __last, _Tp*, _Compare __comp)
173 {
174  __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
175  _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
176 }
177 
178 
179 template <class _RandomAccessIterator, class _Compare>
180 void
181 pop_heap(_RandomAccessIterator __first,
182  _RandomAccessIterator __last, _Compare __comp)
183 {
184  __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
185 }
186 
187 template <class _RandomAccessIterator, class _Tp, class _Distance>
189 void
190 __make_heap(_RandomAccessIterator __first,
191  _RandomAccessIterator __last, _Tp*, _Distance*)
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 }
203 
204 template <class _RandomAccessIterator>
205 void
206 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
207 {
208  __make_heap(__first, __last,
209  _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
210 }
211 
212 template <class _RandomAccessIterator, class _Compare,
213  class _Tp, class _Distance>
215 void
216 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
217  _Compare __comp, _Tp*, _Distance*)
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 }
230 
231 template <class _RandomAccessIterator, class _Compare>
232 void
233 make_heap(_RandomAccessIterator __first,
234  _RandomAccessIterator __last, _Compare __comp)
235 {
236  __make_heap(__first, __last, __comp,
237  _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
238 }
239 
241 
242 #endif /* _STLP_HEAP_C */
243 
244 // Local Variables:
245 // mode:C++
246 // End:
_STLP_INLINE_LOOP void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *, _Distance *)
Definition: _heap.c:190
void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *)
Definition: _heap.c:132
void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance *, _Tp *)
Definition: _heap.c:56
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
Definition: _heap.c:138
void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __val, _Distance *)
Definition: _heap.h:54
void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
Definition: _heap.c:65
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __val)
Definition: _heap.c:111
_STLP_BEGIN_NAMESPACE _STLP_INLINE_LOOP void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __val)
Definition: _heap.c:42
#define _STLP_INLINE_LOOP
Definition: features.h:648
#define _STLP_VALUE_TYPE(_It, _Tp)
#define _STLP_END_NAMESPACE
Definition: features.h:503
void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
Definition: _heap.c:206
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_DISTANCE_TYPE(_It, _Tp)
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439