libstdc++
stl_heap.h
Go to the documentation of this file.
00001 // Heap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2016 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       return std::__is_heap_until(__first, __n,
00095                         __gnu_cxx::__ops::__iter_less_iter()) == __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       return std::__is_heap_until(__first, __n,
00104         __gnu_cxx::__ops::__iter_comp_iter(__comp)) == __n;
00105     }
00106 
00107   template<typename _RandomAccessIterator>
00108     inline bool
00109     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00110     { return std::__is_heap(__first, std::distance(__first, __last)); }
00111 
00112   template<typename _RandomAccessIterator, typename _Compare>
00113     inline bool
00114     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00115               _Compare __comp)
00116     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
00117 
00118   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
00119   // + is_heap and is_heap_until in C++0x.
00120 
00121   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
00122            typename _Compare>
00123     void
00124     __push_heap(_RandomAccessIterator __first,
00125                 _Distance __holeIndex, _Distance __topIndex, _Tp __value,
00126                 _Compare __comp)
00127     {
00128       _Distance __parent = (__holeIndex - 1) / 2;
00129       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
00130         {
00131           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
00132           __holeIndex = __parent;
00133           __parent = (__holeIndex - 1) / 2;
00134         }
00135       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
00136     }
00137 
00138   /**
00139    *  @brief  Push an element onto a heap.
00140    *  @param  __first  Start of heap.
00141    *  @param  __last   End of heap + element.
00142    *  @ingroup heap_algorithms
00143    *
00144    *  This operation pushes the element at last-1 onto the valid heap
00145    *  over the range [__first,__last-1).  After completion,
00146    *  [__first,__last) is a valid heap.
00147   */
00148   template<typename _RandomAccessIterator>
00149     inline void
00150     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00151     {
00152       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00153           _ValueType;
00154       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00155           _DistanceType;
00156 
00157       // concept requirements
00158       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00159             _RandomAccessIterator>)
00160       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
00161       __glibcxx_requires_valid_range(__first, __last);
00162       __glibcxx_requires_irreflexive(__first, __last);
00163       __glibcxx_requires_heap(__first, __last - 1);
00164 
00165       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
00166       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
00167                        _DistanceType(0), _GLIBCXX_MOVE(__value),
00168                        __gnu_cxx::__ops::__iter_less_val());
00169     }
00170 
00171   /**
00172    *  @brief  Push an element onto a heap using comparison functor.
00173    *  @param  __first  Start of heap.
00174    *  @param  __last   End of heap + element.
00175    *  @param  __comp   Comparison functor.
00176    *  @ingroup heap_algorithms
00177    *
00178    *  This operation pushes the element at __last-1 onto the valid
00179    *  heap over the range [__first,__last-1).  After completion,
00180    *  [__first,__last) is a valid heap.  Compare operations are
00181    *  performed using comp.
00182   */
00183   template<typename _RandomAccessIterator, typename _Compare>
00184     inline void
00185     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00186               _Compare __comp)
00187     {
00188       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00189           _ValueType;
00190       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00191           _DistanceType;
00192 
00193       // concept requirements
00194       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00195             _RandomAccessIterator>)
00196       __glibcxx_requires_valid_range(__first, __last);
00197       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00198       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
00199 
00200       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
00201       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
00202                        _DistanceType(0), _GLIBCXX_MOVE(__value),
00203                        __gnu_cxx::__ops::__iter_comp_val(__comp));
00204     }
00205 
00206   template<typename _RandomAccessIterator, typename _Distance,
00207            typename _Tp, typename _Compare>
00208     void
00209     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00210                   _Distance __len, _Tp __value, _Compare __comp)
00211     {
00212       const _Distance __topIndex = __holeIndex;
00213       _Distance __secondChild = __holeIndex;
00214       while (__secondChild < (__len - 1) / 2)
00215         {
00216           __secondChild = 2 * (__secondChild + 1);
00217           if (__comp(__first + __secondChild,
00218                      __first + (__secondChild - 1)))
00219             __secondChild--;
00220           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
00221           __holeIndex = __secondChild;
00222         }
00223       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
00224         {
00225           __secondChild = 2 * (__secondChild + 1);
00226           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
00227                                                      + (__secondChild - 1)));
00228           __holeIndex = __secondChild - 1;
00229         }
00230       std::__push_heap(__first, __holeIndex, __topIndex, 
00231                        _GLIBCXX_MOVE(__value),
00232                        __gnu_cxx::__ops::__iter_comp_val(__comp));
00233     }
00234 
00235   template<typename _RandomAccessIterator, typename _Compare>
00236     inline void
00237     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00238                _RandomAccessIterator __result, _Compare __comp)
00239     {
00240       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00241         _ValueType;
00242       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00243         _DistanceType;
00244 
00245       _ValueType __value = _GLIBCXX_MOVE(*__result);
00246       *__result = _GLIBCXX_MOVE(*__first);
00247       std::__adjust_heap(__first, _DistanceType(0),
00248                          _DistanceType(__last - __first),
00249                          _GLIBCXX_MOVE(__value), __comp);
00250     }
00251 
00252   /**
00253    *  @brief  Pop an element off a heap.
00254    *  @param  __first  Start of heap.
00255    *  @param  __last   End of heap.
00256    *  @pre    [__first, __last) is a valid, non-empty range.
00257    *  @ingroup heap_algorithms
00258    *
00259    *  This operation pops the top of the heap.  The elements __first
00260    *  and __last-1 are swapped and [__first,__last-1) is made into a
00261    *  heap.
00262   */
00263   template<typename _RandomAccessIterator>
00264     inline void
00265     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00266     {
00267       // concept requirements
00268       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00269             _RandomAccessIterator>)
00270       __glibcxx_function_requires(_LessThanComparableConcept<
00271         typename iterator_traits<_RandomAccessIterator>::value_type>)
00272       __glibcxx_requires_non_empty_range(__first, __last);
00273       __glibcxx_requires_valid_range(__first, __last);
00274       __glibcxx_requires_irreflexive(__first, __last);
00275       __glibcxx_requires_heap(__first, __last);
00276 
00277       if (__last - __first > 1)
00278         {
00279           --__last;
00280           std::__pop_heap(__first, __last, __last,
00281                           __gnu_cxx::__ops::__iter_less_iter());
00282         }
00283     }
00284 
00285   /**
00286    *  @brief  Pop an element off a heap using comparison functor.
00287    *  @param  __first  Start of heap.
00288    *  @param  __last   End of heap.
00289    *  @param  __comp   Comparison functor to use.
00290    *  @ingroup heap_algorithms
00291    *
00292    *  This operation pops the top of the heap.  The elements __first
00293    *  and __last-1 are swapped and [__first,__last-1) is made into a
00294    *  heap.  Comparisons are made using comp.
00295   */
00296   template<typename _RandomAccessIterator, typename _Compare>
00297     inline void
00298     pop_heap(_RandomAccessIterator __first,
00299              _RandomAccessIterator __last, _Compare __comp)
00300     {
00301       // concept requirements
00302       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00303             _RandomAccessIterator>)
00304       __glibcxx_requires_valid_range(__first, __last);
00305       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00306       __glibcxx_requires_non_empty_range(__first, __last);
00307       __glibcxx_requires_heap_pred(__first, __last, __comp);
00308 
00309       if (__last - __first > 1)
00310         {
00311           --__last;
00312           std::__pop_heap(__first, __last, __last,
00313                           __gnu_cxx::__ops::__iter_comp_iter(__comp));
00314         }
00315     }
00316 
00317   template<typename _RandomAccessIterator, typename _Compare>
00318     void
00319     __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00320                 _Compare __comp)
00321     {
00322       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00323           _ValueType;
00324       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00325           _DistanceType;
00326 
00327       if (__last - __first < 2)
00328         return;
00329 
00330       const _DistanceType __len = __last - __first;
00331       _DistanceType __parent = (__len - 2) / 2;
00332       while (true)
00333         {
00334           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
00335           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
00336                              __comp);
00337           if (__parent == 0)
00338             return;
00339           __parent--;
00340         }
00341     }
00342   
00343   /**
00344    *  @brief  Construct a heap over a range.
00345    *  @param  __first  Start of heap.
00346    *  @param  __last   End of heap.
00347    *  @ingroup heap_algorithms
00348    *
00349    *  This operation makes the elements in [__first,__last) into a heap.
00350   */
00351   template<typename _RandomAccessIterator>
00352     inline void
00353     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00354     {
00355       // concept requirements
00356       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00357             _RandomAccessIterator>)
00358       __glibcxx_function_requires(_LessThanComparableConcept<
00359             typename iterator_traits<_RandomAccessIterator>::value_type>)
00360       __glibcxx_requires_valid_range(__first, __last);
00361       __glibcxx_requires_irreflexive(__first, __last);
00362 
00363       std::__make_heap(__first, __last,
00364                        __gnu_cxx::__ops::__iter_less_iter());
00365     }
00366 
00367   /**
00368    *  @brief  Construct a heap over a range using comparison functor.
00369    *  @param  __first  Start of heap.
00370    *  @param  __last   End of heap.
00371    *  @param  __comp   Comparison functor to use.
00372    *  @ingroup heap_algorithms
00373    *
00374    *  This operation makes the elements in [__first,__last) into a heap.
00375    *  Comparisons are made using __comp.
00376   */
00377   template<typename _RandomAccessIterator, typename _Compare>
00378     inline void
00379     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00380               _Compare __comp)
00381     {
00382       // concept requirements
00383       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00384             _RandomAccessIterator>)
00385       __glibcxx_requires_valid_range(__first, __last);
00386       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00387 
00388       std::__make_heap(__first, __last,
00389                        __gnu_cxx::__ops::__iter_comp_iter(__comp));
00390     }
00391 
00392   template<typename _RandomAccessIterator, typename _Compare>
00393     void
00394     __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00395                 _Compare __comp)
00396     {
00397       while (__last - __first > 1)
00398         {
00399           --__last;
00400           std::__pop_heap(__first, __last, __last, __comp);
00401         }
00402     }
00403 
00404   /**
00405    *  @brief  Sort a heap.
00406    *  @param  __first  Start of heap.
00407    *  @param  __last   End of heap.
00408    *  @ingroup heap_algorithms
00409    *
00410    *  This operation sorts the valid heap in the range [__first,__last).
00411   */
00412   template<typename _RandomAccessIterator>
00413     inline void
00414     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00415     {
00416       // concept requirements
00417       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00418             _RandomAccessIterator>)
00419       __glibcxx_function_requires(_LessThanComparableConcept<
00420             typename iterator_traits<_RandomAccessIterator>::value_type>)
00421       __glibcxx_requires_valid_range(__first, __last);
00422       __glibcxx_requires_irreflexive(__first, __last);
00423       __glibcxx_requires_heap(__first, __last);
00424 
00425       std::__sort_heap(__first, __last,
00426                        __gnu_cxx::__ops::__iter_less_iter());
00427     }
00428 
00429   /**
00430    *  @brief  Sort a heap using comparison functor.
00431    *  @param  __first  Start of heap.
00432    *  @param  __last   End of heap.
00433    *  @param  __comp   Comparison functor to use.
00434    *  @ingroup heap_algorithms
00435    *
00436    *  This operation sorts the valid heap in the range [__first,__last).
00437    *  Comparisons are made using __comp.
00438   */
00439   template<typename _RandomAccessIterator, typename _Compare>
00440     inline void
00441     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00442               _Compare __comp)
00443     {
00444       // concept requirements
00445       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00446             _RandomAccessIterator>)
00447       __glibcxx_requires_valid_range(__first, __last);
00448       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00449       __glibcxx_requires_heap_pred(__first, __last, __comp);
00450 
00451       std::__sort_heap(__first, __last,
00452                        __gnu_cxx::__ops::__iter_comp_iter(__comp));
00453     }
00454 
00455 #if __cplusplus >= 201103L
00456   /**
00457    *  @brief  Search the end of a heap.
00458    *  @param  __first  Start of range.
00459    *  @param  __last   End of range.
00460    *  @return  An iterator pointing to the first element not in the heap.
00461    *  @ingroup heap_algorithms
00462    *
00463    *  This operation returns the last iterator i in [__first, __last) for which
00464    *  the range [__first, i) is a heap.
00465   */
00466   template<typename _RandomAccessIterator>
00467     inline _RandomAccessIterator
00468     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
00469     {
00470       // concept requirements
00471       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00472             _RandomAccessIterator>)
00473       __glibcxx_function_requires(_LessThanComparableConcept<
00474             typename iterator_traits<_RandomAccessIterator>::value_type>)
00475       __glibcxx_requires_valid_range(__first, __last);
00476       __glibcxx_requires_irreflexive(__first, __last);
00477 
00478       return __first + 
00479         std::__is_heap_until(__first, std::distance(__first, __last),
00480                              __gnu_cxx::__ops::__iter_less_iter());
00481     }
00482 
00483   /**
00484    *  @brief  Search the end of a heap using comparison functor.
00485    *  @param  __first  Start of range.
00486    *  @param  __last   End of range.
00487    *  @param  __comp   Comparison functor to use.
00488    *  @return  An iterator pointing to the first element not in the heap.
00489    *  @ingroup heap_algorithms
00490    *
00491    *  This operation returns the last iterator i in [__first, __last) for which
00492    *  the range [__first, i) is a heap.  Comparisons are made using __comp.
00493   */
00494   template<typename _RandomAccessIterator, typename _Compare>
00495     inline _RandomAccessIterator
00496     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
00497                   _Compare __comp)
00498     {
00499       // concept requirements
00500       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00501             _RandomAccessIterator>)
00502       __glibcxx_requires_valid_range(__first, __last);
00503       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
00504 
00505       return __first
00506         + std::__is_heap_until(__first, std::distance(__first, __last),
00507                                __gnu_cxx::__ops::__iter_comp_iter(__comp));
00508     }
00509 
00510   /**
00511    *  @brief  Determines whether a range is a heap.
00512    *  @param  __first  Start of range.
00513    *  @param  __last   End of range.
00514    *  @return  True if range is a heap, false otherwise.
00515    *  @ingroup heap_algorithms
00516   */
00517   template<typename _RandomAccessIterator>
00518     inline bool
00519     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00520     { return std::is_heap_until(__first, __last) == __last; }
00521 
00522   /**
00523    *  @brief  Determines whether a range is a heap using comparison functor.
00524    *  @param  __first  Start of range.
00525    *  @param  __last   End of range.
00526    *  @param  __comp   Comparison functor to use.
00527    *  @return  True if range is a heap, false otherwise.
00528    *  @ingroup heap_algorithms
00529   */
00530   template<typename _RandomAccessIterator, typename _Compare>
00531     inline bool
00532     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00533             _Compare __comp)
00534     { return std::is_heap_until(__first, __last, __comp) == __last; }
00535 #endif
00536 
00537 _GLIBCXX_END_NAMESPACE_VERSION
00538 } // namespace
00539 
00540 #endif /* _STL_HEAP_H */