GNU C++ STL: stl_algo.h Source File

00001 // Algorithm implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004 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  *
00044  * Copyright (c) 1996
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00061 #ifndef _ALGO_H
00062 #define _ALGO_H 1
00063 
00064 #include <bits/stl_heap.h>
00065 #include <bits/stl_tempbuf.h>     // for _Temporary_buffer
00066 #include <debug/debug.h>
00067 
00068 // See concept_check.h for the __glibcxx_*_requires macros.
00069 
00070 namespace std
00071 {
00084   template<typename _Tp>
00085     inline const _Tp&
00086     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
00087     {
00088       // concept requirements
00089       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00090       if (__a < __b)
00091     if (__b < __c)
00092       return __b;
00093     else if (__a < __c)
00094       return __c;
00095     else
00096       return __a;
00097       else if (__a < __c)
00098     return __a;
00099       else if (__b < __c)
00100     return __c;
00101       else
00102     return __b;
00103     }
00104 
00118   template<typename _Tp, typename _Compare>
00119     inline const _Tp&
00120     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
00121     {
00122       // concept requirements
00123       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
00124       if (__comp(__a, __b))
00125     if (__comp(__b, __c))
00126       return __b;
00127     else if (__comp(__a, __c))
00128       return __c;
00129     else
00130       return __a;
00131       else if (__comp(__a, __c))
00132     return __a;
00133       else if (__comp(__b, __c))
00134     return __c;
00135       else
00136     return __b;
00137     }
00138 
00150   template<typename _InputIterator, typename _Function>
00151     _Function
00152     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
00153     {
00154       // concept requirements
00155       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00156       __glibcxx_requires_valid_range(__first, __last);
00157       for ( ; __first != __last; ++__first)
00158     __f(*__first);
00159       return __f;
00160     }
00161 
00167   template<typename _InputIterator, typename _Tp>
00168     inline _InputIterator
00169     find(_InputIterator __first, _InputIterator __last,
00170      const _Tp& __val, input_iterator_tag)
00171     {
00172       while (__first != __last && !(*__first == __val))
00173     ++__first;
00174       return __first;
00175     }
00176 
00182   template<typename _InputIterator, typename _Predicate>
00183     inline _InputIterator
00184     find_if(_InputIterator __first, _InputIterator __last,
00185         _Predicate __pred, input_iterator_tag)
00186     {
00187       while (__first != __last && !__pred(*__first))
00188     ++__first;
00189       return __first;
00190     }
00191 
00197   template<typename _RandomAccessIterator, typename _Tp>
00198     _RandomAccessIterator
00199     find(_RandomAccessIterator __first, _RandomAccessIterator __last,
00200      const _Tp& __val, random_access_iterator_tag)
00201     {
00202       typename iterator_traits<_RandomAccessIterator>::difference_type
00203     __trip_count = (__last - __first) >> 2;
00204 
00205       for ( ; __trip_count > 0 ; --__trip_count)
00206     {
00207       if (*__first == __val)
00208         return __first;
00209       ++__first;
00210 
00211       if (*__first == __val)
00212         return __first;
00213       ++__first;
00214 
00215       if (*__first == __val)
00216         return __first;
00217       ++__first;
00218 
00219       if (*__first == __val)
00220         return __first;
00221       ++__first;
00222     }
00223 
00224       switch (__last - __first)
00225     {
00226     case 3:
00227       if (*__first == __val)
00228         return __first;
00229       ++__first;
00230     case 2:
00231       if (*__first == __val)
00232         return __first;
00233       ++__first;
00234     case 1:
00235       if (*__first == __val)
00236         return __first;
00237       ++__first;
00238     case 0:
00239     default:
00240       return __last;
00241     }
00242     }
00243 
00249   template<typename _RandomAccessIterator, typename _Predicate>
00250     _RandomAccessIterator
00251     find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
00252         _Predicate __pred, random_access_iterator_tag)
00253     {
00254       typename iterator_traits<_RandomAccessIterator>::difference_type
00255     __trip_count = (__last - __first) >> 2;
00256 
00257       for ( ; __trip_count > 0 ; --__trip_count)
00258     {
00259       if (__pred(*__first))
00260         return __first;
00261       ++__first;
00262 
00263       if (__pred(*__first))
00264         return __first;
00265       ++__first;
00266 
00267       if (__pred(*__first))
00268         return __first;
00269       ++__first;
00270 
00271       if (__pred(*__first))
00272         return __first;
00273       ++__first;
00274     }
00275 
00276       switch (__last - __first)
00277     {
00278     case 3:
00279       if (__pred(*__first))
00280         return __first;
00281       ++__first;
00282     case 2:
00283       if (__pred(*__first))
00284         return __first;
00285       ++__first;
00286     case 1:
00287       if (__pred(*__first))
00288         return __first;
00289       ++__first;
00290     case 0:
00291     default:
00292       return __last;
00293     }
00294     }
00295 
00304   template<typename _InputIterator, typename _Tp>
00305     inline _InputIterator
00306     find(_InputIterator __first, _InputIterator __last,
00307      const _Tp& __val)
00308     {
00309       // concept requirements
00310       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00311       __glibcxx_function_requires(_EqualOpConcept<
00312         typename iterator_traits<_InputIterator>::value_type, _Tp>)
00313       __glibcxx_requires_valid_range(__first, __last);
00314       return std::find(__first, __last, __val,
00315                std::__iterator_category(__first));
00316     }
00317 
00326   template<typename _InputIterator, typename _Predicate>
00327     inline _InputIterator
00328     find_if(_InputIterator __first, _InputIterator __last,
00329         _Predicate __pred)
00330     {
00331       // concept requirements
00332       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00333       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00334           typename iterator_traits<_InputIterator>::value_type>)
00335       __glibcxx_requires_valid_range(__first, __last);
00336       return std::find_if(__first, __last, __pred,
00337               std::__iterator_category(__first));
00338     }
00339 
00348   template<typename _ForwardIterator>
00349     _ForwardIterator
00350     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
00351     {
00352       // concept requirements
00353       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00354       __glibcxx_function_requires(_EqualityComparableConcept<
00355         typename iterator_traits<_ForwardIterator>::value_type>)
00356       __glibcxx_requires_valid_range(__first, __last);
00357       if (__first == __last)
00358     return __last;
00359       _ForwardIterator __next = __first;
00360       while(++__next != __last)
00361     {
00362       if (*__first == *__next)
00363         return __first;
00364       __first = __next;
00365     }
00366       return __last;
00367     }
00368 
00379   template<typename _ForwardIterator, typename _BinaryPredicate>
00380     _ForwardIterator
00381     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
00382           _BinaryPredicate __binary_pred)
00383     {
00384       // concept requirements
00385       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00386       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00387         typename iterator_traits<_ForwardIterator>::value_type,
00388         typename iterator_traits<_ForwardIterator>::value_type>)
00389       __glibcxx_requires_valid_range(__first, __last);
00390       if (__first == __last)
00391     return __last;
00392       _ForwardIterator __next = __first;
00393       while(++__next != __last)
00394     {
00395       if (__binary_pred(*__first, *__next))
00396         return __first;
00397       __first = __next;
00398     }
00399       return __last;
00400     }
00401 
00410   template<typename _InputIterator, typename _Tp>
00411     typename iterator_traits<_InputIterator>::difference_type
00412     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
00413     {
00414       // concept requirements
00415       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00416       __glibcxx_function_requires(_EqualityComparableConcept<
00417         typename iterator_traits<_InputIterator>::value_type >)
00418       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
00419       __glibcxx_requires_valid_range(__first, __last);
00420       typename iterator_traits<_InputIterator>::difference_type __n = 0;
00421       for ( ; __first != __last; ++__first)
00422     if (*__first == __value)
00423       ++__n;
00424       return __n;
00425     }
00426 
00435   template<typename _InputIterator, typename _Predicate>
00436     typename iterator_traits<_InputIterator>::difference_type
00437     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
00438     {
00439       // concept requirements
00440       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00441       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00442         typename iterator_traits<_InputIterator>::value_type>)
00443       __glibcxx_requires_valid_range(__first, __last);
00444       typename iterator_traits<_InputIterator>::difference_type __n = 0;
00445       for ( ; __first != __last; ++__first)
00446     if (__pred(*__first))
00447       ++__n;
00448       return __n;
00449     }
00450 
00474   template<typename _ForwardIterator1, typename _ForwardIterator2>
00475     _ForwardIterator1
00476     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00477        _ForwardIterator2 __first2, _ForwardIterator2 __last2)
00478     {
00479       // concept requirements
00480       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
00481       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
00482       __glibcxx_function_requires(_EqualOpConcept<
00483         typename iterator_traits<_ForwardIterator1>::value_type,
00484         typename iterator_traits<_ForwardIterator2>::value_type>)
00485       __glibcxx_requires_valid_range(__first1, __last1);
00486       __glibcxx_requires_valid_range(__first2, __last2);
00487       // Test for empty ranges
00488       if (__first1 == __last1 || __first2 == __last2)
00489     return __first1;
00490 
00491       // Test for a pattern of length 1.
00492       _ForwardIterator2 __tmp(__first2);
00493       ++__tmp;
00494       if (__tmp == __last2)
00495     return std::find(__first1, __last1, *__first2);
00496 
00497       // General case.
00498       _ForwardIterator2 __p1, __p;
00499       __p1 = __first2; ++__p1;
00500       _ForwardIterator1 __current = __first1;
00501 
00502       while (__first1 != __last1)
00503     {
00504       __first1 = std::find(__first1, __last1, *__first2);
00505       if (__first1 == __last1)
00506         return __last1;
00507 
00508       __p = __p1;
00509       __current = __first1;
00510       if (++__current == __last1)
00511         return __last1;
00512 
00513       while (*__current == *__p)
00514         {
00515           if (++__p == __last2)
00516         return __first1;
00517           if (++__current == __last1)
00518         return __last1;
00519         }
00520       ++__first1;
00521     }
00522       return __first1;
00523     }
00524 
00545   template<typename _ForwardIterator1, typename _ForwardIterator2,
00546        typename _BinaryPredicate>
00547     _ForwardIterator1
00548     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00549        _ForwardIterator2 __first2, _ForwardIterator2 __last2,
00550        _BinaryPredicate  __predicate)
00551     {
00552       // concept requirements
00553       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
00554       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
00555       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00556         typename iterator_traits<_ForwardIterator1>::value_type,
00557         typename iterator_traits<_ForwardIterator2>::value_type>)
00558       __glibcxx_requires_valid_range(__first1, __last1);
00559       __glibcxx_requires_valid_range(__first2, __last2);
00560 
00561       // Test for empty ranges
00562       if (__first1 == __last1 || __first2 == __last2)
00563     return __first1;
00564 
00565       // Test for a pattern of length 1.
00566       _ForwardIterator2 __tmp(__first2);
00567       ++__tmp;
00568       if (__tmp == __last2)
00569     {
00570       while (__first1 != __last1 && !__predicate(*__first1, *__first2))
00571         ++__first1;
00572       return __first1;
00573     }
00574 
00575       // General case.
00576       _ForwardIterator2 __p1, __p;
00577       __p1 = __first2; ++__p1;
00578       _ForwardIterator1 __current = __first1;
00579 
00580       while (__first1 != __last1)
00581     {
00582       while (__first1 != __last1)
00583         {
00584           if (__predicate(*__first1, *__first2))
00585         break;
00586           ++__first1;
00587         }
00588       while (__first1 != __last1 && !__predicate(*__first1, *__first2))
00589         ++__first1;
00590       if (__first1 == __last1)
00591         return __last1;
00592 
00593       __p = __p1;
00594       __current = __first1;
00595       if (++__current == __last1)
00596         return __last1;
00597 
00598       while (__predicate(*__current, *__p))
00599         {
00600           if (++__p == __last2)
00601         return __first1;
00602           if (++__current == __last1)
00603         return __last1;
00604         }
00605       ++__first1;
00606     }
00607       return __first1;
00608     }
00609 
00623   template<typename _ForwardIterator, typename _Integer, typename _Tp>
00624     _ForwardIterator
00625     search_n(_ForwardIterator __first, _ForwardIterator __last,
00626          _Integer __count, const _Tp& __val)
00627     {
00628       // concept requirements
00629       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00630       __glibcxx_function_requires(_EqualityComparableConcept<
00631         typename iterator_traits<_ForwardIterator>::value_type>)
00632       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
00633       __glibcxx_requires_valid_range(__first, __last);
00634 
00635       if (__count <= 0)
00636     return __first;
00637       else
00638     {
00639       __first = std::find(__first, __last, __val);
00640       while (__first != __last)
00641         {
00642           typename iterator_traits<_ForwardIterator>::difference_type
00643         __n = __count;
00644           _ForwardIterator __i = __first;
00645           ++__i;
00646           while (__i != __last && __n != 1 && *__i == __val)
00647         {
00648           ++__i;
00649           --__n;
00650         }
00651           if (__n == 1)
00652         return __first;
00653           else
00654         __first = std::find(__i, __last, __val);
00655         }
00656       return __last;
00657     }
00658     }
00659 
00675   template<typename _ForwardIterator, typename _Integer, typename _Tp,
00676            typename _BinaryPredicate>
00677     _ForwardIterator
00678     search_n(_ForwardIterator __first, _ForwardIterator __last,
00679          _Integer __count, const _Tp& __val,
00680          _BinaryPredicate __binary_pred)
00681     {
00682       // concept requirements
00683       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00684       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00685         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
00686       __glibcxx_requires_valid_range(__first, __last);
00687 
00688       if (__count <= 0)
00689     return __first;
00690       else
00691     {
00692       while (__first != __last)
00693         {
00694           if (__binary_pred(*__first, __val))
00695         break;
00696           ++__first;
00697         }
00698       while (__first != __last)
00699         {
00700           typename iterator_traits<_ForwardIterator>::difference_type
00701         __n = __count;
00702           _ForwardIterator __i = __first;
00703           ++__i;
00704           while (__i != __last && __n != 1 && __binary_pred(*__i, __val))
00705         {
00706           ++__i;
00707           --__n;
00708         }
00709           if (__n == 1)
00710         return __first;
00711           else
00712         {
00713           while (__i != __last)
00714             {
00715               if (__binary_pred(*__i, __val))
00716             break;
00717               ++__i;
00718             }
00719           __first = __i;
00720         }
00721         }
00722       return __last;
00723     }
00724     }
00725 
00737   template<typename _ForwardIterator1, typename _ForwardIterator2>
00738     _ForwardIterator2
00739     swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00740         _ForwardIterator2 __first2)
00741     {
00742       // concept requirements
00743       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00744                   _ForwardIterator1>)
00745       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00746                   _ForwardIterator2>)
00747       __glibcxx_function_requires(_ConvertibleConcept<
00748         typename iterator_traits<_ForwardIterator1>::value_type,
00749         typename iterator_traits<_ForwardIterator2>::value_type>)
00750       __glibcxx_function_requires(_ConvertibleConcept<
00751         typename iterator_traits<_ForwardIterator2>::value_type,
00752         typename iterator_traits<_ForwardIterator1>::value_type>)
00753       __glibcxx_requires_valid_range(__first1, __last1);
00754 
00755       for ( ; __first1 != __last1; ++__first1, ++__first2)
00756     std::iter_swap(__first1, __first2);
00757       return __first2;
00758     }
00759 
00775   template<typename _InputIterator, typename _OutputIterator,
00776        typename _UnaryOperation>
00777     _OutputIterator
00778     transform(_InputIterator __first, _InputIterator __last,
00779           _OutputIterator __result, _UnaryOperation __unary_op)
00780     {
00781       // concept requirements
00782       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00783       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00784             // "the type returned by a _UnaryOperation"
00785             __typeof__(__unary_op(*__first))>)
00786       __glibcxx_requires_valid_range(__first, __last);
00787 
00788       for ( ; __first != __last; ++__first, ++__result)
00789     *__result = __unary_op(*__first);
00790       return __result;
00791     }
00792 
00810   template<typename _InputIterator1, typename _InputIterator2,
00811        typename _OutputIterator, typename _BinaryOperation>
00812     _OutputIterator
00813     transform(_InputIterator1 __first1, _InputIterator1 __last1,
00814           _InputIterator2 __first2, _OutputIterator __result,
00815           _BinaryOperation __binary_op)
00816     {
00817       // concept requirements
00818       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00819       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00820       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00821             // "the type returned by a _BinaryOperation"
00822             __typeof__(__binary_op(*__first1,*__first2))>)
00823       __glibcxx_requires_valid_range(__first1, __last1);
00824 
00825       for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
00826     *__result = __binary_op(*__first1, *__first2);
00827       return __result;
00828     }
00829 
00842   template<typename _ForwardIterator, typename _Tp>
00843     void
00844     replace(_ForwardIterator __first, _ForwardIterator __last,
00845         const _Tp& __old_value, const _Tp& __new_value)
00846     {
00847       // concept requirements
00848       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00849                   _ForwardIterator>)
00850       __glibcxx_function_requires(_EqualOpConcept<
00851         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
00852       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
00853         typename iterator_traits<_ForwardIterator>::value_type>)
00854       __glibcxx_requires_valid_range(__first, __last);
00855 
00856       for ( ; __first != __last; ++__first)
00857     if (*__first == __old_value)
00858       *__first = __new_value;
00859     }
00860 
00873   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
00874     void
00875     replace_if(_ForwardIterator __first, _ForwardIterator __last,
00876            _Predicate __pred, const _Tp& __new_value)
00877     {
00878       // concept requirements
00879       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00880                   _ForwardIterator>)
00881       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
00882         typename iterator_traits<_ForwardIterator>::value_type>)
00883       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00884         typename iterator_traits<_ForwardIterator>::value_type>)
00885       __glibcxx_requires_valid_range(__first, __last);
00886 
00887       for ( ; __first != __last; ++__first)
00888     if (__pred(*__first))
00889       *__first = __new_value;
00890     }
00891 
00906   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
00907     _OutputIterator
00908     replace_copy(_InputIterator __first, _InputIterator __last,
00909          _OutputIterator __result,
00910          const _Tp& __old_value, const _Tp& __new_value)
00911     {
00912       // concept requirements
00913       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00914       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00915         typename iterator_traits<_InputIterator>::value_type>)
00916       __glibcxx_function_requires(_EqualOpConcept<
00917         typename iterator_traits<_InputIterator>::value_type, _Tp>)
00918       __glibcxx_requires_valid_range(__first, __last);
00919 
00920       for ( ; __first != __last; ++__first, ++__result)
00921     *__result = *__first == __old_value ? __new_value : *__first;
00922       return __result;
00923     }
00924 
00939   template<typename _InputIterator, typename _OutputIterator,
00940        typename _Predicate, typename _Tp>
00941     _OutputIterator
00942     replace_copy_if(_InputIterator __first, _InputIterator __last,
00943             _OutputIterator __result,
00944             _Predicate __pred, const _Tp& __new_value)
00945     {
00946       // concept requirements
00947       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00948       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00949         typename iterator_traits<_InputIterator>::value_type>)
00950       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00951         typename iterator_traits<_InputIterator>::value_type>)
00952       __glibcxx_requires_valid_range(__first, __last);
00953 
00954       for ( ; __first != __last; ++__first, ++__result)
00955     *__result = __pred(*__first) ? __new_value : *__first;
00956       return __result;
00957     }
00958 
00970   template<typename _ForwardIterator, typename _Generator>
00971     void
00972     generate(_ForwardIterator __first, _ForwardIterator __last,
00973          _Generator __gen)
00974     {
00975       // concept requirements
00976       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00977       __glibcxx_function_requires(_GeneratorConcept<_Generator,
00978         typename iterator_traits<_ForwardIterator>::value_type>)
00979       __glibcxx_requires_valid_range(__first, __last);
00980 
00981       for ( ; __first != __last; ++__first)
00982     *__first = __gen();
00983     }
00984 
00996   template<typename _OutputIterator, typename _Size, typename _Generator>
00997     _OutputIterator
00998     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
00999     {
01000       // concept requirements
01001       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01002             // "the type returned by a _Generator"
01003             __typeof__(__gen())>)
01004 
01005       for ( ; __n > 0; --__n, ++__first)
01006     *__first = __gen();
01007       return __first;
01008     }
01009 
01023   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
01024     _OutputIterator
01025     remove_copy(_InputIterator __first, _InputIterator __last,
01026         _OutputIterator __result, const _Tp& __value)
01027     {
01028       // concept requirements
01029       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01030       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01031         typename iterator_traits<_InputIterator>::value_type>)
01032       __glibcxx_function_requires(_EqualOpConcept<
01033         typename iterator_traits<_InputIterator>::value_type, _Tp>)
01034       __glibcxx_requires_valid_range(__first, __last);
01035 
01036       for ( ; __first != __last; ++__first)
01037     if (!(*__first == __value))
01038       {
01039         *__result = *__first;
01040         ++__result;
01041       }
01042       return __result;
01043     }
01044 
01059   template<typename _InputIterator, typename _OutputIterator,
01060        typename _Predicate>
01061     _OutputIterator
01062     remove_copy_if(_InputIterator __first, _InputIterator __last,
01063            _OutputIterator __result, _Predicate __pred)
01064     {
01065       // concept requirements
01066       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01067       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01068         typename iterator_traits<_InputIterator>::value_type>)
01069       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01070         typename iterator_traits<_InputIterator>::value_type>)
01071       __glibcxx_requires_valid_range(__first, __last);
01072 
01073       for ( ; __first != __last; ++__first)
01074     if (!__pred(*__first))
01075       {
01076         *__result = *__first;
01077         ++__result;
01078       }
01079       return __result;
01080     }
01081 
01098   template<typename _ForwardIterator, typename _Tp>
01099     _ForwardIterator
01100     remove(_ForwardIterator __first, _ForwardIterator __last,
01101        const _Tp& __value)
01102     {
01103       // concept requirements
01104       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01105                   _ForwardIterator>)
01106       __glibcxx_function_requires(_EqualOpConcept<
01107         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
01108       __glibcxx_requires_valid_range(__first, __last);
01109 
01110       __first = std::find(__first, __last, __value);
01111       _ForwardIterator __i = __first;
01112       return __first == __last ? __first
01113                    : std::remove_copy(++__i, __last,
01114                           __first, __value);
01115     }
01116 
01133   template<typename _ForwardIterator, typename _Predicate>
01134     _ForwardIterator
01135     remove_if(_ForwardIterator __first, _ForwardIterator __last,
01136           _Predicate __pred)
01137     {
01138       // concept requirements
01139       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01140                   _ForwardIterator>)
01141       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01142         typename iterator_traits<_ForwardIterator>::value_type>)
01143       __glibcxx_requires_valid_range(__first, __last);
01144 
01145       __first = std::find_if(__first, __last, __pred);
01146       _ForwardIterator __i = __first;
01147       return __first == __last ? __first
01148                    : std::remove_copy_if(++__i, __last,
01149                              __first, __pred);
01150     }
01151 
01159   template<typename _InputIterator, typename _OutputIterator>
01160     _OutputIterator
01161     __unique_copy(_InputIterator __first, _InputIterator __last,
01162           _OutputIterator __result,
01163           output_iterator_tag)
01164     {
01165       // concept requirements -- taken care of in dispatching function
01166       typename iterator_traits<_InputIterator>::value_type __value = *__first;
01167       *__result = __value;
01168       while (++__first != __last)
01169     if (!(__value == *__first))
01170       {
01171         __value = *__first;
01172         *++__result = __value;
01173       }
01174       return ++__result;
01175     }
01176 
01184   template<typename _InputIterator, typename _ForwardIterator>
01185     _ForwardIterator
01186     __unique_copy(_InputIterator __first, _InputIterator __last,
01187           _ForwardIterator __result,
01188           forward_iterator_tag)
01189     {
01190       // concept requirements -- taken care of in dispatching function
01191       *__result = *__first;
01192       while (++__first != __last)
01193     if (!(*__result == *__first))
01194       *++__result = *__first;
01195       return ++__result;
01196     }
01197 
01206   template<typename _InputIterator, typename _OutputIterator,
01207        typename _BinaryPredicate>
01208     _OutputIterator
01209     __unique_copy(_InputIterator __first, _InputIterator __last,
01210           _OutputIterator __result,
01211           _BinaryPredicate __binary_pred,
01212           output_iterator_tag)
01213     {
01214       // concept requirements -- iterators already checked
01215       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01216       typename iterator_traits<_InputIterator>::value_type,
01217       typename iterator_traits<_InputIterator>::value_type>)
01218 
01219       typename iterator_traits<_InputIterator>::value_type __value = *__first;
01220       *__result = __value;
01221       while (++__first != __last)
01222     if (!__binary_pred(__value, *__first))
01223       {
01224         __value = *__first;
01225         *++__result = __value;
01226       }
01227       return ++__result;
01228     }
01229 
01238   template<typename _InputIterator, typename _ForwardIterator,
01239        typename _BinaryPredicate>
01240     _ForwardIterator
01241     __unique_copy(_InputIterator __first, _InputIterator __last,
01242           _ForwardIterator __result,
01243           _BinaryPredicate __binary_pred,
01244           forward_iterator_tag)
01245     {
01246       // concept requirements -- iterators already checked
01247       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01248         typename iterator_traits<_ForwardIterator>::value_type,
01249         typename iterator_traits<_InputIterator>::value_type>)
01250 
01251       *__result = *__first;
01252       while (++__first != __last)
01253     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
01254       return ++__result;
01255     }
01256 
01270   template<typename _InputIterator, typename _OutputIterator>
01271     inline _OutputIterator
01272     unique_copy(_InputIterator __first, _InputIterator __last,
01273         _OutputIterator __result)
01274     {
01275       // concept requirements
01276       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01277       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01278         typename iterator_traits<_InputIterator>::value_type>)
01279       __glibcxx_function_requires(_EqualityComparableConcept<
01280         typename iterator_traits<_InputIterator>::value_type>)
01281       __glibcxx_requires_valid_range(__first, __last);
01282 
01283       typedef typename iterator_traits<_OutputIterator>::iterator_category
01284     _IterType;
01285 
01286       if (__first == __last) return __result;
01287       return std::__unique_copy(__first, __last, __result, _IterType());
01288     }
01289 
01305   template<typename _InputIterator, typename _OutputIterator,
01306        typename _BinaryPredicate>
01307     inline _OutputIterator
01308     unique_copy(_InputIterator __first, _InputIterator __last,
01309         _OutputIterator __result,
01310         _BinaryPredicate __binary_pred)
01311     {
01312       // concept requirements -- predicates checked later
01313       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01314       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01315         typename iterator_traits<_InputIterator>::value_type>)
01316       __glibcxx_requires_valid_range(__first, __last);
01317 
01318       typedef typename iterator_traits<_OutputIterator>::iterator_category
01319     _IterType;
01320 
01321       if (__first == __last) return __result;
01322       return std::__unique_copy(__first, __last, __result,
01323                 __binary_pred, _IterType());
01324     }
01325 
01339   template<typename _ForwardIterator>
01340     _ForwardIterator
01341     unique(_ForwardIterator __first, _ForwardIterator __last)
01342     {
01343       // concept requirements
01344       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01345                   _ForwardIterator>)
01346       __glibcxx_function_requires(_EqualityComparableConcept<
01347              typename iterator_traits<_ForwardIterator>::value_type>)
01348       __glibcxx_requires_valid_range(__first, __last);
01349 
01350       // Skip the beginning, if already unique.
01351       __first = std::adjacent_find(__first, __last);
01352       if (__first == __last)
01353     return __last;
01354 
01355       // Do the real copy work.
01356       _ForwardIterator __dest = __first;
01357       ++__first;
01358       while (++__first != __last)
01359     if (!(*__dest == *__first))
01360       *++__dest = *__first;
01361       return ++__dest;
01362     }
01363 
01378   template<typename _ForwardIterator, typename _BinaryPredicate>
01379     _ForwardIterator
01380     unique(_ForwardIterator __first, _ForwardIterator __last,
01381            _BinaryPredicate __binary_pred)
01382     {
01383       // concept requirements
01384       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01385                   _ForwardIterator>)
01386       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01387         typename iterator_traits<_ForwardIterator>::value_type,
01388         typename iterator_traits<_ForwardIterator>::value_type>)
01389       __glibcxx_requires_valid_range(__first, __last);
01390 
01391       // Skip the beginning, if already unique.
01392       __first = std::adjacent_find(__first, __last, __binary_pred);
01393       if (__first == __last)
01394     return __last;
01395 
01396       // Do the real copy work.
01397       _ForwardIterator __dest = __first;
01398       ++__first;
01399       while (++__first != __last)
01400     if (!__binary_pred(*__dest, *__first))
01401       *++__dest = *__first;
01402       return ++__dest;
01403     }
01404 
01412   template<typename _BidirectionalIterator>
01413     void
01414     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
01415               bidirectional_iterator_tag)
01416     {
01417       while (true)
01418     if (__first == __last || __first == --__last)
01419       return;
01420     else
01421       std::iter_swap(__first++, __last);
01422     }
01423 
01431   template<typename _RandomAccessIterator>
01432     void
01433     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
01434               random_access_iterator_tag)
01435     {
01436       while (__first < __last)
01437     std::iter_swap(__first++, --__last);
01438     }
01439 
01451   template<typename _BidirectionalIterator>
01452     inline void
01453     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
01454     {
01455       // concept requirements
01456       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01457             _BidirectionalIterator>)
01458       __glibcxx_requires_valid_range(__first, __last);
01459       std::__reverse(__first, __last, std::__iterator_category(__first));
01460     }
01461 
01477   template<typename _BidirectionalIterator, typename _OutputIterator>
01478     _OutputIterator
01479     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
01480                  _OutputIterator __result)
01481     {
01482       // concept requirements
01483       __glibcxx_function_requires(_BidirectionalIteratorConcept<
01484                   _BidirectionalIterator>)
01485       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01486         typename iterator_traits<_BidirectionalIterator>::value_type>)
01487       __glibcxx_requires_valid_range(__first, __last);
01488 
01489       while (__first != __last)
01490     {
01491       --__last;
01492       *__result = *__last;
01493       ++__result;
01494     }
01495       return __result;
01496     }
01497 
01498 
01505   template<typename _EuclideanRingElement>
01506     _EuclideanRingElement
01507     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
01508     {
01509       while (__n != 0)
01510     {
01511       _EuclideanRingElement __t = __m % __n;
01512       __m = __n;
01513       __n = __t;
01514     }
01515       return __m;
01516     }
01517 
01523   template<typename _ForwardIterator>
01524     void
01525     __rotate(_ForwardIterator __first,
01526          _ForwardIterator __middle,
01527          _ForwardIterator __last,
01528           forward_iterator_tag)
01529     {
01530       if ((__first == __middle) || (__last  == __middle))
01531     return;
01532 
01533       _ForwardIterator __first2 = __middle;
01534       do
01535     {
01536       swap(*__first++, *__first2++);
01537       if (__first == __middle)
01538         __middle = __first2;
01539     }
01540       while (__first2 != __last);
01541 
01542       __first2 = __middle;
01543 
01544       while (__first2 != __last)
01545     {
01546       swap(*__first++, *__first2++);
01547       if (__first == __middle)
01548         __middle = __first2;
01549       else if (__first2 == __last)
01550         __first2 = __middle;
01551     }
01552     }
01553 
01559   template<typename _BidirectionalIterator>
01560     void
01561     __rotate(_BidirectionalIterator __first,
01562          _BidirectionalIterator __middle,
01563          _BidirectionalIterator __last,
01564           bidirectional_iterator_tag)
01565     {
01566       // concept requirements
01567       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01568         _BidirectionalIterator>)
01569 
01570       if ((__first == __middle) || (__last  == __middle))
01571     return;
01572 
01573       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01574       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01575 
01576       while (__first != __middle && __middle != __last)
01577     swap(*__first++, *--__last);
01578 
01579       if (__first == __middle)
01580     std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01581       else
01582     std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01583     }
01584 
01590   template<typename _RandomAccessIterator>
01591     void
01592     __rotate(_RandomAccessIterator __first,
01593          _RandomAccessIterator __middle,
01594          _RandomAccessIterator __last,
01595          random_access_iterator_tag)
01596     {
01597       // concept requirements
01598       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01599         _RandomAccessIterator>)
01600 
01601       if ((__first == __middle) || (__last  == __middle))
01602     return;
01603 
01604       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01605     _Distance;
01606       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01607     _ValueType;
01608 
01609       const _Distance __n = __last   - __first;
01610       const _Distance __k = __middle - __first;
01611       const _Distance __l = __n - __k;
01612 
01613       if (__k == __l)
01614     {
01615       std::swap_ranges(__first, __middle, __middle);
01616       return;
01617     }
01618 
01619       const _Distance __d = __gcd(__n, __k);
01620 
01621       for (_Distance __i = 0; __i < __d; __i++)
01622     {
01623       const _ValueType __tmp = *__first;
01624       _RandomAccessIterator __p = __first;
01625 
01626       if (__k < __l)
01627         {
01628           for (_Distance __j = 0; __j < __l / __d; __j++)
01629         {
01630           if (__p > __first + __l)
01631             {
01632               *__p = *(__p - __l);
01633               __p -= __l;
01634             }
01635 
01636           *__p = *(__p + __k);
01637           __p += __k;
01638         }
01639         }
01640       else
01641         {
01642           for (_Distance __j = 0; __j < __k / __d - 1; __j ++)
01643         {
01644           if (__p < __last - __k)
01645             {
01646               *__p = *(__p + __k);
01647               __p += __k;
01648             }
01649           *__p = * (__p - __l);
01650           __p -= __l;
01651         }
01652         }
01653 
01654       *__p = __tmp;
01655       ++__first;
01656     }
01657     }
01658 
01677   template<typename _ForwardIterator>
01678     inline void
01679     rotate(_ForwardIterator __first, _ForwardIterator __middle,
01680        _ForwardIterator __last)
01681     {
01682       // concept requirements
01683       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01684                   _ForwardIterator>)
01685       __glibcxx_requires_valid_range(__first, __middle);
01686       __glibcxx_requires_valid_range(__middle, __last);
01687 
01688       typedef typename iterator_traits<_ForwardIterator>::iterator_category
01689     _IterType;
01690       std::__rotate(__first, __middle, __last, _IterType());
01691     }
01692 
01710   template<typename _ForwardIterator, typename _OutputIterator>
01711     _OutputIterator
01712     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
01713                 _ForwardIterator __last, _OutputIterator __result)
01714     {
01715       // concept requirements
01716       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
01717       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01718         typename iterator_traits<_ForwardIterator>::value_type>)
01719       __glibcxx_requires_valid_range(__first, __middle);
01720       __glibcxx_requires_valid_range(__middle, __last);
01721 
01722       return std::copy(__first, __middle, copy(__middle, __last, __result));
01723     }
01724 
01735   template<typename _RandomAccessIterator>
01736     inline void
01737     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
01738     {
01739       // concept requirements
01740       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01741         _RandomAccessIterator>)
01742       __glibcxx_requires_valid_range(__first, __last);
01743 
01744       if (__first != __last)
01745     for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
01746       std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
01747     }
01748 
01762   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
01763     void
01764     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
01765            _RandomNumberGenerator& __rand)
01766     {
01767       // concept requirements
01768       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01769         _RandomAccessIterator>)
01770       __glibcxx_requires_valid_range(__first, __last);
01771 
01772       if (__first == __last)
01773     return;
01774       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
01775     std::iter_swap(__i, __first + __rand((__i - __first) + 1));
01776     }
01777 
01778 
01784   template<typename _ForwardIterator, typename _Predicate>
01785     _ForwardIterator
01786     __partition(_ForwardIterator __first, _ForwardIterator __last,
01787         _Predicate __pred,
01788         forward_iterator_tag)
01789     {
01790       if (__first == __last)
01791     return __first;
01792 
01793       while (__pred(*__first))
01794     if (++__first == __last)
01795       return __first;
01796 
01797       _ForwardIterator __next = __first;
01798 
01799       while (++__next != __last)
01800     if (__pred(*__next))
01801       {
01802         swap(*__first, *__next);
01803         ++__first;
01804       }
01805 
01806       return __first;
01807     }
01808 
01814   template<typename _BidirectionalIterator, typename _Predicate>
01815     _BidirectionalIterator
01816     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
01817         _Predicate __pred,
01818         bidirectional_iterator_tag)
01819     {
01820       while (true)
01821     {
01822       while (true)
01823         if (__first == __last)
01824           return __first;
01825         else if (__pred(*__first))
01826           ++__first;
01827         else
01828           break;
01829       --__last;
01830       while (true)
01831         if (__first == __last)
01832           return __first;
01833         else if (!__pred(*__last))
01834           --__last;
01835         else
01836           break;
01837       std::iter_swap(__first, __last);
01838       ++__first;
01839     }
01840     }
01841 
01856   template<typename _ForwardIterator, typename _Predicate>
01857     inline _ForwardIterator
01858     partition(_ForwardIterator __first, _ForwardIterator __last,
01859           _Predicate   __pred)
01860     {
01861       // concept requirements
01862       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01863                   _ForwardIterator>)
01864       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01865         typename iterator_traits<_ForwardIterator>::value_type>)
01866       __glibcxx_requires_valid_range(__first, __last);
01867 
01868       return std::__partition(__first, __last, __pred,
01869                   std::__iterator_category(__first));
01870     }
01871 
01872 
01878   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
01879     _ForwardIterator
01880     __inplace_stable_partition(_ForwardIterator __first,
01881                    _ForwardIterator __last,
01882                    _Predicate __pred, _Distance __len)
01883     {
01884       if (__len == 1)
01885     return __pred(*__first) ? __last : __first;
01886       _ForwardIterator __middle = __first;
01887       std::advance(__middle, __len / 2);
01888       _ForwardIterator __begin = std::__inplace_stable_partition(__first,
01889                                  __middle,
01890                                  __pred,
01891                                  __len / 2);
01892       _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
01893                                    __pred,
01894                                    __len
01895                                    - __len / 2);
01896       std::rotate(__begin, __middle, __end);
01897       std::advance(__begin, std::distance(__middle, __end));
01898       return __begin;
01899     }
01900 
01906   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
01907        typename _Distance>
01908     _ForwardIterator
01909     __stable_partition_adaptive(_ForwardIterator __first,
01910                 _ForwardIterator __last,
01911                 _Predicate __pred, _Distance __len,
01912                 _Pointer __buffer,
01913                 _Distance __buffer_size)
01914     {
01915       if (__len <= __buffer_size)
01916     {
01917       _ForwardIterator __result1 = __first;
01918       _Pointer __result2 = __buffer;
01919       for ( ; __first != __last ; ++__first)
01920         if (__pred(*__first))
01921           {
01922         *__result1 = *__first;
01923         ++__result1;
01924           }
01925         else
01926           {
01927         *__result2 = *__first;
01928         ++__result2;
01929           }
01930       std::copy(__buffer, __result2, __result1);
01931       return __result1;
01932     }
01933       else
01934     {
01935       _ForwardIterator __middle = __first;
01936       std::advance(__middle, __len / 2);
01937       _ForwardIterator __begin =
01938         std::__stable_partition_adaptive(__first, __middle, __pred,
01939                          __len / 2, __buffer,
01940                          __buffer_size);
01941       _ForwardIterator __end =
01942         std::__stable_partition_adaptive(__middle, __last, __pred,
01943                          __len - __len / 2,
01944                          __buffer, __buffer_size);
01945       std::rotate(__begin, __middle, __end);
01946       std::advance(__begin, std::distance(__middle, __end));
01947       return __begin;
01948     }
01949     }
01950 
01967   template<typename _ForwardIterator, typename _Predicate>
01968     _ForwardIterator
01969     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
01970              _Predicate __pred)
01971     {
01972       // concept requirements
01973       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01974                   _ForwardIterator>)
01975       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01976         typename iterator_traits<_ForwardIterator>::value_type>)
01977       __glibcxx_requires_valid_range(__first, __last);
01978 
01979       if (__first == __last)
01980     return __first;
01981       else
01982     {
01983       typedef typename iterator_traits<_ForwardIterator>::value_type
01984         _ValueType;
01985       typedef typename iterator_traits<_ForwardIterator>::difference_type
01986         _DistanceType;
01987 
01988       _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
01989                                 __last);
01990     if (__buf.size() > 0)
01991       return
01992         std::__stable_partition_adaptive(__first, __last, __pred,
01993                       _DistanceType(__buf.requested_size()),
01994                       __buf.begin(), __buf.size());
01995     else
01996       return
01997         std::__inplace_stable_partition(__first, __last, __pred,
01998                      _DistanceType(__buf.requested_size()));
01999     }
02000     }
02001 
02007   template<typename _RandomAccessIterator, typename _Tp>
02008     _RandomAccessIterator
02009     __unguarded_partition(_RandomAccessIterator __first,
02010               _RandomAccessIterator __last, _Tp __pivot)
02011     {
02012       while (true)
02013     {
02014       while (*__first < __pivot)
02015         ++__first;
02016       --__last;
02017       while (__pivot < *__last)
02018         --__last;
02019       if (!(__first < __last))
02020         return __first;
02021       std::iter_swap(__first, __last);
02022       ++__first;
02023     }
02024     }
02025 
02031   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
02032     _RandomAccessIterator
02033     __unguarded_partition(_RandomAccessIterator __first,
02034               _RandomAccessIterator __last,
02035               _Tp __pivot, _Compare __comp)
02036     {
02037       while (true)
02038     {
02039       while (__comp(*__first, __pivot))
02040         ++__first;
02041       --__last;
02042       while (__comp(__pivot, *__last))
02043         --__last;
02044       if (!(__first < __last))
02045         return __first;
02046       std::iter_swap(__first, __last);
02047       ++__first;
02048     }
02049     }
02050 
02057   enum { _S_threshold = 16 };
02058 
02064   template<typename _RandomAccessIterator, typename _Tp>
02065     void
02066     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
02067     {
02068       _RandomAccessIterator __next = __last;
02069       --__next;
02070       while (__val < *__next)
02071     {
02072       *__last = *__next;
02073       __last = __next;
02074       --__next;
02075     }
02076       *__last = __val;
02077     }
02078 
02084   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
02085     void
02086     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
02087                   _Compare __comp)
02088     {
02089       _RandomAccessIterator __next = __last;
02090       --__next;
02091       while (__comp(__val, *__next))
02092     {
02093       *__last = *__next;
02094       __last = __next;
02095       --__next;
02096     }
02097       *__last = __val;
02098     }
02099 
02105   template<typename _RandomAccessIterator>
02106     void
02107     __insertion_sort(_RandomAccessIterator __first,
02108              _RandomAccessIterator __last)
02109     {
02110       if (__first == __last)
02111     return;
02112 
02113       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02114     {
02115       typename iterator_traits<_RandomAccessIterator>::value_type
02116         __val = *__i;
02117       if (__val < *__first)
02118         {
02119           std::copy_backward(__first, __i, __i + 1);
02120           *__first = __val;
02121         }
02122       else
02123         std::__unguarded_linear_insert(__i, __val);
02124     }
02125     }
02126 
02132   template<typename _RandomAccessIterator, typename _Compare>
02133     void
02134     __insertion_sort(_RandomAccessIterator __first,
02135              _RandomAccessIterator __last, _Compare __comp)
02136     {
02137       if (__first == __last) return;
02138 
02139       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02140     {
02141       typename iterator_traits<_RandomAccessIterator>::value_type
02142         __val = *__i;
02143       if (__comp(__val, *__first))
02144         {
02145           std::copy_backward(__first, __i, __i + 1);
02146           *__first = __val;
02147         }
02148       else
02149         std::__unguarded_linear_insert(__i, __val, __comp);
02150     }
02151     }
02152 
02158   template<typename _RandomAccessIterator>
02159     inline void
02160     __unguarded_insertion_sort(_RandomAccessIterator __first,
02161                    _RandomAccessIterator __last)
02162     {
02163       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02164     _ValueType;
02165 
02166       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02167     std::__unguarded_linear_insert(__i, _ValueType(*__i));
02168     }
02169 
02175   template<typename _RandomAccessIterator, typename _Compare>
02176     inline void
02177     __unguarded_insertion_sort(_RandomAccessIterator __first,
02178                    _RandomAccessIterator __last, _Compare __comp)
02179     {
02180       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02181     _ValueType;
02182 
02183       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02184     std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
02185     }
02186 
02192   template<typename _RandomAccessIterator>
02193     void
02194     __final_insertion_sort(_RandomAccessIterator __first,
02195                _RandomAccessIterator __last)
02196     {
02197       if (__last - __first > _S_threshold)
02198     {
02199       std::__insertion_sort(__first, __first + _S_threshold);
02200       std::__unguarded_insertion_sort(__first + _S_threshold, __last);
02201     }
02202       else
02203     std::__insertion_sort(__first, __last);
02204     }
02205 
02211   template<typename _RandomAccessIterator, typename _Compare>
02212     void
02213     __final_insertion_sort(_RandomAccessIterator __first,
02214                _RandomAccessIterator __last, _Compare __comp)
02215     {
02216       if (__last - __first > _S_threshold)
02217     {
02218       std::__insertion_sort(__first, __first + _S_threshold, __comp);
02219       std::__unguarded_insertion_sort(__first + _S_threshold, __last,
02220                       __comp);
02221     }
02222       else
02223     std::__insertion_sort(__first, __last, __comp);
02224     }
02225 
02231   template<typename _Size>
02232     inline _Size
02233     __lg(_Size __n)
02234     {
02235       _Size __k;
02236       for (__k = 0; __n != 1; __n >>= 1)
02237     ++__k;
02238       return __k;
02239     }
02240 
02256   template<typename _RandomAccessIterator>
02257     void
02258     partial_sort(_RandomAccessIterator __first,
02259          _RandomAccessIterator __middle,
02260          _RandomAccessIterator __last)
02261     {
02262       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02263     _ValueType;
02264 
02265       // concept requirements
02266       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02267         _RandomAccessIterator>)
02268       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
02269       __glibcxx_requires_valid_range(__first, __middle);
02270       __glibcxx_requires_valid_range(__middle, __last);
02271 
02272       std::make_heap(__first, __middle);
02273       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
02274     if (*__i < *__first)
02275       std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
02276       std::sort_heap(__first, __middle);
02277     }
02278 
02297   template<typename _RandomAccessIterator, typename _Compare>
02298     void
02299     partial_sort(_RandomAccessIterator __first,
02300          _RandomAccessIterator __middle,
02301          _RandomAccessIterator __last,
02302          _Compare __comp)
02303     {
02304       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02305     _ValueType;
02306 
02307       // concept requirements
02308       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02309         _RandomAccessIterator>)
02310       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02311                   _ValueType, _ValueType>)
02312       __glibcxx_requires_valid_range(__first, __middle);
02313       __glibcxx_requires_valid_range(__middle, __last);
02314 
02315       std::make_heap(__first, __middle, __comp);
02316       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
02317     if (__comp(*__i, *__first))
02318       std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
02319       std::sort_heap(__first, __middle, __comp);
02320     }
02321 
02339   template<typename _InputIterator, typename _RandomAccessIterator>
02340     _RandomAccessIterator
02341     partial_sort_copy(_InputIterator __first, _InputIterator __last,
02342               _RandomAccessIterator __result_first,
02343               _RandomAccessIterator __result_last)
02344     {
02345       typedef typename iterator_traits<_InputIterator>::value_type
02346     _InputValueType;
02347       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02348     _OutputValueType;
02349       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
02350     _DistanceType;
02351 
02352       // concept requirements
02353       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
02354       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
02355                   _OutputValueType>)
02356       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
02357       __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>)
02358       __glibcxx_requires_valid_range(__first, __last);
02359       __glibcxx_requires_valid_range(__result_first, __result_last);
02360 
02361       if (__result_first == __result_last)
02362     return __result_last;
02363       _RandomAccessIterator __result_real_last = __result_first;
02364       while(__first != __last && __result_real_last != __result_last)
02365     {
02366       *__result_real_last = *__first;
02367       ++__result_real_last;
02368       ++__first;
02369     }
02370       std::make_heap(__result_first, __result_real_last);
02371       while (__first != __last)
02372     {
02373       if (*__first < *__result_first)
02374         std::__adjust_heap(__result_first, _DistanceType(0),
02375                    _DistanceType(__result_real_last
02376                          - __result_first),
02377                    _InputValueType(*__first));
02378       ++__first;
02379     }
02380       std::sort_heap(__result_first, __result_real_last);
02381       return __result_real_last;
02382     }
02383 
02403   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
02404     _RandomAccessIterator
02405     partial_sort_copy(_InputIterator __first, _InputIterator __last,
02406               _RandomAccessIterator __result_first,
02407               _RandomAccessIterator __result_last,
02408               _Compare __comp)
02409     {
02410       typedef typename iterator_traits<_InputIterator>::value_type
02411     _InputValueType;
02412       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02413     _OutputValueType;
02414       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
02415     _DistanceType;
02416 
02417       // concept requirements
02418       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
02419       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02420                   _RandomAccessIterator>)
02421       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
02422                   _OutputValueType>)
02423       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02424                   _OutputValueType, _OutputValueType>)
02425       __glibcxx_requires_valid_range(__first, __last);
02426       __glibcxx_requires_valid_range(__result_first, __result_last);
02427 
02428       if (__result_first == __result_last)
02429     return __result_last;
02430       _RandomAccessIterator __result_real_last = __result_first;
02431       while(__first != __last && __result_real_last != __result_last)
02432     {
02433       *__result_real_last = *__first;
02434       ++__result_real_last;
02435       ++__first;
02436     }
02437       std::make_heap(__result_first, __result_real_last, __comp);
02438       while (__first != __last)
02439     {
02440       if (__comp(*__first, *__result_first))
02441         std::__adjust_heap(__result_first, _DistanceType(0),
02442                    _DistanceType(__result_real_last
02443                          - __result_first),
02444                    _InputValueType(*__first),
02445                    __comp);
02446       ++__first;
02447     }
02448       std::sort_heap(__result_first, __result_real_last, __comp);
02449       return __result_real_last;
02450     }
02451 
02457   template<typename _RandomAccessIterator, typename _Size>
02458     void
02459     __introsort_loop(_RandomAccessIterator __first,
02460              _RandomAccessIterator __last,
02461              _Size __depth_limit)
02462     {
02463       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02464     _ValueType;
02465 
02466       while (__last - __first > _S_threshold)
02467     {
02468       if (__depth_limit == 0)
02469         {
02470           std::partial_sort(__first, __last, __last);
02471           return;
02472         }
02473       --__depth_limit;
02474       _RandomAccessIterator __cut =
02475         std::__unguarded_partition(__first, __last,
02476                        _ValueType(std::__median(*__first,
02477                                 *(__first
02478                                   + (__last
02479                                      - __first)
02480                                   / 2),
02481                                 *(__last
02482                                   - 1))));
02483       std::__introsort_loop(__cut, __last, __depth_limit);
02484       __last = __cut;
02485     }
02486     }
02487 
02493   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02494     void
02495     __introsort_loop(_RandomAccessIterator __first,
02496              _RandomAccessIterator __last,
02497              _Size __depth_limit, _Compare __comp)
02498     {
02499       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02500     _ValueType;
02501 
02502       while (__last - __first > _S_threshold)
02503     {
02504       if (__depth_limit == 0)
02505         {
02506           std::partial_sort(__first, __last, __last, __comp);
02507           return;
02508         }
02509       --__depth_limit;
02510       _RandomAccessIterator __cut =
02511         std::__unguarded_partition(__first, __last,
02512                        _ValueType(std::__median(*__first,
02513                                 *(__first
02514                                   + (__last
02515                                      - __first)
02516                                   / 2),
02517                                 *(__last - 1),
02518                                 __comp)),
02519                        __comp);
02520       std::__introsort_loop(__cut, __last, __depth_limit, __comp);
02521       __last = __cut;
02522     }
02523     }
02524 
02538   template<typename _RandomAccessIterator>
02539     inline void
02540     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
02541     {
02542       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02543     _ValueType;
02544 
02545       // concept requirements
02546       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02547         _RandomAccessIterator>)
02548       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
02549       __glibcxx_requires_valid_range(__first, __last);
02550 
02551       if (__first != __last)
02552     {
02553       std::__introsort_loop(__first, __last, __lg(__last - __first) * 2);
02554       std::__final_insertion_sort(__first, __last);
02555     }
02556     }
02557 
02572   template<typename _RandomAccessIterator, typename _Compare>
02573     inline void
02574     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
02575      _Compare __comp)
02576     {
02577       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02578     _ValueType;
02579 
02580       // concept requirements
02581       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02582         _RandomAccessIterator>)
02583       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
02584                   _ValueType>)
02585       __glibcxx_requires_valid_range(__first, __last);
02586 
02587       if (__first != __last)
02588     {
02589       std::__introsort_loop(__first, __last, __lg(__last - __first) * 2,
02590                 __comp);
02591       std::__final_insertion_sort(__first, __last, __comp);
02592     }
02593     }
02594 
02605   template<typename _ForwardIterator, typename _Tp>
02606     _ForwardIterator
02607     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
02608         const _Tp& __val)
02609     {
02610       typedef typename iterator_traits<_ForwardIterator>::value_type
02611     _ValueType;
02612       typedef typename iterator_traits<_ForwardIterator>::difference_type
02613     _DistanceType;
02614 
02615       // concept requirements
02616       // Note that these are slightly stricter than those of the 4-argument
02617       // version, defined next.  The difference is in the strictness of the
02618       // comparison operations... so for looser checking, define your own
02619       // comparison function, as was intended.
02620       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02621       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02622       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
02623       __glibcxx_requires_partitioned(__first, __last, __val);
02624 
02625       _DistanceType __len = std::distance(__first, __last);
02626       _DistanceType __half;
02627       _ForwardIterator __middle;
02628 
02629       while (__len > 0)
02630     {
02631       __half = __len >> 1;
02632       __middle = __first;
02633       std::advance(__middle, __half);
02634       if (*__middle < __val)
02635         {
02636           __first = __middle;
02637           ++__first;
02638           __len = __len - __half - 1;
02639         }
02640       else
02641         __len = __half;
02642     }
02643       return __first;
02644     }
02645 
02660   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02661     _ForwardIterator
02662     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
02663         const _Tp& __val, _Compare __comp)
02664     {
02665       typedef typename iterator_traits<_ForwardIterator>::value_type
02666     _ValueType;
02667       typedef typename iterator_traits<_ForwardIterator>::difference_type
02668     _DistanceType;
02669 
02670       // concept requirements
02671       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02672       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02673                   _ValueType, _Tp>)
02674       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
02675 
02676       _DistanceType __len = std::distance(__first, __last);
02677       _DistanceType __half;
02678       _ForwardIterator __middle;
02679 
02680       while (__len > 0)
02681     {
02682       __half = __len >> 1;
02683       __middle = __first;
02684       std::advance(__middle, __half);
02685       if (__comp(*__middle, __val))
02686         {
02687           __first = __middle;
02688           ++__first;
02689           __len = __len - __half - 1;
02690         }
02691       else
02692         __len = __half;
02693     }
02694       return __first;
02695     }
02696 
02707   template<typename _ForwardIterator, typename _Tp>
02708     _ForwardIterator
02709     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02710         const _Tp& __val)
02711     {
02712       typedef typename iterator_traits<_ForwardIterator>::value_type
02713     _ValueType;
02714       typedef typename iterator_traits<_ForwardIterator>::difference_type
02715     _DistanceType;
02716 
02717       // concept requirements
02718       // See comments on lower_bound.
02719       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02720       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02721       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
02722       __glibcxx_requires_partitioned(__first, __last, __val);
02723 
02724       _DistanceType __len = std::distance(__first, __last);
02725       _DistanceType __half;
02726       _ForwardIterator __middle;
02727 
02728       while (__len > 0)
02729     {
02730       __half = __len >> 1;
02731       __middle = __first;
02732       std::advance(__middle, __half);
02733       if (__val < *__middle)
02734         __len = __half;
02735       else
02736         {
02737           __first = __middle;
02738           ++__first;
02739           __len = __len - __half - 1;
02740         }
02741     }
02742       return __first;
02743     }
02744 
02759   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02760     _ForwardIterator
02761     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02762         const _Tp& __val, _Compare __comp)
02763     {
02764       typedef typename iterator_traits<_ForwardIterator>::value_type
02765     _ValueType;
02766       typedef typename iterator_traits<_ForwardIterator>::difference_type
02767     _DistanceType;
02768 
02769       // concept requirements
02770       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02771       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02772                   _Tp, _ValueType>)
02773       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
02774 
02775       _DistanceType __len = std::distance(__first, __last);
02776       _DistanceType __half;
02777       _ForwardIterator __middle;
02778 
02779       while (__len > 0)
02780     {
02781       __half = __len >> 1;
02782       __middle = __first;
02783       std::advance(__middle, __half);
02784       if (__comp(__val, *__middle))
02785         __len = __half;
02786       else
02787         {
02788           __first = __middle;
02789           ++__first;
02790           __len = __len - __half - 1;
02791         }
02792     }
02793       return __first;
02794     }
02795 
02801   template<typename _BidirectionalIterator, typename _Distance>
02802     void
02803     __merge_without_buffer(_BidirectionalIterator __first,
02804                _BidirectionalIterator __middle,
02805                _BidirectionalIterator __last,
02806                _Distance __len1, _Distance __len2)
02807     {
02808       if (__len1 == 0 || __len2 == 0)
02809     return;
02810       if (__len1 + __len2 == 2)
02811     {
02812       if (*__middle < *__first)
02813         std::iter_swap(__first, __middle);
02814       return;
02815     }
02816       _BidirectionalIterator __first_cut = __first;
02817       _BidirectionalIterator __second_cut = __middle;
02818       _Distance __len11 = 0;
02819       _Distance __len22 = 0;
02820       if (__len1 > __len2)
02821     {
02822       __len11 = __len1 / 2;
02823       std::advance(__first_cut, __len11);
02824       __second_cut = std::lower_bound(__middle, __last, *__first_cut);
02825       __len22 = std::distance(__middle, __second_cut);
02826     }
02827       else
02828     {
02829       __len22 = __len2 / 2;
02830       std::advance(__second_cut, __len22);
02831       __first_cut = std::upper_bound(__first, __middle, *__second_cut);
02832       __len11 = std::distance(__first, __first_cut);
02833     }
02834       std::rotate(__first_cut, __middle, __second_cut);
02835       _BidirectionalIterator __new_middle = __first_cut;
02836       std::advance(__new_middle, std::distance(__middle, __second_cut));
02837       std::__merge_without_buffer(__first, __first_cut, __new_middle,
02838                   __len11, __len22);
02839       std::__merge_without_buffer(__new_middle, __second_cut, __last,
02840                   __len1 - __len11, __len2 - __len22);
02841     }
02842 
02848   template<typename _BidirectionalIterator, typename _Distance,
02849        typename _Compare>
02850     void
02851     __merge_without_buffer(_BidirectionalIterator __first,
02852                            _BidirectionalIterator __middle,
02853                _BidirectionalIterator __last,
02854                _Distance __len1, _Distance __len2,
02855                _Compare __comp)
02856     {
02857       if (__len1 == 0 || __len2 == 0)
02858     return;
02859       if (__len1 + __len2 == 2)
02860     {
02861       if (__comp(*__middle, *__first))
02862         std::iter_swap(__first, __middle);
02863       return;
02864     }
02865       _BidirectionalIterator __first_cut = __first;
02866       _BidirectionalIterator __second_cut = __middle;
02867       _Distance __len11 = 0;
02868       _Distance __len22 = 0;
02869       if (__len1 > __len2)
02870     {
02871       __len11 = __len1 / 2;
02872       std::advance(__first_cut, __len11);
02873       __second_cut = std::lower_bound(__middle, __last, *__first_cut,
02874                       __comp);
02875       __len22 = std::distance(__middle, __second_cut);
02876     }
02877       else
02878     {
02879       __len22 = __len2 / 2;
02880       std::advance(__second_cut, __len22);
02881       __first_cut = std::upper_bound(__first, __middle, *__second_cut,
02882                      __comp);
02883       __len11 = std::distance(__first, __first_cut);
02884     }
02885       std::rotate(__first_cut, __middle, __second_cut);
02886       _BidirectionalIterator __new_middle = __first_cut;
02887       std::advance(__new_middle, std::distance(__middle, __second_cut));
02888       std::__merge_without_buffer(__first, __first_cut, __new_middle,
02889                   __len11, __len22, __comp);
02890       std::__merge_without_buffer(__new_middle, __second_cut, __last,
02891                   __len1 - __len11, __len2 - __len22, __comp);
02892     }
02893 
02899   template<typename _RandomAccessIterator>
02900     void
02901     __inplace_stable_sort(_RandomAccessIterator __first,
02902               _RandomAccessIterator __last)
02903     {
02904       if (__last - __first < 15)
02905     {
02906       std::__insertion_sort(__first, __last);
02907       return;
02908     }
02909       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
02910       std::__inplace_stable_sort(__first, __middle);
02911       std::__inplace_stable_sort(__middle, __last);
02912       std::__merge_without_buffer(__first, __middle, __last,
02913                   __middle - __first,
02914                   __last - __middle);
02915     }
02916 
02922   template<typename _RandomAccessIterator, typename _Compare>
02923     void
02924     __inplace_stable_sort(_RandomAccessIterator __first,
02925               _RandomAccessIterator __last, _Compare __comp)
02926     {
02927       if (__last - __first < 15)
02928     {
02929       std::__insertion_sort(__first, __last, __comp);
02930       return;
02931     }
02932       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
02933       std::__inplace_stable_sort(__first, __middle, __comp);
02934       std::__inplace_stable_sort(__middle, __last, __comp);
02935       std::__merge_without_buffer(__first, __middle, __last,
02936                   __middle - __first,
02937                   __last - __middle,
02938                   __comp);
02939     }
02940 
02957   template<typename _InputIterator1, typename _InputIterator2,
02958        typename _OutputIterator>
02959     _OutputIterator
02960     merge(_InputIterator1 __first1, _InputIterator1 __last1,
02961       _InputIterator2 __first2, _InputIterator2 __last2,
02962       _OutputIterator __result)
02963     {
02964       // concept requirements
02965       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
02966       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
02967       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
02968         typename iterator_traits<_InputIterator1>::value_type>)
02969       __glibcxx_function_requires(_SameTypeConcept<
02970         typename iterator_traits<_InputIterator1>::value_type,
02971         typename iterator_traits<_InputIterator2>::value_type>)
02972       __glibcxx_function_requires(_LessThanComparableConcept<
02973         typename iterator_traits<_InputIterator1>::value_type>)
02974       __glibcxx_requires_sorted(__first1, __last1);
02975       __glibcxx_requires_sorted(__first2, __last2);
02976 
02977       while (__first1 != __last1 && __first2 != __last2)
02978     {
02979       if (*__first2 < *__first1)
02980         {
02981           *__result = *__first2;
02982           ++__first2;
02983         }
02984       else
02985         {
02986           *__result = *__first1;
02987           ++__first1;
02988         }
02989       ++__result;
02990     }
02991       return std::copy(__first2, __last2, std::copy(__first1, __last1,
02992                             __result));
02993     }
02994 
03015   template<typename _InputIterator1, typename _InputIterator2,
03016        typename _OutputIterator, typename _Compare>
03017     _OutputIterator
03018     merge(_InputIterator1 __first1, _InputIterator1 __last1,
03019       _InputIterator2 __first2, _InputIterator2 __last2,
03020       _OutputIterator __result, _Compare __comp)
03021     {
03022       // concept requirements
03023       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03024       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03025       __glibcxx_function_requires(_SameTypeConcept<
03026         typename iterator_traits<_InputIterator1>::value_type,
03027         typename iterator_traits<_InputIterator2>::value_type>)
03028       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03029         typename iterator_traits<_InputIterator1>::value_type>)
03030       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03031         typename iterator_traits<_InputIterator1>::value_type,
03032         typename iterator_traits<_InputIterator2>::value_type>)
03033       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
03034       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
03035 
03036       while (__first1 != __last1 && __first2 != __last2)
03037     {
03038       if (__comp(*__first2, *__first1))
03039         {
03040           *__result = *__first2;
03041           ++__first2;
03042         }
03043       else
03044         {
03045           *__result = *__first1;
03046           ++__first1;
03047         }
03048       ++__result;
03049     }
03050       return std::copy(__first2, __last2, std::copy(__first1, __last1,
03051                             __result));
03052     }
03053 
03054   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03055        typename _Distance>
03056     void
03057     __merge_sort_loop(_RandomAccessIterator1 __first,
03058               _RandomAccessIterator1 __last,
03059               _RandomAccessIterator2 __result,
03060               _Distance __step_size)
03061     {
03062       const _Distance __two_step = 2 * __step_size;
03063 
03064       while (__last - __first >= __two_step)
03065     {
03066       __result = std::merge(__first, __first + __step_size,
03067                 __first + __step_size, __first + __two_step,
03068                 __result);
03069       __first += __two_step;
03070     }
03071 
03072       __step_size = std::min(_Distance(__last - __first), __step_size);
03073       std::merge(__first, __first + __step_size, __first + __step_size, __last,
03074          __result);
03075     }
03076 
03077   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03078        typename _Distance, typename _Compare>
03079     void
03080     __merge_sort_loop(_RandomAccessIterator1 __first,
03081               _RandomAccessIterator1 __last,
03082               _RandomAccessIterator2 __result, _Distance __step_size,
03083               _Compare __comp)
03084     {
03085       const _Distance __two_step = 2 * __step_size;
03086 
03087       while (__last - __first >= __two_step)
03088     {
03089       __result = std::merge(__first, __first + __step_size,
03090                 __first + __step_size, __first + __two_step,
03091                 __result,
03092                 __comp);
03093       __first += __two_step;
03094     }
03095       __step_size = std::min(_Distance(__last - __first), __step_size);
03096 
03097       std::merge(__first, __first + __step_size,
03098          __first + __step_size, __last,
03099          __result,
03100          __comp);
03101     }
03102 
03103   enum { _S_chunk_size = 7 };
03104 
03105   template<typename _RandomAccessIterator, typename _Distance>
03106     void
03107     __chunk_insertion_sort(_RandomAccessIterator __first,
03108                _RandomAccessIterator __last,
03109                _Distance __chunk_size)
03110     {
03111       while (__last - __first >= __chunk_size)
03112     {
03113       std::__insertion_sort(__first, __first + __chunk_size);
03114       __first += __chunk_size;
03115     }
03116       std::__insertion_sort(__first, __last);
03117     }
03118 
03119   template<typename _RandomAccessIterator, typename _Distance, typename _Compare>
03120     void
03121     __chunk_insertion_sort(_RandomAccessIterator __first,
03122                _RandomAccessIterator __last,
03123                _Distance __chunk_size, _Compare __comp)
03124     {
03125       while (__last - __first >= __chunk_size)
03126     {
03127       std::__insertion_sort(__first, __first + __chunk_size, __comp);
03128       __first += __chunk_size;
03129     }
03130       std::__insertion_sort(__first, __last, __comp);
03131     }
03132 
03133   template<typename _RandomAccessIterator, typename _Pointer>
03134     void
03135     __merge_sort_with_buffer(_RandomAccessIterator __first,
03136                  _RandomAccessIterator __last,
03137                              _Pointer __buffer)
03138     {
03139       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03140     _Distance;
03141 
03142       const _Distance __len = __last - __first;
03143       const _Pointer __buffer_last = __buffer + __len;
03144 
03145       _Distance __step_size = _S_chunk_size;
03146       std::__chunk_insertion_sort(__first, __last, __step_size);
03147 
03148       while (__step_size < __len)
03149     {
03150       std::__merge_sort_loop(__first, __last, __buffer, __step_size);
03151       __step_size *= 2;
03152       std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
03153       __step_size *= 2;
03154     }
03155     }
03156 
03157   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
03158     void
03159     __merge_sort_with_buffer(_RandomAccessIterator __first,
03160                  _RandomAccessIterator __last,
03161                              _Pointer __buffer, _Compare __comp)
03162     {
03163       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03164     _Distance;
03165 
03166       const _Distance __len = __last - __first;
03167       const _Pointer __buffer_last = __buffer + __len;
03168 
03169       _Distance __step_size = _S_chunk_size;
03170       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
03171 
03172       while (__step_size < __len)
03173     {
03174       std::__merge_sort_loop(__first, __last, __buffer,
03175                  __step_size, __comp);
03176       __step_size *= 2;
03177       std::__merge_sort_loop(__buffer, __buffer_last, __first,
03178                  __step_size, __comp);
03179       __step_size *= 2;
03180     }
03181     }
03182 
03188   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
03189        typename _BidirectionalIterator3>
03190     _BidirectionalIterator3
03191     __merge_backward(_BidirectionalIterator1 __first1,
03192              _BidirectionalIterator1 __last1,
03193              _BidirectionalIterator2 __first2,
03194              _BidirectionalIterator2 __last2,
03195              _BidirectionalIterator3 __result)
03196     {
03197       if (__first1 == __last1)
03198     return std::copy_backward(__first2, __last2, __result);
03199       if (__first2 == __last2)
03200     return std::copy_backward(__first1, __last1, __result);
03201       --__last1;
03202       --__last2;
03203       while (true)
03204     {
03205       if (*__last2 < *__last1)
03206         {
03207           *--__result = *__last1;
03208           if (__first1 == __last1)
03209         return std::copy_backward(__first2, ++__last2, __result);
03210           --__last1;
03211         }
03212       else
03213         {
03214           *--__result = *__last2;
03215           if (__first2 == __last2)
03216         return std::copy_backward(__first1, ++__last1, __result);
03217           --__last2;
03218         }
03219     }
03220     }
03221 
03227   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
03228        typename _BidirectionalIterator3, typename _Compare>
03229     _BidirectionalIterator3
03230     __merge_backward(_BidirectionalIterator1 __first1,
03231              _BidirectionalIterator1 __last1,
03232              _BidirectionalIterator2 __first2,
03233              _BidirectionalIterator2 __last2,
03234              _BidirectionalIterator3 __result,
03235              _Compare __comp)
03236     {
03237       if (__first1 == __last1)
03238     return std::copy_backward(__first2, __last2, __result);
03239       if (__first2 == __last2)
03240     return std::copy_backward(__first1, __last1, __result);
03241       --__last1;
03242       --__last2;
03243       while (true)
03244     {
03245       if (__comp(*__last2, *__last1))
03246         {
03247           *--__result = *__last1;
03248           if (__first1 == __last1)
03249         return std::copy_backward(__first2, ++__last2, __result);
03250           --__last1;
03251         }
03252       else
03253         {
03254           *--__result = *__last2;
03255           if (__first2 == __last2)
03256         return std::copy_backward(__first1, ++__last1, __result);
03257           --__last2;
03258         }
03259     }
03260     }
03261 
03267   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
03268        typename _Distance>
03269     _BidirectionalIterator1
03270     __rotate_adaptive(_BidirectionalIterator1 __first,
03271               _BidirectionalIterator1 __middle,
03272               _BidirectionalIterator1 __last,
03273               _Distance __len1, _Distance __len2,
03274               _BidirectionalIterator2 __buffer,
03275               _Distance __buffer_size)
03276     {
03277       _BidirectionalIterator2 __buffer_end;
03278       if (__len1 > __len2 && __len2 <= __buffer_size)
03279     {
03280       __buffer_end = std::copy(__middle, __last, __buffer);
03281       std::copy_backward(__first, __middle, __last);
03282       return std::copy(__buffer, __buffer_end, __first);
03283     }
03284       else if (__len1 <= __buffer_size)
03285     {
03286       __buffer_end = std::copy(__first, __middle, __buffer);
03287       std::copy(__middle, __last, __first);
03288       return std::copy_backward(__buffer, __buffer_end, __last);
03289     }
03290       else
03291     {
03292       std::rotate(__first, __middle, __last);
03293       std::advance(__first, std::distance(__middle, __last));
03294       return __first;
03295     }
03296     }
03297 
03303   template<typename _BidirectionalIterator, typename _Distance,
03304        typename _Pointer>
03305     void
03306     __merge_adaptive(_BidirectionalIterator __first,
03307                      _BidirectionalIterator __middle,
03308              _BidirectionalIterator __last,
03309              _Distance __len1, _Distance __len2,
03310              _Pointer __buffer, _Distance __buffer_size)
03311     {
03312       if (__len1 <= __len2 && __len1 <= __buffer_size)
03313     {
03314       _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
03315       std::merge(__buffer, __buffer_end, __middle, __last, __first);
03316     }
03317       else if (__len2 <= __buffer_size)
03318     {
03319       _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
03320       std::__merge_backward(__first, __middle, __buffer,
03321                 __buffer_end, __last);
03322     }
03323       else
03324     {
03325       _BidirectionalIterator __first_cut = __first;
03326       _BidirectionalIterator __second_cut = __middle;
03327       _Distance __len11 = 0;
03328       _Distance __len22 = 0;
03329       if (__len1 > __len2)
03330         {
03331           __len11 = __len1 / 2;
03332           std::advance(__first_cut, __len11);
03333           __second_cut = std::lower_bound(__middle, __last,
03334                           *__first_cut);
03335           __len22 = std::distance(__middle, __second_cut);
03336         }
03337       else
03338         {
03339           __len22 = __len2 / 2;
03340           std::advance(__second_cut, __len22);
03341           __first_cut = std::upper_bound(__first, __middle,
03342                          *__second_cut);
03343           __len11 = std::distance(__first, __first_cut);
03344         }
03345       _BidirectionalIterator __new_middle =
03346         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
03347                    __len1 - __len11, __len22, __buffer,
03348                    __buffer_size);
03349       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
03350                 __len22, __buffer, __buffer_size);
03351       std::__merge_adaptive(__new_middle, __second_cut, __last,
03352                 __len1 - __len11,
03353                 __len2 - __len22, __buffer, __buffer_size);
03354     }
03355     }
03356 
03362   template<typename _BidirectionalIterator, typename _Distance, typename _Pointer,
03363        typename _Compare>
03364     void
03365     __merge_adaptive(_BidirectionalIterator __first,
03366                      _BidirectionalIterator __middle,
03367              _BidirectionalIterator __last,
03368              _Distance __len1, _Distance __len2,
03369              _Pointer __buffer, _Distance __buffer_size,
03370              _Compare __comp)
03371     {
03372       if (__len1 <= __len2 && __len1 <= __buffer_size)
03373     {
03374       _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
03375       std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
03376     }
03377       else if (__len2 <= __buffer_size)
03378     {
03379       _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
03380       std::__merge_backward(__first, __middle, __buffer, __buffer_end,
03381                 __last, __comp);
03382     }
03383       else
03384     {
03385       _BidirectionalIterator __first_cut = __first;
03386       _BidirectionalIterator __second_cut = __middle;
03387       _Distance __len11 = 0;
03388       _Distance __len22 = 0;
03389       if (__len1 > __len2)
03390         {
03391           __len11 = __len1 / 2;
03392           std::advance(__first_cut, __len11);
03393           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03394                           __comp);
03395           __len22 = std::distance(__middle, __second_cut);
03396         }
03397       else
03398         {
03399           __len22 = __len2 / 2;
03400           std::advance(__second_cut, __len22);
03401           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03402                          __comp);
03403           __len11 = std::distance(__first, __first_cut);
03404         }
03405       _BidirectionalIterator __new_middle =
03406         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
03407                    __len1 - __len11, __len22, __buffer,
03408                    __buffer_size);
03409       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
03410                 __len22, __buffer, __buffer_size, __comp);
03411       std::__merge_adaptive(__new_middle, __second_cut, __last,
03412                 __len1 - __len11,
03413                 __len2 - __len22, __buffer,
03414                 __buffer_size, __comp);
03415     }
03416     }
03417 
03435   template<typename _BidirectionalIterator>
03436     void
03437     inplace_merge(_BidirectionalIterator __first,
03438           _BidirectionalIterator __middle,
03439           _BidirectionalIterator __last)
03440     {
03441       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03442           _ValueType;
03443       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03444           _DistanceType;
03445 
03446       // concept requirements
03447       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03448         _BidirectionalIterator>)
03449       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03450       __glibcxx_requires_sorted(__first, __middle);
03451       __glibcxx_requires_sorted(__middle, __last);
03452 
03453       if (__first == __middle || __middle == __last)
03454     return;
03455 
03456       _DistanceType __len1 = std::distance(__first, __middle);
03457       _DistanceType __len2 = std::distance(__middle, __last);
03458 
03459       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03460                                   __last);
03461       if (__buf.begin() == 0)
03462     std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
03463       else
03464     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03465                   __buf.begin(), _DistanceType(__buf.size()));
03466     }
03467 
03489   template<typename _BidirectionalIterator, typename _Compare>
03490     void
03491     inplace_merge(_BidirectionalIterator __first,
03492           _BidirectionalIterator __middle,
03493           _BidirectionalIterator __last,
03494           _Compare __comp)
03495     {
03496       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03497           _ValueType;
03498       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03499           _DistanceType;
03500 
03501       // concept requirements
03502       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03503         _BidirectionalIterator>)
03504       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03505         _ValueType, _ValueType>)
03506       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
03507       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
03508 
03509       if (__first == __middle || __middle == __last)
03510     return;
03511 
03512       const _DistanceType __len1 = std::distance(__first, __middle);
03513       const _DistanceType __len2 = std::distance(__middle, __last);
03514 
03515       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03516                                   __last);
03517       if (__buf.begin() == 0)
03518     std::__merge_without_buffer(__first, __middle, __last, __len1,
03519                     __len2, __comp);
03520       else
03521     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03522                   __buf.begin(), _DistanceType(__buf.size()),
03523                   __comp);
03524     }
03525 
03526   template<typename _RandomAccessIterator, typename _Pointer,
03527        typename _Distance>
03528     void
03529     __stable_sort_adaptive(_RandomAccessIterator __first,
03530                _RandomAccessIterator __last,
03531                            _Pointer __buffer, _Distance __buffer_size)
03532     {
03533       const _Distance __len = (__last - __first + 1) / 2;
03534       const _RandomAccessIterator __middle = __first + __len;
03535       if (__len > __buffer_size)
03536     {
03537       std::__stable_sort_adaptive(__first, __middle,
03538                       __buffer, __buffer_size);
03539       std::__stable_sort_adaptive(__middle, __last,
03540                       __buffer, __buffer_size);
03541     }
03542       else
03543     {
03544       std::__merge_sort_with_buffer(__first, __middle, __buffer);
03545       std::__merge_sort_with_buffer(__middle, __last, __buffer);
03546     }
03547       std::__merge_adaptive(__first, __middle, __last,
03548                 _Distance(__middle - __first),
03549                 _Distance(__last - __middle),
03550                 __buffer, __buffer_size);
03551     }
03552 
03553   template<typename _RandomAccessIterator, typename _Pointer,
03554        typename _Distance, typename _Compare>
03555     void
03556     __stable_sort_adaptive(_RandomAccessIterator __first,
03557                _RandomAccessIterator __last,
03558                            _Pointer __buffer, _Distance __buffer_size,
03559                            _Compare __comp)
03560     {
03561       const _Distance __len = (__last - __first + 1) / 2;
03562       const _RandomAccessIterator __middle = __first + __len;
03563       if (__len > __buffer_size)
03564     {
03565       std::__stable_sort_adaptive(__first, __middle, __buffer,
03566                       __buffer_size, __comp);
03567       std::__stable_sort_adaptive(__middle, __last, __buffer,
03568                       __buffer_size, __comp);
03569     }
03570       else
03571     {
03572       std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
03573       std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
03574     }
03575       std::__merge_adaptive(__first, __middle, __last,
03576                 _Distance(__middle - __first),
03577                 _Distance(__last - __middle),
03578                 __buffer, __buffer_size,
03579                 __comp);
03580     }
03581 
03598   template<typename _RandomAccessIterator>
03599     inline void
03600     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
03601     {
03602       typedef typename iterator_traits<_RandomAccessIterator>::value_type
03603     _ValueType;
03604       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03605     _DistanceType;
03606 
03607       // concept requirements
03608       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03609         _RandomAccessIterator>)
03610       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03611       __glibcxx_requires_valid_range(__first, __last);
03612 
03613       _Temporary_buffer<_RandomAccessIterator, _ValueType>
03614     buf(__first, __last);
03615       if (buf.begin() == 0)
03616     std::__inplace_stable_sort(__first, __last);
03617       else
03618     std::__stable_sort_adaptive(__first, __last, buf.begin(),
03619                     _DistanceType(buf.size()));
03620     }
03621 
03639   template<typename _RandomAccessIterator, typename _Compare>
03640     inline void
03641     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
03642         _Compare __comp)
03643     {
03644       typedef typename iterator_traits<_RandomAccessIterator>::value_type
03645     _ValueType;
03646       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03647     _DistanceType;
03648 
03649       // concept requirements
03650       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03651         _RandomAccessIterator>)
03652       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03653                   _ValueType,
03654                   _ValueType>)
03655       __glibcxx_requires_valid_range(__first, __last);
03656 
03657       _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last);
03658       if (buf.begin() == 0)
03659     std::__inplace_stable_sort(__first, __last, __comp);
03660       else
03661     std::__stable_sort_adaptive(__first, __last, buf.begin(),
03662                     _DistanceType(buf.size()), __comp);
03663     }
03664 
03680   template<typename _RandomAccessIterator>
03681     void
03682     nth_element(_RandomAccessIterator __first,
03683         _RandomAccessIterator __nth,
03684         _RandomAccessIterator __last)
03685     {
03686       typedef typename iterator_traits<_RandomAccessIterator>::value_type
03687     _ValueType;
03688 
03689       // concept requirements
03690       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03691                   _RandomAccessIterator>)
03692       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03693       __glibcxx_requires_valid_range(__first, __nth);
03694       __glibcxx_requires_valid_range(__nth, __last);
03695 
03696       while (__last - __first > 3)
03697     {
03698       _RandomAccessIterator __cut =
03699         std::__unguarded_partition(__first, __last,
03700                        _ValueType(std::__median(*__first,
03701                                 *(__first
03702                                   + (__last
03703                                      - __first)
03704                                   / 2),
03705                                 *(__last
03706                                   - 1))));
03707       if (__cut <= __nth)
03708         __first = __cut;
03709       else
03710         __last = __cut;
03711     }
03712       std::__insertion_sort(__first, __last);
03713     }
03714 
03731   template<typename _RandomAccessIterator, typename _Compare>
03732     void
03733     nth_element(_RandomAccessIterator __first,
03734         _RandomAccessIterator __nth,
03735         _RandomAccessIterator __last,
03736                 _Compare __comp)
03737     {
03738       typedef typename iterator_traits<_RandomAccessIterator>::value_type
03739     _ValueType;
03740 
03741       // concept requirements
03742       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03743                   _RandomAccessIterator>)
03744       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03745                   _ValueType, _ValueType>)
03746       __glibcxx_requires_valid_range(__first, __nth);
03747       __glibcxx_requires_valid_range(__nth, __last);
03748 
03749       while (__last - __first > 3)
03750     {
03751       _RandomAccessIterator __cut =
03752         std::__unguarded_partition(__first, __last,
03753                        _ValueType(std::__median(*__first,
03754                                 *(__first
03755                                   + (__last
03756                                      - __first)
03757                                   / 2),
03758                                 *(__last - 1),
03759                                   __comp)), __comp);
03760       if (__cut <= __nth)
03761         __first = __cut;
03762       else
03763         __last = __cut;
03764     }
03765       std::__insertion_sort(__first, __last, __comp);
03766     }
03767 
03784   template<typename _ForwardIterator, typename _Tp>
03785     pair<_ForwardIterator, _ForwardIterator>
03786     equal_range(_ForwardIterator __first, _ForwardIterator __last,
03787         const _Tp& __val)
03788     {
03789       typedef typename iterator_traits<_ForwardIterator>::value_type
03790     _ValueType;
03791       typedef typename iterator_traits<_ForwardIterator>::difference_type
03792     _DistanceType;
03793 
03794       // concept requirements
03795       // See comments on lower_bound.
03796       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03797       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
03798       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
03799       __glibcxx_requires_partitioned(__first, __last, __val);
03800 
03801       _DistanceType __len = std::distance(__first, __last);
03802       _DistanceType __half;
03803       _ForwardIterator __middle, __left, __right;
03804 
03805       while (__len > 0)
03806     {
03807       __half = __len >> 1;
03808       __middle = __first;
03809       std::advance(__middle, __half);
03810       if (*__middle < __val)
03811         {
03812           __first = __middle;
03813           ++__first;
03814           __len = __len - __half - 1;
03815         }
03816       else if (__val < *__middle)
03817         __len = __half;
03818       else
03819         {
03820           __left = std::lower_bound(__first, __middle, __val);
03821           std::advance(__first, __len);
03822           __right = std::upper_bound(++__middle, __first, __val);
03823           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
03824         }
03825     }
03826       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
03827     }
03828 
03846   template<typename _ForwardIterator, typename _Tp, typename _Compare>
03847     pair<_ForwardIterator, _ForwardIterator>
03848     equal_range(_ForwardIterator __first, _ForwardIterator __last,
03849         const _Tp& __val,
03850         _Compare __comp)
03851     {
03852       typedef typename iterator_traits<_ForwardIterator>::value_type
03853     _ValueType;
03854       typedef typename iterator_traits<_ForwardIterator>::difference_type
03855     _DistanceType;
03856 
03857       // concept requirements
03858       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03859       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03860                   _ValueType, _Tp>)
03861       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03862                   _Tp, _ValueType>)
03863       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
03864 
03865       _DistanceType __len = std::distance(__first, __last);
03866       _DistanceType __half;
03867       _ForwardIterator __middle, __left, __right;
03868 
03869       while (__len > 0)
03870     {
03871       __half = __len >> 1;
03872       __middle = __first;
03873       std::advance(__middle, __half);
03874       if (__comp(*__middle, __val))
03875         {
03876           __first = __middle;
03877           ++__first;
03878           __len = __len - __half - 1;
03879         }
03880       else if (__comp(__val, *__middle))
03881         __len = __half;
03882       else
03883         {
03884           __left = std::lower_bound(__first, __middle, __val, __comp);
03885           std::advance(__first, __len);
03886           __right = std::upper_bound(++__middle, __first, __val, __comp);
03887           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
03888         }
03889     }
03890       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
03891     }
03892 
03904   template<typename _ForwardIterator, typename _Tp>
03905     bool
03906     binary_search(_ForwardIterator __first, _ForwardIterator __last,
03907                   const _Tp& __val)
03908     {
03909       // concept requirements
03910       // See comments on lower_bound.
03911       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03912       __glibcxx_function_requires(_SameTypeConcept<_Tp,
03913         typename iterator_traits<_ForwardIterator>::value_type>)
03914       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
03915       __glibcxx_requires_partitioned(__first, __last, __val);
03916 
03917       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
03918       return __i != __last && !(__val < *__i);
03919     }
03920 
03936   template<typename _ForwardIterator, typename _Tp, typename _Compare>
03937     bool
03938     binary_search(_ForwardIterator __first, _ForwardIterator __last,
03939                   const _Tp& __val, _Compare __comp)
03940     {
03941       // concept requirements
03942       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03943       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03944         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
03945       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
03946         typename iterator_traits<_ForwardIterator>::value_type>)
03947       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
03948 
03949       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
03950       return __i != __last && !__comp(__val, *__i);
03951     }
03952 
03953   // Set algorithms: includes, set_union, set_intersection, set_difference,
03954   // set_symmetric_difference.  All of these algorithms have the precondition
03955   // that their input ranges are sorted and the postcondition that their output
03956   // ranges are sorted.
03957 
03974   template<typename _InputIterator1, typename _InputIterator2>
03975     bool
03976     includes(_InputIterator1 __first1, _InputIterator1 __last1,
03977          _InputIterator2 __first2, _InputIterator2 __last2)
03978     {
03979       // concept requirements
03980       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03981       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03982       __glibcxx_function_requires(_SameTypeConcept<
03983         typename iterator_traits<_InputIterator1>::value_type,
03984         typename iterator_traits<_InputIterator2>::value_type>)
03985       __glibcxx_function_requires(_LessThanComparableConcept<
03986         typename iterator_traits<_InputIterator1>::value_type>)
03987       __glibcxx_requires_sorted(__first1, __last1);
03988       __glibcxx_requires_sorted(__first2, __last2);
03989 
03990       while (__first1 != __last1 && __first2 != __last2)
03991     if (*__first2 < *__first1)
03992       return false;
03993     else if(*__first1 < *__first2)
03994       ++__first1;
03995     else
03996       ++__first1, ++__first2;
03997 
03998       return __first2 == __last2;
03999     }
04000 
04020   template<typename _InputIterator1, typename _InputIterator2,
04021        typename _Compare>
04022     bool
04023     includes(_InputIterator1 __first1, _InputIterator1 __last1,
04024          _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
04025     {
04026       // concept requirements
04027       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04028       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04029       __glibcxx_function_requires(_SameTypeConcept<
04030         typename iterator_traits<_InputIterator1>::value_type,
04031         typename iterator_traits<_InputIterator2>::value_type>)
04032       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04033         typename iterator_traits<_InputIterator1>::value_type,
04034         typename iterator_traits<_InputIterator2>::value_type>)
04035       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04036       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04037 
04038       while (__first1 != __last1 && __first2 != __last2)
04039     if (__comp(*__first2, *__first1))
04040       return false;
04041     else if(__comp(*__first1, *__first2))
04042       ++__first1;
04043     else
04044       ++__first1, ++__first2;
04045 
04046       return __first2 == __last2;
04047     }
04048 
04066   template<typename _InputIterator1, typename _InputIterator2,
04067        typename _OutputIterator>
04068     _OutputIterator
04069     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
04070           _InputIterator2 __first2, _InputIterator2 __last2,
04071           _OutputIterator __result)
04072     {
04073       // concept requirements
04074       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04075       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04076       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04077         typename iterator_traits<_InputIterator1>::value_type>)
04078       __glibcxx_function_requires(_SameTypeConcept<
04079         typename iterator_traits<_InputIterator1>::value_type,
04080         typename iterator_traits<_InputIterator2>::value_type>)
04081       __glibcxx_function_requires(_LessThanComparableConcept<
04082         typename iterator_traits<_InputIterator1>::value_type>)
04083       __glibcxx_requires_sorted(__first1, __last1);
04084       __glibcxx_requires_sorted(__first2, __last2);
04085 
04086       while (__first1 != __last1 && __first2 != __last2)
04087     {
04088       if (*__first1 < *__first2)
04089         {
04090           *__result = *__first1;
04091           ++__first1;
04092         }
04093       else if (*__first2 < *__first1)
04094         {
04095           *__result = *__first2;
04096           ++__first2;
04097         }
04098       else
04099         {
04100           *__result = *__first1;
04101           ++__first1;
04102           ++__first2;
04103         }
04104       ++__result;
04105     }
04106       return std::copy(__first2, __last2, std::copy(__first1, __last1,
04107                             __result));
04108     }
04109 
04128   template<typename _InputIterator1, typename _InputIterator2,
04129        typename _OutputIterator, typename _Compare>
04130     _OutputIterator
04131     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
04132           _InputIterator2 __first2, _InputIterator2 __last2,
04133           _OutputIterator __result, _Compare __comp)
04134     {
04135       // concept requirements
04136       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04137       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04138       __glibcxx_function_requires(_SameTypeConcept<
04139         typename iterator_traits<_InputIterator1>::value_type,
04140         typename iterator_traits<_InputIterator2>::value_type>)
04141       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04142         typename iterator_traits<_InputIterator1>::value_type>)
04143       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04144         typename iterator_traits<_InputIterator1>::value_type,
04145         typename iterator_traits<_InputIterator2>::value_type>)
04146       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04147       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04148 
04149       while (__first1 != __last1 && __first2 != __last2)
04150     {
04151       if (__comp(*__first1, *__first2))
04152         {
04153           *__result = *__first1;
04154           ++__first1;
04155         }
04156       else if (__comp(*__first2, *__first1))
04157         {
04158           *__result = *__first2;
04159           ++__first2;
04160         }
04161       else
04162         {
04163           *__result = *__first1;
04164           ++__first1;
04165           ++__first2;
04166         }
04167       ++__result;
04168     }
04169       return std::copy(__first2, __last2, std::copy(__first1, __last1,
04170                             __result));
04171     }
04172 
04189   template<typename _InputIterator1, typename _InputIterator2,
04190        typename _OutputIterator>
04191     _OutputIterator
04192     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
04193              _InputIterator2 __first2, _InputIterator2 __last2,
04194              _OutputIterator __result)
04195     {
04196       // concept requirements
04197       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04198       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04199       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04200         typename iterator_traits<_InputIterator1>::value_type>)
04201       __glibcxx_function_requires(_SameTypeConcept<
04202         typename iterator_traits<_InputIterator1>::value_type,
04203         typename iterator_traits<_InputIterator2>::value_type>)
04204       __glibcxx_function_requires(_LessThanComparableConcept<
04205         typename iterator_traits<_InputIterator1>::value_type>)
04206       __glibcxx_requires_sorted(__first1, __last1);
04207       __glibcxx_requires_sorted(__first2, __last2);
04208 
04209       while (__first1 != __last1 && __first2 != __last2)
04210     if (*__first1 < *__first2)
04211       ++__first1;
04212     else if (*__first2 < *__first1)
04213       ++__first2;
04214     else
04215       {
04216         *__result = *__first1;
04217         ++__first1;
04218         ++__first2;
04219         ++__result;
04220       }
04221       return __result;
04222     }
04223 
04243   template<typename _InputIterator1, typename _InputIterator2,
04244        typename _OutputIterator, typename _Compare>
04245     _OutputIterator
04246     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
04247              _InputIterator2 __first2, _InputIterator2 __last2,
04248              _OutputIterator __result, _Compare __comp)
04249     {
04250       // concept requirements
04251       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04252       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04253       __glibcxx_function_requires(_SameTypeConcept<
04254         typename iterator_traits<_InputIterator1>::value_type,
04255         typename iterator_traits<_InputIterator2>::value_type>)
04256       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04257         typename iterator_traits<_InputIterator1>::value_type>)
04258       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04259         typename iterator_traits<_InputIterator1>::value_type,
04260         typename iterator_traits<_InputIterator2>::value_type>)
04261       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04262       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04263 
04264       while (__first1 != __last1 && __first2 != __last2)
04265     if (__comp(*__first1, *__first2))
04266       ++__first1;
04267     else if (__comp(*__first2, *__first1))
04268       ++__first2;
04269     else
04270       {
04271         *__result = *__first1;
04272         ++__first1;
04273         ++__first2;
04274         ++__result;
04275       }
04276       return __result;
04277     }
04278 
04297   template<typename _InputIterator1, typename _InputIterator2,
04298        typename _OutputIterator>
04299     _OutputIterator
04300     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
04301            _InputIterator2 __first2, _InputIterator2 __last2,
04302            _OutputIterator __result)
04303     {
04304       // concept requirements
04305       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04306       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04307       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04308         typename iterator_traits<_InputIterator1>::value_type>)
04309       __glibcxx_function_requires(_SameTypeConcept<
04310         typename iterator_traits<_InputIterator1>::value_type,
04311         typename iterator_traits<_InputIterator2>::value_type>)
04312       __glibcxx_function_requires(_LessThanComparableConcept<
04313         typename iterator_traits<_InputIterator1>::value_type>)
04314       __glibcxx_requires_sorted(__first1, __last1);
04315       __glibcxx_requires_sorted(__first2, __last2);
04316 
04317       while (__first1 != __last1 && __first2 != __last2)
04318     if (*__first1 < *__first2)
04319       {
04320         *__result = *__first1;
04321         ++__first1;
04322         ++__result;
04323       }
04324     else if (*__first2 < *__first1)
04325       ++__first2;
04326     else
04327       {
04328         ++__first1;
04329         ++__first2;
04330       }
04331       return std::copy(__first1, __last1, __result);
04332     }
04333 
04355   template<typename _InputIterator1, typename _InputIterator2,
04356        typename _OutputIterator, typename _Compare>
04357     _OutputIterator
04358     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
04359            _InputIterator2 __first2, _InputIterator2 __last2,
04360            _OutputIterator __result, _Compare __comp)
04361     {
04362       // concept requirements
04363       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04364       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04365       __glibcxx_function_requires(_SameTypeConcept<
04366         typename iterator_traits<_InputIterator1>::value_type,
04367         typename iterator_traits<_InputIterator2>::value_type>)
04368       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04369         typename iterator_traits<_InputIterator1>::value_type>)
04370       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04371         typename iterator_traits<_InputIterator1>::value_type,
04372         typename iterator_traits<_InputIterator2>::value_type>)
04373       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04374       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04375 
04376       while (__first1 != __last1 && __first2 != __last2)
04377     if (__comp(*__first1, *__first2))
04378       {
04379         *__result = *__first1;
04380         ++__first1;
04381         ++__result;
04382       }
04383     else if (__comp(*__first2, *__first1))
04384       ++__first2;
04385     else
04386       {
04387         ++__first1;
04388         ++__first2;
04389       }
04390       return std::copy(__first1, __last1, __result);
04391     }
04392 
04409   template<typename _InputIterator1, typename _InputIterator2,
04410        typename _OutputIterator>
04411     _OutputIterator
04412     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
04413                  _InputIterator2 __first2, _InputIterator2 __last2,
04414                  _OutputIterator __result)
04415     {
04416       // concept requirements
04417       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04418       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04419       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04420         typename iterator_traits<_InputIterator1>::value_type>)
04421       __glibcxx_function_requires(_SameTypeConcept<
04422         typename iterator_traits<_InputIterator1>::value_type,
04423         typename iterator_traits<_InputIterator2>::value_type>)
04424       __glibcxx_function_requires(_LessThanComparableConcept<
04425         typename iterator_traits<_InputIterator1>::value_type>)
04426       __glibcxx_requires_sorted(__first1, __last1);
04427       __glibcxx_requires_sorted(__first2, __last2);
04428 
04429       while (__first1 != __last1 && __first2 != __last2)
04430     if (*__first1 < *__first2)
04431       {
04432         *__result = *__first1;
04433         ++__first1;
04434         ++__result;
04435       }
04436     else if (*__first2 < *__first1)
04437       {
04438         *__result = *__first2;
04439         ++__first2;
04440         ++__result;
04441       }
04442     else
04443       {
04444         ++__first1;
04445         ++__first2;
04446       }
04447       return std::copy(__first2, __last2, std::copy(__first1,
04448                             __last1, __result));
04449     }
04450 
04470   template<typename _InputIterator1, typename _InputIterator2,
04471        typename _OutputIterator, typename _Compare>
04472     _OutputIterator
04473     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
04474                  _InputIterator2 __first2, _InputIterator2 __last2,
04475                  _OutputIterator __result,
04476                  _Compare __comp)
04477     {
04478       // concept requirements
04479       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04480       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04481       __glibcxx_function_requires(_SameTypeConcept<
04482         typename iterator_traits<_InputIterator1>::value_type,
04483         typename iterator_traits<_InputIterator2>::value_type>)
04484       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04485         typename iterator_traits<_InputIterator1>::value_type>)
04486       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04487         typename iterator_traits<_InputIterator1>::value_type,
04488         typename iterator_traits<_InputIterator2>::value_type>)
04489       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04490       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04491 
04492       while (__first1 != __last1 && __first2 != __last2)
04493     if (__comp(*__first1, *__first2))
04494       {
04495         *__result = *__first1;
04496         ++__first1;
04497         ++__result;
04498       }
04499     else if (__comp(*__first2, *__first1))
04500       {
04501         *__result = *__first2;
04502         ++__first2;
04503         ++__result;
04504       }
04505     else
04506       {
04507         ++__first1;
04508         ++__first2;
04509       }
04510       return std::copy(__first2, __last2, std::copy(__first1,
04511                             __last1, __result));
04512     }
04513 
04514   // min_element and max_element, with and without an explicitly supplied
04515   // comparison function.
04516 
04523   template<typename _ForwardIterator>
04524     _ForwardIterator
04525     max_element(_ForwardIterator __first, _ForwardIterator __last)
04526     {
04527       // concept requirements
04528       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04529       __glibcxx_function_requires(_LessThanComparableConcept<
04530         typename iterator_traits<_ForwardIterator>::value_type>)
04531       __glibcxx_requires_valid_range(__first, __last);
04532 
04533       if (__first == __last)
04534     return __first;
04535       _ForwardIterator __result = __first;
04536       while (++__first != __last)
04537     if (*__result < *__first)
04538       __result = __first;
04539       return __result;
04540     }
04541 
04550   template<typename _ForwardIterator, typename _Compare>
04551     _ForwardIterator
04552     max_element(_ForwardIterator __first, _ForwardIterator __last,
04553         _Compare __comp)
04554     {
04555       // concept requirements
04556       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04557       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04558         typename iterator_traits<_ForwardIterator>::value_type,
04559         typename iterator_traits<_ForwardIterator>::value_type>)
04560       __glibcxx_requires_valid_range(__first, __last);
04561 
04562       if (__first == __last) return __first;
04563       _ForwardIterator __result = __first;
04564       while (++__first != __last)
04565     if (__comp(*__result, *__first)) __result = __first;
04566       return __result;
04567     }
04568 
04575   template<typename _ForwardIterator>
04576     _ForwardIterator
04577     min_element(_ForwardIterator __first, _ForwardIterator __last)
04578     {
04579       // concept requirements
04580       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04581       __glibcxx_function_requires(_LessThanComparableConcept<
04582         typename iterator_traits<_ForwardIterator>::value_type>)
04583       __glibcxx_requires_valid_range(__first, __last);
04584 
04585       if (__first == __last)
04586     return __first;
04587       _ForwardIterator __result = __first;
04588       while (++__first != __last)
04589     if (*__first < *__result)
04590       __result = __first;
04591       return __result;
04592     }
04593 
04602   template<typename _ForwardIterator, typename _Compare>
04603     _ForwardIterator
04604     min_element(_ForwardIterator __first, _ForwardIterator __last,
04605         _Compare __comp)
04606     {
04607       // concept requirements
04608       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04609       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04610         typename iterator_traits<_ForwardIterator>::value_type,
04611         typename iterator_traits<_ForwardIterator>::value_type>)
04612       __glibcxx_requires_valid_range(__first, __last);
04613 
04614       if (__first == __last)
04615     return __first;
04616       _ForwardIterator __result = __first;
04617       while (++__first != __last)
04618     if (__comp(*__first, *__result))
04619       __result = __first;
04620       return __result;
04621     }
04622 
04623   // next_permutation and prev_permutation, with and without an explicitly
04624   // supplied comparison function.
04625 
04637   template<typename _BidirectionalIterator>
04638     bool
04639     next_permutation(_BidirectionalIterator __first,
04640              _BidirectionalIterator __last)
04641     {
04642       // concept requirements
04643       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04644                   _BidirectionalIterator>)
04645       __glibcxx_function_requires(_LessThanComparableConcept<
04646         typename iterator_traits<_BidirectionalIterator>::value_type>)
04647       __glibcxx_requires_valid_range(__first, __last);
04648 
04649       if (__first == __last)
04650     return false;
04651       _BidirectionalIterator __i = __first;
04652       ++__i;
04653       if (__i == __last)
04654     return false;
04655       __i = __last;
04656       --__i;
04657 
04658       for(;;)
04659     {
04660       _BidirectionalIterator __ii = __i;
04661       --__i;
04662       if (*__i < *__ii)
04663         {
04664           _BidirectionalIterator __j = __last;
04665           while (!(*__i < *--__j))
04666         {}
04667           std::iter_swap(__i, __j);
04668           std::reverse(__ii, __last);
04669           return true;
04670         }
04671       if (__i == __first)
04672         {
04673           std::reverse(__first, __last);
04674           return false;
04675         }
04676     }
04677     }
04678 
04693   template<typename _BidirectionalIterator, typename _Compare>
04694     bool
04695     next_permutation(_BidirectionalIterator __first,
04696              _BidirectionalIterator __last, _Compare __comp)
04697     {
04698       // concept requirements
04699       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04700                   _BidirectionalIterator>)
04701       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04702         typename iterator_traits<_BidirectionalIterator>::value_type,
04703         typename iterator_traits<_BidirectionalIterator>::value_type>)
04704       __glibcxx_requires_valid_range(__first, __last);
04705 
04706       if (__first == __last)
04707     return false;
04708       _BidirectionalIterator __i = __first;
04709       ++__i;
04710       if (__i == __last)
04711     return false;
04712       __i = __last;
04713       --__i;
04714 
04715       for(;;)
04716     {
04717       _BidirectionalIterator __ii = __i;
04718       --__i;
04719       if (__comp(*__i, *__ii))
04720         {
04721           _BidirectionalIterator __j = __last;
04722           while (!__comp(*__i, *--__j))
04723         {}
04724           std::iter_swap(__i, __j);
04725           std::reverse(__ii, __last);
04726           return true;
04727         }
04728       if (__i == __first)
04729         {
04730           std::reverse(__first, __last);
04731           return false;
04732         }
04733     }
04734     }
04735 
04748   template<typename _BidirectionalIterator>
04749     bool
04750     prev_permutation(_BidirectionalIterator __first,
04751              _BidirectionalIterator __last)
04752     {
04753       // concept requirements
04754       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04755                   _BidirectionalIterator>)
04756       __glibcxx_function_requires(_LessThanComparableConcept<
04757         typename iterator_traits<_BidirectionalIterator>::value_type>)
04758       __glibcxx_requires_valid_range(__first, __last);
04759 
04760       if (__first == __last)
04761     return false;
04762       _BidirectionalIterator __i = __first;
04763       ++__i;
04764       if (__i == __last)
04765     return false;
04766       __i = __last;
04767       --__i;
04768 
04769       for(;;)
04770     {
04771       _BidirectionalIterator __ii = __i;
04772       --__i;
04773       if (*__ii < *__i)
04774         {
04775           _BidirectionalIterator __j = __last;
04776           while (!(*--__j < *__i))
04777         {}
04778           std::iter_swap(__i, __j);
04779           std::reverse(__ii, __last);
04780           return true;
04781         }
04782       if (__i == __first)
04783         {
04784           std::reverse(__first, __last);
04785           return false;
04786         }
04787     }
04788     }
04789 
04804   template<typename _BidirectionalIterator, typename _Compare>
04805     bool
04806     prev_permutation(_BidirectionalIterator __first,
04807              _BidirectionalIterator __last, _Compare __comp)
04808     {
04809       // concept requirements
04810       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04811                   _BidirectionalIterator>)
04812       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04813         typename iterator_traits<_BidirectionalIterator>::value_type,
04814         typename iterator_traits<_BidirectionalIterator>::value_type>)
04815       __glibcxx_requires_valid_range(__first, __last);
04816 
04817       if (__first == __last)
04818     return false;
04819       _BidirectionalIterator __i = __first;
04820       ++__i;
04821       if (__i == __last)
04822     return false;
04823       __i = __last;
04824       --__i;
04825 
04826       for(;;)
04827     {
04828       _BidirectionalIterator __ii = __i;
04829       --__i;
04830       if (__comp(*__ii, *__i))
04831         {
04832           _BidirectionalIterator __j = __last;
04833           while (!__comp(*--__j, *__i))
04834         {}
04835           std::iter_swap(__i, __j);
04836           std::reverse(__ii, __last);
04837           return true;
04838         }
04839       if (__i == __first)
04840         {
04841           std::reverse(__first, __last);
04842           return false;
04843         }
04844     }
04845     }
04846 
04847   // find_first_of, with and without an explicitly supplied comparison function.
04848 
04863   template<typename _InputIterator, typename _ForwardIterator>
04864     _InputIterator
04865     find_first_of(_InputIterator __first1, _InputIterator __last1,
04866           _ForwardIterator __first2, _ForwardIterator __last2)
04867     {
04868       // concept requirements
04869       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04870       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04871       __glibcxx_function_requires(_EqualOpConcept<
04872         typename iterator_traits<_InputIterator>::value_type,
04873         typename iterator_traits<_ForwardIterator>::value_type>)
04874       __glibcxx_requires_valid_range(__first1, __last1);
04875       __glibcxx_requires_valid_range(__first2, __last2);
04876 
04877       for ( ; __first1 != __last1; ++__first1)
04878     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04879       if (*__first1 == *__iter)
04880         return __first1;
04881       return __last1;
04882     }
04883 
04899   template<typename _InputIterator, typename _ForwardIterator,
04900        typename _BinaryPredicate>
04901     _InputIterator
04902     find_first_of(_InputIterator __first1, _InputIterator __last1,
04903           _ForwardIterator __first2, _ForwardIterator __last2,
04904           _BinaryPredicate __comp)
04905     {
04906       // concept requirements
04907       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04908       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04909       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04910         typename iterator_traits<_InputIterator>::value_type,
04911         typename iterator_traits<_ForwardIterator>::value_type>)
04912       __glibcxx_requires_valid_range(__first1, __last1);
04913       __glibcxx_requires_valid_range(__first2, __last2);
04914 
04915       for ( ; __first1 != __last1; ++__first1)
04916     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04917       if (__comp(*__first1, *__iter))
04918         return __first1;
04919       return __last1;
04920     }
04921 
04922 
04923   // find_end, with and without an explicitly supplied comparison function.
04924   // Search [first2, last2) as a subsequence in [first1, last1), and return
04925   // the *last* possible match.  Note that find_end for bidirectional iterators
04926   // is much faster than for forward iterators.
04927 
04928   // find_end for forward iterators.
04929   template<typename _ForwardIterator1, typename _ForwardIterator2>
04930     _ForwardIterator1
04931     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04932            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
04933            forward_iterator_tag, forward_iterator_tag)
04934     {
04935       if (__first2 == __last2)
04936     return __last1;
04937       else
04938     {
04939       _ForwardIterator1 __result = __last1;
04940       while (1)
04941         {
04942           _ForwardIterator1 __new_result
04943         = std::search(__first1, __last1, __first2, __last2);
04944           if (__new_result == __last1)
04945         return __result;
04946           else
04947         {
04948           __result = __new_result;
04949           __first1 = __new_result;
04950           ++__first1;
04951         }
04952         }
04953     }
04954     }
04955 
04956   template<typename _ForwardIterator1, typename _ForwardIterator2,
04957        typename _BinaryPredicate>
04958     _ForwardIterator1
04959     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04960            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
04961            forward_iterator_tag, forward_iterator_tag,
04962            _BinaryPredicate __comp)
04963     {
04964       if (__first2 == __last2)
04965     return __last1;
04966       else
04967     {
04968       _ForwardIterator1 __result = __last1;
04969       while (1)
04970         {
04971           _ForwardIterator1 __new_result
04972         = std::search(__first1, __last1, __first2, __last2, __comp);
04973           if (__new_result == __last1)
04974         return __result;
04975           else
04976         {
04977           __result = __new_result;
04978           __first1 = __new_result;
04979           ++__first1;
04980         }
04981         }
04982     }
04983     }
04984 
04985   // find_end for bidirectional iterators.  Requires partial specialization.
04986   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
04987     _BidirectionalIterator1
04988     __find_end(_BidirectionalIterator1 __first1,
04989            _BidirectionalIterator1 __last1,
04990            _BidirectionalIterator2 __first2,
04991            _BidirectionalIterator2 __last2,
04992            bidirectional_iterator_tag, bidirectional_iterator_tag)
04993     {
04994       // concept requirements
04995       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04996                   _BidirectionalIterator1>)
04997       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04998                   _BidirectionalIterator2>)
04999 
05000       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
05001       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
05002 
05003       _RevIterator1 __rlast1(__first1);
05004       _RevIterator2 __rlast2(__first2);
05005       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
05006                         _RevIterator2(__last2), __rlast2);
05007 
05008       if (__rresult == __rlast1)
05009     return __last1;
05010       else
05011     {
05012       _BidirectionalIterator1 __result = __rresult.base();
05013       std::advance(__result, -std::distance(__first2, __last2));
05014       return __result;
05015     }
05016     }
05017 
05018   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
05019        typename _BinaryPredicate>
05020     _BidirectionalIterator1
05021     __find_end(_BidirectionalIterator1 __first1,
05022            _BidirectionalIterator1 __last1,
05023            _BidirectionalIterator2 __first2,
05024            _BidirectionalIterator2 __last2,
05025            bidirectional_iterator_tag, bidirectional_iterator_tag,
05026            _BinaryPredicate __comp)
05027     {
05028       // concept requirements
05029       __glibcxx_function_requires(_BidirectionalIteratorConcept<
05030                   _BidirectionalIterator1>)
05031       __glibcxx_function_requires(_BidirectionalIteratorConcept<
05032                   _BidirectionalIterator2>)
05033 
05034       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
05035       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
05036 
05037       _RevIterator1 __rlast1(__first1);
05038       _RevIterator2 __rlast2(__first2);
05039       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
05040                         _RevIterator2(__last2), __rlast2,
05041                         __comp);
05042 
05043       if (__rresult == __rlast1)
05044     return __last1;
05045       else
05046     {
05047       _BidirectionalIterator1 __result = __rresult.base();
05048       std::advance(__result, -std::distance(__first2, __last2));
05049       return __result;
05050     }
05051     }
05052 
05053   // Dispatching functions for find_end.
05054 
05079   template<typename _ForwardIterator1, typename _ForwardIterator2>
05080     inline _ForwardIterator1
05081     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
05082          _ForwardIterator2 __first2, _ForwardIterator2 __last2)
05083     {
05084       // concept requirements
05085       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
05086       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
05087       __glibcxx_function_requires(_EqualOpConcept<
05088         typename iterator_traits<_ForwardIterator1>::value_type,
05089         typename iterator_traits<_ForwardIterator2>::value_type>)
05090       __glibcxx_requires_valid_range(__first1, __last1);
05091       __glibcxx_requires_valid_range(__first2, __last2);
05092 
05093       return std::__find_end(__first1, __last1, __first2, __last2,
05094                  std::__iterator_category(__first1),
05095                  std::__iterator_category(__first2));
05096     }
05097 
05124   template<typename _ForwardIterator1, typename _ForwardIterator2,
05125        typename _BinaryPredicate>
05126     inline _ForwardIterator1
05127     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
05128          _ForwardIterator2 __first2, _ForwardIterator2 __last2,
05129          _BinaryPredicate __comp)
05130     {
05131       // concept requirements
05132       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
05133       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
05134       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
05135         typename iterator_traits<_ForwardIterator1>::value_type,
05136         typename iterator_traits<_ForwardIterator2>::value_type>)
05137       __glibcxx_requires_valid_range(__first1, __last1);
05138       __glibcxx_requires_valid_range(__first2, __last2);
05139 
05140       return std::__find_end(__first1, __last1, __first2, __last2,
05141                  std::__iterator_category(__first1),
05142                  std::__iterator_category(__first2),
05143                  __comp);
05144     }
05145 
05146 } // namespace std
05147 
05148 #endif /* _ALGO_H */