1 // Heap implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /*
27 *
28 * Copyright (c) 1994
29 * Hewlett-Packard Company
30 *
31 * Permission to use, copy, modify, distribute and sell this software
32 * and its documentation for any purpose is hereby granted without fee,
33 * provided that the above copyright notice appear in all copies and
34 * that both that copyright notice and this permission notice appear
35 * in supporting documentation. Hewlett-Packard Company makes no
36 * representations about the suitability of this software for any
37 * purpose. It is provided "as is" without express or implied warranty.
38 *
39 * Copyright (c) 1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51 /** @file bits/stl_heap.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{queue}
54 */
55
56 #ifndef _STL_HEAP_H
57 #define _STL_HEAP_H 1
58
59 #include <debug/debug.h>
60 #include <bits/move.h>
61
_GLIBCXX_VISIBILITY(default)62 namespace std _GLIBCXX_VISIBILITY(default)
63 {
64 _GLIBCXX_BEGIN_NAMESPACE_VERSION
65
66 /**
67 * @defgroup heap_algorithms Heap
68 * @ingroup sorting_algorithms
69 */
70
71 template<typename _RandomAccessIterator, typename _Distance>
72 _Distance
73 __is_heap_until(_RandomAccessIterator __first, _Distance __n)
74 {
75 _Distance __parent = 0;
76 for (_Distance __child = 1; __child < __n; ++__child)
77 {
78 if (__first[__parent] < __first[__child])
79 return __child;
80 if ((__child & 1) == 0)
81 ++__parent;
82 }
83 return __n;
84 }
85
86 template<typename _RandomAccessIterator, typename _Distance,
87 typename _Compare>
88 _Distance
89 __is_heap_until(_RandomAccessIterator __first, _Distance __n,
90 _Compare __comp)
91 {
92 _Distance __parent = 0;
93 for (_Distance __child = 1; __child < __n; ++__child)
94 {
95 if (__comp(__first[__parent], __first[__child]))
96 return __child;
97 if ((__child & 1) == 0)
98 ++__parent;
99 }
100 return __n;
101 }
102
103 // __is_heap, a predicate testing whether or not a range is a heap.
104 // This function is an extension, not part of the C++ standard.
105 template<typename _RandomAccessIterator, typename _Distance>
106 inline bool
107 __is_heap(_RandomAccessIterator __first, _Distance __n)
108 { return std::__is_heap_until(__first, __n) == __n; }
109
110 template<typename _RandomAccessIterator, typename _Compare,
111 typename _Distance>
112 inline bool
113 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
114 { return std::__is_heap_until(__first, __n, __comp) == __n; }
115
116 template<typename _RandomAccessIterator>
117 inline bool
118 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
119 { return std::__is_heap(__first, std::distance(__first, __last)); }
120
121 template<typename _RandomAccessIterator, typename _Compare>
122 inline bool
123 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
124 _Compare __comp)
125 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
126
127 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
128 // + is_heap and is_heap_until in C++0x.
129
130 template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
131 void
132 __push_heap(_RandomAccessIterator __first,
133 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
134 {
135 _Distance __parent = (__holeIndex - 1) / 2;
136 while (__holeIndex > __topIndex && *(__first + __parent) < __value)
137 {
138 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
139 __holeIndex = __parent;
140 __parent = (__holeIndex - 1) / 2;
141 }
142 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
143 }
144
145 /**
146 * @brief Push an element onto a heap.
147 * @param __first Start of heap.
148 * @param __last End of heap + element.
149 * @ingroup heap_algorithms
150 *
151 * This operation pushes the element at last-1 onto the valid heap
152 * over the range [__first,__last-1). After completion,
153 * [__first,__last) is a valid heap.
154 */
155 template<typename _RandomAccessIterator>
156 inline void
157 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
158 {
159 typedef typename iterator_traits<_RandomAccessIterator>::value_type
160 _ValueType;
161 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
162 _DistanceType;
163
164 // concept requirements
165 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
166 _RandomAccessIterator>)
167 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
168 __glibcxx_requires_valid_range(__first, __last);
169 __glibcxx_requires_heap(__first, __last - 1);
170
171 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
172 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
173 _DistanceType(0), _GLIBCXX_MOVE(__value));
174 }
175
176 template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
177 typename _Compare>
178 void
179 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
180 _Distance __topIndex, _Tp __value, _Compare __comp)
181 {
182 _Distance __parent = (__holeIndex - 1) / 2;
183 while (__holeIndex > __topIndex
184 && __comp(*(__first + __parent), __value))
185 {
186 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
187 __holeIndex = __parent;
188 __parent = (__holeIndex - 1) / 2;
189 }
190 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
191 }
192
193 /**
194 * @brief Push an element onto a heap using comparison functor.
195 * @param __first Start of heap.
196 * @param __last End of heap + element.
197 * @param __comp Comparison functor.
198 * @ingroup heap_algorithms
199 *
200 * This operation pushes the element at __last-1 onto the valid
201 * heap over the range [__first,__last-1). After completion,
202 * [__first,__last) is a valid heap. Compare operations are
203 * performed using comp.
204 */
205 template<typename _RandomAccessIterator, typename _Compare>
206 inline void
207 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
208 _Compare __comp)
209 {
210 typedef typename iterator_traits<_RandomAccessIterator>::value_type
211 _ValueType;
212 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
213 _DistanceType;
214
215 // concept requirements
216 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
217 _RandomAccessIterator>)
218 __glibcxx_requires_valid_range(__first, __last);
219 __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
220
221 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
222 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
223 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
224 }
225
226 template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
227 void
228 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
229 _Distance __len, _Tp __value)
230 {
231 const _Distance __topIndex = __holeIndex;
232 _Distance __secondChild = __holeIndex;
233 while (__secondChild < (__len - 1) / 2)
234 {
235 __secondChild = 2 * (__secondChild + 1);
236 if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
237 __secondChild--;
238 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
239 __holeIndex = __secondChild;
240 }
241 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
242 {
243 __secondChild = 2 * (__secondChild + 1);
244 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
245 + (__secondChild - 1)));
246 __holeIndex = __secondChild - 1;
247 }
248 std::__push_heap(__first, __holeIndex, __topIndex,
249 _GLIBCXX_MOVE(__value));
250 }
251
252 template<typename _RandomAccessIterator>
253 inline void
254 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
255 _RandomAccessIterator __result)
256 {
257 typedef typename iterator_traits<_RandomAccessIterator>::value_type
258 _ValueType;
259 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
260 _DistanceType;
261
262 _ValueType __value = _GLIBCXX_MOVE(*__result);
263 *__result = _GLIBCXX_MOVE(*__first);
264 std::__adjust_heap(__first, _DistanceType(0),
265 _DistanceType(__last - __first),
266 _GLIBCXX_MOVE(__value));
267 }
268
269 /**
270 * @brief Pop an element off a heap.
271 * @param __first Start of heap.
272 * @param __last End of heap.
273 * @pre [__first, __last) is a valid, non-empty range.
274 * @ingroup heap_algorithms
275 *
276 * This operation pops the top of the heap. The elements __first
277 * and __last-1 are swapped and [__first,__last-1) is made into a
278 * heap.
279 */
280 template<typename _RandomAccessIterator>
281 inline void
282 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
283 {
284 typedef typename iterator_traits<_RandomAccessIterator>::value_type
285 _ValueType;
286
287 // concept requirements
288 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
289 _RandomAccessIterator>)
290 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
291 __glibcxx_requires_non_empty_range(__first, __last);
292 __glibcxx_requires_valid_range(__first, __last);
293 __glibcxx_requires_heap(__first, __last);
294
295 --__last;
296 std::__pop_heap(__first, __last, __last);
297 }
298
299 template<typename _RandomAccessIterator, typename _Distance,
300 typename _Tp, typename _Compare>
301 void
302 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
303 _Distance __len, _Tp __value, _Compare __comp)
304 {
305 const _Distance __topIndex = __holeIndex;
306 _Distance __secondChild = __holeIndex;
307 while (__secondChild < (__len - 1) / 2)
308 {
309 __secondChild = 2 * (__secondChild + 1);
310 if (__comp(*(__first + __secondChild),
311 *(__first + (__secondChild - 1))))
312 __secondChild--;
313 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
314 __holeIndex = __secondChild;
315 }
316 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
317 {
318 __secondChild = 2 * (__secondChild + 1);
319 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
320 + (__secondChild - 1)));
321 __holeIndex = __secondChild - 1;
322 }
323 std::__push_heap(__first, __holeIndex, __topIndex,
324 _GLIBCXX_MOVE(__value), __comp);
325 }
326
327 template<typename _RandomAccessIterator, typename _Compare>
328 inline void
329 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
330 _RandomAccessIterator __result, _Compare __comp)
331 {
332 typedef typename iterator_traits<_RandomAccessIterator>::value_type
333 _ValueType;
334 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
335 _DistanceType;
336
337 _ValueType __value = _GLIBCXX_MOVE(*__result);
338 *__result = _GLIBCXX_MOVE(*__first);
339 std::__adjust_heap(__first, _DistanceType(0),
340 _DistanceType(__last - __first),
341 _GLIBCXX_MOVE(__value), __comp);
342 }
343
344 /**
345 * @brief Pop an element off a heap using comparison functor.
346 * @param __first Start of heap.
347 * @param __last End of heap.
348 * @param __comp Comparison functor to use.
349 * @ingroup heap_algorithms
350 *
351 * This operation pops the top of the heap. The elements __first
352 * and __last-1 are swapped and [__first,__last-1) is made into a
353 * heap. Comparisons are made using comp.
354 */
355 template<typename _RandomAccessIterator, typename _Compare>
356 inline void
357 pop_heap(_RandomAccessIterator __first,
358 _RandomAccessIterator __last, _Compare __comp)
359 {
360 // concept requirements
361 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
362 _RandomAccessIterator>)
363 __glibcxx_requires_valid_range(__first, __last);
364 __glibcxx_requires_non_empty_range(__first, __last);
365 __glibcxx_requires_heap_pred(__first, __last, __comp);
366
367 --__last;
368 std::__pop_heap(__first, __last, __last, __comp);
369 }
370
371 /**
372 * @brief Construct a heap over a range.
373 * @param __first Start of heap.
374 * @param __last End of heap.
375 * @ingroup heap_algorithms
376 *
377 * This operation makes the elements in [__first,__last) into a heap.
378 */
379 template<typename _RandomAccessIterator>
380 void
381 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
382 {
383 typedef typename iterator_traits<_RandomAccessIterator>::value_type
384 _ValueType;
385 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
386 _DistanceType;
387
388 // concept requirements
389 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
390 _RandomAccessIterator>)
391 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
392 __glibcxx_requires_valid_range(__first, __last);
393
394 if (__last - __first < 2)
395 return;
396
397 const _DistanceType __len = __last - __first;
398 _DistanceType __parent = (__len - 2) / 2;
399 while (true)
400 {
401 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
402 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
403 if (__parent == 0)
404 return;
405 __parent--;
406 }
407 }
408
409 /**
410 * @brief Construct a heap over a range using comparison functor.
411 * @param __first Start of heap.
412 * @param __last End of heap.
413 * @param __comp Comparison functor to use.
414 * @ingroup heap_algorithms
415 *
416 * This operation makes the elements in [__first,__last) into a heap.
417 * Comparisons are made using __comp.
418 */
419 template<typename _RandomAccessIterator, typename _Compare>
420 void
421 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
422 _Compare __comp)
423 {
424 typedef typename iterator_traits<_RandomAccessIterator>::value_type
425 _ValueType;
426 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
427 _DistanceType;
428
429 // concept requirements
430 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
431 _RandomAccessIterator>)
432 __glibcxx_requires_valid_range(__first, __last);
433
434 if (__last - __first < 2)
435 return;
436
437 const _DistanceType __len = __last - __first;
438 _DistanceType __parent = (__len - 2) / 2;
439 while (true)
440 {
441 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
442 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
443 __comp);
444 if (__parent == 0)
445 return;
446 __parent--;
447 }
448 }
449
450 /**
451 * @brief Sort a heap.
452 * @param __first Start of heap.
453 * @param __last End of heap.
454 * @ingroup heap_algorithms
455 *
456 * This operation sorts the valid heap in the range [__first,__last).
457 */
458 template<typename _RandomAccessIterator>
459 void
460 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
461 {
462 // concept requirements
463 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
464 _RandomAccessIterator>)
465 __glibcxx_function_requires(_LessThanComparableConcept<
466 typename iterator_traits<_RandomAccessIterator>::value_type>)
467 __glibcxx_requires_valid_range(__first, __last);
468 __glibcxx_requires_heap(__first, __last);
469
470 while (__last - __first > 1)
471 {
472 --__last;
473 std::__pop_heap(__first, __last, __last);
474 }
475 }
476
477 /**
478 * @brief Sort a heap using comparison functor.
479 * @param __first Start of heap.
480 * @param __last End of heap.
481 * @param __comp Comparison functor to use.
482 * @ingroup heap_algorithms
483 *
484 * This operation sorts the valid heap in the range [__first,__last).
485 * Comparisons are made using __comp.
486 */
487 template<typename _RandomAccessIterator, typename _Compare>
488 void
489 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
490 _Compare __comp)
491 {
492 // concept requirements
493 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
494 _RandomAccessIterator>)
495 __glibcxx_requires_valid_range(__first, __last);
496 __glibcxx_requires_heap_pred(__first, __last, __comp);
497
498 while (__last - __first > 1)
499 {
500 --__last;
501 std::__pop_heap(__first, __last, __last, __comp);
502 }
503 }
504
505 #ifdef __GXX_EXPERIMENTAL_CXX0X__
506 /**
507 * @brief Search the end of a heap.
508 * @param __first Start of range.
509 * @param __last End of range.
510 * @return An iterator pointing to the first element not in the heap.
511 * @ingroup heap_algorithms
512 *
513 * This operation returns the last iterator i in [__first, __last) for which
514 * the range [__first, i) is a heap.
515 */
516 template<typename _RandomAccessIterator>
517 inline _RandomAccessIterator
518 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
519 {
520 // concept requirements
521 __glibcxx_function_requires(_RandomAccessIteratorConcept<
522 _RandomAccessIterator>)
523 __glibcxx_function_requires(_LessThanComparableConcept<
524 typename iterator_traits<_RandomAccessIterator>::value_type>)
525 __glibcxx_requires_valid_range(__first, __last);
526
527 return __first + std::__is_heap_until(__first, std::distance(__first,
528 __last));
529 }
530
531 /**
532 * @brief Search the end of a heap using comparison functor.
533 * @param __first Start of range.
534 * @param __last End of range.
535 * @param __comp Comparison functor to use.
536 * @return An iterator pointing to the first element not in the heap.
537 * @ingroup heap_algorithms
538 *
539 * This operation returns the last iterator i in [__first, __last) for which
540 * the range [__first, i) is a heap. Comparisons are made using __comp.
541 */
542 template<typename _RandomAccessIterator, typename _Compare>
543 inline _RandomAccessIterator
544 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
545 _Compare __comp)
546 {
547 // concept requirements
548 __glibcxx_function_requires(_RandomAccessIteratorConcept<
549 _RandomAccessIterator>)
550 __glibcxx_requires_valid_range(__first, __last);
551
552 return __first + std::__is_heap_until(__first, std::distance(__first,
553 __last),
554 __comp);
555 }
556
557 /**
558 * @brief Determines whether a range is a heap.
559 * @param __first Start of range.
560 * @param __last End of range.
561 * @return True if range is a heap, false otherwise.
562 * @ingroup heap_algorithms
563 */
564 template<typename _RandomAccessIterator>
565 inline bool
566 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
567 { return std::is_heap_until(__first, __last) == __last; }
568
569 /**
570 * @brief Determines whether a range is a heap using comparison functor.
571 * @param __first Start of range.
572 * @param __last End of range.
573 * @param __comp Comparison functor to use.
574 * @return True if range is a heap, false otherwise.
575 * @ingroup heap_algorithms
576 */
577 template<typename _RandomAccessIterator, typename _Compare>
578 inline bool
579 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
580 _Compare __comp)
581 { return std::is_heap_until(__first, __last, __comp) == __last; }
582 #endif
583
584 _GLIBCXX_END_NAMESPACE_VERSION
585 } // namespace
586
587 #endif /* _STL_HEAP_H */
588