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