libstdc++
stl_heap.h
Go to the documentation of this file.
00001 // Heap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  * Copyright (c) 1997
00039  * Silicon Graphics Computer Systems, Inc.
00040  *
00041  * Permission to use, copy, modify, distribute and sell this software
00042  * and its documentation for any purpose is hereby granted without fee,
00043  * provided that the above copyright notice appear in all copies and
00044  * that both that copyright notice and this permission notice appear
00045  * in supporting documentation.  Silicon Graphics makes no
00046  * representations about the suitability of this software for any
00047  * purpose.  It is provided "as is" without express or implied warranty.
00048  */
00049 
00050 /** @file bits/stl_heap.h
00051  *  This is an internal header file, included by other library headers.
00052  *  Do not attempt to use it directly. @headername{queue}
00053  */
00054 
00055 #ifndef _STL_HEAP_H
00056 #define _STL_HEAP_H 1
00057 
00058 #include <debug/debug.h>
00059 #include <bits/move.h>
00060 #include <bits/predefined_ops.h>
00061 
00062 namespace std _GLIBCXX_VISIBILITY(default)
00063 {
00064 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00065 
00066   /**
00067    * @defgroup heap_algorithms Heap
00068    * @ingroup sorting_algorithms
00069    */
00070 
00071   template<typename _RandomAccessIterator, typename _Distance,
00072            typename _Compare>
00073     _Distance
00074     __is_heap_until(_RandomAccessIterator __first, _Distance __n,
00075                     _Compare& __comp)
00076     {
00077       _Distance __parent = 0;
00078       for (_Distance __child = 1; __child < __n; ++__child)
00079         {
00080           if (__comp(__first + __parent, __first + __child))
00081             return __child;
00082           if ((__child & 1) == 0)
00083             ++__parent;
00084         }
00085       return __n;
00086     }
00087 
00088   // __is_heap, a predicate testing whether or not a range is a heap.
00089   // This function is an extension, not part of the C++ standard.
00090   template<typename _RandomAccessIterator, typename _Distance>
00091     inline bool
00092     __is_heap(_RandomAccessIterator __first, _Distance __n)
00093     {
00094       __gnu_cxx::__ops::_Iter_less_iter __comp;
00095       return std::__is_heap_until(__first, __n, __comp) == __n;
00096     }
00097 
00098   template<typename _RandomAccessIterator, typename _Compare,
00099            typename _Distance>
00100     inline bool
00101     __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
00102     {
00103       typedef __decltype(__comp) _Cmp;
00104       __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
00105       return std::__is_heap_until(__first, __n, __cmp) == __n;
00106     }
00107 
00108   template<typename _RandomAccessIterator>
00109     inline bool
00110     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00111     { return std::__is_heap(__first, std::distance(__first, __last)); }
00112 
00113   template<typename _RandomAccessIterator, typename _Compare>
00114     inline bool
00115     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00116               _Compare __comp)
00117     {
00118       return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
00119                             std::distance(__first, __last));
00120     }
00121 
00122   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
00123   // + is_heap and is_heap_until in C++0x.
00124 
00125   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
00126            typename _Compare>
00127     void
00128     __push_heap(_RandomAccessIterator __first,
00129                 _Distance __holeIndex, _Distance __topIndex, _Tp __value,
00130                 _Compare& __comp)
00131     {
00132       _Distance __parent = (__holeIndex - 1) / 2;
00133       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
00134         {
00135           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
00136           __holeIndex = __parent;
00137           __parent = (__holeIndex - 1) / 2;
00138         }
00139       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
00140     }
00141 
00142   /**
00143    *  @brief  Push an element onto a heap.
00144    *  @param  __first  Start of heap.
00145    *  @param  __last   End of heap + element.
00146    *  @ingroup heap_algorithms
00147    *
00148    *  This operation pushes the element at last-1 onto the valid heap
00149    *  over the range [__first,__last-1).  After completion,
00150    *  [__first,__last) is a valid heap.
00151   */
00152   template<typename _RandomAccessIterator>
00153     inline void
00154     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00155     {
00156       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00157           _ValueType;
00158       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00159           _DistanceType;
00160 
00161       // concept requirements
00162       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00163             _RandomAccessIterator>)
00164       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
00165       __glibcxx_requires_valid_range(__first, __last);
00166       __glibcxx_requires_irreflexive(__first, __last);
00167       __glibcxx_requires_heap(__first, __last - 1);
00168 
00169       __gnu_cxx::__ops::_Iter_less_val __comp;
00170       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
00171       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
00172                        _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
00173     }
00174 
00175   /**
00176    *  @brief  Push an element onto a heap using comparison functor.
00177    *  @param  __first  Start of heap.
00178    *  @param  __last   End of heap + element.
00179    *  @param  __comp   Comparison functor.
00180    *  @ingroup heap_algorithms
00181    *
00182    *  This operation pushes the element at __last-1 onto the valid
00183    *  heap over the range [__first,__last-1).  After completion,
00184    *  [__first,__last) is a valid heap.  Compare operations are
00185    *  performed using comp.
00186   */
00187   template<typename _RandomAccessIterator, typename _Compare>
00188     inline void
00189     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00190               _Compare __comp)
00191     {
00192       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00193           _ValueType;
00194       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00195           _DistanceType;
00196 
00197       // concept requirements
00198       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00199             _RandomAccessIterator>)
00200       __glibcxx_requires_valid_range(__first, __last);
00201       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00202       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
00203 
00204       __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
00205         __cmp(_GLIBCXX_MOVE(__comp));
00206       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
00207       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
00208                        _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
00209     }
00210 
00211   template<typename _RandomAccessIterator, typename _Distance,
00212            typename _Tp, typename _Compare>
00213     void
00214     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00215                   _Distance __len, _Tp __value, _Compare __comp)
00216     {
00217       const _Distance __topIndex = __holeIndex;
00218       _Distance __secondChild = __holeIndex;
00219       while (__secondChild < (__len - 1) / 2)
00220         {
00221           __secondChild = 2 * (__secondChild + 1);
00222           if (__comp(__first + __secondChild,
00223                      __first + (__secondChild - 1)))
00224             __secondChild--;
00225           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
00226           __holeIndex = __secondChild;
00227         }
00228       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
00229         {
00230           __secondChild = 2 * (__secondChild + 1);
00231           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
00232                                                      + (__secondChild - 1)));
00233           __holeIndex = __secondChild - 1;
00234         }
00235       __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
00236         __cmp(_GLIBCXX_MOVE(__comp));
00237       std::__push_heap(__first, __holeIndex, __topIndex,
00238                        _GLIBCXX_MOVE(__value), __cmp);
00239     }
00240 
00241   template<typename _RandomAccessIterator, typename _Compare>
00242     inline void
00243     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00244                _RandomAccessIterator __result, _Compare& __comp)
00245     {
00246       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00247         _ValueType;
00248       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00249         _DistanceType;
00250 
00251       _ValueType __value = _GLIBCXX_MOVE(*__result);
00252       *__result = _GLIBCXX_MOVE(*__first);
00253       std::__adjust_heap(__first, _DistanceType(0),
00254                          _DistanceType(__last - __first),
00255                          _GLIBCXX_MOVE(__value), __comp);
00256     }
00257 
00258   /**
00259    *  @brief  Pop an element off a heap.
00260    *  @param  __first  Start of heap.
00261    *  @param  __last   End of heap.
00262    *  @pre    [__first, __last) is a valid, non-empty range.
00263    *  @ingroup heap_algorithms
00264    *
00265    *  This operation pops the top of the heap.  The elements __first
00266    *  and __last-1 are swapped and [__first,__last-1) is made into a
00267    *  heap.
00268   */
00269   template<typename _RandomAccessIterator>
00270     inline void
00271     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00272     {
00273       // concept requirements
00274       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00275             _RandomAccessIterator>)
00276       __glibcxx_function_requires(_LessThanComparableConcept<
00277         typename iterator_traits<_RandomAccessIterator>::value_type>)
00278       __glibcxx_requires_non_empty_range(__first, __last);
00279       __glibcxx_requires_valid_range(__first, __last);
00280       __glibcxx_requires_irreflexive(__first, __last);
00281       __glibcxx_requires_heap(__first, __last);
00282 
00283       if (__last - __first > 1)
00284         {
00285           --__last;
00286           __gnu_cxx::__ops::_Iter_less_iter __comp;
00287           std::__pop_heap(__first, __last, __last, __comp);
00288         }
00289     }
00290 
00291   /**
00292    *  @brief  Pop an element off a heap using comparison functor.
00293    *  @param  __first  Start of heap.
00294    *  @param  __last   End of heap.
00295    *  @param  __comp   Comparison functor to use.
00296    *  @ingroup heap_algorithms
00297    *
00298    *  This operation pops the top of the heap.  The elements __first
00299    *  and __last-1 are swapped and [__first,__last-1) is made into a
00300    *  heap.  Comparisons are made using comp.
00301   */
00302   template<typename _RandomAccessIterator, typename _Compare>
00303     inline void
00304     pop_heap(_RandomAccessIterator __first,
00305              _RandomAccessIterator __last, _Compare __comp)
00306     {
00307       // concept requirements
00308       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00309             _RandomAccessIterator>)
00310       __glibcxx_requires_valid_range(__first, __last);
00311       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00312       __glibcxx_requires_non_empty_range(__first, __last);
00313       __glibcxx_requires_heap_pred(__first, __last, __comp);
00314 
00315       if (__last - __first > 1)
00316         {
00317           typedef __decltype(__comp) _Cmp;
00318           __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
00319           --__last;
00320           std::__pop_heap(__first, __last, __last, __cmp);
00321         }
00322     }
00323 
00324   template<typename _RandomAccessIterator, typename _Compare>
00325     void
00326     __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00327                 _Compare& __comp)
00328     {
00329       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00330           _ValueType;
00331       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00332           _DistanceType;
00333 
00334       if (__last - __first < 2)
00335         return;
00336 
00337       const _DistanceType __len = __last - __first;
00338       _DistanceType __parent = (__len - 2) / 2;
00339       while (true)
00340         {
00341           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
00342           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
00343                              __comp);
00344           if (__parent == 0)
00345             return;
00346           __parent--;
00347         }
00348     }
00349   
00350   /**
00351    *  @brief  Construct a heap over a range.
00352    *  @param  __first  Start of heap.
00353    *  @param  __last   End of heap.
00354    *  @ingroup heap_algorithms
00355    *
00356    *  This operation makes the elements in [__first,__last) into a heap.
00357   */
00358   template<typename _RandomAccessIterator>
00359     inline void
00360     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00361     {
00362       // concept requirements
00363       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00364             _RandomAccessIterator>)
00365       __glibcxx_function_requires(_LessThanComparableConcept<
00366             typename iterator_traits<_RandomAccessIterator>::value_type>)
00367       __glibcxx_requires_valid_range(__first, __last);
00368       __glibcxx_requires_irreflexive(__first, __last);
00369 
00370       __gnu_cxx::__ops::_Iter_less_iter __comp;
00371       std::__make_heap(__first, __last, __comp);
00372     }
00373 
00374   /**
00375    *  @brief  Construct a heap over a range using comparison functor.
00376    *  @param  __first  Start of heap.
00377    *  @param  __last   End of heap.
00378    *  @param  __comp   Comparison functor to use.
00379    *  @ingroup heap_algorithms
00380    *
00381    *  This operation makes the elements in [__first,__last) into a heap.
00382    *  Comparisons are made using __comp.
00383   */
00384   template<typename _RandomAccessIterator, typename _Compare>
00385     inline void
00386     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00387               _Compare __comp)
00388     {
00389       // concept requirements
00390       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00391             _RandomAccessIterator>)
00392       __glibcxx_requires_valid_range(__first, __last);
00393       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00394 
00395       typedef __decltype(__comp) _Cmp;
00396       __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
00397       std::__make_heap(__first, __last, __cmp);
00398     }
00399 
00400   template<typename _RandomAccessIterator, typename _Compare>
00401     void
00402     __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00403                 _Compare& __comp)
00404     {
00405       while (__last - __first > 1)
00406         {
00407           --__last;
00408           std::__pop_heap(__first, __last, __last, __comp);
00409         }
00410     }
00411 
00412   /**
00413    *  @brief  Sort a heap.
00414    *  @param  __first  Start of heap.
00415    *  @param  __last   End of heap.
00416    *  @ingroup heap_algorithms
00417    *
00418    *  This operation sorts the valid heap in the range [__first,__last).
00419   */
00420   template<typename _RandomAccessIterator>
00421     inline void
00422     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00423     {
00424       // concept requirements
00425       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00426             _RandomAccessIterator>)
00427       __glibcxx_function_requires(_LessThanComparableConcept<
00428             typename iterator_traits<_RandomAccessIterator>::value_type>)
00429       __glibcxx_requires_valid_range(__first, __last);
00430       __glibcxx_requires_irreflexive(__first, __last);
00431       __glibcxx_requires_heap(__first, __last);
00432 
00433       __gnu_cxx::__ops::_Iter_less_iter __comp;
00434       std::__sort_heap(__first, __last, __comp);
00435     }
00436 
00437   /**
00438    *  @brief  Sort a heap using comparison functor.
00439    *  @param  __first  Start of heap.
00440    *  @param  __last   End of heap.
00441    *  @param  __comp   Comparison functor to use.
00442    *  @ingroup heap_algorithms
00443    *
00444    *  This operation sorts the valid heap in the range [__first,__last).
00445    *  Comparisons are made using __comp.
00446   */
00447   template<typename _RandomAccessIterator, typename _Compare>
00448     inline void
00449     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00450               _Compare __comp)
00451     {
00452       // concept requirements
00453       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00454             _RandomAccessIterator>)
00455       __glibcxx_requires_valid_range(__first, __last);
00456       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00457       __glibcxx_requires_heap_pred(__first, __last, __comp);
00458 
00459       typedef __decltype(__comp) _Cmp;
00460       __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
00461       std::__sort_heap(__first, __last, __cmp);
00462     }
00463 
00464 #if __cplusplus >= 201103L
00465   /**
00466    *  @brief  Search the end of a heap.
00467    *  @param  __first  Start of range.
00468    *  @param  __last   End of range.
00469    *  @return  An iterator pointing to the first element not in the heap.
00470    *  @ingroup heap_algorithms
00471    *
00472    *  This operation returns the last iterator i in [__first, __last) for which
00473    *  the range [__first, i) is a heap.
00474   */
00475   template<typename _RandomAccessIterator>
00476     inline _RandomAccessIterator
00477     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
00478     {
00479       // concept requirements
00480       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00481             _RandomAccessIterator>)
00482       __glibcxx_function_requires(_LessThanComparableConcept<
00483             typename iterator_traits<_RandomAccessIterator>::value_type>)
00484       __glibcxx_requires_valid_range(__first, __last);
00485       __glibcxx_requires_irreflexive(__first, __last);
00486 
00487       __gnu_cxx::__ops::_Iter_less_iter __comp;
00488       return __first + 
00489         std::__is_heap_until(__first, std::distance(__first, __last), __comp);
00490     }
00491 
00492   /**
00493    *  @brief  Search the end of a heap using comparison functor.
00494    *  @param  __first  Start of range.
00495    *  @param  __last   End of range.
00496    *  @param  __comp   Comparison functor to use.
00497    *  @return  An iterator pointing to the first element not in the heap.
00498    *  @ingroup heap_algorithms
00499    *
00500    *  This operation returns the last iterator i in [__first, __last) for which
00501    *  the range [__first, i) is a heap.  Comparisons are made using __comp.
00502   */
00503   template<typename _RandomAccessIterator, typename _Compare>
00504     inline _RandomAccessIterator
00505     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
00506                   _Compare __comp)
00507     {
00508       // concept requirements
00509       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00510             _RandomAccessIterator>)
00511       __glibcxx_requires_valid_range(__first, __last);
00512       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00513 
00514       typedef __decltype(__comp) _Cmp;
00515       __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
00516       return __first
00517         + std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
00518     }
00519 
00520   /**
00521    *  @brief  Determines whether a range is a heap.
00522    *  @param  __first  Start of range.
00523    *  @param  __last   End of range.
00524    *  @return  True if range is a heap, false otherwise.
00525    *  @ingroup heap_algorithms
00526   */
00527   template<typename _RandomAccessIterator>
00528     inline bool
00529     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00530     { return std::is_heap_until(__first, __last) == __last; }
00531 
00532   /**
00533    *  @brief  Determines whether a range is a heap using comparison functor.
00534    *  @param  __first  Start of range.
00535    *  @param  __last   End of range.
00536    *  @param  __comp   Comparison functor to use.
00537    *  @return  True if range is a heap, false otherwise.
00538    *  @ingroup heap_algorithms
00539   */
00540   template<typename _RandomAccessIterator, typename _Compare>
00541     inline bool
00542     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00543             _Compare __comp)
00544     {
00545       // concept requirements
00546       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00547             _RandomAccessIterator>)
00548       __glibcxx_requires_valid_range(__first, __last);
00549       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00550 
00551       const auto __dist = std::distance(__first, __last);
00552       typedef __decltype(__comp) _Cmp;
00553       __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
00554       return std::__is_heap_until(__first, __dist, __cmp) == __dist;
00555     }
00556 #endif
00557 
00558 _GLIBCXX_END_NAMESPACE_VERSION
00559 } // namespace
00560 
00561 #endif /* _STL_HEAP_H */