# stl_heap.h

Go to the documentation of this file.

    00001 // Heap implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2004, 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License along
    00017 // with this library; see the file COPYING.  If not, write to the Free
    00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00019 // USA.
    00020
    00021 // As a special exception, you may use this file as part of a free software
    00022 // library without restriction.  Specifically, if other files instantiate
    00023 // templates or use macros or inline functions from this file, or you compile
    00024 // this file and link it with other files to produce an executable, this
    00025 // file does not by itself cause the resulting executable to be covered by
    00026 // the GNU General Public License.  This exception does not however
    00027 // invalidate any other reasons why the executable file might be covered by
    00028 // the GNU General Public License.
    00029
    00030 /*
    00031  *
    00032  * Copyright (c) 1994
    00033  * Hewlett-Packard Company
    00034  *
    00035  * Permission to use, copy, modify, distribute and sell this software
    00036  * and its documentation for any purpose is hereby granted without fee,
    00037  * provided that the above copyright notice appear in all copies and
    00038  * that both that copyright notice and this permission notice appear
    00039  * in supporting documentation.  Hewlett-Packard Company makes no
    00040  * representations about the suitability of this software for any
    00041  * purpose.  It is provided "as is" without express or implied warranty.
    00042  *
    00043  * Copyright (c) 1997
    00044  * Silicon Graphics Computer Systems, Inc.
    00045  *
    00046  * Permission to use, copy, modify, distribute and sell this software
    00047  * and its documentation for any purpose is hereby granted without fee,
    00048  * provided that the above copyright notice appear in all copies and
    00049  * that both that copyright notice and this permission notice appear
    00050  * in supporting documentation.  Silicon Graphics makes no
    00051  * representations about the suitability of this software for any
    00052  * purpose.  It is provided "as is" without express or implied warranty.
    00053  */
    00054
    00055 /** @file stl_heap.h
    00056  *  This is an internal header file, included by other library headers.
    00057  *  You should not attempt to use it directly.
    00058  */
    00059
    00060 #ifndef _STL_HEAP_H
    00061 #define _STL_HEAP_H 1
    00062
    00063 #include <debug/debug.h>
    00064
    00065 _GLIBCXX_BEGIN_NAMESPACE(std)
    00066
    00067   // is_heap, a predicate testing whether or not a range is
    00068   // a heap.  This function is an extension, not part of the C++
    00069   // standard.
    00070   template<typename _RandomAccessIterator, typename _Distance>
    00071     bool
    00072     __is_heap(_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 false;
    00079       if ((__child & 1) == 0)
    00080         ++__parent;
    00081     }
    00082       return true;
    00083     }
    00084
    00085   template<typename _RandomAccessIterator, typename _Distance,
    00086            typename _StrictWeakOrdering>
    00087     bool
    00088     __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
    00089           _Distance __n)
    00090     {
    00091       _Distance __parent = 0;
    00092       for (_Distance __child = 1; __child < __n; ++__child)
    00093     {
    00094       if (__comp(__first[__parent], __first[__child]))
    00095         return false;
    00096       if ((__child & 1) == 0)
    00097         ++__parent;
    00098     }
    00099       return true;
    00100     }
    00101
    00102   template<typename _RandomAccessIterator>
    00103     bool
    00104     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00105     { return std::__is_heap(__first, std::distance(__first, __last)); }
    00106
    00107   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
    00108     bool
    00109     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00110         _StrictWeakOrdering __comp)
    00111     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
    00112
    00113   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
    00114
    00115   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
    00116     void
    00117     __push_heap(_RandomAccessIterator __first,
    00118         _Distance __holeIndex, _Distance __topIndex, _Tp __value)
    00119     {
    00120       _Distance __parent = (__holeIndex - 1) / 2;
    00121       while (__holeIndex > __topIndex && *(__first + __parent) < __value)
    00122     {
    00123       *(__first + __holeIndex) = *(__first + __parent);
    00124       __holeIndex = __parent;
    00125       __parent = (__holeIndex - 1) / 2;
    00126     }
    00127       *(__first + __holeIndex) = __value;
    00128     }
    00129
    00130   /**
    00131    *  @brief  Push an element onto a heap.
    00132    *  @param  first  Start of heap.
    00133    *  @param  last   End of heap + element.
    00134    *  @ingroup heap
    00135    *
    00136    *  This operation pushes the element at last-1 onto the valid heap over the
    00137    *  range [first,last-1).  After completion, [first,last) is a valid heap.
    00138   */
    00139   template<typename _RandomAccessIterator>
    00140     inline void
    00141     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00142     {
    00143       typedef typename iterator_traits<_RandomAccessIterator>::value_type
    00144       _ValueType;
    00145       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    00146       _DistanceType;
    00147
    00148       // concept requirements
    00149       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00150         _RandomAccessIterator>)
    00151       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
    00152       __glibcxx_requires_valid_range(__first, __last);
    00153       //      __glibcxx_requires_heap(__first, __last - 1);
    00154
    00155       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
    00156                _DistanceType(0), _ValueType(*(__last - 1)));
    00157     }
    00158
    00159   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
    00160         typename _Compare>
    00161     void
    00162     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
    00163         _Distance __topIndex, _Tp __value, _Compare __comp)
    00164     {
    00165       _Distance __parent = (__holeIndex - 1) / 2;
    00166       while (__holeIndex > __topIndex
    00167          && __comp(*(__first + __parent), __value))
    00168     {
    00169       *(__first + __holeIndex) = *(__first + __parent);
    00170       __holeIndex = __parent;
    00171       __parent = (__holeIndex - 1) / 2;
    00172     }
    00173       *(__first + __holeIndex) = __value;
    00174     }
    00175
    00176   /**
    00177    *  @brief  Push an element onto a heap using comparison functor.
    00178    *  @param  first  Start of heap.
    00179    *  @param  last   End of heap + element.
    00180    *  @param  comp   Comparison functor.
    00181    *  @ingroup heap
    00182    *
    00183    *  This operation pushes the element at last-1 onto the valid heap over the
    00184    *  range [first,last-1).  After completion, [first,last) is a valid heap.
    00185    *  Compare operations are performed using comp.
    00186   */
    00187   template<typename _RandomAccessIterator, typename _Compare>
    00188     inline void
    00189     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00190           _Compare __comp)
    00191     {
    00192       typedef typename iterator_traits<_RandomAccessIterator>::value_type
    00193       _ValueType;
    00194       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    00195       _DistanceType;
    00196
    00197       // concept requirements
    00198       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00199         _RandomAccessIterator>)
    00200       __glibcxx_requires_valid_range(__first, __last);
    00201       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
    00202
    00203       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
    00204                _DistanceType(0), _ValueType(*(__last - 1)), __comp);
    00205     }
    00206
    00207   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
    00208     void
    00209     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
    00210           _Distance __len, _Tp __value)
    00211     {
    00212       const _Distance __topIndex = __holeIndex;
    00213       _Distance __secondChild = 2 * __holeIndex + 2;
    00214       while (__secondChild < __len)
    00215     {
    00216       if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
    00217         __secondChild--;
    00218       *(__first + __holeIndex) = *(__first + __secondChild);
    00219       __holeIndex = __secondChild;
    00220       __secondChild = 2 * (__secondChild + 1);
    00221     }
    00222       if (__secondChild == __len)
    00223     {
    00224       *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    00225       __holeIndex = __secondChild - 1;
    00226     }
    00227       std::__push_heap(__first, __holeIndex, __topIndex, __value);
    00228     }
    00229
    00230   template<typename _RandomAccessIterator, typename _Tp>
    00231     inline void
    00232     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00233            _RandomAccessIterator __result, _Tp __value)
    00234     {
    00235       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    00236     _Distance;
    00237       *__result = *__first;
    00238       std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
    00239              __value);
    00240     }
    00241
    00242   /**
    00243    *  @brief  Pop an element off a heap.
    00244    *  @param  first  Start of heap.
    00245    *  @param  last   End of heap.
    00246    *  @ingroup heap
    00247    *
    00248    *  This operation pops the top of the heap.  The elements first and last-1
    00249    *  are swapped and [first,last-1) is made into a heap.
    00250   */
    00251   template<typename _RandomAccessIterator>
    00252     inline void
    00253     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00254     {
    00255       typedef typename iterator_traits<_RandomAccessIterator>::value_type
    00256     _ValueType;
    00257
    00258       // concept requirements
    00259       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00260         _RandomAccessIterator>)
    00261       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
    00262       __glibcxx_requires_valid_range(__first, __last);
    00263       __glibcxx_requires_heap(__first, __last);
    00264
    00265       std::__pop_heap(__first, __last - 1, __last - 1,
    00266               _ValueType(*(__last - 1)));
    00267     }
    00268
    00269   template<typename _RandomAccessIterator, typename _Distance,
    00270        typename _Tp, typename _Compare>
    00271     void
    00272     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
    00273           _Distance __len, _Tp __value, _Compare __comp)
    00274     {
    00275       const _Distance __topIndex = __holeIndex;
    00276       _Distance __secondChild = 2 * __holeIndex + 2;
    00277       while (__secondChild < __len)
    00278     {
    00279       if (__comp(*(__first + __secondChild),
    00280              *(__first + (__secondChild - 1))))
    00281         __secondChild--;
    00282       *(__first + __holeIndex) = *(__first + __secondChild);
    00283       __holeIndex = __secondChild;
    00284       __secondChild = 2 * (__secondChild + 1);
    00285     }
    00286       if (__secondChild == __len)
    00287     {
    00288       *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    00289       __holeIndex = __secondChild - 1;
    00290     }
    00291       std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
    00292     }
    00293
    00294   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
    00295     inline void
    00296     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00297            _RandomAccessIterator __result, _Tp __value, _Compare __comp)
    00298     {
    00299       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    00300     _Distance;
    00301       *__result = *__first;
    00302       std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
    00303              __value, __comp);
    00304     }
    00305
    00306   /**
    00307    *  @brief  Pop an element off a heap using comparison functor.
    00308    *  @param  first  Start of heap.
    00309    *  @param  last   End of heap.
    00310    *  @param  comp   Comparison functor to use.
    00311    *  @ingroup heap
    00312    *
    00313    *  This operation pops the top of the heap.  The elements first and last-1
    00314    *  are swapped and [first,last-1) is made into a heap.  Comparisons are
    00315    *  made using comp.
    00316   */
    00317   template<typename _RandomAccessIterator, typename _Compare>
    00318     inline void
    00319     pop_heap(_RandomAccessIterator __first,
    00320          _RandomAccessIterator __last, _Compare __comp)
    00321     {
    00322       // concept requirements
    00323       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00324         _RandomAccessIterator>)
    00325       __glibcxx_requires_valid_range(__first, __last);
    00326       __glibcxx_requires_heap_pred(__first, __last, __comp);
    00327
    00328       typedef typename iterator_traits<_RandomAccessIterator>::value_type
    00329     _ValueType;
    00330       std::__pop_heap(__first, __last - 1, __last - 1,
    00331               _ValueType(*(__last - 1)), __comp);
    00332     }
    00333
    00334   /**
    00335    *  @brief  Construct a heap over a range.
    00336    *  @param  first  Start of heap.
    00337    *  @param  last   End of heap.
    00338    *  @ingroup heap
    00339    *
    00340    *  This operation makes the elements in [first,last) into a heap.
    00341   */
    00342   template<typename _RandomAccessIterator>
    00343     void
    00344     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00345     {
    00346       typedef typename iterator_traits<_RandomAccessIterator>::value_type
    00347       _ValueType;
    00348       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    00349       _DistanceType;
    00350
    00351       // concept requirements
    00352       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00353         _RandomAccessIterator>)
    00354       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
    00355       __glibcxx_requires_valid_range(__first, __last);
    00356
    00357       if (__last - __first < 2)
    00358     return;
    00359
    00360       const _DistanceType __len = __last - __first;
    00361       _DistanceType __parent = (__len - 2) / 2;
    00362       while (true)
    00363     {
    00364       std::__adjust_heap(__first, __parent, __len,
    00365                  _ValueType(*(__first + __parent)));
    00366       if (__parent == 0)
    00367         return;
    00368       __parent--;
    00369     }
    00370     }
    00371
    00372   /**
    00373    *  @brief  Construct a heap over a range using comparison functor.
    00374    *  @param  first  Start of heap.
    00375    *  @param  last   End of heap.
    00376    *  @param  comp   Comparison functor to use.
    00377    *  @ingroup heap
    00378    *
    00379    *  This operation makes the elements in [first,last) into a heap.
    00380    *  Comparisons are made using comp.
    00381   */
    00382   template<typename _RandomAccessIterator, typename _Compare>
    00383     inline void
    00384     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00385           _Compare __comp)
    00386     {
    00387       typedef typename iterator_traits<_RandomAccessIterator>::value_type
    00388       _ValueType;
    00389       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    00390       _DistanceType;
    00391
    00392       // concept requirements
    00393       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00394         _RandomAccessIterator>)
    00395       __glibcxx_requires_valid_range(__first, __last);
    00396
    00397       if (__last - __first < 2)
    00398     return;
    00399
    00400       const _DistanceType __len = __last - __first;
    00401       _DistanceType __parent = (__len - 2) / 2;
    00402       while (true)
    00403     {
    00404       std::__adjust_heap(__first, __parent, __len,
    00405                  _ValueType(*(__first + __parent)), __comp);
    00406       if (__parent == 0)
    00407         return;
    00408       __parent--;
    00409     }
    00410     }
    00411
    00412   /**
    00413    *  @brief  Sort a heap.
    00414    *  @param  first  Start of heap.
    00415    *  @param  last   End of heap.
    00416    *  @ingroup heap
    00417    *
    00418    *  This operation sorts the valid heap in the range [first,last).
    00419   */
    00420   template<typename _RandomAccessIterator>
    00421     void
    00422     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00423     {
    00424       // concept requirements
    00425       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00426         _RandomAccessIterator>)
    00427       __glibcxx_function_requires(_LessThanComparableConcept<
    00428         typename iterator_traits<_RandomAccessIterator>::value_type>)
    00429       __glibcxx_requires_valid_range(__first, __last);
    00430       //      __glibcxx_requires_heap(__first, __last);
    00431
    00432       while (__last - __first > 1)
    00433     std::pop_heap(__first, _RandomAccessIterator(__last--));
    00434     }
    00435
    00436   /**
    00437    *  @brief  Sort a heap using comparison functor.
    00438    *  @param  first  Start of heap.
    00439    *  @param  last   End of heap.
    00440    *  @param  comp   Comparison functor to use.
    00441    *  @ingroup heap
    00442    *
    00443    *  This operation sorts the valid heap in the range [first,last).
    00444    *  Comparisons are made using comp.
    00445   */
    00446   template<typename _RandomAccessIterator, typename _Compare>
    00447     void
    00448     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00449           _Compare __comp)
    00450     {
    00451       // concept requirements
    00452       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00453         _RandomAccessIterator>)
    00454       __glibcxx_requires_valid_range(__first, __last);
    00455       __glibcxx_requires_heap_pred(__first, __last, __comp);
    00456
    00457       while (__last - __first > 1)
    00458     std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);
    00459     }
    00460
    00461 _GLIBCXX_END_NAMESPACE
    00462
    00463 #endif /* _STL_HEAP_H */