COCONUT API: stlp_addalgo.h Source File

00001 // Additional Algorithm implementation -*- C++ -*-
00002 
00003 // $Id: stlp_addalgo.h 347 2008-02-06 15:20:01Z schilly $
00004 // Copyright (C) 2003 Hermann Schichl using code templates
00005 //                    from Free Software Foundation, Inc.
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 
00035 #ifndef __STLP_ADDALGO_H
00036 #define __STLP_ADDALGO_H
00037 
00038 #if ( __GNUC__ == 3 && __GNUC_MINOR__ >= 4 || __GNUC__ >= 4 )
00039 #define __ISTLGLIBCXX_function_requires(...) __glibcxx_function_requires( __gnu_cxx::__VA_ARGS__ )
00040 #define __ISTLGLIBCXX_requires_valid_range(A, B) __glibcxx_requires_valid_range(A, B)
00041 #else
00042 #define __ISTLGLIBCXX_function_requires(...) __glibcpp_function_requires( __gnu_cxx::__VA_ARGS__ )
00043 #define __ISTLGLIBCXX_requires_valid_range(A, B)
00044 #endif
00045 
00046 #include <bits/stlp_pairheap.h>
00047 #include <bits/stl_tempbuf.h>     // for _Temporary_buffer
00048 #include <bits/stl_algobase.h>    // for various
00049 #include <bits/stl_algo.h>        // for various
00050 
00051 // See concept_check.h for the __ISTLGLIBCXX_*_requires macros.
00052 
00053 namespace std
00054 {
00055   enum { _M_p_chunk_size = 7 };
00056   enum { _M_p_threshold = 16 };
00062   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00063            typename _Tp>
00064     pair<_RandomAccessIter, _RandomAccessIterp>
00065     __unguarded_p_partition(_RandomAccessIter __first, _RandomAccessIter __last,
00066                        _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
00067                        _Tp __pivot)
00068     {
00069       while (true) {
00070         while (*__first < __pivot)
00071         {
00072           ++__first;
00073           ++__firstp;
00074         }
00075         --__last;
00076         --__lastp;
00077         while (__pivot < *__last)
00078         {
00079           --__last;
00080           --__lastp;
00081         }
00082         if (!(__first < __last))
00083           return make_pair(__first,__firstp);
00084         iter_swap(__first, __last);
00085         iter_swap(__firstp, __lastp);
00086         ++__first;
00087         ++__firstp;
00088       }
00089     }
00090 
00096   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00097            typename _Tp, typename _Compare>
00098     pair<_RandomAccessIter, _RandomAccessIterp>
00099     __unguarded_p_partition(_RandomAccessIter __first, _RandomAccessIter __last,
00100                         _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
00101                         _Tp __pivot, _Compare __comp)
00102     {
00103       while (true) {
00104         while (__comp(*__first, __pivot))
00105         {
00106           ++__first;
00107           ++__firstp;
00108         }
00109         --__last;
00110         --__lastp;
00111         while (__comp(__pivot, *__last))
00112         {
00113           --__last;
00114           --__lastp;
00115         }
00116         if (!(__first < __last))
00117           return make_pair(__first,__firstp);
00118         iter_swap(__first, __last);
00119         iter_swap(__firstp, __lastp);
00120         ++__first;
00121         ++__firstp;
00122       }
00123     }
00124 
00130   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00131            typename _Tp, typename _Tpp>
00132     void
00133     __unguarded_linear_p_insert(_RandomAccessIter __last1, _Tp __val1,
00134                                 _RandomAccessIterp __last2, _Tpp __val2)
00135     {
00136       _RandomAccessIter __next1 = __last1;
00137       _RandomAccessIterp __next2 = __last2;
00138       --__next1;
00139       --__next2;
00140       while (__val1 < *__next1) {
00141         *__last1 = *__next1;
00142         *__last2 = *__next2;
00143         __last1 = __next1;
00144         __last2 = __next2;
00145         --__next1;
00146         --__next2;
00147       }
00148       *__last1 = __val1;
00149       *__last2 = __val2;
00150     }
00151 
00157   template<typename _RandomAccessIter, typename _Tp,
00158            typename _RandomAccessIterp, typename _Tpp, typename _Compare>
00159     void
00160     __unguarded_linear_p_insert(_RandomAccessIter __last1, _Tp __val1,
00161                     _RandomAccessIterp __last2, _Tpp __val2, _Compare __comp)
00162     {
00163       _RandomAccessIter __next1 = __last1;
00164       _RandomAccessIterp __next2 = __last2;
00165       --__next1;
00166       --__next2;
00167       while (__comp(__val1, *__next1)) {
00168         *__last1 = *__next1;
00169         *__last2 = *__next2;
00170         __last1 = __next1;
00171         __last2 = __next2;
00172         --__next1;
00173         --__next2;
00174       }
00175       *__last1 = __val1;
00176       *__last2 = __val2;
00177     }
00178 
00184   template<typename _RandomAccessIter, typename _RandomAccessIterp>
00185     void
00186     __insertion_p_sort(_RandomAccessIter __first, _RandomAccessIter __last,
00187         _RandomAccessIterp __firstp, _RandomAccessIterp __lastp)
00188     {
00189       if (__first == __last) return;
00190 
00191       _RandomAccessIter __i;
00192       _RandomAccessIterp __ip;
00193       for (__i = __first + 1, __ip = __firstp + 1; __i != __last; ++__i, ++__ip)
00194       {
00195         typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
00196         typename iterator_traits<_RandomAccessIterp>::value_type __valp = *__ip;
00197         if (__val < *__first) {
00198           copy_backward(__first, __i, __i + 1);
00199           copy_backward(__firstp, __ip, __ip + 1);
00200           *__first = __val;
00201           *__firstp = __valp;
00202         }
00203         else
00204           __unguarded_linear_p_insert(__i, __val, __ip, __valp);
00205       }
00206     }
00207 
00213   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00214            typename _Compare>
00215     void
00216     __insertion_p_sort(_RandomAccessIter __first, _RandomAccessIter __last,
00217                        _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
00218                        _Compare __comp)
00219     {
00220       if (__first == __last) return;
00221 
00222       _RandomAccessIter __i;
00223       _RandomAccessIterp __ip;
00224       for (__i = __first + 1, __ip = __firstp + 1; __i != __last; ++__i, ++__ip)
00225       {
00226         typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
00227         typename iterator_traits<_RandomAccessIterp>::value_type __valp = *__ip;
00228         if (__comp(__val, *__first)) {
00229           copy_backward(__first, __i, __i + 1);
00230           copy_backward(__firstp, __ip, __ip + 1);
00231           *__first = __val;
00232           *__firstp = __valp;
00233         }
00234         else
00235           __unguarded_linear_p_insert(__i, __val, __ip, __valp, __comp);
00236       }
00237     }
00238 
00244   template<typename _RandomAccessIter, typename _RandomAccessIterp>
00245     inline void
00246     __unguarded_insertion_p_sort(_RandomAccessIter __first,
00247         _RandomAccessIter __last, _RandomAccessIterp __firstp,
00248         _RandomAccessIterp __lastp)
00249     {
00250       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
00251       typedef typename iterator_traits<_RandomAccessIterp>::value_type _ValueTypep;
00252 
00253       _RandomAccessIter __i;
00254       _RandomAccessIterp __ip;
00255       for (__i = __first, __ip = __firstp; __i != __last; ++__i, ++__ip)
00256         __unguarded_linear_p_insert(__i, _ValueType(*__i), __ip,
00257                                     _ValueTypep(*__ip));
00258     }
00259 
00265   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00266            typename _Compare>
00267     inline void
00268     __unguarded_insertion_p_sort(_RandomAccessIter __first,
00269         _RandomAccessIter __last, _RandomAccessIterp __firstp,
00270         _RandomAccessIterp __lastp, _Compare __comp)
00271     {
00272       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
00273       typedef typename iterator_traits<_RandomAccessIterp>::value_type _ValueTypep;
00274 
00275       _RandomAccessIter __i;
00276       _RandomAccessIterp __ip;
00277       for (__i = __first, __ip = __firstp; __i != __last; ++__i, ++__ip)
00278         __unguarded_linear_p_insert(__i, _ValueType(*__i),
00279                                     __ip, _ValueTypep(*__ip), __comp);
00280     }
00281 
00287   template<typename _RandomAccessIter, typename _RandomAccessIterp>
00288     void
00289     __final_insertion_p_sort(_RandomAccessIter __first,
00290         _RandomAccessIter __last, _RandomAccessIterp __firstp,
00291         _RandomAccessIterp __lastp)
00292     {
00293       if (__last - __first > _M_p_threshold) {
00294         __insertion_p_sort(__first, __first + _M_p_threshold,
00295                            __firstp, __firstp + _M_p_threshold);
00296         __unguarded_insertion_p_sort(__first + _M_p_threshold, __last,
00297                                      __firstp + _M_p_threshold, __lastp);
00298       }
00299       else
00300         __insertion_p_sort(__first, __last, __firstp, __lastp);
00301     }
00302 
00308   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00309            typename _Compare>
00310     void
00311     __final_insertion_p_sort(_RandomAccessIter __first,
00312             _RandomAccessIter __last, _RandomAccessIterp __firstp,
00313             _RandomAccessIterp __lastp, _Compare __comp)
00314     {
00315       if (__last - __first > _M_p_threshold) {
00316         __insertion_p_sort(__first, __first + _M_p_threshold, __firstp,
00317                            __firstp + _M_p_threshold, __comp);
00318         __unguarded_insertion_p_sort(__first + _M_p_threshold, __last,
00319                            __firstp + _M_p_threshold, __lastp, __comp);
00320       }
00321       else
00322         __insertion_p_sort(__first, __last, __firstp, __lastp, __comp);
00323     }
00324 
00330   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00331            typename _Size>
00332     void
00333     __intro_p_sort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
00334         _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
00335         _Size __depth_limit)
00336     {
00337       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
00338 
00339       while (__last - __first > _M_p_threshold) {
00340         if (__depth_limit == 0) {
00341           partial_pair_sort(__first, __last, __last, __firstp, __lastp);
00342           return;
00343         }
00344         --__depth_limit;
00345         pair<_RandomAccessIter,_RandomAccessIterp> __cut =
00346           __unguarded_p_partition(__first, __last, __firstp, __lastp,
00347                         _ValueType(__median(*__first,
00348                                             *(__first + (__last - __first)/2),
00349                                             *(__last - 1))));
00350         __intro_p_sort_loop(__cut.first, __last, __cut.second, __lastp,
00351                             __depth_limit);
00352         __last = __cut.first;
00353         __lastp = __cut.second;
00354       }
00355     }
00356 
00362   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00363            typename _Size, typename _Compare>
00364     void
00365     __intro_p_sort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
00366                         _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
00367                         _Size __depth_limit, _Compare __comp)
00368     {
00369       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
00370 
00371       while (__last - __first > _M_p_threshold) {
00372         if (__depth_limit == 0) {
00373           partial_pair_sort(__first, __last, __last, __firstp, __lastp, __comp);
00374           return;
00375         }
00376         --__depth_limit;
00377         pair<_RandomAccessIter,_RandomAccessIterp> __cut =
00378           __unguarded_p_partition(__first, __last, __firstp, __lastp,
00379                         _ValueType(__median(*__first,
00380                                             *(__first + (__last - __first)/2),
00381                                             *(__last - 1), __comp)),
00382            __comp);
00383         __introsort_p_loop(__cut.first, __last, __cut.second, __lastp,
00384                            __depth_limit, __comp);
00385         __last = __cut.first;
00386         __lastp = __cut.second;
00387       }
00388     }
00389 
00393   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00394            typename _Size>
00395     void
00396     __introsort_p_loop(_RandomAccessIter __first, _RandomAccessIter __last,
00397                        _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
00398                      _Size __depth_limit)
00399     {
00400       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
00401 
00402       while (__last - __first > _M_p_threshold) {
00403         if (__depth_limit == 0) {
00404           partial_pair_sort(__first, __last, __last, __firstp, __lastp);
00405           return;
00406         }
00407         --__depth_limit;
00408         pair<_RandomAccessIter, _RandomAccessIterp> __cut =
00409           __unguarded_p_partition(__first, __last, __firstp, __lastp,
00410                         _ValueType(__median(*__first,
00411                                             *(__first + (__last - __first)/2),
00412                                             *(__last - 1))));
00413         __introsort_p_loop(__cut.first, __last, __cut.second, __lastp,
00414                            __depth_limit);
00415         __last = __cut.first;
00416         __lastp = __cut.second;
00417       }
00418     }
00419 
00425   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00426            typename _Size, typename _Compare>
00427     void
00428     __introsort_p_loop(_RandomAccessIter __first, _RandomAccessIter __last,
00429                        _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
00430                        _Size __depth_limit, _Compare __comp)
00431     {
00432       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
00433 
00434       while (__last - __first > _M_p_threshold) {
00435         if (__depth_limit == 0) {
00436           partial_pair_sort(__first, __last, __last, __firstp, __lastp, __comp);
00437           return;
00438         }
00439         --__depth_limit;
00440         pair<_RandomAccessIter, _RandomAccessIterp> __cut =
00441           __unguarded_p_partition(__first, __last, __firstp, __lastp,
00442                                 _ValueType(__median(*__first,
00443                                                     *(__first + (__last - __first)/2),
00444                                                     *(__last - 1), __comp)),
00445            __comp);
00446         __introsort_p_loop(__cut.first, __last, __cut.second, __lastp,
00447                            __depth_limit, __comp);
00448         __last = __cut.first;
00449         __lastp = __cut.second;
00450       }
00451     }
00452 
00473   template<typename _RandomAccessIter, typename _RandomAccessIterp>
00474     inline bool
00475     pair_sort(_RandomAccessIter __first, _RandomAccessIter __last,
00476               _RandomAccessIterp __firstp, _RandomAccessIterp __lastp)
00477     {
00478       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
00479 
00480       // concept requirements
00481       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00482             _RandomAccessIter>)
00483       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00484             _RandomAccessIterp>)
00485       __ISTLGLIBCXX_function_requires(_LessThanComparableConcept<_ValueType>)
00486       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00487       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00488 
00489       if (__first - __last != __firstp - __lastp) return false;
00490 
00491       if (__first != __last) {
00492         __intro_p_sort_loop(__first, __last, __firstp, __lastp,
00493                             __lg(__last - __first) * 2);
00494         __final_insertion_p_sort(__first, __last, __firstp, __lastp);
00495       }
00496       return true;
00497     }
00498 
00520   template<typename _RandomAccessIter, typename _RandomAccessIterp,
00521            typename _Compare>
00522     inline bool
00523     pair_sort(_RandomAccessIter __first, _RandomAccessIter __last,
00524        _RandomAccessIterp __firstp, _RandomAccessIterp __lastp, _Compare __comp)
00525     {
00526       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
00527 
00528       // concept requirements
00529       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00530             _RandomAccessIter>)
00531       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
00532             _RandomAccessIterp>)
00533       __ISTLGLIBCXX_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>)
00534       __ISTLGLIBCXX_requires_valid_range(__first, __last);
00535       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
00536 
00537       if (__first - __last != __firstp - __lastp) return false;
00538 
00539       if (__first != __last) {
00540         __intro_p_sort_loop(__first, __last, __firstp, __lastp,
00541                             __lg(__last - __first) * 2, __comp);
00542         __final_insertion_p_sort(__first, __last, __firstp, __lastp, __comp);
00543       }
00544       return true;
00545     }
00546 
00552   template<typename _BidirectionalIter, typename _BidirectionalIterp,
00553            typename _Distance>
00554     void
00555     __merge_p_without_buffer(_BidirectionalIter __first,
00556                              _BidirectionalIter __middle,
00557                              _BidirectionalIter __last,
00558                              _BidirectionalIterp __firstp,
00559                              _BidirectionalIterp __middlep,
00560                              _BidirectionalIterp __lastp,
00561                              _Distance __len1, _Distance __len2)
00562     {
00563       if (__len1 == 0 || __len2 == 0)
00564         return;
00565       if (__len1 + __len2 == 2) {
00566         if (*__middle < *__first)
00567         {
00568               iter_swap(__first, __middle);
00569               iter_swap(__firstp, __middlep);
00570         }
00571         return;
00572       }
00573       _BidirectionalIter __first_cut = __first;
00574       _BidirectionalIter __second_cut = __middle;
00575       _BidirectionalIterp __first_cutp = __firstp;
00576       _BidirectionalIterp __second_cutp = __middlep;
00577       _Distance __len11 = 0;
00578       _Distance __len22 = 0;
00579       if (__len1 > __len2) {
00580         __len11 = __len1 / 2;
00581         advance(__first_cut, __len11);
00582         advance(__first_cutp, __len11);
00583         __second_cut = lower_bound(__middle, __last, *__first_cut);
00584         __len22 = distance(__middle, __second_cut);
00585         __second_cutp = __middlep + __len22;
00586       }
00587       else {
00588         __len22 = __len2 / 2;
00589         advance(__second_cut, __len22);
00590         advance(__second_cutp, __len22);
00591         __first_cut = upper_bound(__first, __middle, *__second_cut);
00592         __len11 = distance(__first, __first_cut);
00593         __first_cutp = __firstp + __len11;
00594       }
00595       rotate(__first_cut, __middle, __second_cut);
00596       rotate(__first_cutp, __middlep, __second_cutp);
00597       _BidirectionalIter __new_middle = __first_cut;
00598       _BidirectionalIterp __new_middlep = __first_cutp;
00599       advance(__new_middle, distance(__middle, __second_cut));
00600       advance(__new_middlep, distance(__middle, __second_cut));
00601       __merge_p_without_buffer(__first, __first_cut, __new_middle,
00602                                __firstp, __first_cutp, __new_middlep,
00603                                __len11, __len22);
00604       __merge_p_without_buffer(__new_middle, __second_cut, __last,
00605                                __new_middlep, __second_cutp, __lastp,
00606                                __len1 - __len11, __len2 - __len22);
00607     }
00608 
00614   template<typename _BidirectionalIter, typename _BidirectionalIterp,
00615            typename _Distance, typename _Compare>
00616     void
00617     __merge_p_without_buffer(_BidirectionalIter __first,
00618                              _BidirectionalIter __middle,
00619                              _BidirectionalIter __last,
00620                              _BidirectionalIterp __firstp,
00621                              _BidirectionalIterp __middlep,
00622                              _BidirectionalIterp __lastp,
00623                              _Distance __len1, _Distance __len2,
00624                              _Compare __comp)
00625     {
00626       if (__len1 == 0 || __len2 == 0)
00627         return;
00628       if (__len1 + __len2 == 2) {
00629         if (__comp(*__middle, *__first))
00630         {
00631               iter_swap(__first, __middle);
00632               iter_swap(__firstp, __middlep);
00633         }
00634         return;
00635       }
00636       _BidirectionalIter __first_cut = __first;
00637       _BidirectionalIter __second_cut = __middle;
00638       _BidirectionalIterp __first_cutp = __firstp;
00639       _BidirectionalIterp __second_cutp = __middlep;
00640       _Distance __len11 = 0;
00641       _Distance __len22 = 0;
00642       if (__len1 > __len2) {
00643         __len11 = __len1 / 2;
00644         advance(__first_cut, __len11);
00645         advance(__first_cutp, __len11);
00646         __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
00647         __len22 = distance(__middle, __second_cut);
00648         __second_cutp = __middlep + __len22;
00649       }
00650       else {
00651         __len22 = __len2 / 2;
00652         advance(__second_cut, __len22);
00653         __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
00654         __len11 = distance(__first, __first_cut);
00655         __first_cutp = __firstp + __len11;
00656       }
00657       rotate(__first_cut, __middle, __second_cut);
00658       rotate(__first_cutp, __middlep, __second_cutp);
00659       _BidirectionalIter __new_middle = __first_cut;
00660       _BidirectionalIterp __new_middlep = __first_cutp;
00661       advance(__new_middle, distance(__middle, __second_cut));
00662       advance(__new_middlep, distance(__middle, __second_cut));
00663       __merge_p_without_buffer(__first, __first_cut, __new_middle,
00664                                __firstp, __first_cutp, __new_middlep,
00665                                __len11, __len22, __comp);
00666       __merge_p_without_buffer(__new_middle, __second_cut, __last,
00667                                __new_middlep, __second_cutp, __lastp,
00668                                __len1 - __len11, __len2 - __len22, __comp);
00669     }
00670 
00676   template<typename _BidirectionalIter, typename _BidirectionalIterp,
00677            typename _Distance, typename _Pointer, typename _Pointerp>
00678     void
00679     __p_merge_adaptive(_BidirectionalIter __first,
00680                        _BidirectionalIter __middle,
00681                        _BidirectionalIter __last,
00682                        _BidirectionalIterp __firstp,
00683                        _BidirectionalIterp __middlep,  
00684                        _BidirectionalIterp __lastp,
00685                        _Distance __len1, _Distance __len2,
00686                        _Pointer __buffer, _Pointerp __bufferp,
00687                        _Distance __buffer_size)
00688     {
00689           if (__len1 <= __len2 && __len1 <= __buffer_size) {
00690             _Pointer __buffer_end = copy(__first, __middle, __buffer);
00691             _Pointerp __buffer_endp = copy(__firstp, __middlep, __bufferp);
00692             pair_merge(__buffer, __buffer_end, __middle, __last, __first,
00693                        __bufferp, __buffer_endp, __middlep, __lastp, __firstp);
00694           }
00695           else if (__len2 <= __buffer_size) {
00696             _Pointer __buffer_end = copy(__middle, __last, __buffer);
00697             _Pointerp __buffer_endp = copy(__middlep, __lastp, __bufferp);
00698             __p_merge_backward(__first, __middle, __buffer, __buffer_end,
00699                 __last, __firstp, __middlep, __bufferp, __buffer_endp, __lastp);
00700           }
00701           else {
00702             _BidirectionalIter __first_cut = __first;
00703             _BidirectionalIter __second_cut = __middle;
00704             _BidirectionalIterp __first_cutp = __firstp;
00705             _BidirectionalIterp __second_cutp = __middlep;
00706             _Distance __len11 = 0;
00707             _Distance __len22 = 0;
00708             if (__len1 > __len2) {
00709                   __len11 = __len1 / 2;
00710                   advance(__first_cut, __len11);
00711                   advance(__first_cutp, __len11);
00712                   __second_cut = lower_bound(__middle, __last, *__first_cut);
00713                   __len22 = distance(__middle, __second_cut);
00714                   __second_cutp = __middlep + __len22;
00715             }
00716             else {
00717                   __len22 = __len2 / 2;
00718                   advance(__second_cut, __len22);
00719                   advance(__second_cutp, __len22);
00720                   __first_cut = upper_bound(__first, __middle, *__second_cut);
00721                   __len11 = distance(__first, __first_cut);
00722                   __first_cutp = __firstp + __len11;
00723             }
00724             _BidirectionalIter __new_middle =
00725                   __rotate_adaptive(__first_cut, __middle, __second_cut,
00726                                     __len1 - __len11, __len22, __buffer,
00727                                     __buffer_size);
00728             _BidirectionalIterp __new_middlep =
00729                   __rotate_adaptive(__first_cutp, __middlep, __second_cutp,
00730                                     __len1 - __len11, __len22, __bufferp,
00731                                     __buffer_size);
00732             __p_merge_adaptive(__first, __first_cut, __new_middle, __firstp,
00733                                __first_cutp, __new_middlep, __len11, __len22,
00734                                __buffer, __bufferp, __buffer_size);
00735             __p_merge_adaptive(__new_middle, __second_cut, __last,
00736                                __new_middlep, __second_cutp, __lastp,
00737                                __len1 - __len11, __len2 - __len22, __buffer,
00738                                __bufferp, __buffer_size);
00739           }
00740     }
00741 
00747   template<typename _BidirectionalIter, typename _BidirectionalIterp,
00748            typename _Distance, typename _Pointer, typename _Pointerp,
00749            typename _Compare>
00750     void
00751     __p_merge_adaptive(_BidirectionalIter __first,
00752                        _BidirectionalIter __middle,
00753                        _BidirectionalIter __last,
00754                        _BidirectionalIterp __firstp,
00755                        _BidirectionalIterp __middlep,
00756                        _BidirectionalIterp __lastp,
00757                        _Distance __len1, _Distance __len2,
00758                        _Pointer __buffer, _Pointerp __bufferp,
00759                        _Distance __buffer_size, _Compare __comp)
00760     {
00761           if (__len1 <= __len2 && __len1 <= __buffer_size) {
00762             _Pointer __buffer_end = copy(__first, __middle, __buffer);
00763             _Pointerp __buffer_endp = copy(__firstp, __middlep, __bufferp);
00764             pair_merge(__buffer, __buffer_end, __middle, __last, __first,
00765                 __bufferp, __buffer_endp, __middlep, __lastp, __firstp, __comp);
00766           }
00767           else if (__len2 <= __buffer_size) {
00768             _Pointer __buffer_end = copy(__middle, __last, __buffer);
00769             _Pointerp __buffer_endp = copy(__middlep, __lastp, __bufferp);
00770             __p_merge_backward(__first, __middle, __buffer, __buffer_end,
00771                         __last, __firstp, __middlep, __bufferp, __buffer_endp,
00772                         __lastp, __comp);
00773           }
00774           else {
00775             _BidirectionalIter __first_cut = __first;
00776             _BidirectionalIter __second_cut = __middle;
00777             _BidirectionalIterp __first_cutp = __firstp;
00778             _BidirectionalIterp __second_cutp = __middlep;
00779             _Distance __len11 = 0;
00780             _Distance __len22 = 0;
00781             if (__len1 > __len2) {
00782                   __len11 = __len1 / 2;
00783                   advance(__first_cut, __len11);
00784                   advance(__first_cutp, __len11);
00785                   __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
00786                   __len22 = distance(__middle, __second_cut);
00787                   __second_cutp = __middlep + __len22;
00788             }
00789             else {
00790                   __len22 = __len2 / 2;
00791                   advance(__second_cut, __len22);
00792                   advance(__second_cutp, __len22);
00793                   __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
00794                   __len11 = distance(__first, __first_cut);
00795                   __first_cutp = __firstp + __len11;
00796             }
00797             _BidirectionalIter __new_middle =
00798                   __rotate_adaptive(__first_cut, __middle, __second_cut,
00799                                     __len1 - __len11, __len22, __buffer,
00800                                     __buffer_size);
00801             _BidirectionalIter __new_middlep =
00802                   __rotate_adaptive(__first_cutp, __middlep, __second_cutp,
00803                                     __len1 - __len11, __len22, __bufferp,
00804                                     __buffer_size);
00805             __p_merge_adaptive(__first, __first_cut, __new_middle, __firstp,
00806                                __first_cutp, __new_middlep, __len11, __len22,
00807                                __buffer, __bufferp, __buffer_size, __comp);
00808             __p_merge_adaptive(__new_middle, __second_cut, __last,
00809                                __new_middlep, __second_cutp, __lastp,
00810                                __len1 - __len11, __len2 - __len22, __buffer,
00811                                __bufferp, __buffer_size, __comp);
00812           }
00813     }
00814 
00831   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
00832            typename _InputIter1p, typename _InputIter2p, typename _OutputIterp>
00833     pair<_OutputIter,_OutputIterp>
00834     pair_merge(_InputIter1 __first1, _InputIter1 __last1,
00835           _InputIter2 __first2, _InputIter2 __last2,
00836           _OutputIter __result, _InputIter1p __first1p, _InputIter1p __last1p,
00837           _InputIter2p __first2p, _InputIter2p __last2p,
00838           _OutputIterp __resultp)
00839     {
00840       // concept requirements
00841       __ISTLGLIBCXX_function_requires(_InputIteratorConcept<_InputIter1>)
00842       __ISTLGLIBCXX_function_requires(_InputIteratorConcept<_InputIter2>)
00843       __ISTLGLIBCXX_function_requires(_InputIteratorConcept<_InputIter1p>)
00844       __ISTLGLIBCXX_function_requires(_InputIteratorConcept<_InputIter2p>)
00845       __ISTLGLIBCXX_function_requires(_OutputIteratorConcept<_OutputIter,
00846             typename iterator_traits<_InputIter1>::value_type>)
00847       __ISTLGLIBCXX_function_requires(_OutputIteratorConcept<_OutputIterp,
00848             typename iterator_traits<_InputIter1p>::value_type>)
00849       __ISTLGLIBCXX_function_requires(_SameTypeConcept<
00850             typename iterator_traits<_InputIter1>::value_type,
00851             typename iterator_traits<_InputIter2>::value_type>)
00852       __ISTLGLIBCXX_function_requires(_SameTypeConcept<
00853             typename iterator_traits<_InputIter1p>::value_type,
00854             typename iterator_traits<_InputIter2p>::value_type>)
00855       __ISTLGLIBCXX_function_requires(_LessThanComparableConcept<
00856             typename iterator_traits<_InputIter1>::value_type>)
00857       __ISTLGLIBCXX_requires_valid_range(__first1, __last1);
00858       __ISTLGLIBCXX_requires_valid_range(__first1p, __last1p);
00859       __ISTLGLIBCXX_requires_valid_range(__first2, __last2);
00860       __ISTLGLIBCXX_requires_valid_range(__first2p, __last2p);
00861 
00862       while (__first1 != __last1 && __first2 != __last2) {
00863         if (*__first2 < *__first1) {
00864           *__result = *__first2;
00865           *__resultp = *__first2p;
00866           ++__first2;
00867           ++__first2p;
00868         }
00869         else {
00870           *__result = *__first1;
00871           *__resultp = *__first1p;
00872           ++__first1;
00873           ++__first1p;
00874         }
00875         ++__result;
00876         ++__resultp;
00877       }
00878       return make_pair(
00879           copy(__first2, __last2, copy(__first1, __last1, __result)),
00880           copy(__first2p, __last2p, copy(__first1p, __last1p, __resultp)));
00881     }
00882 
00903   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
00904            typename _InputIter1p, typename _InputIter2p, typename _OutputIterp,
00905            typename _Compare>
00906     pair<_OutputIter,_OutputIterp>
00907     pair_merge(_InputIter1 __first1, _InputIter1 __last1,
00908                _InputIter2 __first2, _InputIter2 __last2,
00909                _OutputIter __result, _InputIter1p __first1p,
00910                _InputIter1p __last1p, _InputIter2p __first2p,
00911                _InputIter2p __last2p, _OutputIterp __resultp, _Compare __comp)
00912     {
00913       // concept requirements
00914       __ISTLGLIBCXX_function_requires(_InputIteratorConcept<_InputIter1>)
00915       __ISTLGLIBCXX_function_requires(_InputIteratorConcept<_InputIter2>)
00916       __ISTLGLIBCXX_function_requires(_InputIteratorConcept<_InputIter1p>)
00917       __ISTLGLIBCXX_function_requires(_InputIteratorConcept<_InputIter2p>)
00918       __ISTLGLIBCXX_function_requires(_SameTypeConcept<
00919             typename iterator_traits<_InputIter1>::value_type,
00920             typename iterator_traits<_InputIter2>::value_type>)
00921       __ISTLGLIBCXX_function_requires(_SameTypeConcept<
00922             typename iterator_traits<_InputIter1p>::value_type,
00923             typename iterator_traits<_InputIter2p>::value_type>)
00924       __ISTLGLIBCXX_function_requires(_OutputIteratorConcept<_OutputIter,
00925             typename iterator_traits<_InputIter1>::value_type>)
00926       __ISTLGLIBCXX_function_requires(_OutputIteratorConcept<_OutputIterp,
00927             typename iterator_traits<_InputIter1p>::value_type>)
00928       __ISTLGLIBCXX_function_requires(_BinaryPredicateConcept<_Compare,
00929             typename iterator_traits<_InputIter1>::value_type,
00930             typename iterator_traits<_InputIter2>::value_type>)
00931       __ISTLGLIBCXX_requires_valid_range(__first1, __last1);
00932       __ISTLGLIBCXX_requires_valid_range(__first1p, __last1p);
00933       __ISTLGLIBCXX_requires_valid_range(__first2, __last2);
00934       __ISTLGLIBCXX_requires_valid_range(__first2p, __last2p);
00935 
00936       while (__first1 != __last1 && __first2 != __last2) {
00937         if (__comp(*__first2, *__first1)) {
00938           *__result = *__first2;
00939           *__resultp = *__first2p;
00940           ++__first2;
00941           ++__first2p;
00942         }
00943         else {
00944           *__result = *__first1;
00945           *__resultp = *__first1p;
00946           ++__first1;
00947           ++__first1p;
00948         }
00949         ++__result;
00950         ++__resultp;
00951       }
00952       return make_pair(
00953           copy(__first2, __last2, copy(__first1, __last1, __result)),
00954           copy(__first2p, __last2p, copy(__first1p, __last1p, __resultp)));
00955     }
00956 
00962   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
00963            typename _BidirectionalIter3, typename _BidirectionalIter1p,
00964            typename _BidirectionalIter2p, typename _BidirectionalIter3p>
00965     pair<_BidirectionalIter3,_BidirectionalIter3p>
00966     __p_merge_backward(_BidirectionalIter1 __first1,
00967                 _BidirectionalIter1 __last1, _BidirectionalIter2 __first2,
00968                 _BidirectionalIter2 __last2, _BidirectionalIter3 __result,
00969                 _BidirectionalIter1p __first1p, _BidirectionalIter1p __last1p,
00970                 _BidirectionalIter2p __first2p, _BidirectionalIter2p __last2p,
00971                 _BidirectionalIter3p __resultp)
00972     {
00973       if (__first1 == __last1)
00974         return make_pair(copy_backward(__first2, __last2, __result),
00975                          copy_backward(__first2p, __last2p, __resultp));
00976       if (__first2 == __last2)
00977         return make_pair(copy_backward(__first1, __last1, __result),
00978                          copy_backward(__first1p, __last1p, __resultp));
00979       --__last1;
00980       --__last1p;
00981       --__last2;
00982       --__last2p;
00983       while (true) {
00984         if (*__last2 < *__last1) {
00985           *--__result = *__last1;
00986           *--__resultp = *__last1p;
00987           if (__first1 == __last1)
00988             return make_pair(copy_backward(__first2, ++__last2, __result),
00989                              copy_backward(__first2p, ++__last2p, __resultp));
00990           --__last1;
00991           --__last1p;
00992         }
00993         else {
00994           *--__result = *__last2;
00995           *--__resultp = *__last2p;
00996           if (__first2 == __last2)
00997             return make_pair(copy_backward(__first1, ++__last1, __result),
00998                              copy_backward(__first1p, ++__last1p, __resultp));
00999           --__last2;
01000           --__last2p;
01001         }
01002       }
01003     }
01004 
01010   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
01011            typename _BidirectionalIter3, typename _BidirectionalIter1p,
01012            typename _BidirectionalIter2p, typename _BidirectionalIter3p,
01013            typename _Compare>
01014     pair<_BidirectionalIter3,_BidirectionalIter3p>
01015     __p_merge_backward(_BidirectionalIter1 __first1,
01016                 _BidirectionalIter1 __last1, _BidirectionalIter2 __first2,
01017                 _BidirectionalIter2 __last2, _BidirectionalIter3 __result,
01018                 _BidirectionalIter1p __first1p, _BidirectionalIter1p __last1p,
01019                 _BidirectionalIter2p __first2p, _BidirectionalIter2p __last2p,
01020                 _BidirectionalIter3p __resultp, _Compare __comp)
01021     {
01022       if (__first1 == __last1)
01023         return make_pair(copy_backward(__first2, __last2, __result),
01024                          copy_backward(__first2p, __last2p, __resultp));
01025       if (__first2 == __last2)
01026         return make_pair(copy_backward(__first1, __last1, __result),
01027                          copy_backward(__first1p, __last1p, __resultp));
01028       --__last1;
01029       --__last1p;
01030       --__last2;
01031       --__last2p;
01032       while (true) {
01033         if (__comp(*__last2, *__last1)) {
01034           *--__result = *__last1;
01035           *--__resultp = *__last1p;
01036           if (__first1 == __last1)
01037             return make_pair(copy_backward(__first2, ++__last2, __result),
01038                              copy_backward(__first2p, ++__last2p, __resultp));
01039           --__last1;
01040           --__last1p;
01041         }
01042         else {
01043           *--__result = *__last2;
01044           *--__resultp = *__last2p;
01045           if (__first2 == __last2)
01046             return make_pair(copy_backward(__first1, ++__last1, __result),
01047                              copy_backward(__first1p, ++__last1p, __resultp));
01048           --__last2;
01049           --__last2p;
01050         }
01051       }
01052     }
01053 
01054 
01060   template<typename _RandomAccessIter, typename _RandomAccessIterp>
01061     void
01062     __inplace_stable_p_sort(_RandomAccessIter __first, _RandomAccessIter __last,
01063         _RandomAccessIterp __firstp, _RandomAccessIterp __lastp)
01064     {
01065       if (__last - __first < 15) {
01066         __insertion_p_sort(__first, __last, __firstp, __lastp);
01067         return;
01068       }
01069       _RandomAccessIter __middle = __first + (__last - __first) / 2;
01070       _RandomAccessIterp __middlep = __firstp + (__lastp - __firstp) / 2;
01071       __inplace_stable_p_sort(__first, __middle, __firstp, __middlep);
01072       __inplace_stable_p_sort(__middle, __last, __middlep, __lastp);
01073       __merge_p_without_buffer(__first, __middle, __last,
01074                                __firstp, __middlep, __lastp,
01075                                __middle - __first,
01076                                __last - __middle);
01077     }
01078 
01084   template<typename _RandomAccessIter, typename _RandomAccessIterp,
01085            typename _Compare>
01086     void
01087     __inplace_stable_p_sort(_RandomAccessIter __first, _RandomAccessIter __last,
01088                         _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
01089                         _Compare __comp)
01090     {
01091       if (__last - __first < 15) {
01092         __insertion_p_sort(__first, __last, __firstp, __lastp, __comp);
01093         return;
01094       }
01095       _RandomAccessIter __middle = __first + (__last - __first) / 2;
01096       _RandomAccessIterp __middlep = __firstp + (__lastp - __firstp) / 2;
01097       __inplace_stable_p_sort(__first, __middle, __firstp, __middlep, __comp);
01098       __inplace_stable_p_sort(__middle, __last, __middlep, __lastp, __comp);
01099       __merge_p_without_buffer(__first, __middle, __last,
01100                                __firstp, __middlep, __lastp,
01101                                __middle - __first,
01102                                __last - __middle,
01103                                __comp);
01104     }
01105 
01106   template<typename _RandomAccessIter1, typename _RandomAccessIter2,
01107            typename _RandomAccessIter1p, typename _RandomAccessIter2p,
01108            typename _Distance>
01109     void
01110     __merge_p_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
01111                 _RandomAccessIter2 __result, _RandomAccessIter1p __firstp,
01112                 _RandomAccessIter1p __lastp, _RandomAccessIter2p __resultp,
01113                 _Distance __step_size)
01114     {
01115       _Distance __two_step = 2 * __step_size;
01116       pair<_RandomAccessIter2,_RandomAccessIter2p> __res;
01117 
01118       while (__last - __first >= __two_step) {
01119         __res = pair_merge(__first, __first + __step_size,
01120                          __first + __step_size, __first + __two_step, __result,
01121                          __firstp, __firstp + __step_size,
01122                          __firstp + __step_size, __firstp + __two_step,
01123                          __resultp);
01124         __result = __res.first;
01125         __resultp = __res.second;
01126         __first += __two_step;
01127         __firstp += __two_step;
01128       }
01129 
01130       __step_size = min(_Distance(__last - __first), __step_size);
01131       pair_merge(__first, __first + __step_size, __first + __step_size, __last,
01132             __result, __firstp, __firstp + __step_size, __firstp + __step_size,
01133             __lastp, __resultp);
01134     }
01135 
01136   template<typename _RandomAccessIter1, typename _RandomAccessIter2,
01137            typename _RandomAccessIter1p, typename _RandomAccessIter2p,
01138            typename _Distance, typename _Compare>
01139     void
01140     __merge_p_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
01141               _RandomAccessIter2 __result, _RandomAccessIter1p __firstp,
01142               _RandomAccessIter1p __lastp, _RandomAccessIter2p __resultp,
01143               _Distance __step_size, _Compare __comp)
01144     {
01145       _Distance __two_step = 2 * __step_size;
01146       pair<_RandomAccessIter2,_RandomAccessIter2p> __res;
01147 
01148       while (__last - __first >= __two_step) {
01149         __res = pair_merge(__first, __first + __step_size,
01150                       __first + __step_size, __first + __two_step,
01151                       __result, __firstp, __firstp + __step_size,
01152                       __firstp + __step_size, __firstp + __two_step,
01153                       __resultp, __comp);
01154         __result = __res.first;
01155         __resultp = __res.second;
01156         __first += __two_step;
01157         __firstp += __two_step;
01158       }
01159       __step_size = min(_Distance(__last - __first), __step_size);
01160 
01161       pair_merge(__first, __first + __step_size,
01162             __first + __step_size, __last,
01163             __result, __firstp, __firstp + __step_size,
01164             __firstp + __step_size, __lastp,
01165             __resultp, __comp);
01166     }
01167 
01168   template<typename _RandomAccessIter, typename _RandomAccessIterp,
01169            typename _Distance>
01170     void
01171     __chunk_insertion_p_sort(_RandomAccessIter __first,
01172         _RandomAccessIter __last, _RandomAccessIterp __firstp,
01173         _RandomAccessIterp __lastp, _Distance __chunk_size)
01174     {
01175       while (__last - __first >= __chunk_size) {
01176         __insertion_p_sort(__first, __first + __chunk_size,
01177                            __firstp, __firstp + __chunk_size);
01178         __first += __chunk_size;
01179         __firstp += __chunk_size;
01180       }
01181       __insertion_p_sort(__first, __last, __firstp, __lastp);
01182     }
01183 
01184   template<typename _RandomAccessIter, typename _RandomAccessIterp,
01185            typename _Distance, typename _Compare>
01186     void
01187     __chunk_insertion_p_sort(_RandomAccessIter __first,
01188         _RandomAccessIter __last, _RandomAccessIterp __firstp,
01189         _RandomAccessIterp __lastp, _Distance __chunk_size, _Compare __comp)
01190     {
01191       while (__last - __first >= __chunk_size) {
01192         __insertion_p_sort(__first, __first + __chunk_size, __firstp,
01193             __firstp + __chunk_size, __comp);
01194         __first += __chunk_size;
01195         __firstp += __chunk_size;
01196       }
01197       __insertion_p_sort(__first, __last, __firstp, __lastp, __comp);
01198     }
01199 
01200   template<typename _RandomAccessIter, typename _RandomAccessIterp,
01201            typename _Pointer, typename _Pointerp>
01202     void
01203     __merge_p_sort_with_buffer(_RandomAccessIter __first,
01204         _RandomAccessIter __last, _Pointer __buffer,
01205         _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
01206         _Pointerp __bufferp)
01207     {
01208       typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
01209       typedef typename iterator_traits<_RandomAccessIterp>::difference_type _Distancep;
01210 
01211       _Distance __len = __last - __first;
01212       _Distancep __lenp = __lastp - __firstp;
01213       _Pointer __buffer_last = __buffer + __len;
01214       _Pointerp __buffer_lastp = __bufferp + __lenp;
01215 
01216       _Distance __step_size = _M_p_chunk_size;
01217       __chunk_insertion_p_sort(__first, __last, __firstp, __lastp, __step_size);
01218 
01219       while (__step_size < __len) {
01220         __merge_p_sort_loop(__first, __last, __buffer, __firstp, __lastp,
01221                             __bufferp, __step_size);
01222         __step_size *= 2;
01223         __merge_p_sort_loop(__buffer, __buffer_last, __first, __bufferp,
01224                             __buffer_lastp, __firstp, __step_size);
01225         __step_size *= 2;
01226       }
01227     }
01228 
01229   template<typename _RandomAccessIter, typename _RandomAccessIterp,
01230            typename _Pointer, typename _Pointerp, typename _Compare>
01231     void
01232     __merge_p_sort_with_buffer(_RandomAccessIter __first,
01233         _RandomAccessIter __last, _Pointer __buffer,
01234         _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
01235         _Pointerp __bufferp, _Compare __comp)
01236     {
01237       typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
01238       typedef typename iterator_traits<_RandomAccessIterp>::difference_type _Distancep;
01239 
01240       _Distance __len = __last - __first;
01241       _Distancep __lenp = __lastp - __firstp;
01242       _Pointer __buffer_last = __buffer + __len;
01243       _Pointerp __buffer_lastp = __bufferp + __lenp;
01244 
01245       _Distance __step_size = _M_p_chunk_size;
01246       __chunk_insertion_p_sort(__first, __last, __firstp, __lastp, __step_size,
01247                                __comp);
01248 
01249       while (__step_size < __len) {
01250         __merge_p_sort_loop(__first, __last, __buffer, __firstp, __lastp,
01251                             __bufferp, __step_size, __comp);
01252         __step_size *= 2;
01253         __merge_p_sort_loop(__buffer, __buffer_last, __first, __bufferp,
01254                             __buffer_lastp, __firstp, __step_size, __comp);
01255         __step_size *= 2;
01256       }
01257     }
01258 
01259   template<typename _RandomAccessIter, typename _Pointer,
01260            typename _RandomAccessIterp, typename _Pointerp, typename _Distance>
01261     void
01262     __stable_p_sort_adaptive(_RandomAccessIter __first,
01263                 _RandomAccessIter __last, _Pointer __buffer,
01264                 _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
01265                 _Pointerp __bufferp, _Distance __buffer_size)
01266     {
01267       _Distance __len = (__last - __first + 1) / 2;
01268       _RandomAccessIter __middle = __first + __len;
01269       _RandomAccessIterp __middlep = __firstp + __len;
01270       if (__len > __buffer_size) {
01271         __stable_p_sort_adaptive(__first, __middle, __buffer, __firstp,
01272                                  __middlep, __bufferp, __buffer_size);
01273         __stable_p_sort_adaptive(__middle, __last, __buffer, __middlep, __lastp,
01274                                  __bufferp, __buffer_size);
01275       }
01276       else {
01277         __merge_p_sort_with_buffer(__first, __middle, __buffer, __firstp,
01278                                    __middlep, __bufferp);
01279         __merge_p_sort_with_buffer(__middle, __last, __buffer, __middlep,
01280                                    __lastp, __bufferp);
01281       }
01282       __p_merge_adaptive(__first, __middle, __last, __firstp, __middlep,
01283           __lastp, _Distance(__middle - __first), _Distance(__last - __middle),
01284           __buffer, __bufferp, __buffer_size);
01285     }
01286 
01287   template<typename _RandomAccessIter, typename _Pointer,
01288            typename _RandomAccessIterp, typename _Pointerp, typename _Distance,
01289            typename _Compare>
01290     void
01291     __stable_p_sort_adaptive(_RandomAccessIter __first,
01292                 _RandomAccessIter __last, _Pointer __buffer,
01293                 _RandomAccessIterp __firstp, _RandomAccessIterp __lastp,
01294                 _Pointerp __bufferp, _Distance __buffer_size, _Compare __comp)
01295     {
01296       _Distance __len = (__last - __first + 1) / 2;
01297       _RandomAccessIter __middle = __first + __len;
01298       _RandomAccessIterp __middlep = __firstp + __len;
01299       if (__len > __buffer_size) {
01300         __stable_p_sort_adaptive(__first, __middle, __buffer, __firstp,
01301                                  __middlep, __bufferp, __buffer_size, __comp);
01302         __stable_p_sort_adaptive(__middle, __last, __buffer, __middlep, __lastp,
01303                                   __bufferp, __buffer_size, __comp);
01304       }
01305       else {
01306         __merge_p_sort_with_buffer(__first, __middle, __buffer, __firstp,
01307                                    __middlep, __bufferp, __comp);
01308         __merge_p_sort_with_buffer(__middle, __last, __buffer, __middlep,
01309                                    __lastp, __bufferp, __comp);
01310       }
01311       __p_merge_adaptive(__first, __middle, __last, __firstp, __middlep,
01312                 __lastp, _Distance(__middle - __first),
01313                 _Distance(__last - __middle), __buffer, __bufferp,
01314                 __buffer_size, __comp);
01315     }
01316 
01340   template<typename _RandomAccessIter, typename _RandomAccessIterp>
01341     inline bool
01342     stable_pair_sort(_RandomAccessIter __first, _RandomAccessIter __last,
01343                      _RandomAccessIterp __firstp, _RandomAccessIterp __lastp)
01344     {
01345       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
01346       typedef typename iterator_traits<_RandomAccessIterp>::value_type _ValueTypep;
01347       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
01348 
01349       // concept requirements
01350       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01351             _RandomAccessIter>)
01352       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01353             _RandomAccessIterp>)
01354       __ISTLGLIBCXX_function_requires(_LessThanComparableConcept<_ValueType>)
01355       __ISTLGLIBCXX_requires_valid_range(__first, __last);
01356       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
01357 
01358       if (__first - __last != __firstp - __lastp) return false;
01359 
01360       _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
01361       _Temporary_buffer<_RandomAccessIterp, _ValueTypep> bufp(__firstp, __lastp);
01362       if (buf.begin() == 0 || bufp.begin() == 0)
01363         __inplace_stable_p_sort(__first, __last, __firstp, __lastp);
01364       else
01365         __stable_p_sort_adaptive(__first, __last, buf.begin(), __firstp,
01366                          __lastp, bufp.begin(), _DistanceType(buf.size()));
01367       return true;
01368     }
01369 
01394   template<typename _RandomAccessIter, typename _RandomAccessIterp,
01395            typename _Compare>
01396     inline bool
01397     stable_sort(_RandomAccessIter __first, _RandomAccessIter __last,
01398        _RandomAccessIterp __firstp, _RandomAccessIterp __lastp, _Compare __comp)
01399     {
01400       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
01401       typedef typename iterator_traits<_RandomAccessIterp>::value_type _ValueTypep;
01402       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
01403 
01404       // concept requirements
01405       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01406             _RandomAccessIter>)
01407       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01408             _RandomAccessIterp>)
01409       __ISTLGLIBCXX_function_requires(_BinaryPredicateConcept<_Compare,
01410                                                           _ValueType, _ValueType>)
01411       __ISTLGLIBCXX_requires_valid_range(__first, __last);
01412       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
01413       if (__first - __last != __firstp - __lastp) return false;
01414 
01415       _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
01416       _Temporary_buffer<_RandomAccessIterp, _ValueTypep> bufp(__firstp, __lastp);
01417       if (buf.begin() == 0 || bufp.begin() == 0)
01418         __inplace_stable_p_sort(__first, __last, __firstp, __lastp, __comp);
01419       else
01420         __stable_p_sort_adaptive(__first, __last, buf.begin(), __firstp,
01421                 __lastp, bufp.begin(), _DistanceType(buf.size()), __comp);
01422       return true;
01423     }
01424 
01447   template<typename _RandomAccessIter, typename _RandomAccessIterp>
01448     bool
01449     partial_pair_sort(_RandomAccessIter __first,
01450                       _RandomAccessIter __middle,
01451                       _RandomAccessIter __last,
01452                       _RandomAccessIterp __firstp,
01453                       _RandomAccessIterp __lastp)
01454     {
01455       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
01456       typedef typename iterator_traits<_RandomAccessIterp>::value_type _ValueTypep;
01457 
01458       // concept requirements
01459       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01460             _RandomAccessIter>)
01461       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01462             _RandomAccessIterp>)
01463       __ISTLGLIBCXX_function_requires(_LessThanComparableConcept<_ValueType>)
01464       __ISTLGLIBCXX_requires_valid_range(__first, __last);
01465       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
01466 
01467       if (__first - __last != __firstp - __lastp) return false;
01468       
01469       _RandomAccessIterp __middlep = __firstp + (__middle - __first);
01470       
01471       make_pair_heap(__first, __middle, __firstp, __middlep);
01472       _RandomAccessIter __i;
01473       _RandomAccessIterp __ip;
01474       for (__i = __middle, __ip = __middlep; __i < __last; ++__i, ++__ip)
01475         if (*__i < *__first)
01476           __pop_pair_heap(__first, __middle, __i, _ValueType(*__i),
01477                           __firstp, __middlep, __ip, _ValueTypep(*__ip));
01478       sort_pair_heap(__first, __middle, __firstp, __middlep);
01479       return true;
01480     }
01481 
01504   template<typename _RandomAccessIter, typename _RandomAccessIterp,
01505            typename _Compare>
01506     bool
01507     partial_pair_sort(_RandomAccessIter __first,
01508                       _RandomAccessIter __middle,
01509                       _RandomAccessIter __last,
01510                       _RandomAccessIterp __firstp,
01511                       _RandomAccessIterp __lastp,
01512                       _Compare __comp)
01513     {
01514       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
01515       typedef typename iterator_traits<_RandomAccessIterp>::value_type _ValueTypep;
01516 
01517       // concept requirements
01518       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01519             _RandomAccessIter>)
01520       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01521             _RandomAccessIterp>)
01522       __ISTLGLIBCXX_function_requires(_BinaryPredicateConcept<_Compare,
01523                                                   _ValueType, _ValueType>)
01524       __ISTLGLIBCXX_requires_valid_range(__first, __last);
01525       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
01526 
01527       if (__first - __last != __firstp - __lastp) return false;
01528       
01529       _RandomAccessIterp __middlep = __firstp + (__middle - __first);
01530       
01531       make_pair_heap(__first, __middle, __firstp, __middlep, __comp);
01532       _RandomAccessIter __i;
01533       _RandomAccessIterp __ip;
01534       for (__i = __middle, __ip = __middlep; __i < __last; ++__i, ++__ip)
01535         if (*__i < *__first)
01536           __pop_pair_heap(__first, __middle, __i, _ValueType(*__i),
01537                         __firstp, __middlep, __ip, _ValueTypep(*__ip), __comp);
01538       sort_pair_heap(__first, __middle, __firstp, __middlep, __comp);
01539       return true;
01540     }
01541 
01567   template<typename _RandomAccessIter, typename _RandomAccessIterp,
01568            typename _Compare>
01569     bool
01570     partial_sort(_RandomAccessIter __first,
01571                  _RandomAccessIter __middle,
01572                  _RandomAccessIter __last,
01573                  _RandomAccessIter __firstp,
01574                  _RandomAccessIter __lastp,
01575                  _Compare __comp)
01576     {
01577       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
01578       typedef typename iterator_traits<_RandomAccessIterp>::value_type _ValueTypep;
01579 
01580       // concept requirements
01581       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01582             _RandomAccessIter>)
01583       __ISTLGLIBCXX_function_requires(_Mutable_RandomAccessIteratorConcept<
01584             _RandomAccessIterp>)
01585       __ISTLGLIBCXX_function_requires(_BinaryPredicateConcept<_Compare,
01586                                                   _ValueType, _ValueType>)
01587       __ISTLGLIBCXX_requires_valid_range(__first, __last);
01588       __ISTLGLIBCXX_requires_valid_range(__firstp, __lastp);
01589 
01590       if (__first - __last != __firstp - __lastp) return false;
01591       
01592       _RandomAccessIterp __middlep = __firstp + (__middle - __first);
01593       
01594       make_pair_heap(__first, __middle, __firstp, __middlep, __comp);
01595       _RandomAccessIter __i;
01596       _RandomAccessIterp __ip;
01597       for (__i = __middle, __ip = __middlep; __i < __last; ++__i, ++__ip)
01598         if (__comp(*__i, *__first))
01599           __pop_pair_heap(__first, __middle, __i, _ValueType(*__i),
01600                           __firstp, __middlep, __ip, _ValueType(*__ip), __comp);
01601       sort_pair_heap(__first, __middle, __firstp, __middlep, __comp);
01602     }
01603 
01604 } // namespace std
01605 
01606 #endif /* __STLP_ADDALGO_H */
01607