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