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