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
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 2, 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 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /*
00032  *
00033  * Copyright (c) 1994
00034  * Hewlett-Packard Company
00035  *
00036  * Permission to use, copy, modify, distribute and sell this software
00037  * and its documentation for any purpose is hereby granted without fee,
00038  * provided that the above copyright notice appear in all copies and
00039  * that both that copyright notice and this permission notice appear
00040  * in supporting documentation.  Hewlett-Packard Company makes no
00041  * representations about the suitability of this software for any
00042  * purpose.  It is provided "as is" without express or implied warranty.
00043  *
00044  * Copyright (c) 1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /** @file stl_heap.h
00057  *  This is an internal header file, included by other library headers.
00058  *  You should not attempt to use it directly.
00059  */
00060 
00061 #ifndef _STL_HEAP_H
00062 #define _STL_HEAP_H 1
00063 
00064 #include <debug/debug.h>
00065 #include <bits/stl_move.h>
00066 
00067 _GLIBCXX_BEGIN_NAMESPACE(std)
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
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
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
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       std::__pop_heap(__first, __last - 1, __last - 1);
00289     }
00290 
00291   template<typename _RandomAccessIterator, typename _Distance,
00292        typename _Tp, typename _Compare>
00293     void
00294     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00295           _Distance __len, _Tp __value, _Compare __comp)
00296     {
00297       const _Distance __topIndex = __holeIndex;
00298       _Distance __secondChild = __holeIndex;
00299       while (__secondChild < (__len - 1) / 2)
00300     {
00301       __secondChild = 2 * (__secondChild + 1);
00302       if (__comp(*(__first + __secondChild),
00303              *(__first + (__secondChild - 1))))
00304         __secondChild--;
00305       *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
00306       __holeIndex = __secondChild;
00307     }
00308       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
00309     {
00310       __secondChild = 2 * (__secondChild + 1);
00311       *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
00312                              + (__secondChild - 1)));
00313       __holeIndex = __secondChild - 1;
00314     }
00315       std::__push_heap(__first, __holeIndex, __topIndex, 
00316                _GLIBCXX_MOVE(__value), __comp);      
00317     }
00318 
00319   template<typename _RandomAccessIterator, typename _Compare>
00320     inline void
00321     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00322            _RandomAccessIterator __result, _Compare __comp)
00323     {
00324       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00325     _ValueType;
00326       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00327     _DistanceType;
00328 
00329       _ValueType __value = _GLIBCXX_MOVE(*__result);
00330       *__result = _GLIBCXX_MOVE(*__first);
00331       std::__adjust_heap(__first, _DistanceType(0),
00332              _DistanceType(__last - __first),
00333              _GLIBCXX_MOVE(__value), __comp);
00334     }
00335 
00336   /**
00337    *  @brief  Pop an element off a heap using comparison functor.
00338    *  @param  first  Start of heap.
00339    *  @param  last   End of heap.
00340    *  @param  comp   Comparison functor to use.
00341    *  @ingroup heap
00342    *
00343    *  This operation pops the top of the heap.  The elements first and last-1
00344    *  are swapped and [first,last-1) is made into a heap.  Comparisons are
00345    *  made using comp.
00346   */
00347   template<typename _RandomAccessIterator, typename _Compare>
00348     inline void
00349     pop_heap(_RandomAccessIterator __first,
00350          _RandomAccessIterator __last, _Compare __comp)
00351     {
00352       // concept requirements
00353       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00354         _RandomAccessIterator>)
00355       __glibcxx_requires_valid_range(__first, __last);
00356       __glibcxx_requires_heap_pred(__first, __last, __comp);
00357 
00358       std::__pop_heap(__first, __last - 1, __last - 1, __comp);
00359     }
00360 
00361   /**
00362    *  @brief  Construct a heap over a range.
00363    *  @param  first  Start of heap.
00364    *  @param  last   End of heap.
00365    *  @ingroup heap
00366    *
00367    *  This operation makes the elements in [first,last) into a heap.
00368   */
00369   template<typename _RandomAccessIterator>
00370     void
00371     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00372     {
00373       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00374       _ValueType;
00375       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00376       _DistanceType;
00377 
00378       // concept requirements
00379       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00380         _RandomAccessIterator>)
00381       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
00382       __glibcxx_requires_valid_range(__first, __last);
00383 
00384       if (__last - __first < 2)
00385     return;
00386 
00387       const _DistanceType __len = __last - __first;
00388       _DistanceType __parent = (__len - 2) / 2;
00389       while (true)
00390     {
00391       _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
00392       std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
00393       if (__parent == 0)
00394         return;
00395       __parent--;
00396     }
00397     }
00398 
00399   /**
00400    *  @brief  Construct a heap over a range using comparison functor.
00401    *  @param  first  Start of heap.
00402    *  @param  last   End of heap.
00403    *  @param  comp   Comparison functor to use.
00404    *  @ingroup heap
00405    *
00406    *  This operation makes the elements in [first,last) into a heap.
00407    *  Comparisons are made using comp.
00408   */
00409   template<typename _RandomAccessIterator, typename _Compare>
00410     void
00411     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00412           _Compare __comp)
00413     {
00414       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00415       _ValueType;
00416       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00417       _DistanceType;
00418 
00419       // concept requirements
00420       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00421         _RandomAccessIterator>)
00422       __glibcxx_requires_valid_range(__first, __last);
00423 
00424       if (__last - __first < 2)
00425     return;
00426 
00427       const _DistanceType __len = __last - __first;
00428       _DistanceType __parent = (__len - 2) / 2;
00429       while (true)
00430     {
00431       _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
00432       std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
00433                  __comp);
00434       if (__parent == 0)
00435         return;
00436       __parent--;
00437     }
00438     }
00439 
00440   /**
00441    *  @brief  Sort a heap.
00442    *  @param  first  Start of heap.
00443    *  @param  last   End of heap.
00444    *  @ingroup heap
00445    *
00446    *  This operation sorts the valid heap in the range [first,last).
00447   */
00448   template<typename _RandomAccessIterator>
00449     void
00450     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00451     {
00452       // concept requirements
00453       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00454         _RandomAccessIterator>)
00455       __glibcxx_function_requires(_LessThanComparableConcept<
00456         typename iterator_traits<_RandomAccessIterator>::value_type>)
00457       __glibcxx_requires_valid_range(__first, __last);
00458       __glibcxx_requires_heap(__first, __last);
00459 
00460       while (__last - __first > 1)
00461     std::pop_heap(__first, _RandomAccessIterator(__last--));
00462     }
00463 
00464   /**
00465    *  @brief  Sort a heap using comparison functor.
00466    *  @param  first  Start of heap.
00467    *  @param  last   End of heap.
00468    *  @param  comp   Comparison functor to use.
00469    *  @ingroup heap
00470    *
00471    *  This operation sorts the valid heap in the range [first,last).
00472    *  Comparisons are made using comp.
00473   */
00474   template<typename _RandomAccessIterator, typename _Compare>
00475     void
00476     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00477           _Compare __comp)
00478     {
00479       // concept requirements
00480       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00481         _RandomAccessIterator>)
00482       __glibcxx_requires_valid_range(__first, __last);
00483       __glibcxx_requires_heap_pred(__first, __last, __comp);
00484 
00485       while (__last - __first > 1)
00486     std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);
00487     }
00488 
00489 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00490   /**
00491    *  @brief  Search the end of a heap.
00492    *  @param  first  Start of range.
00493    *  @param  last   End of range.
00494    *  @return  An iterator pointing to the first element not in the heap.
00495    *  @ingroup heap
00496    *
00497    *  This operation returns the last iterator i in [first, last) for which
00498    *  the range [first, i) is a heap.
00499   */
00500   template<typename _RandomAccessIterator>
00501     inline _RandomAccessIterator
00502     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
00503     {
00504       // concept requirements
00505       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00506         _RandomAccessIterator>)
00507       __glibcxx_function_requires(_LessThanComparableConcept<
00508         typename iterator_traits<_RandomAccessIterator>::value_type>)
00509       __glibcxx_requires_valid_range(__first, __last);
00510 
00511       return __first + std::__is_heap_until(__first, std::distance(__first,
00512                                    __last));
00513     }
00514 
00515   /**
00516    *  @brief  Search the end of a heap using comparison functor.
00517    *  @param  first  Start of range.
00518    *  @param  last   End of range.
00519    *  @param  comp   Comparison functor to use.
00520    *  @return  An iterator pointing to the first element not in the heap.
00521    *  @ingroup heap
00522    *
00523    *  This operation returns the last iterator i in [first, last) for which
00524    *  the range [first, i) is a heap.  Comparisons are made using comp.
00525   */
00526   template<typename _RandomAccessIterator, typename _Compare>
00527     inline _RandomAccessIterator
00528     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
00529           _Compare __comp)
00530     {
00531       // concept requirements
00532       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00533         _RandomAccessIterator>)
00534       __glibcxx_requires_valid_range(__first, __last);
00535 
00536       return __first + std::__is_heap_until(__first, std::distance(__first,
00537                                    __last),
00538                         __comp);
00539     }
00540 
00541   /**
00542    *  @brief  Determines whether a range is a heap.
00543    *  @param  first  Start of range.
00544    *  @param  last   End of range.
00545    *  @return  True if range is a heap, false otherwise.
00546    *  @ingroup heap
00547   */
00548   template<typename _RandomAccessIterator>
00549     inline bool
00550     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00551     { return std::is_heap_until(__first, __last) == __last; }
00552 
00553   /**
00554    *  @brief  Determines whether a range is a heap using comparison functor.
00555    *  @param  first  Start of range.
00556    *  @param  last   End of range.
00557    *  @param  comp   Comparison functor to use.
00558    *  @return  True if range is a heap, false otherwise.
00559    *  @ingroup heap
00560   */
00561   template<typename _RandomAccessIterator, typename _Compare>
00562     inline bool
00563     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00564         _Compare __comp)
00565     { return std::is_heap_until(__first, __last, __comp) == __last; }
00566 #endif
00567 
00568 _GLIBCXX_END_NAMESPACE
00569 
00570 #endif /* _STL_HEAP_H */

Generated on Wed Mar 26 00:43:14 2008 for libstdc++ by  doxygen 1.5.1