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