1 /*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
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.
13 *
14 * Copyright (c) 1997
15 * Silicon Graphics Computer Systems, Inc.
16 *
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.
24 */
25
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
28 */
29
30 #ifndef __SGI_STL_INTERNAL_HEAP_H
31 #define __SGI_STL_INTERNAL_HEAP_H
32
33 __STL_BEGIN_NAMESPACE
34
35 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
36 #pragma set woff 1209
37 #endif
38
39 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
40
41 template <class _RandomAccessIterator, class _Distance, class _Tp>
42 void
__push_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __topIndex,_Tp __value)43 __push_heap(_RandomAccessIterator __first,
44 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
45 {
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;
51 }
52 *(__first + __holeIndex) = __value;
53 }
54
55 template <class _RandomAccessIterator, class _Distance, class _Tp>
56 inline void
__push_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Distance *,_Tp *)57 __push_heap_aux(_RandomAccessIterator __first,
58 _RandomAccessIterator __last, _Distance*, _Tp*)
59 {
60 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
61 _Tp(*(__last - 1)));
62 }
63
64 template <class _RandomAccessIterator>
65 inline void
push_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)66 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
67 {
68 __push_heap_aux(__first, __last,
69 __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
70 }
71
72 template <class _RandomAccessIterator, class _Distance, class _Tp,
73 class _Compare>
74 void
__push_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __topIndex,_Tp __value,_Compare __comp)75 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
76 _Distance __topIndex, _Tp __value, _Compare __comp)
77 {
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;
83 }
84 *(__first + __holeIndex) = __value;
85 }
86
87 template <class _RandomAccessIterator, class _Compare,
88 class _Distance, class _Tp>
89 inline void
__push_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,_Distance *,_Tp *)90 __push_heap_aux(_RandomAccessIterator __first,
91 _RandomAccessIterator __last, _Compare __comp,
92 _Distance*, _Tp*)
93 {
94 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
95 _Tp(*(__last - 1)), __comp);
96 }
97
98 template <class _RandomAccessIterator, class _Compare>
99 inline void
push_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)100 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
101 _Compare __comp)
102 {
103 __push_heap_aux(__first, __last, __comp,
104 __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
105 }
106
107 template <class _RandomAccessIterator, class _Distance, class _Tp>
108 void
__adjust_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __len,_Tp __value)109 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
110 _Distance __len, _Tp __value)
111 {
112 _Distance __topIndex = __holeIndex;
113 _Distance __secondChild = 2 * __holeIndex + 2;
114 while (__secondChild < __len) {
115 if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
116 __secondChild--;
117 *(__first + __holeIndex) = *(__first + __secondChild);
118 __holeIndex = __secondChild;
119 __secondChild = 2 * (__secondChild + 1);
120 }
121 if (__secondChild == __len) {
122 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
123 __holeIndex = __secondChild - 1;
124 }
125 __push_heap(__first, __holeIndex, __topIndex, __value);
126 }
127
128 template <class _RandomAccessIterator, class _Tp, class _Distance>
129 inline void
__pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomAccessIterator __result,_Tp __value,_Distance *)130 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
131 _RandomAccessIterator __result, _Tp __value, _Distance*)
132 {
133 *__result = *__first;
134 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
135 }
136
137 template <class _RandomAccessIterator, class _Tp>
138 inline void
__pop_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *)139 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
140 _Tp*)
141 {
142 __pop_heap(__first, __last - 1, __last - 1,
143 _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
144 }
145
146 template <class _RandomAccessIterator>
pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)147 inline void pop_heap(_RandomAccessIterator __first,
148 _RandomAccessIterator __last)
149 {
150 __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
151 }
152
153 template <class _RandomAccessIterator, class _Distance,
154 class _Tp, class _Compare>
155 void
__adjust_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __len,_Tp __value,_Compare __comp)156 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
157 _Distance __len, _Tp __value, _Compare __comp)
158 {
159 _Distance __topIndex = __holeIndex;
160 _Distance __secondChild = 2 * __holeIndex + 2;
161 while (__secondChild < __len) {
162 if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
163 __secondChild--;
164 *(__first + __holeIndex) = *(__first + __secondChild);
165 __holeIndex = __secondChild;
166 __secondChild = 2 * (__secondChild + 1);
167 }
168 if (__secondChild == __len) {
169 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
170 __holeIndex = __secondChild - 1;
171 }
172 __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
173 }
174
175 template <class _RandomAccessIterator, class _Tp, class _Compare,
176 class _Distance>
177 inline void
__pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomAccessIterator __result,_Tp __value,_Compare __comp,_Distance *)178 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
179 _RandomAccessIterator __result, _Tp __value, _Compare __comp,
180 _Distance*)
181 {
182 *__result = *__first;
183 __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
184 __value, __comp);
185 }
186
187 template <class _RandomAccessIterator, class _Tp, class _Compare>
188 inline void
__pop_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *,_Compare __comp)189 __pop_heap_aux(_RandomAccessIterator __first,
190 _RandomAccessIterator __last, _Tp*, _Compare __comp)
191 {
192 __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
193 __DISTANCE_TYPE(__first));
194 }
195
196 template <class _RandomAccessIterator, class _Compare>
197 inline void
pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)198 pop_heap(_RandomAccessIterator __first,
199 _RandomAccessIterator __last, _Compare __comp)
200 {
201 __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
202 }
203
204 template <class _RandomAccessIterator, class _Tp, class _Distance>
205 void
__make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *,_Distance *)206 __make_heap(_RandomAccessIterator __first,
207 _RandomAccessIterator __last, _Tp*, _Distance*)
208 {
209 if (__last - __first < 2) return;
210 _Distance __len = __last - __first;
211 _Distance __parent = (__len - 2)/2;
212
213 while (true) {
214 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
215 if (__parent == 0) return;
216 __parent--;
217 }
218 }
219
220 template <class _RandomAccessIterator>
221 inline void
make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)222 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
223 {
224 __make_heap(__first, __last,
225 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
226 }
227
228 template <class _RandomAccessIterator, class _Compare,
229 class _Tp, class _Distance>
230 void
__make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,_Tp *,_Distance *)231 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
232 _Compare __comp, _Tp*, _Distance*)
233 {
234 if (__last - __first < 2) return;
235 _Distance __len = __last - __first;
236 _Distance __parent = (__len - 2)/2;
237
238 while (true) {
239 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
240 __comp);
241 if (__parent == 0) return;
242 __parent--;
243 }
244 }
245
246 template <class _RandomAccessIterator, class _Compare>
247 inline void
make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)248 make_heap(_RandomAccessIterator __first,
249 _RandomAccessIterator __last, _Compare __comp)
250 {
251 __make_heap(__first, __last, __comp,
252 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
253 }
254
255 template <class _RandomAccessIterator>
sort_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)256 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
257 {
258 while (__last - __first > 1)
259 pop_heap(__first, __last--);
260 }
261
262 template <class _RandomAccessIterator, class _Compare>
263 void
sort_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)264 sort_heap(_RandomAccessIterator __first,
265 _RandomAccessIterator __last, _Compare __comp)
266 {
267 while (__last - __first > 1)
268 pop_heap(__first, __last--, __comp);
269 }
270
271 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
272 #pragma reset woff 1209
273 #endif
274
275 __STL_END_NAMESPACE
276
277 #endif /* __SGI_STL_INTERNAL_HEAP_H */
278
279 // Local Variables:
280 // mode:C++
281 // End:
282