Clang Project

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