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