Whole document tree
    

Whole document tree

stl_heap.h Source File
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

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 /* NOTE: This is an internal header file, included by other STL headers.
00056  *   You should not attempt to use it directly.
00057  */
00058 
00059 #ifndef _CPP_BITS_STL_HEAP_H
00060 #define _CPP_BITS_STL_HEAP_H 1
00061 
00062 namespace std
00063 {
00064 
00065 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
00066 
00067 template <class _RandomAccessIterator, class _Distance, class _Tp>
00068 void 
00069 __push_heap(_RandomAccessIterator __first,
00070             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
00071 {
00072   _Distance __parent = (__holeIndex - 1) / 2;
00073   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
00074     *(__first + __holeIndex) = *(__first + __parent);
00075     __holeIndex = __parent;
00076     __parent = (__holeIndex - 1) / 2;
00077   }    
00078   *(__first + __holeIndex) = __value;
00079 }
00080 
00081 template <class _RandomAccessIterator, class _Distance, class _Tp>
00082 inline void 
00083 __push_heap_aux(_RandomAccessIterator __first,
00084                 _RandomAccessIterator __last, _Distance*, _Tp*)
00085 {
00086   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
00087               _Tp(*(__last - 1)));
00088 }
00089 
00090 template <class _RandomAccessIterator>
00091 inline void 
00092 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00093 {
00094   // concept requirements
00095   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00096         _RandomAccessIterator>);
00097   __glibcpp_function_requires(_LessThanComparableConcept<
00098         typename iterator_traits<_RandomAccessIterator>::value_type>);
00099 
00100   __push_heap_aux(__first, __last,
00101                   __distance_type(__first), __value_type(__first));
00102 }
00103 
00104 template <class _RandomAccessIterator, class _Distance, class _Tp, 
00105           class _Compare>
00106 void
00107 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00108             _Distance __topIndex, _Tp __value, _Compare __comp)
00109 {
00110   _Distance __parent = (__holeIndex - 1) / 2;
00111   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
00112     *(__first + __holeIndex) = *(__first + __parent);
00113     __holeIndex = __parent;
00114     __parent = (__holeIndex - 1) / 2;
00115   }
00116   *(__first + __holeIndex) = __value;
00117 }
00118 
00119 template <class _RandomAccessIterator, class _Compare,
00120           class _Distance, class _Tp>
00121 inline void 
00122 __push_heap_aux(_RandomAccessIterator __first,
00123                 _RandomAccessIterator __last, _Compare __comp,
00124                 _Distance*, _Tp*) 
00125 {
00126   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
00127               _Tp(*(__last - 1)), __comp);
00128 }
00129 
00130 template <class _RandomAccessIterator, class _Compare>
00131 inline void 
00132 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00133           _Compare __comp)
00134 {
00135   // concept requirements
00136   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00137         _RandomAccessIterator>);
00138 
00139   __push_heap_aux(__first, __last, __comp,
00140                   __distance_type(__first), __value_type(__first));
00141 }
00142 
00143 template <class _RandomAccessIterator, class _Distance, class _Tp>
00144 void 
00145 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00146               _Distance __len, _Tp __value)
00147 {
00148   _Distance __topIndex = __holeIndex;
00149   _Distance __secondChild = 2 * __holeIndex + 2;
00150   while (__secondChild < __len) {
00151     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
00152       __secondChild--;
00153     *(__first + __holeIndex) = *(__first + __secondChild);
00154     __holeIndex = __secondChild;
00155     __secondChild = 2 * (__secondChild + 1);
00156   }
00157   if (__secondChild == __len) {
00158     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00159     __holeIndex = __secondChild - 1;
00160   }
00161   __push_heap(__first, __holeIndex, __topIndex, __value);
00162 }
00163 
00164 template <class _RandomAccessIterator, class _Tp, class _Distance>
00165 inline void 
00166 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00167            _RandomAccessIterator __result, _Tp __value, _Distance*)
00168 {
00169   *__result = *__first;
00170   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
00171 }
00172 
00173 template <class _RandomAccessIterator, class _Tp>
00174 inline void 
00175 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
00176                _Tp*)
00177 {
00178   __pop_heap(__first, __last - 1, __last - 1, 
00179              _Tp(*(__last - 1)), __distance_type(__first));
00180 }
00181 
00182 template <class _RandomAccessIterator>
00183 inline void pop_heap(_RandomAccessIterator __first, 
00184                      _RandomAccessIterator __last)
00185 {
00186   // concept requirements
00187   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00188         _RandomAccessIterator>);
00189   __glibcpp_function_requires(_LessThanComparableConcept<
00190         typename iterator_traits<_RandomAccessIterator>::value_type>);
00191 
00192   __pop_heap_aux(__first, __last, __value_type(__first));
00193 }
00194 
00195 template <class _RandomAccessIterator, class _Distance,
00196           class _Tp, class _Compare>
00197 void
00198 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00199               _Distance __len, _Tp __value, _Compare __comp)
00200 {
00201   _Distance __topIndex = __holeIndex;
00202   _Distance __secondChild = 2 * __holeIndex + 2;
00203   while (__secondChild < __len) {
00204     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
00205       __secondChild--;
00206     *(__first + __holeIndex) = *(__first + __secondChild);
00207     __holeIndex = __secondChild;
00208     __secondChild = 2 * (__secondChild + 1);
00209   }
00210   if (__secondChild == __len) {
00211     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00212     __holeIndex = __secondChild - 1;
00213   }
00214   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
00215 }
00216 
00217 template <class _RandomAccessIterator, class _Tp, class _Compare, 
00218           class _Distance>
00219 inline void 
00220 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00221            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
00222            _Distance*)
00223 {
00224   *__result = *__first;
00225   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
00226                 __value, __comp);
00227 }
00228 
00229 template <class _RandomAccessIterator, class _Tp, class _Compare>
00230 inline void 
00231 __pop_heap_aux(_RandomAccessIterator __first,
00232                _RandomAccessIterator __last, _Tp*, _Compare __comp)
00233 {
00234   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
00235              __distance_type(__first));
00236 }
00237 
00238 template <class _RandomAccessIterator, class _Compare>
00239 inline void 
00240 pop_heap(_RandomAccessIterator __first,
00241          _RandomAccessIterator __last, _Compare __comp)
00242 {
00243   // concept requirements
00244   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00245         _RandomAccessIterator>);
00246 
00247   __pop_heap_aux(__first, __last, __value_type(__first), __comp);
00248 }
00249 
00250 template <class _RandomAccessIterator, class _Tp, class _Distance>
00251 void 
00252 __make_heap(_RandomAccessIterator __first,
00253             _RandomAccessIterator __last, _Tp*, _Distance*)
00254 {
00255   if (__last - __first < 2) return;
00256   _Distance __len = __last - __first;
00257   _Distance __parent = (__len - 2)/2;
00258     
00259   while (true) {
00260     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
00261     if (__parent == 0) return;
00262     __parent--;
00263   }
00264 }
00265 
00266 template <class _RandomAccessIterator>
00267 inline void 
00268 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00269 {
00270   // concept requirements
00271   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00272         _RandomAccessIterator>);
00273   __glibcpp_function_requires(_LessThanComparableConcept<
00274         typename iterator_traits<_RandomAccessIterator>::value_type>);
00275 
00276   __make_heap(__first, __last,
00277               __value_type(__first), __distance_type(__first));
00278 }
00279 
00280 template <class _RandomAccessIterator, class _Compare,
00281           class _Tp, class _Distance>
00282 void
00283 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00284             _Compare __comp, _Tp*, _Distance*)
00285 {
00286   if (__last - __first < 2) return;
00287   _Distance __len = __last - __first;
00288   _Distance __parent = (__len - 2)/2;
00289     
00290   while (true) {
00291     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
00292                   __comp);
00293     if (__parent == 0) return;
00294     __parent--;
00295   }
00296 }
00297 
00298 template <class _RandomAccessIterator, class _Compare>
00299 inline void 
00300 make_heap(_RandomAccessIterator __first, 
00301           _RandomAccessIterator __last, _Compare __comp)
00302 {
00303   // concept requirements
00304   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00305         _RandomAccessIterator>);
00306 
00307   __make_heap(__first, __last, __comp,
00308               __value_type(__first), __distance_type(__first));
00309 }
00310 
00311 template <class _RandomAccessIterator>
00312 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00313 {
00314   // concept requirements
00315   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00316         _RandomAccessIterator>);
00317   __glibcpp_function_requires(_LessThanComparableConcept<
00318         typename iterator_traits<_RandomAccessIterator>::value_type>);
00319 
00320   while (__last - __first > 1)
00321     pop_heap(__first, __last--);
00322 }
00323 
00324 template <class _RandomAccessIterator, class _Compare>
00325 void 
00326 sort_heap(_RandomAccessIterator __first,
00327           _RandomAccessIterator __last, _Compare __comp)
00328 {
00329   // concept requirements
00330   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00331         _RandomAccessIterator>);
00332 
00333   while (__last - __first > 1)
00334     pop_heap(__first, __last--, __comp);
00335 }
00336 
00337 } // namespace std
00338 
00339 #endif /* _CPP_BITS_STL_HEAP_H */
00340 
00341 // Local Variables:
00342 // mode:C++
00343 // End:

Generated on Mon Apr 8 03:11:41 2002 for libstdc++-v3 Source by doxygen1.2.15