COCONUT API: stlp_pairheap.h Source File

00001 // Pair Heap implementation -*- C++ -*-
00002 
00003 // $Id: stlp_pairheap.h 347 2008-02-06 15:20:01Z schilly $
00004 // Copyright (C) 2003 Hermann Schichl
00005 //              using code templates from the Free Software Foundation
00006 //
00007 // This file is part of the COCONUT API.  This library is free
00008 // software; you can redistribute it and/or modify it under the
00009 // terms of the GNU General Public License as published by the
00010 // Free Software Foundation; either version 2, or (at your option)
00011 // any later version.
00012 
00013 // This library is distributed in the hope that it will be useful,
00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 // GNU General Public License for more details.
00017 
00018 // You should have received a copy of the GNU General Public License along
00019 // with this library; see the file COPYING.  If not, write to the Free
00020 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00021 // USA.
00022 
00023 // As a special exception, you may use this file as part of a free software
00024 // library without restriction.  Specifically, if other files instantiate
00025 // templates or use macros or inline functions from this file, or you compile
00026 // this file and link it with other files to produce an executable, this
00027 // file does not by itself cause the resulting executable to be covered by
00028 // the GNU General Public License.  This exception does not however
00029 // invalidate any other reasons why the executable file might be covered by
00030 // the GNU General Public License.
00031 
00037 #ifndef __STLP_PAIRHEAP_H
00038 #define __STLP_PAIRHEAP_H 1
00039 
00040 #if ( __GNUC__ == 3 && __GNUC_MINOR__ >= 4 || __GNUC__ >= 4 )
00041 #include <debug/debug.h>
00042 #endif
00043 
00044 namespace std
00045 {
00046 
00047   // Pair-Heap-manipulation functions:
00048   //            push_pair_heap, pop_pair_heap, make_pair_heap, sort_pair_heap.
00049 
00050   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
00051            typename _RandomAccessIteratorp, typename _Distancep, typename _Tpp>
00052     void 
00053     __push_pair_heap(_RandomAccessIterator __first,
00054                 _Distance __holeIndex, _Distance __topIndex, _Tp __value,
00055                 _RandomAccessIteratorp __firstp,
00056                 _Distancep __holeIndexp, _Distancep __topIndexp, _Tpp __valuep)
00057     {
00058       _Distance __parent = (__holeIndex - 1) / 2;
00059       _Distancep __parentp = (__holeIndexp - 1) / 2;
00060       while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
00061         *(__first + __holeIndex) = *(__first + __parent);
00062         *(__firstp + __holeIndexp) = *(__firstp + __parentp);
00063         __holeIndex = __parent;
00064         __holeIndexp = __parentp;
00065         __parent = (__holeIndex - 1) / 2;
00066         __parentp = (__holeIndexp - 1) / 2;
00067       }    
00068       *(__first + __holeIndex) = __value;
00069       *(__firstp + __holeIndexp) = __valuep;
00070     }
00071 
00072   template<typename _RandomAccessIterator, typename _RandomAccessIteratorp>
00073     inline void 
00074     push_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00075                _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp)
00076     {
00077       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00078           _ValueType;
00079       typedef typename iterator_traits<_RandomAccessIteratorp>::value_type
00080           _ValueTypep;
00081       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00082           _DistanceType;
00083       typedef typename iterator_traits<_RandomAccessIteratorp>::difference_type
00084           _DistanceTypep;
00085 
00086       // concept requirements
00087       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00088             _RandomAccessIterator>)
00089       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00090             _RandomAccessIteratorp>)
00091       __ISTLGLIBCXX_function_requires(_LessThanComparableConcept<_ValueType>)
00092       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00093       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00094 
00095       __push_pair_heap(__first, _DistanceType((__last - __first) - 1),
00096                   _DistanceType(0), _ValueType(*(__last - 1)),
00097                   __firstp, _DistanceTypep((__lastp - __firstp) - 1),
00098                   _DistanceTypep(0), _ValueTypep(*(__lastp - 1)));
00099     }
00100 
00101   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
00102            typename _RandomAccessIteratorp, typename _Distancep, typename _Tpp, 
00103             typename _Compare>
00104     void
00105     __push_pair_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00106                 _Distance __topIndex, _Tp __value,
00107                 _RandomAccessIteratorp __firstp, _Distancep __holeIndexp,
00108                 _Distancep __topIndexp, _Tpp __valuep, _Compare __comp)
00109     {
00110       _Distance __parent = (__holeIndex - 1) / 2;
00111       _Distancep __parentp = (__holeIndexp - 1) / 2;
00112       while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
00113         *(__first + __holeIndex) = *(__first + __parent);
00114         *(__firstp + __holeIndexp) = *(__firstp + __parentp);
00115         __holeIndex = __parent;
00116         __holeIndexp = __parentp;
00117         __parent = (__holeIndex - 1) / 2;
00118         __parentp = (__holeIndexp - 1) / 2;
00119       }
00120       *(__first + __holeIndex) = __value;
00121       *(__firstp + __holeIndexp) = __valuep;
00122     }
00123 
00124   template<typename _RandomAccessIterator, typename _RandomAccessIteratorp,
00125            typename _Compare>
00126     inline void 
00127     push_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00128               _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp,
00129               _Compare __comp)
00130     {
00131       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00132           _ValueType;
00133       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00134           _DistanceType;
00135       typedef typename iterator_traits<_RandomAccessIteratorp>::difference_type
00136           _DistanceTypep;
00137 
00138       // concept requirements
00139       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00140             _RandomAccessIterator>)
00141       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00142             _RandomAccessIteratorp>)
00143       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00144       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00145 
00146       __push_pair_heap(__first, _DistanceType((__last - __first) - 1),
00147                        _DistanceType(0), _ValueType(*(__last - 1)), __firstp,
00148                        _DistanceTypep((__lastp - __firstp) - 1),
00149                        _DistanceTypep(0), _ValueTypep(*(__lastp - 1)), __comp);
00150     }
00151 
00152   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
00153            typename _RandomAccessIteratorp, typename _Distancep, typename _Tpp>
00154     void 
00155     __adjust_pair_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00156                   _Distance __len, _Tp __value,
00157                   _RandomAccessIteratorp __firstp, _Distancep __holeIndexp,
00158                   _Distancep __lenp, _Tpp __valuep)
00159     {
00160       _Distance __topIndex = __holeIndex;
00161       _Distancep __topIndexp = __holeIndexp;
00162       _Distance __secondChild = 2 * __holeIndex + 2;
00163       _Distancep __secondChildp = 2 * __holeIndexp + 2;
00164       while (__secondChild < __len) {
00165         if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
00166         {
00167           __secondChild--;
00168           __secondChildp--;
00169         }
00170         *(__first + __holeIndex) = *(__first + __secondChild);
00171         *(__firstp + __holeIndexp) = *(__firstp + __secondChildp);
00172         __holeIndex = __secondChild;
00173         __holeIndexp = __secondChildp;
00174         __secondChild = 2 * (__secondChild + 1);
00175         __secondChildp = 2 * (__secondChildp + 1);
00176       }
00177       if (__secondChild == __len) {
00178         *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00179         *(__firstp + __holeIndexp) = *(__firstp + (__secondChildp - 1));
00180         __holeIndex = __secondChild - 1;
00181         __holeIndexp = __secondChildp - 1;
00182       }
00183       __push_pair_heap(__first, __holeIndex, __topIndex, __value,
00184                   __firstp, __holeIndexp, __topIndexp, __valuep);
00185     }
00186 
00187   template<typename _RandomAccessIterator, typename _Tp,
00188            typename _RandomAccessIteratorp, typename _Tpp>
00189     inline void 
00190     __pop_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00191                _RandomAccessIterator __result, _Tp __value,
00192                _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp,
00193                _RandomAccessIteratorp __resultp, _Tpp __valuep)
00194     {
00195       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
00196       typedef typename iterator_traits<_RandomAccessIteratorp>::difference_type _Distancep;
00197       *__result = *__first;
00198       *__resultp = *__firstp;
00199       __adjust_pair_heap(__first, _Distance(0), _Distance(__last - __first),
00200           __value, __firstp, _Distancep(0), _Distancep(__lastp - __firstp),
00201           __valuep);
00202     }
00203 
00204   template<typename _RandomAccessIterator, typename _RandomAccessIteratorp>
00205     inline void
00206     pop_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00207                 _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp)
00208     {
00209       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
00210       typedef typename iterator_traits<_RandomAccessIteratorp>::value_type _ValueTypep;
00211 
00212       // concept requirements
00213       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00214             _RandomAccessIterator>)
00215       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00216             _RandomAccessIteratorp>)
00217       __ISTLGLIBCXX_function_requires(_LessThanComparableConcept<_ValueType>)
00218       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00219       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00220 
00221       __pop_pair_heap(__first, __last - 1, __last - 1,
00222                       _ValueType(*(__last - 1)), __firstp, __lastp - 1,
00223                       __lastp - 1, _ValueTypep(*(__lastp - 1)));
00224     }
00225 
00226   template<typename _RandomAccessIterator, typename _Distance,
00227            typename _Tp, typename _RandomAccessIteratorp, typename _Distancep,
00228            typename _Tpp, typename _Compare>
00229     void
00230     __adjust_pair_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00231                   _Distance __len, _Tp __value, _RandomAccessIteratorp __firstp,
00232                   _Distancep __holeIndexp, _Distancep __lenp, _Tpp __valuep,
00233                   _Compare __comp)
00234     {
00235       _Distance __topIndex = __holeIndex;
00236       _Distancep __topIndexp = __holeIndexp;
00237       _Distance __secondChild = 2 * __holeIndex + 2;
00238       _Distancep __secondChildp = 2 * __holeIndexp + 2;
00239       while (__secondChild < __len) {
00240         if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
00241         {
00242           __secondChild--;
00243           __secondChildp--;
00244         }
00245         *(__first + __holeIndex) = *(__first + __secondChild);
00246         *(__firstp + __holeIndexp) = *(__firstp + __secondChildp);
00247         __holeIndex = __secondChild;
00248         __holeIndexp = __secondChildp;
00249         __secondChild = 2 * (__secondChild + 1);
00250         __secondChildp = 2 * (__secondChildp + 1);
00251       }
00252       if (__secondChild == __len) {
00253         *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00254         *(__firstp + __holeIndexp) = *(__firstp + (__secondChildp - 1));
00255         __holeIndex = __secondChild - 1;
00256         __holeIndexp = __secondChildp - 1;
00257       }
00258       __push_pair_heap(__first, __holeIndex, __topIndex, __value, __firstp,
00259                        __holeIndexp, __topIndexp, __valuep, __comp);
00260     }
00261 
00262   template<typename _RandomAccessIterator, typename _Tp,
00263            typename _RandomAccessIteratorp, typename _Tpp, typename _Compare>
00264     inline void 
00265     __pop_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00266                _RandomAccessIterator __result, _Tp __value,
00267                _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp,
00268                _RandomAccessIteratorp __resultp, _Tpp __valuep, _Compare __comp)
00269     {
00270       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
00271       typedef typename iterator_traits<_RandomAccessIteratorp>::difference_type _Distancep;
00272       *__result = *__first;
00273       *__resultp = *__firstp;
00274       __adjust_pair_heap(__first, _Distance(0), _Distance(__last - __first), 
00275                          __value, __firstp, _Distancep(0),
00276                          _Distancep(__lastp - __firstp), __valuep, __comp);
00277     }
00278 
00279   template<typename _RandomAccessIterator, typename _RandomAccessIteratorp,
00280            typename _Compare>
00281     inline void 
00282     pop_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00283               _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp,
00284               _Compare __comp)
00285     {
00286       // concept requirements
00287       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00288             _RandomAccessIterator>)
00289       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00290             _RandomAccessIteratorp>)
00291       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00292       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00293 
00294       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
00295       typedef typename iterator_traits<_RandomAccessIteratorp>::value_type _ValueTypep;
00296       __pop_pair_heap(__first, __last - 1, __last - 1,
00297                       _ValueType(*(__last - 1)), __firstp, __lastp - 1,
00298                       __lastp - 1, _ValueTypep(*(__lastp - 1)), __comp);
00299     }
00300 
00301   template<typename _RandomAccessIterator, typename _RandomAccessIteratorp>
00302     void 
00303     make_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00304                _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp)
00305     {
00306       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00307           _ValueType;
00308       typedef typename iterator_traits<_RandomAccessIteratorp>::value_type
00309           _ValueTypep;
00310       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00311           _DistanceType;
00312       typedef typename iterator_traits<_RandomAccessIteratorp>::difference_type
00313           _DistanceTypep;
00314 
00315       // concept requirements
00316       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00317             _RandomAccessIterator>)
00318       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00319             _RandomAccessIteratorp>)
00320       __ISTLGLIBCXX_function_requires(_LessThanComparableConcept<_ValueType>)
00321       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00322       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00323 
00324       if (__last - __first < 2) return;
00325       _DistanceType __len = __last - __first;
00326       _DistanceType __parent = (__len - 2)/2;
00327       _DistanceType __lenp = __lastp - __firstp;
00328       _DistanceType __parentp = (__lenp - 2)/2;
00329         
00330       while (true) {
00331         __adjust_pair_heap(__first, __parent, __len,
00332             _ValueType(*(__first + __parent)), __firstp, __parentp, __lenp,
00333             _ValueTypep(*(__firstp + __parentp)));
00334         if (__parent == 0) return;
00335         __parent--;
00336         __parentp--;
00337       }
00338     }
00339 
00340   template<typename _RandomAccessIterator, typename _RandomAccessIteratorp,
00341            typename _Compare>
00342     inline void 
00343     make_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00344               _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp,
00345               _Compare __comp)
00346     {
00347       typedef typename iterator_traits<_RandomAccessIterator>::value_type
00348           _ValueType;
00349       typedef typename iterator_traits<_RandomAccessIteratorp>::value_type
00350           _ValueTypep;
00351       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00352           _DistanceType;
00353       typedef typename iterator_traits<_RandomAccessIteratorp>::difference_type
00354           _DistanceTypep;
00355 
00356       // concept requirements
00357       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00358             _RandomAccessIterator>)
00359       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00360             _RandomAccessIteratorp>)
00361       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00362       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00363 
00364       if (__last - __first < 2) return;
00365       _DistanceType __len = __last - __first;
00366       _DistanceTypep __lenp = __lastp - __firstp;
00367       _DistanceType __parent = (__len - 2)/2;
00368       _DistanceTypep __parentp = (__lenp - 2)/2;
00369         
00370       while (true) {
00371         __adjust_pair_heap(__first, __parent, __len,
00372                            _ValueType(*(__first + __parent)),
00373                            __firstp, __parentp, __lenp,
00374                            _ValueTypep(*(__firstp + __parentp)), __comp);
00375         if (__parent == 0) return;
00376         __parent--;
00377         __parentp--;
00378       }
00379     }
00380 
00381   template<typename _RandomAccessIterator, typename _RandomAccessIteratorp>
00382     void
00383     sort_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00384                 _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp)
00385     {
00386       // concept requirements
00387       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00388             _RandomAccessIterator>)
00389       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00390             _RandomAccessIteratorp>)
00391       __ISTLGLIBCXX_function_requires(_LessThanComparableConcept<
00392             typename iterator_traits<_RandomAccessIterator>::value_type>)
00393       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00394       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00395 
00396       while (__last - __first > 1)
00397         pop_pair_heap(__first, __last--, __firstp, __lastp--);
00398     }
00399 
00400   template<typename _RandomAccessIterator, typename _RandomAccessIteratorp,
00401            typename _Compare>
00402     void 
00403     sort_pair_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00404                 _RandomAccessIteratorp __firstp, _RandomAccessIteratorp __lastp,
00405                 _Compare __comp)
00406     {
00407       // concept requirements
00408       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00409             _RandomAccessIterator>)
00410       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00411             _RandomAccessIteratorp>)
00412       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00413       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00414 
00415       while (__last - __first > 1)
00416         pop_pair_heap(__first, __last--, __firstp, __lastp--, __comp);
00417     }
00418 
00419 } // namespace std
00420 
00421 #endif /* __STLP_PAIRHEAP_H */
00422 
00423 // Local Variables:
00424 // mode:C++
00425 // End: