4 * Hewlett-Packard Company
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
15 * Silicon Graphics Computer Systems, Inc.
17 * Permission to use, copy, modify, distribute and sell this software
18 * and its documentation for any purpose is hereby granted without fee,
19 * provided that the above copyright notice appear in all copies and
20 * that both that copyright notice and this permission notice appear
21 * in supporting documentation. Silicon Graphics makes no
22 * representations about the suitability of this software for any
23 * purpose. It is provided "as is" without express or implied warranty.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef __SGI_STL_INTERNAL_HEAP_H
31 #define __SGI_STL_INTERNAL_HEAP_H
35 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
39 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
41 template <class _RandomAccessIterator, class _Distance, class _Tp>
43 __push_heap(_RandomAccessIterator __first,
44 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
46 _Distance __parent = (__holeIndex - 1) / 2;
47 while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
48 *(__first + __holeIndex) = *(__first + __parent);
49 __holeIndex = __parent;
50 __parent = (__holeIndex - 1) / 2;
52 *(__first + __holeIndex) = __value;
55 template <class _RandomAccessIterator, class _Distance, class _Tp>
57 __push_heap_aux(_RandomAccessIterator __first,
58 _RandomAccessIterator __last, _Distance*, _Tp*)
60 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
64 template <class _RandomAccessIterator>
66 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
68 __push_heap_aux(__first, __last,
69 __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
72 template <class _RandomAccessIterator, class _Distance, class _Tp,
75 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
76 _Distance __topIndex, _Tp __value, _Compare __comp)
78 _Distance __parent = (__holeIndex - 1) / 2;
79 while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
80 *(__first + __holeIndex) = *(__first + __parent);
81 __holeIndex = __parent;
82 __parent = (__holeIndex - 1) / 2;
84 *(__first + __holeIndex) = __value;
87 template <class _RandomAccessIterator, class _Compare,
88 class _Distance, class _Tp>
90 __push_heap_aux(_RandomAccessIterator __first,
91 _RandomAccessIterator __last, _Compare __comp,
94 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
95 _Tp(*(__last - 1)), __comp);
98 template <class _RandomAccessIterator, class _Compare>
100 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
103 __push_heap_aux(__first, __last, __comp,
104 __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
107 template <class _RandomAccessIterator, class _Distance, class _Tp>
109 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
110 _Distance __len, _Tp __value)
112 _Distance __topIndex = __holeIndex;
113 _Distance __secondChild = 2 * __holeIndex + 2;
114 while (__secondChild < __len) {
115 if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
117 *(__first + __holeIndex) = *(__first + __secondChild);
118 __holeIndex = __secondChild;
119 __secondChild = 2 * (__secondChild + 1);
121 if (__secondChild == __len) {
122 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
123 __holeIndex = __secondChild - 1;
125 __push_heap(__first, __holeIndex, __topIndex, __value);
128 template <class _RandomAccessIterator, class _Tp, class _Distance>
130 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
131 _RandomAccessIterator __result, _Tp __value, _Distance*)
133 *__result = *__first;
134 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
137 template <class _RandomAccessIterator, class _Tp>
139 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
142 __pop_heap(__first, __last - 1, __last - 1,
143 _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
146 template <class _RandomAccessIterator>
147 inline void pop_heap(_RandomAccessIterator __first,
148 _RandomAccessIterator __last)
150 __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
153 template <class _RandomAccessIterator, class _Distance,
154 class _Tp, class _Compare>
156 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
157 _Distance __len, _Tp __value, _Compare __comp)
159 _Distance __topIndex = __holeIndex;
160 _Distance __secondChild = 2 * __holeIndex + 2;
161 while (__secondChild < __len) {
162 if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
164 *(__first + __holeIndex) = *(__first + __secondChild);
165 __holeIndex = __secondChild;
166 __secondChild = 2 * (__secondChild + 1);
168 if (__secondChild == __len) {
169 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
170 __holeIndex = __secondChild - 1;
172 __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
175 template <class _RandomAccessIterator, class _Tp, class _Compare,
178 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
179 _RandomAccessIterator __result, _Tp __value, _Compare __comp,
182 *__result = *__first;
183 __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
187 template <class _RandomAccessIterator, class _Tp, class _Compare>
189 __pop_heap_aux(_RandomAccessIterator __first,
190 _RandomAccessIterator __last, _Tp*, _Compare __comp)
192 __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
193 __DISTANCE_TYPE(__first));
196 template <class _RandomAccessIterator, class _Compare>
198 pop_heap(_RandomAccessIterator __first,
199 _RandomAccessIterator __last, _Compare __comp)
201 __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
204 template <class _RandomAccessIterator, class _Tp, class _Distance>
206 __make_heap(_RandomAccessIterator __first,
207 _RandomAccessIterator __last, _Tp*, _Distance*)
209 if (__last - __first < 2) return;
210 _Distance __len = __last - __first;
211 _Distance __parent = (__len - 2)/2;
214 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
215 if (__parent == 0) return;
220 template <class _RandomAccessIterator>
222 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
224 __make_heap(__first, __last,
225 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
228 template <class _RandomAccessIterator, class _Compare,
229 class _Tp, class _Distance>
231 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
232 _Compare __comp, _Tp*, _Distance*)
234 if (__last - __first < 2) return;
235 _Distance __len = __last - __first;
236 _Distance __parent = (__len - 2)/2;
239 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
241 if (__parent == 0) return;
246 template <class _RandomAccessIterator, class _Compare>
248 make_heap(_RandomAccessIterator __first,
249 _RandomAccessIterator __last, _Compare __comp)
251 __make_heap(__first, __last, __comp,
252 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
255 template <class _RandomAccessIterator>
256 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
258 while (__last - __first > 1)
259 pop_heap(__first, __last--);
262 template <class _RandomAccessIterator, class _Compare>
264 sort_heap(_RandomAccessIterator __first,
265 _RandomAccessIterator __last, _Compare __comp)
267 while (__last - __first > 1)
268 pop_heap(__first, __last--, __comp);
271 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
272 #pragma reset woff 1209
277 #endif /* __SGI_STL_INTERNAL_HEAP_H */