Line data Source code
1 : // Heap implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2019 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 : #include <bits/predefined_ops.h>
61 :
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 : typename _Compare>
73 : _Distance
74 : __is_heap_until(_RandomAccessIterator __first, _Distance __n,
75 : _Compare& __comp)
76 : {
77 : _Distance __parent = 0;
78 : for (_Distance __child = 1; __child < __n; ++__child)
79 : {
80 : if (__comp(__first + __parent, __first + __child))
81 : return __child;
82 : if ((__child & 1) == 0)
83 : ++__parent;
84 : }
85 : return __n;
86 : }
87 :
88 : // __is_heap, a predicate testing whether or not a range is a heap.
89 : // This function is an extension, not part of the C++ standard.
90 : template<typename _RandomAccessIterator, typename _Distance>
91 : inline bool
92 : __is_heap(_RandomAccessIterator __first, _Distance __n)
93 : {
94 : __gnu_cxx::__ops::_Iter_less_iter __comp;
95 : return std::__is_heap_until(__first, __n, __comp) == __n;
96 : }
97 :
98 : template<typename _RandomAccessIterator, typename _Compare,
99 : typename _Distance>
100 : inline bool
101 : __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
102 : {
103 : typedef __decltype(__comp) _Cmp;
104 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
105 : return std::__is_heap_until(__first, __n, __cmp) == __n;
106 : }
107 :
108 : template<typename _RandomAccessIterator>
109 : inline bool
110 : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
111 : { return std::__is_heap(__first, std::distance(__first, __last)); }
112 :
113 : template<typename _RandomAccessIterator, typename _Compare>
114 : inline bool
115 : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
116 : _Compare __comp)
117 : {
118 : return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
119 : std::distance(__first, __last));
120 : }
121 :
122 : // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
123 : // + is_heap and is_heap_until in C++0x.
124 :
125 : template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
126 : typename _Compare>
127 : void
128 0 : __push_heap(_RandomAccessIterator __first,
129 : _Distance __holeIndex, _Distance __topIndex, _Tp __value,
130 : _Compare& __comp)
131 : {
132 0 : _Distance __parent = (__holeIndex - 1) / 2;
133 0 : while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
134 : {
135 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
136 0 : __holeIndex = __parent;
137 0 : __parent = (__holeIndex - 1) / 2;
138 : }
139 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
140 0 : }
141 :
142 : /**
143 : * @brief Push an element onto a heap.
144 : * @param __first Start of heap.
145 : * @param __last End of heap + element.
146 : * @ingroup heap_algorithms
147 : *
148 : * This operation pushes the element at last-1 onto the valid heap
149 : * over the range [__first,__last-1). After completion,
150 : * [__first,__last) is a valid heap.
151 : */
152 : template<typename _RandomAccessIterator>
153 : inline void
154 : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
155 : {
156 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
157 : _ValueType;
158 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
159 : _DistanceType;
160 :
161 : // concept requirements
162 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
163 : _RandomAccessIterator>)
164 : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
165 : __glibcxx_requires_valid_range(__first, __last);
166 : __glibcxx_requires_irreflexive(__first, __last);
167 : __glibcxx_requires_heap(__first, __last - 1);
168 :
169 : __gnu_cxx::__ops::_Iter_less_val __comp;
170 : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
171 : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
172 : _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
173 : }
174 :
175 : /**
176 : * @brief Push an element onto a heap using comparison functor.
177 : * @param __first Start of heap.
178 : * @param __last End of heap + element.
179 : * @param __comp Comparison functor.
180 : * @ingroup heap_algorithms
181 : *
182 : * This operation pushes the element at __last-1 onto the valid
183 : * heap over the range [__first,__last-1). After completion,
184 : * [__first,__last) is a valid heap. Compare operations are
185 : * 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_irreflexive_pred(__first, __last, __comp);
202 : __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
203 :
204 : __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
205 : __cmp(_GLIBCXX_MOVE(__comp));
206 : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
207 : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
208 : _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
209 : }
210 :
211 : template<typename _RandomAccessIterator, typename _Distance,
212 : typename _Tp, typename _Compare>
213 : void
214 0 : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
215 : _Distance __len, _Tp __value, _Compare __comp)
216 : {
217 0 : const _Distance __topIndex = __holeIndex;
218 0 : _Distance __secondChild = __holeIndex;
219 0 : while (__secondChild < (__len - 1) / 2)
220 : {
221 0 : __secondChild = 2 * (__secondChild + 1);
222 0 : if (__comp(__first + __secondChild,
223 0 : __first + (__secondChild - 1)))
224 0 : __secondChild--;
225 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
226 0 : __holeIndex = __secondChild;
227 : }
228 0 : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
229 : {
230 0 : __secondChild = 2 * (__secondChild + 1);
231 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
232 : + (__secondChild - 1)));
233 0 : __holeIndex = __secondChild - 1;
234 : }
235 : __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
236 0 : __cmp(_GLIBCXX_MOVE(__comp));
237 0 : std::__push_heap(__first, __holeIndex, __topIndex,
238 0 : _GLIBCXX_MOVE(__value), __cmp);
239 0 : }
240 :
241 : template<typename _RandomAccessIterator, typename _Compare>
242 : inline void
243 0 : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
244 : _RandomAccessIterator __result, _Compare& __comp)
245 : {
246 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
247 : _ValueType;
248 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
249 : _DistanceType;
250 :
251 0 : _ValueType __value = _GLIBCXX_MOVE(*__result);
252 0 : *__result = _GLIBCXX_MOVE(*__first);
253 0 : std::__adjust_heap(__first, _DistanceType(0),
254 0 : _DistanceType(__last - __first),
255 0 : _GLIBCXX_MOVE(__value), __comp);
256 0 : }
257 :
258 : /**
259 : * @brief Pop an element off a heap.
260 : * @param __first Start of heap.
261 : * @param __last End of heap.
262 : * @pre [__first, __last) is a valid, non-empty range.
263 : * @ingroup heap_algorithms
264 : *
265 : * This operation pops the top of the heap. The elements __first
266 : * and __last-1 are swapped and [__first,__last-1) is made into a
267 : * heap.
268 : */
269 : template<typename _RandomAccessIterator>
270 : inline void
271 : pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
272 : {
273 : // concept requirements
274 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
275 : _RandomAccessIterator>)
276 : __glibcxx_function_requires(_LessThanComparableConcept<
277 : typename iterator_traits<_RandomAccessIterator>::value_type>)
278 : __glibcxx_requires_non_empty_range(__first, __last);
279 : __glibcxx_requires_valid_range(__first, __last);
280 : __glibcxx_requires_irreflexive(__first, __last);
281 : __glibcxx_requires_heap(__first, __last);
282 :
283 : if (__last - __first > 1)
284 : {
285 : --__last;
286 : __gnu_cxx::__ops::_Iter_less_iter __comp;
287 : std::__pop_heap(__first, __last, __last, __comp);
288 : }
289 : }
290 :
291 : /**
292 : * @brief Pop an element off a heap using comparison functor.
293 : * @param __first Start of heap.
294 : * @param __last End of heap.
295 : * @param __comp Comparison functor to use.
296 : * @ingroup heap_algorithms
297 : *
298 : * This operation pops the top of the heap. The elements __first
299 : * and __last-1 are swapped and [__first,__last-1) is made into a
300 : * heap. Comparisons are made using comp.
301 : */
302 : template<typename _RandomAccessIterator, typename _Compare>
303 : inline void
304 : pop_heap(_RandomAccessIterator __first,
305 : _RandomAccessIterator __last, _Compare __comp)
306 : {
307 : // concept requirements
308 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
309 : _RandomAccessIterator>)
310 : __glibcxx_requires_valid_range(__first, __last);
311 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
312 : __glibcxx_requires_non_empty_range(__first, __last);
313 : __glibcxx_requires_heap_pred(__first, __last, __comp);
314 :
315 : if (__last - __first > 1)
316 : {
317 : typedef __decltype(__comp) _Cmp;
318 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
319 : --__last;
320 : std::__pop_heap(__first, __last, __last, __cmp);
321 : }
322 : }
323 :
324 : template<typename _RandomAccessIterator, typename _Compare>
325 : void
326 0 : __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
327 : _Compare& __comp)
328 : {
329 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
330 : _ValueType;
331 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
332 : _DistanceType;
333 :
334 0 : if (__last - __first < 2)
335 : return;
336 :
337 0 : const _DistanceType __len = __last - __first;
338 0 : _DistanceType __parent = (__len - 2) / 2;
339 0 : while (true)
340 : {
341 0 : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
342 0 : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
343 : __comp);
344 0 : if (__parent == 0)
345 0 : return;
346 0 : __parent--;
347 : }
348 : }
349 :
350 : /**
351 : * @brief Construct a heap over a range.
352 : * @param __first Start of heap.
353 : * @param __last End of heap.
354 : * @ingroup heap_algorithms
355 : *
356 : * This operation makes the elements in [__first,__last) into a heap.
357 : */
358 : template<typename _RandomAccessIterator>
359 : inline void
360 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
361 : {
362 : // concept requirements
363 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
364 : _RandomAccessIterator>)
365 : __glibcxx_function_requires(_LessThanComparableConcept<
366 : typename iterator_traits<_RandomAccessIterator>::value_type>)
367 : __glibcxx_requires_valid_range(__first, __last);
368 : __glibcxx_requires_irreflexive(__first, __last);
369 :
370 : __gnu_cxx::__ops::_Iter_less_iter __comp;
371 : std::__make_heap(__first, __last, __comp);
372 : }
373 :
374 : /**
375 : * @brief Construct a heap over a range using comparison functor.
376 : * @param __first Start of heap.
377 : * @param __last End of heap.
378 : * @param __comp Comparison functor to use.
379 : * @ingroup heap_algorithms
380 : *
381 : * This operation makes the elements in [__first,__last) into a heap.
382 : * Comparisons are made using __comp.
383 : */
384 : template<typename _RandomAccessIterator, typename _Compare>
385 : inline void
386 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
387 : _Compare __comp)
388 : {
389 : // concept requirements
390 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
391 : _RandomAccessIterator>)
392 : __glibcxx_requires_valid_range(__first, __last);
393 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
394 :
395 : typedef __decltype(__comp) _Cmp;
396 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
397 : std::__make_heap(__first, __last, __cmp);
398 : }
399 :
400 : template<typename _RandomAccessIterator, typename _Compare>
401 : void
402 0 : __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
403 : _Compare& __comp)
404 : {
405 0 : while (__last - __first > 1)
406 : {
407 0 : --__last;
408 0 : std::__pop_heap(__first, __last, __last, __comp);
409 : }
410 : }
411 :
412 : /**
413 : * @brief Sort a heap.
414 : * @param __first Start of heap.
415 : * @param __last End of heap.
416 : * @ingroup heap_algorithms
417 : *
418 : * This operation sorts the valid heap in the range [__first,__last).
419 : */
420 : template<typename _RandomAccessIterator>
421 : inline 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_irreflexive(__first, __last);
431 : __glibcxx_requires_heap(__first, __last);
432 :
433 : __gnu_cxx::__ops::_Iter_less_iter __comp;
434 : std::__sort_heap(__first, __last, __comp);
435 : }
436 :
437 : /**
438 : * @brief Sort a heap using comparison functor.
439 : * @param __first Start of heap.
440 : * @param __last End of heap.
441 : * @param __comp Comparison functor to use.
442 : * @ingroup heap_algorithms
443 : *
444 : * This operation sorts the valid heap in the range [__first,__last).
445 : * Comparisons are made using __comp.
446 : */
447 : template<typename _RandomAccessIterator, typename _Compare>
448 : inline void
449 : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
450 : _Compare __comp)
451 : {
452 : // concept requirements
453 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
454 : _RandomAccessIterator>)
455 : __glibcxx_requires_valid_range(__first, __last);
456 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
457 : __glibcxx_requires_heap_pred(__first, __last, __comp);
458 :
459 : typedef __decltype(__comp) _Cmp;
460 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
461 : std::__sort_heap(__first, __last, __cmp);
462 : }
463 :
464 : #if __cplusplus >= 201103L
465 : /**
466 : * @brief Search the end of a heap.
467 : * @param __first Start of range.
468 : * @param __last End of range.
469 : * @return An iterator pointing to the first element not in the heap.
470 : * @ingroup heap_algorithms
471 : *
472 : * This operation returns the last iterator i in [__first, __last) for which
473 : * the range [__first, i) is a heap.
474 : */
475 : template<typename _RandomAccessIterator>
476 : inline _RandomAccessIterator
477 : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
478 : {
479 : // concept requirements
480 : __glibcxx_function_requires(_RandomAccessIteratorConcept<
481 : _RandomAccessIterator>)
482 : __glibcxx_function_requires(_LessThanComparableConcept<
483 : typename iterator_traits<_RandomAccessIterator>::value_type>)
484 : __glibcxx_requires_valid_range(__first, __last);
485 : __glibcxx_requires_irreflexive(__first, __last);
486 :
487 : __gnu_cxx::__ops::_Iter_less_iter __comp;
488 : return __first +
489 : std::__is_heap_until(__first, std::distance(__first, __last), __comp);
490 : }
491 :
492 : /**
493 : * @brief Search the end of a heap using comparison functor.
494 : * @param __first Start of range.
495 : * @param __last End of range.
496 : * @param __comp Comparison functor to use.
497 : * @return An iterator pointing to the first element not in the heap.
498 : * @ingroup heap_algorithms
499 : *
500 : * This operation returns the last iterator i in [__first, __last) for which
501 : * the range [__first, i) is a heap. Comparisons are made using __comp.
502 : */
503 : template<typename _RandomAccessIterator, typename _Compare>
504 : inline _RandomAccessIterator
505 : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
506 : _Compare __comp)
507 : {
508 : // concept requirements
509 : __glibcxx_function_requires(_RandomAccessIteratorConcept<
510 : _RandomAccessIterator>)
511 : __glibcxx_requires_valid_range(__first, __last);
512 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
513 :
514 : typedef __decltype(__comp) _Cmp;
515 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
516 : return __first
517 : + std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
518 : }
519 :
520 : /**
521 : * @brief Determines whether a range is a heap.
522 : * @param __first Start of range.
523 : * @param __last End of range.
524 : * @return True if range is a heap, false otherwise.
525 : * @ingroup heap_algorithms
526 : */
527 : template<typename _RandomAccessIterator>
528 : inline bool
529 : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
530 : { return std::is_heap_until(__first, __last) == __last; }
531 :
532 : /**
533 : * @brief Determines whether a range is a heap using comparison functor.
534 : * @param __first Start of range.
535 : * @param __last End of range.
536 : * @param __comp Comparison functor to use.
537 : * @return True if range is a heap, false otherwise.
538 : * @ingroup heap_algorithms
539 : */
540 : template<typename _RandomAccessIterator, typename _Compare>
541 : inline bool
542 : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
543 : _Compare __comp)
544 : {
545 : // concept requirements
546 : __glibcxx_function_requires(_RandomAccessIteratorConcept<
547 : _RandomAccessIterator>)
548 : __glibcxx_requires_valid_range(__first, __last);
549 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
550 :
551 : const auto __dist = std::distance(__first, __last);
552 : typedef __decltype(__comp) _Cmp;
553 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
554 : return std::__is_heap_until(__first, __dist, __cmp) == __dist;
555 : }
556 : #endif
557 :
558 : _GLIBCXX_END_NAMESPACE_VERSION
559 : } // namespace
560 :
561 : #endif /* _STL_HEAP_H */
|
