stl_heap.h

Go to the documentation of this file.
00001 // Heap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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 _CPP_BITS_STL_HEAP_H
00061 #define _CPP_BITS_STL_HEAP_H 1
00062 
00063 namespace std
00064 {
00065 
00066   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
00067 
00068   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
00069     void 
00070     __push_heap(_RandomAccessIterator __first,
00071         _Distance __holeIndex, _Distance __topIndex, _Tp __value)
00072     {
00073       _Distance __parent = (__holeIndex - 1) / 2;
00074       while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
00075     *(__first + __holeIndex) = *(__first + __parent);
00076     __holeIndex = __parent;
00077     __parent = (__holeIndex - 1) / 2;
00078       }    
00079       *(__first + __holeIndex) = __value;
00080     }
00081 
00082   template<typename _RandomAccessIterator>
00083     inline void 
00084     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00085     {
00086       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00087       _ValueType;
00088       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00089       _DistanceType;
00090 
00091       // concept requirements
00092       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00093         _RandomAccessIterator>)
00094       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
00095 
00096       __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
00097           _ValueType(*(__last - 1)));
00098     }
00099 
00100   template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 
00101         typename _Compare>
00102     void
00103     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00104         _Distance __topIndex, _Tp __value, _Compare __comp)
00105     {
00106       _Distance __parent = (__holeIndex - 1) / 2;
00107       while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
00108     *(__first + __holeIndex) = *(__first + __parent);
00109     __holeIndex = __parent;
00110     __parent = (__holeIndex - 1) / 2;
00111       }
00112       *(__first + __holeIndex) = __value;
00113     }
00114 
00115   template<typename _RandomAccessIterator, typename _Compare>
00116     inline void 
00117     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00118           _Compare __comp)
00119     {
00120       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00121       _ValueType;
00122       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00123       _DistanceType;
00124 
00125       // concept requirements
00126       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00127         _RandomAccessIterator>)
00128 
00129       __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
00130           _ValueType(*(__last - 1)), __comp);
00131     }
00132 
00133   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
00134     void 
00135     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00136           _Distance __len, _Tp __value)
00137     {
00138       _Distance __topIndex = __holeIndex;
00139       _Distance __secondChild = 2 * __holeIndex + 2;
00140       while (__secondChild < __len) {
00141     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
00142       __secondChild--;
00143     *(__first + __holeIndex) = *(__first + __secondChild);
00144     __holeIndex = __secondChild;
00145     __secondChild = 2 * (__secondChild + 1);
00146       }
00147       if (__secondChild == __len) {
00148     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00149     __holeIndex = __secondChild - 1;
00150       }
00151       __push_heap(__first, __holeIndex, __topIndex, __value);
00152     }
00153 
00154   template<typename _RandomAccessIterator, typename _Tp>
00155     inline void 
00156     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00157            _RandomAccessIterator __result, _Tp __value)
00158     {
00159       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
00160       *__result = *__first;
00161       __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
00162     }
00163 
00164   template<typename _RandomAccessIterator>
00165     inline void
00166     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00167     {
00168       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
00169 
00170       // concept requirements
00171       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00172         _RandomAccessIterator>)
00173       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
00174 
00175       __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
00176     }
00177 
00178   template<typename _RandomAccessIterator, typename _Distance,
00179        typename _Tp, typename _Compare>
00180     void
00181     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00182           _Distance __len, _Tp __value, _Compare __comp)
00183     {
00184       _Distance __topIndex = __holeIndex;
00185       _Distance __secondChild = 2 * __holeIndex + 2;
00186       while (__secondChild < __len) {
00187     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
00188       __secondChild--;
00189     *(__first + __holeIndex) = *(__first + __secondChild);
00190     __holeIndex = __secondChild;
00191     __secondChild = 2 * (__secondChild + 1);
00192       }
00193       if (__secondChild == __len) {
00194     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00195     __holeIndex = __secondChild - 1;
00196       }
00197       __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
00198     }
00199 
00200   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
00201     inline void 
00202     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00203            _RandomAccessIterator __result, _Tp __value, _Compare __comp)
00204     {
00205       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
00206       *__result = *__first;
00207       __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
00208             __value, __comp);
00209     }
00210 
00211   template<typename _RandomAccessIterator, typename _Compare>
00212     inline void 
00213     pop_heap(_RandomAccessIterator __first,
00214          _RandomAccessIterator __last, _Compare __comp)
00215     {
00216       // concept requirements
00217       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00218         _RandomAccessIterator>)
00219 
00220       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
00221       __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
00222     }
00223 
00224   template<typename _RandomAccessIterator>
00225     void 
00226     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00227     {
00228       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00229       _ValueType;
00230       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00231       _DistanceType;
00232 
00233       // concept requirements
00234       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00235         _RandomAccessIterator>)
00236       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
00237 
00238       if (__last - __first < 2) return;
00239       _DistanceType __len = __last - __first;
00240       _DistanceType __parent = (__len - 2)/2;
00241     
00242       while (true) {
00243     __adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent)));
00244     if (__parent == 0) return;
00245     __parent--;
00246       }
00247     }
00248 
00249   template<typename _RandomAccessIterator, typename _Compare>
00250     inline void 
00251     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00252           _Compare __comp)
00253     {
00254       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00255       _ValueType;
00256       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00257       _DistanceType;
00258 
00259       // concept requirements
00260       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00261         _RandomAccessIterator>)
00262 
00263       if (__last - __first < 2) return;
00264       _DistanceType __len = __last - __first;
00265       _DistanceType __parent = (__len - 2)/2;
00266     
00267       while (true) {
00268     __adjust_heap(__first, __parent, __len,
00269                   _ValueType(*(__first + __parent)), __comp);
00270     if (__parent == 0) return;
00271     __parent--;
00272       }
00273     }
00274 
00275   template<typename _RandomAccessIterator>
00276     void
00277     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00278     {
00279       // concept requirements
00280       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00281         _RandomAccessIterator>)
00282       __glibcpp_function_requires(_LessThanComparableConcept<
00283         typename iterator_traits<_RandomAccessIterator>::value_type>)
00284 
00285       while (__last - __first > 1)
00286     pop_heap(__first, __last--);
00287     }
00288 
00289   template<typename _RandomAccessIterator, typename _Compare>
00290     void 
00291     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00292           _Compare __comp)
00293     {
00294       // concept requirements
00295       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00296         _RandomAccessIterator>)
00297 
00298       while (__last - __first > 1)
00299     pop_heap(__first, __last--, __comp);
00300     }
00301 
00302 } // namespace std
00303 
00304 #endif /* _CPP_BITS_STL_HEAP_H */
00305 
00306 // Local Variables:
00307 // mode:C++
00308 // End:

Generated on Thu Feb 10 23:22:58 2005 for libstdc++-v3 Source by  doxygen 1.4.0