Line data Source code
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 0 : __push_heap(_RandomAccessIterator __first,
125 : _Distance __holeIndex, _Distance __topIndex, _Tp __value,
126 : _Compare __comp)
127 : {
128 0 : _Distance __parent = (__holeIndex - 1) / 2;
129 0 : while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
130 : {
131 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
132 0 : __holeIndex = __parent;
133 0 : __parent = (__holeIndex - 1) / 2;
134 : }
135 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
136 0 : }
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 0 : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
208 : _Distance __len, _Tp __value, _Compare __comp)
209 : {
210 0 : const _Distance __topIndex = __holeIndex;
211 0 : _Distance __secondChild = __holeIndex;
212 0 : while (__secondChild < (__len - 1) / 2)
213 : {
214 0 : __secondChild = 2 * (__secondChild + 1);
215 0 : if (__comp(__first + __secondChild,
216 0 : __first + (__secondChild - 1)))
217 0 : __secondChild--;
218 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
219 0 : __holeIndex = __secondChild;
220 : }
221 0 : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
222 : {
223 0 : __secondChild = 2 * (__secondChild + 1);
224 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
225 : + (__secondChild - 1)));
226 0 : __holeIndex = __secondChild - 1;
227 : }
228 0 : std::__push_heap(__first, __holeIndex, __topIndex,
229 0 : _GLIBCXX_MOVE(__value),
230 0 : __gnu_cxx::__ops::__iter_comp_val(__comp));
231 0 : }
232 :
233 : template<typename _RandomAccessIterator, typename _Compare>
234 : inline void
235 0 : __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 0 : _ValueType __value = _GLIBCXX_MOVE(*__result);
244 0 : *__result = _GLIBCXX_MOVE(*__first);
245 0 : std::__adjust_heap(__first, _DistanceType(0),
246 : _DistanceType(__last - __first),
247 0 : _GLIBCXX_MOVE(__value), __comp);
248 0 : }
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 0 : __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 0 : if (__last - __first < 2)
326 0 : return;
327 :
328 0 : const _DistanceType __len = __last - __first;
329 0 : _DistanceType __parent = (__len - 2) / 2;
330 0 : while (true)
331 : {
332 0 : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
333 0 : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
334 0 : __comp);
335 0 : if (__parent == 0)
336 0 : return;
337 0 : __parent--;
338 0 : }
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 0 : __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
391 : _Compare __comp)
392 : {
393 0 : while (__last - __first > 1)
394 : {
395 0 : --__last;
396 0 : std::__pop_heap(__first, __last, __last, __comp);
397 : }
398 0 : }
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 */
|
