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

Generated on Thu Jul 23 21:16:20 2009 for libstdc++ by  doxygen 1.5.8