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 | |
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 | |