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