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