1 /*
2 *
3 * Copyright 2009, The Android Open Source Project
4 * Copyright (c) 1994
5 * Hewlett-Packard Company
6 *
7 * Permission to use, copy, modify, distribute and sell this software
8 * and its documentation for any purpose is hereby granted without fee,
9 * provided that the above copyright notice appear in all copies and
10 * that both that copyright notice and this permission notice appear
11 * in supporting documentation. Hewlett-Packard Company makes no
12 * representations about the suitability of this software for any
13 * purpose. It is provided "as is" without express or implied warranty.
14 *
15 * Copyright (c) 1997
16 * Silicon Graphics Computer Systems, Inc.
17 *
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation. Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose. It is provided "as is" without express or implied warranty.
25 */
26
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
29 */
30
31 #ifndef __SGI_STL_INTERNAL_HEAP_H
32 #define __SGI_STL_INTERNAL_HEAP_H
33
34 __STL_BEGIN_NAMESPACE
35
36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
37 #pragma set woff 1209
38 #endif
39
40 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
41
42 template <class _RandomAccessIterator, class _Distance, class _Tp>
43 void
__push_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __topIndex,_Tp __value)44 __push_heap(_RandomAccessIterator __first,
45 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
46 {
47 _Distance __parent = (__holeIndex - 1) / 2;
48 while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
49 *(__first + __holeIndex) = *(__first + __parent);
50 __holeIndex = __parent;
51 __parent = (__holeIndex - 1) / 2;
52 }
53 *(__first + __holeIndex) = __value;
54 }
55
56 template <class _RandomAccessIterator, class _Distance, class _Tp>
57 inline void
__push_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Distance *,_Tp *)58 __push_heap_aux(_RandomAccessIterator __first,
59 _RandomAccessIterator __last, _Distance*, _Tp*)
60 {
61 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
62 _Tp(*(__last - 1)));
63 }
64
65 template <class _RandomAccessIterator>
66 inline void
push_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)67 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
68 {
69 __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
70 __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
71 _LessThanComparable);
72 __push_heap_aux(__first, __last,
73 __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
74 }
75
76 template <class _RandomAccessIterator, class _Distance, class _Tp,
77 class _Compare>
78 void
__push_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __topIndex,_Tp __value,_Compare __comp)79 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
80 _Distance __topIndex, _Tp __value, _Compare __comp)
81 {
82 _Distance __parent = (__holeIndex - 1) / 2;
83 while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
84 *(__first + __holeIndex) = *(__first + __parent);
85 __holeIndex = __parent;
86 __parent = (__holeIndex - 1) / 2;
87 }
88 *(__first + __holeIndex) = __value;
89 }
90
91 template <class _RandomAccessIterator, class _Compare,
92 class _Distance, class _Tp>
93 inline void
__push_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,_Distance *,_Tp *)94 __push_heap_aux(_RandomAccessIterator __first,
95 _RandomAccessIterator __last, _Compare __comp,
96 _Distance*, _Tp*)
97 {
98 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
99 _Tp(*(__last - 1)), __comp);
100 }
101
102 template <class _RandomAccessIterator, class _Compare>
103 inline void
push_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)104 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
105 _Compare __comp)
106 {
107 __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
108 __push_heap_aux(__first, __last, __comp,
109 __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
110 }
111
112 template <class _RandomAccessIterator, class _Distance, class _Tp>
113 void
__adjust_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __len,_Tp __value)114 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
115 _Distance __len, _Tp __value)
116 {
117 _Distance __topIndex = __holeIndex;
118 _Distance __secondChild = 2 * __holeIndex + 2;
119 while (__secondChild < __len) {
120 if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
121 __secondChild--;
122 *(__first + __holeIndex) = *(__first + __secondChild);
123 __holeIndex = __secondChild;
124 __secondChild = 2 * (__secondChild + 1);
125 }
126 if (__secondChild == __len) {
127 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
128 __holeIndex = __secondChild - 1;
129 }
130 __push_heap(__first, __holeIndex, __topIndex, __value);
131 }
132
133 template <class _RandomAccessIterator, class _Tp, class _Distance>
134 inline void
__pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomAccessIterator __result,_Tp __value,_Distance *)135 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
136 _RandomAccessIterator __result, _Tp __value, _Distance*)
137 {
138 *__result = *__first;
139 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
140 }
141
142 template <class _RandomAccessIterator, class _Tp>
143 inline void
__pop_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *)144 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
145 _Tp*)
146 {
147 __pop_heap(__first, __last - 1, __last - 1,
148 _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
149 }
150
151 template <class _RandomAccessIterator>
pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)152 inline void pop_heap(_RandomAccessIterator __first,
153 _RandomAccessIterator __last)
154 {
155 __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
156 __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
157 _LessThanComparable);
158 __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
159 }
160
161 template <class _RandomAccessIterator, class _Distance,
162 class _Tp, class _Compare>
163 void
__adjust_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __len,_Tp __value,_Compare __comp)164 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
165 _Distance __len, _Tp __value, _Compare __comp)
166 {
167 _Distance __topIndex = __holeIndex;
168 _Distance __secondChild = 2 * __holeIndex + 2;
169 while (__secondChild < __len) {
170 if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
171 __secondChild--;
172 *(__first + __holeIndex) = *(__first + __secondChild);
173 __holeIndex = __secondChild;
174 __secondChild = 2 * (__secondChild + 1);
175 }
176 if (__secondChild == __len) {
177 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
178 __holeIndex = __secondChild - 1;
179 }
180 __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
181 }
182
183 template <class _RandomAccessIterator, class _Tp, class _Compare,
184 class _Distance>
185 inline void
__pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomAccessIterator __result,_Tp __value,_Compare __comp,_Distance *)186 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
187 _RandomAccessIterator __result, _Tp __value, _Compare __comp,
188 _Distance*)
189 {
190 *__result = *__first;
191 __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
192 __value, __comp);
193 }
194
195 template <class _RandomAccessIterator, class _Tp, class _Compare>
196 inline void
__pop_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *,_Compare __comp)197 __pop_heap_aux(_RandomAccessIterator __first,
198 _RandomAccessIterator __last, _Tp*, _Compare __comp)
199 {
200 __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
201 __DISTANCE_TYPE(__first));
202 }
203
204 template <class _RandomAccessIterator, class _Compare>
205 inline void
pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)206 pop_heap(_RandomAccessIterator __first,
207 _RandomAccessIterator __last, _Compare __comp)
208 {
209 __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
210 __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
211 }
212
213 template <class _RandomAccessIterator, class _Tp, class _Distance>
214 void
__make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *,_Distance *)215 __make_heap(_RandomAccessIterator __first,
216 _RandomAccessIterator __last, _Tp*, _Distance*)
217 {
218 if (__last - __first < 2) return;
219 _Distance __len = __last - __first;
220 _Distance __parent = (__len - 2)/2;
221
222 while (true) {
223 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
224 if (__parent == 0) return;
225 __parent--;
226 }
227 }
228
229 template <class _RandomAccessIterator>
230 inline void
make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)231 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
232 {
233 __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
234 __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
235 _LessThanComparable);
236 __make_heap(__first, __last,
237 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
238 }
239
240 template <class _RandomAccessIterator, class _Compare,
241 class _Tp, class _Distance>
242 void
__make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,_Tp *,_Distance *)243 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
244 _Compare __comp, _Tp*, _Distance*)
245 {
246 if (__last - __first < 2) return;
247 _Distance __len = __last - __first;
248 _Distance __parent = (__len - 2)/2;
249
250 while (true) {
251 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
252 __comp);
253 if (__parent == 0) return;
254 __parent--;
255 }
256 }
257
258 template <class _RandomAccessIterator, class _Compare>
259 inline void
make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)260 make_heap(_RandomAccessIterator __first,
261 _RandomAccessIterator __last, _Compare __comp)
262 {
263 __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
264 __make_heap(__first, __last, __comp,
265 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
266 }
267
268 template <class _RandomAccessIterator>
sort_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)269 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
270 {
271 __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
272 __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
273 _LessThanComparable);
274 while (__last - __first > 1)
275 pop_heap(__first, __last--);
276 }
277
278 template <class _RandomAccessIterator, class _Compare>
279 void
sort_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)280 sort_heap(_RandomAccessIterator __first,
281 _RandomAccessIterator __last, _Compare __comp)
282 {
283 __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
284 while (__last - __first > 1)
285 pop_heap(__first, __last--, __comp);
286 }
287
288 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
289 #pragma reset woff 1209
290 #endif
291
292 __STL_END_NAMESPACE
293
294 #endif /* __SGI_STL_INTERNAL_HEAP_H */
295
296 // Local Variables:
297 // mode:C++
298 // End:
299