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