1 : // Heap implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2004 Free Software Foundation, Inc.
4 : //
5 : // This file is part of the GNU ISO C++ Library. This library is free
6 : // software; you can redistribute it and/or modify it under the
7 : // terms of the GNU General Public License as published by the
8 : // Free Software Foundation; either version 2, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // You should have received a copy of the GNU General Public License along
17 : // with this library; see the file COPYING. If not, write to the Free
18 : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19 : // USA.
20 :
21 : // As a special exception, you may use this file as part of a free software
22 : // library without restriction. Specifically, if other files instantiate
23 : // templates or use macros or inline functions from this file, or you compile
24 : // this file and link it with other files to produce an executable, this
25 : // file does not by itself cause the resulting executable to be covered by
26 : // the GNU General Public License. This exception does not however
27 : // invalidate any other reasons why the executable file might be covered by
28 : // the GNU General Public License.
29 :
30 : /*
31 : *
32 : * Copyright (c) 1994
33 : * Hewlett-Packard Company
34 : *
35 : * Permission to use, copy, modify, distribute and sell this software
36 : * and its documentation for any purpose is hereby granted without fee,
37 : * provided that the above copyright notice appear in all copies and
38 : * that both that copyright notice and this permission notice appear
39 : * in supporting documentation. Hewlett-Packard Company makes no
40 : * representations about the suitability of this software for any
41 : * purpose. It is provided "as is" without express or implied warranty.
42 : *
43 : * Copyright (c) 1997
44 : * Silicon Graphics Computer Systems, Inc.
45 : *
46 : * Permission to use, copy, modify, distribute and sell this software
47 : * and its documentation for any purpose is hereby granted without fee,
48 : * provided that the above copyright notice appear in all copies and
49 : * that both that copyright notice and this permission notice appear
50 : * in supporting documentation. Silicon Graphics makes no
51 : * representations about the suitability of this software for any
52 : * purpose. It is provided "as is" without express or implied warranty.
53 : */
54 :
55 : /** @file stl_heap.h
56 : * This is an internal header file, included by other library headers.
57 : * You should not attempt to use it directly.
58 : */
59 :
60 : #ifndef _STL_HEAP_H
61 : #define _STL_HEAP_H 1
62 :
63 : #include <debug/debug.h>
64 :
65 : namespace std
66 : {
67 : // is_heap, a predicate testing whether or not a range is
68 : // a heap. This function is an extension, not part of the C++
69 : // standard.
70 : template<typename _RandomAccessIterator, typename _Distance>
71 : bool
72 : __is_heap(_RandomAccessIterator __first, _Distance __n)
73 : {
74 : _Distance __parent = 0;
75 : for (_Distance __child = 1; __child < __n; ++__child)
76 : {
77 : if (__first[__parent] < __first[__child])
78 : return false;
79 : if ((__child & 1) == 0)
80 : ++__parent;
81 : }
82 : return true;
83 : }
84 :
85 : template<typename _RandomAccessIterator, typename _Distance,
86 : typename _StrictWeakOrdering>
87 : bool
88 : __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
89 : _Distance __n)
90 : {
91 : _Distance __parent = 0;
92 : for (_Distance __child = 1; __child < __n; ++__child)
93 : {
94 : if (__comp(__first[__parent], __first[__child]))
95 : return false;
96 : if ((__child & 1) == 0)
97 : ++__parent;
98 : }
99 : return true;
100 : }
101 :
102 : template<typename _RandomAccessIterator>
103 : bool
104 : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
105 : { return std::__is_heap(__first, std::distance(__first, __last)); }
106 :
107 : template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
108 : bool
109 : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
110 : _StrictWeakOrdering __comp)
111 : { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
112 :
113 : // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
114 :
115 : template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
116 : void
117 : __push_heap(_RandomAccessIterator __first,
118 : _Distance __holeIndex, _Distance __topIndex, _Tp __value)
119 : {
120 : _Distance __parent = (__holeIndex - 1) / 2;
121 : while (__holeIndex > __topIndex && *(__first + __parent) < __value)
122 : {
123 : *(__first + __holeIndex) = *(__first + __parent);
124 : __holeIndex = __parent;
125 : __parent = (__holeIndex - 1) / 2;
126 : }
127 : *(__first + __holeIndex) = __value;
128 : }
129 :
130 : /**
131 : * @brief Push an element onto a heap.
132 : * @param first Start of heap.
133 : * @param last End of heap + element.
134 : * @ingroup heap
135 : *
136 : * This operation pushes the element at last-1 onto the valid heap over the
137 : * range [first,last-1). After completion, [first,last) is a valid heap.
138 : */
139 : template<typename _RandomAccessIterator>
140 : inline void
141 : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
142 : {
143 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
144 : _ValueType;
145 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
146 : _DistanceType;
147 :
148 : // concept requirements
149 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
150 : _RandomAccessIterator>)
151 : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
152 : __glibcxx_requires_valid_range(__first, __last);
153 : // __glibcxx_requires_heap(__first, __last - 1);
154 :
155 : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
156 : _DistanceType(0), _ValueType(*(__last - 1)));
157 : }
158 :
159 : template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
160 : typename _Compare>
161 : void
162 : __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
163 0 : _Distance __topIndex, _Tp __value, _Compare __comp)
164 : {
165 0 : _Distance __parent = (__holeIndex - 1) / 2;
166 0 : while (__holeIndex > __topIndex
167 : && __comp(*(__first + __parent), __value))
168 : {
169 0 : *(__first + __holeIndex) = *(__first + __parent);
170 0 : __holeIndex = __parent;
171 0 : __parent = (__holeIndex - 1) / 2;
172 : }
173 0 : *(__first + __holeIndex) = __value;
174 : }
175 :
176 : /**
177 : * @brief Push an element onto a heap using comparison functor.
178 : * @param first Start of heap.
179 : * @param last End of heap + element.
180 : * @param comp Comparison functor.
181 : * @ingroup heap
182 : *
183 : * This operation pushes the element at last-1 onto the valid heap over the
184 : * range [first,last-1). After completion, [first,last) is a valid heap.
185 : * Compare operations are performed using comp.
186 : */
187 : template<typename _RandomAccessIterator, typename _Compare>
188 : inline void
189 : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
190 : _Compare __comp)
191 : {
192 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
193 : _ValueType;
194 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
195 : _DistanceType;
196 :
197 : // concept requirements
198 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
199 : _RandomAccessIterator>)
200 : __glibcxx_requires_valid_range(__first, __last);
201 : __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
202 :
203 : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
204 : _DistanceType(0), _ValueType(*(__last - 1)), __comp);
205 : }
206 :
207 : template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
208 : void
209 : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
210 : _Distance __len, _Tp __value)
211 : {
212 : const _Distance __topIndex = __holeIndex;
213 : _Distance __secondChild = 2 * __holeIndex + 2;
214 : while (__secondChild < __len)
215 : {
216 : if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
217 : __secondChild--;
218 : *(__first + __holeIndex) = *(__first + __secondChild);
219 : __holeIndex = __secondChild;
220 : __secondChild = 2 * (__secondChild + 1);
221 : }
222 : if (__secondChild == __len)
223 : {
224 : *(__first + __holeIndex) = *(__first + (__secondChild - 1));
225 : __holeIndex = __secondChild - 1;
226 : }
227 : std::__push_heap(__first, __holeIndex, __topIndex, __value);
228 : }
229 :
230 : template<typename _RandomAccessIterator, typename _Tp>
231 : inline void
232 : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
233 : _RandomAccessIterator __result, _Tp __value)
234 : {
235 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
236 : _Distance;
237 : *__result = *__first;
238 : std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
239 : __value);
240 : }
241 :
242 : /**
243 : * @brief Pop an element off a heap.
244 : * @param first Start of heap.
245 : * @param last End of heap.
246 : * @ingroup heap
247 : *
248 : * This operation pops the top of the heap. The elements first and last-1
249 : * are swapped and [first,last-1) is made into a heap.
250 : */
251 : template<typename _RandomAccessIterator>
252 : inline void
253 : pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
254 : {
255 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
256 : _ValueType;
257 :
258 : // concept requirements
259 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
260 : _RandomAccessIterator>)
261 : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
262 : __glibcxx_requires_valid_range(__first, __last);
263 : __glibcxx_requires_heap(__first, __last);
264 :
265 : std::__pop_heap(__first, __last - 1, __last - 1,
266 : _ValueType(*(__last - 1)));
267 : }
268 :
269 : template<typename _RandomAccessIterator, typename _Distance,
270 : typename _Tp, typename _Compare>
271 : void
272 : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
273 0 : _Distance __len, _Tp __value, _Compare __comp)
274 : {
275 0 : const _Distance __topIndex = __holeIndex;
276 0 : _Distance __secondChild = 2 * __holeIndex + 2;
277 0 : while (__secondChild < __len)
278 : {
279 0 : if (__comp(*(__first + __secondChild),
280 : *(__first + (__secondChild - 1))))
281 0 : __secondChild--;
282 0 : *(__first + __holeIndex) = *(__first + __secondChild);
283 0 : __holeIndex = __secondChild;
284 0 : __secondChild = 2 * (__secondChild + 1);
285 : }
286 0 : if (__secondChild == __len)
287 : {
288 0 : *(__first + __holeIndex) = *(__first + (__secondChild - 1));
289 0 : __holeIndex = __secondChild - 1;
290 : }
291 0 : std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
292 : }
293 :
294 : template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
295 : inline void
296 : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
297 0 : _RandomAccessIterator __result, _Tp __value, _Compare __comp)
298 : {
299 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
300 : _Distance;
301 0 : *__result = *__first;
302 0 : std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
303 : __value, __comp);
304 : }
305 :
306 : /**
307 : * @brief Pop an element off a heap using comparison functor.
308 : * @param first Start of heap.
309 : * @param last End of heap.
310 : * @param comp Comparison functor to use.
311 : * @ingroup heap
312 : *
313 : * This operation pops the top of the heap. The elements first and last-1
314 : * are swapped and [first,last-1) is made into a heap. Comparisons are
315 : * made using comp.
316 : */
317 : template<typename _RandomAccessIterator, typename _Compare>
318 : inline void
319 : pop_heap(_RandomAccessIterator __first,
320 0 : _RandomAccessIterator __last, _Compare __comp)
321 : {
322 : // concept requirements
323 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
324 : _RandomAccessIterator>)
325 : __glibcxx_requires_valid_range(__first, __last);
326 : __glibcxx_requires_heap_pred(__first, __last, __comp);
327 :
328 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
329 : _ValueType;
330 0 : std::__pop_heap(__first, __last - 1, __last - 1,
331 : _ValueType(*(__last - 1)), __comp);
332 : }
333 :
334 : /**
335 : * @brief Construct a heap over a range.
336 : * @param first Start of heap.
337 : * @param last End of heap.
338 : * @ingroup heap
339 : *
340 : * This operation makes the elements in [first,last) into a heap.
341 : */
342 : template<typename _RandomAccessIterator>
343 : void
344 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
345 : {
346 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
347 : _ValueType;
348 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
349 : _DistanceType;
350 :
351 : // concept requirements
352 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
353 : _RandomAccessIterator>)
354 : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
355 : __glibcxx_requires_valid_range(__first, __last);
356 :
357 : if (__last - __first < 2)
358 : return;
359 :
360 : const _DistanceType __len = __last - __first;
361 : _DistanceType __parent = (__len - 2) / 2;
362 : while (true)
363 : {
364 : std::__adjust_heap(__first, __parent, __len,
365 : _ValueType(*(__first + __parent)));
366 : if (__parent == 0)
367 : return;
368 : __parent--;
369 : }
370 : }
371 :
372 : /**
373 : * @brief Construct a heap over a range using comparison functor.
374 : * @param first Start of heap.
375 : * @param last End of heap.
376 : * @param comp Comparison functor to use.
377 : * @ingroup heap
378 : *
379 : * This operation makes the elements in [first,last) into a heap.
380 : * Comparisons are made using comp.
381 : */
382 : template<typename _RandomAccessIterator, typename _Compare>
383 : inline void
384 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
385 0 : _Compare __comp)
386 : {
387 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
388 : _ValueType;
389 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
390 : _DistanceType;
391 :
392 : // concept requirements
393 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
394 : _RandomAccessIterator>)
395 : __glibcxx_requires_valid_range(__first, __last);
396 :
397 0 : if (__last - __first < 2)
398 0 : return;
399 :
400 0 : const _DistanceType __len = __last - __first;
401 0 : _DistanceType __parent = (__len - 2) / 2;
402 0 : while (true)
403 : {
404 0 : std::__adjust_heap(__first, __parent, __len,
405 : _ValueType(*(__first + __parent)), __comp);
406 0 : if (__parent == 0)
407 0 : return;
408 0 : __parent--;
409 : }
410 : }
411 :
412 : /**
413 : * @brief Sort a heap.
414 : * @param first Start of heap.
415 : * @param last End of heap.
416 : * @ingroup heap
417 : *
418 : * This operation sorts the valid heap in the range [first,last).
419 : */
420 : template<typename _RandomAccessIterator>
421 : void
422 : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
423 : {
424 : // concept requirements
425 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
426 : _RandomAccessIterator>)
427 : __glibcxx_function_requires(_LessThanComparableConcept<
428 : typename iterator_traits<_RandomAccessIterator>::value_type>)
429 : __glibcxx_requires_valid_range(__first, __last);
430 : // __glibcxx_requires_heap(__first, __last);
431 :
432 : while (__last - __first > 1)
433 : std::pop_heap(__first, __last--);
434 : }
435 :
436 : /**
437 : * @brief Sort a heap using comparison functor.
438 : * @param first Start of heap.
439 : * @param last End of heap.
440 : * @param comp Comparison functor to use.
441 : * @ingroup heap
442 : *
443 : * This operation sorts the valid heap in the range [first,last).
444 : * Comparisons are made using comp.
445 : */
446 : template<typename _RandomAccessIterator, typename _Compare>
447 : void
448 : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
449 0 : _Compare __comp)
450 : {
451 : // concept requirements
452 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
453 : _RandomAccessIterator>)
454 : __glibcxx_requires_valid_range(__first, __last);
455 : __glibcxx_requires_heap_pred(__first, __last, __comp);
456 :
457 0 : while (__last - __first > 1)
458 0 : std::pop_heap(__first, __last--, __comp);
459 : }
460 :
461 : } // namespace std
462 :
463 : #endif /* _STL_HEAP_H */
464 :
465 : // Local Variables:
466 : // mode:C++
467 : // End:
|
