GNU C++ STL: stl_algo.h Source File

00001 // Algorithm implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 2, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /*
00032  *
00033  * Copyright (c) 1994
00034  * Hewlett-Packard Company
00035  *
00036  * Permission to use, copy, modify, distribute and sell this software
00037  * and its documentation for any purpose is hereby granted without fee,
00038  * provided that the above copyright notice appear in all copies and
00039  * that both that copyright notice and this permission notice appear
00040  * in supporting documentation.  Hewlett-Packard Company makes no
00041  * representations about the suitability of this software for any
00042  * purpose.  It is provided "as is" without express or implied warranty.
00043  *
00044  *
00045  * Copyright (c) 1996
00046  * Silicon Graphics Computer Systems, Inc.
00047  *
00048  * Permission to use, copy, modify, distribute and sell this software
00049  * and its documentation for any purpose is hereby granted without fee,
00050  * provided that the above copyright notice appear in all copies and
00051  * that both that copyright notice and this permission notice appear
00052  * in supporting documentation.  Silicon Graphics makes no
00053  * representations about the suitability of this software for any
00054  * purpose.  It is provided "as is" without express or implied warranty.
00055  */
00056 
00062 #ifndef _ALGO_H
00063 #define _ALGO_H 1
00064 
00065 #include <bits/stl_heap.h>
00066 #include <bits/stl_tempbuf.h>     // for _Temporary_buffer
00067 #include <debug/debug.h>
00068 
00069 // See concept_check.h for the __glibcxx_*_requires macros.
00070 
00071 namespace std
00072 {
00085   template<typename _Tp>
00086     inline const _Tp&
00087     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
00088     {
00089       // concept requirements
00090       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00091       if (__a < __b)
00092     if (__b < __c)
00093       return __b;
00094     else if (__a < __c)
00095       return __c;
00096     else
00097       return __a;
00098       else if (__a < __c)
00099     return __a;
00100       else if (__b < __c)
00101     return __c;
00102       else
00103     return __b;
00104     }
00105 
00119   template<typename _Tp, typename _Compare>
00120     inline const _Tp&
00121     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
00122     {
00123       // concept requirements
00124       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
00125       if (__comp(__a, __b))
00126     if (__comp(__b, __c))
00127       return __b;
00128     else if (__comp(__a, __c))
00129       return __c;
00130     else
00131       return __a;
00132       else if (__comp(__a, __c))
00133     return __a;
00134       else if (__comp(__b, __c))
00135     return __c;
00136       else
00137     return __b;
00138     }
00139 
00151   template<typename _InputIterator, typename _Function>
00152     _Function
00153     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
00154     {
00155       // concept requirements
00156       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00157       __glibcxx_requires_valid_range(__first, __last);
00158       for ( ; __first != __last; ++__first)
00159     __f(*__first);
00160       return __f;
00161     }
00162 
00168   template<typename _InputIterator, typename _Tp>
00169     inline _InputIterator
00170     __find(_InputIterator __first, _InputIterator __last,
00171        const _Tp& __val, input_iterator_tag)
00172     {
00173       while (__first != __last && !(*__first == __val))
00174     ++__first;
00175       return __first;
00176     }
00177 
00183   template<typename _InputIterator, typename _Predicate>
00184     inline _InputIterator
00185     __find_if(_InputIterator __first, _InputIterator __last,
00186           _Predicate __pred, input_iterator_tag)
00187     {
00188       while (__first != __last && !__pred(*__first))
00189     ++__first;
00190       return __first;
00191     }
00192 
00198   template<typename _RandomAccessIterator, typename _Tp>
00199     _RandomAccessIterator
00200     __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
00201        const _Tp& __val, random_access_iterator_tag)
00202     {
00203       typename iterator_traits<_RandomAccessIterator>::difference_type
00204     __trip_count = (__last - __first) >> 2;
00205 
00206       for ( ; __trip_count > 0 ; --__trip_count)
00207     {
00208       if (*__first == __val)
00209         return __first;
00210       ++__first;
00211 
00212       if (*__first == __val)
00213         return __first;
00214       ++__first;
00215 
00216       if (*__first == __val)
00217         return __first;
00218       ++__first;
00219 
00220       if (*__first == __val)
00221         return __first;
00222       ++__first;
00223     }
00224 
00225       switch (__last - __first)
00226     {
00227     case 3:
00228       if (*__first == __val)
00229         return __first;
00230       ++__first;
00231     case 2:
00232       if (*__first == __val)
00233         return __first;
00234       ++__first;
00235     case 1:
00236       if (*__first == __val)
00237         return __first;
00238       ++__first;
00239     case 0:
00240     default:
00241       return __last;
00242     }
00243     }
00244 
00250   template<typename _RandomAccessIterator, typename _Predicate>
00251     _RandomAccessIterator
00252     __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
00253           _Predicate __pred, random_access_iterator_tag)
00254     {
00255       typename iterator_traits<_RandomAccessIterator>::difference_type
00256     __trip_count = (__last - __first) >> 2;
00257 
00258       for ( ; __trip_count > 0 ; --__trip_count)
00259     {
00260       if (__pred(*__first))
00261         return __first;
00262       ++__first;
00263 
00264       if (__pred(*__first))
00265         return __first;
00266       ++__first;
00267 
00268       if (__pred(*__first))
00269         return __first;
00270       ++__first;
00271 
00272       if (__pred(*__first))
00273         return __first;
00274       ++__first;
00275     }
00276 
00277       switch (__last - __first)
00278     {
00279     case 3:
00280       if (__pred(*__first))
00281         return __first;
00282       ++__first;
00283     case 2:
00284       if (__pred(*__first))
00285         return __first;
00286       ++__first;
00287     case 1:
00288       if (__pred(*__first))
00289         return __first;
00290       ++__first;
00291     case 0:
00292     default:
00293       return __last;
00294     }
00295     }
00296 
00305   template<typename _InputIterator, typename _Tp>
00306     inline _InputIterator
00307     find(_InputIterator __first, _InputIterator __last,
00308      const _Tp& __val)
00309     {
00310       // concept requirements
00311       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00312       __glibcxx_function_requires(_EqualOpConcept<
00313         typename iterator_traits<_InputIterator>::value_type, _Tp>)
00314       __glibcxx_requires_valid_range(__first, __last);
00315       return std::__find(__first, __last, __val,
00316                  std::__iterator_category(__first));
00317     }
00318 
00327   template<typename _InputIterator, typename _Predicate>
00328     inline _InputIterator
00329     find_if(_InputIterator __first, _InputIterator __last,
00330         _Predicate __pred)
00331     {
00332       // concept requirements
00333       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00334       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00335           typename iterator_traits<_InputIterator>::value_type>)
00336       __glibcxx_requires_valid_range(__first, __last);
00337       return std::__find_if(__first, __last, __pred,
00338                 std::__iterator_category(__first));
00339     }
00340 
00349   template<typename _ForwardIterator>
00350     _ForwardIterator
00351     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
00352     {
00353       // concept requirements
00354       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00355       __glibcxx_function_requires(_EqualityComparableConcept<
00356         typename iterator_traits<_ForwardIterator>::value_type>)
00357       __glibcxx_requires_valid_range(__first, __last);
00358       if (__first == __last)
00359     return __last;
00360       _ForwardIterator __next = __first;
00361       while(++__next != __last)
00362     {
00363       if (*__first == *__next)
00364         return __first;
00365       __first = __next;
00366     }
00367       return __last;
00368     }
00369 
00380   template<typename _ForwardIterator, typename _BinaryPredicate>
00381     _ForwardIterator
00382     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
00383           _BinaryPredicate __binary_pred)
00384     {
00385       // concept requirements
00386       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00387       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00388         typename iterator_traits<_ForwardIterator>::value_type,
00389         typename iterator_traits<_ForwardIterator>::value_type>)
00390       __glibcxx_requires_valid_range(__first, __last);
00391       if (__first == __last)
00392     return __last;
00393       _ForwardIterator __next = __first;
00394       while(++__next != __last)
00395     {
00396       if (__binary_pred(*__first, *__next))
00397         return __first;
00398       __first = __next;
00399     }
00400       return __last;
00401     }
00402 
00411   template<typename _InputIterator, typename _Tp>
00412     typename iterator_traits<_InputIterator>::difference_type
00413     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
00414     {
00415       // concept requirements
00416       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00417       __glibcxx_function_requires(_EqualOpConcept<
00418     typename iterator_traits<_InputIterator>::value_type, _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 
00617   template<typename _ForwardIterator, typename _Integer, typename _Tp>
00618     _ForwardIterator
00619     __search_n(_ForwardIterator __first, _ForwardIterator __last,
00620            _Integer __count, const _Tp& __val,
00621            std::forward_iterator_tag)
00622     {
00623       __first = std::find(__first, __last, __val);
00624       while (__first != __last)
00625     {
00626       typename iterator_traits<_ForwardIterator>::difference_type
00627         __n = __count;
00628       _ForwardIterator __i = __first;
00629       ++__i;
00630       while (__i != __last && __n != 1 && *__i == __val)
00631         {
00632           ++__i;
00633           --__n;
00634         }
00635       if (__n == 1)
00636         return __first;
00637       if (__i == __last)
00638         return __last;
00639       __first = std::find(++__i, __last, __val);
00640     }
00641       return __last;
00642     }
00643 
00651   template<typename _RandomAccessIter, typename _Integer, typename _Tp>
00652     _RandomAccessIter
00653     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
00654            _Integer __count, const _Tp& __val, 
00655            std::random_access_iterator_tag)
00656     {
00657       
00658       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
00659     _DistanceType;
00660 
00661       _DistanceType __tailSize = __last - __first;
00662       const _DistanceType __pattSize = __count;
00663 
00664       if (__tailSize < __pattSize)
00665         return __last;
00666 
00667       const _DistanceType __skipOffset = __pattSize - 1;
00668       _RandomAccessIter __lookAhead = __first + __skipOffset;
00669       __tailSize -= __pattSize;
00670 
00671       while (1) // the main loop...
00672     {
00673       // __lookAhead here is always pointing to the last element of next 
00674       // possible match.
00675       while (!(*__lookAhead == __val)) // the skip loop...
00676         {
00677           if (__tailSize < __pattSize)
00678         return __last;  // Failure
00679           __lookAhead += __pattSize;
00680           __tailSize -= __pattSize;
00681         }
00682       _DistanceType __remainder = __skipOffset;
00683       for (_RandomAccessIter __backTrack = __lookAhead - 1; 
00684            *__backTrack == __val; --__backTrack)
00685         {
00686           if (--__remainder == 0)
00687         return (__lookAhead - __skipOffset); // Success
00688         }
00689       if (__remainder > __tailSize)
00690         return __last; // Failure
00691       __lookAhead += __remainder;
00692       __tailSize -= __remainder;
00693     }
00694     }
00695 
00709   template<typename _ForwardIterator, typename _Integer, typename _Tp>
00710     _ForwardIterator
00711     search_n(_ForwardIterator __first, _ForwardIterator __last,
00712          _Integer __count, const _Tp& __val)
00713     {
00714       // concept requirements
00715       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00716       __glibcxx_function_requires(_EqualOpConcept<
00717     typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
00718       __glibcxx_requires_valid_range(__first, __last);
00719 
00720       if (__count <= 0)
00721     return __first;
00722       if (__count == 1)
00723     return std::find(__first, __last, __val);
00724       return std::__search_n(__first, __last, __count, __val,
00725                  std::__iterator_category(__first));
00726     }
00727 
00736   template<typename _ForwardIterator, typename _Integer, typename _Tp,
00737            typename _BinaryPredicate>
00738     _ForwardIterator
00739     __search_n(_ForwardIterator __first, _ForwardIterator __last,
00740            _Integer __count, const _Tp& __val,
00741            _BinaryPredicate __binary_pred, std::forward_iterator_tag)
00742     {
00743       while (__first != __last && !__binary_pred(*__first, __val))
00744         ++__first;
00745 
00746       while (__first != __last)
00747     {
00748       typename iterator_traits<_ForwardIterator>::difference_type
00749         __n = __count;
00750       _ForwardIterator __i = __first;
00751       ++__i;
00752       while (__i != __last && __n != 1 && __binary_pred(*__i, __val))
00753         {
00754           ++__i;
00755           --__n;
00756         }
00757       if (__n == 1)
00758         return __first;
00759       if (__i == __last)
00760         return __last;
00761       __first = ++__i;
00762       while (__first != __last && !__binary_pred(*__first, __val))
00763         ++__first;
00764     }
00765       return __last;
00766     }
00767 
00776   template<typename _RandomAccessIter, typename _Integer, typename _Tp,
00777        typename _BinaryPredicate>
00778     _RandomAccessIter
00779     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
00780            _Integer __count, const _Tp& __val,
00781            _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
00782     {
00783       
00784       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
00785     _DistanceType;
00786 
00787       _DistanceType __tailSize = __last - __first;
00788       const _DistanceType __pattSize = __count;
00789 
00790       if (__tailSize < __pattSize)
00791         return __last;
00792 
00793       const _DistanceType __skipOffset = __pattSize - 1;
00794       _RandomAccessIter __lookAhead = __first + __skipOffset;
00795       __tailSize -= __pattSize;
00796 
00797       while (1) // the main loop...
00798     {
00799       // __lookAhead here is always pointing to the last element of next 
00800       // possible match.
00801       while (!__binary_pred(*__lookAhead, __val)) // the skip loop...
00802         {
00803           if (__tailSize < __pattSize)
00804         return __last;  // Failure
00805           __lookAhead += __pattSize;
00806           __tailSize -= __pattSize;
00807         }
00808       _DistanceType __remainder = __skipOffset;
00809       for (_RandomAccessIter __backTrack = __lookAhead - 1; 
00810            __binary_pred(*__backTrack, __val); --__backTrack)
00811         {
00812           if (--__remainder == 0)
00813         return (__lookAhead - __skipOffset); // Success
00814         }
00815       if (__remainder > __tailSize)
00816         return __last; // Failure
00817       __lookAhead += __remainder;
00818       __tailSize -= __remainder;
00819     }
00820     }
00821 
00837   template<typename _ForwardIterator, typename _Integer, typename _Tp,
00838            typename _BinaryPredicate>
00839     _ForwardIterator
00840     search_n(_ForwardIterator __first, _ForwardIterator __last,
00841          _Integer __count, const _Tp& __val,
00842          _BinaryPredicate __binary_pred)
00843     {
00844       // concept requirements
00845       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00846       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00847         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
00848       __glibcxx_requires_valid_range(__first, __last);
00849 
00850       if (__count <= 0)
00851     return __first;
00852       if (__count == 1)
00853     {
00854       while (__first != __last && !__binary_pred(*__first, __val))
00855         ++__first;
00856       return __first;
00857     }
00858       return std::__search_n(__first, __last, __count, __val, __binary_pred,
00859                  std::__iterator_category(__first));
00860     }
00861 
00873   template<typename _ForwardIterator1, typename _ForwardIterator2>
00874     _ForwardIterator2
00875     swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00876         _ForwardIterator2 __first2)
00877     {
00878       // concept requirements
00879       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00880                   _ForwardIterator1>)
00881       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00882                   _ForwardIterator2>)
00883       __glibcxx_function_requires(_ConvertibleConcept<
00884         typename iterator_traits<_ForwardIterator1>::value_type,
00885         typename iterator_traits<_ForwardIterator2>::value_type>)
00886       __glibcxx_function_requires(_ConvertibleConcept<
00887         typename iterator_traits<_ForwardIterator2>::value_type,
00888         typename iterator_traits<_ForwardIterator1>::value_type>)
00889       __glibcxx_requires_valid_range(__first1, __last1);
00890 
00891       for ( ; __first1 != __last1; ++__first1, ++__first2)
00892     std::iter_swap(__first1, __first2);
00893       return __first2;
00894     }
00895 
00911   template<typename _InputIterator, typename _OutputIterator,
00912        typename _UnaryOperation>
00913     _OutputIterator
00914     transform(_InputIterator __first, _InputIterator __last,
00915           _OutputIterator __result, _UnaryOperation __unary_op)
00916     {
00917       // concept requirements
00918       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00919       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00920             // "the type returned by a _UnaryOperation"
00921             __typeof__(__unary_op(*__first))>)
00922       __glibcxx_requires_valid_range(__first, __last);
00923 
00924       for ( ; __first != __last; ++__first, ++__result)
00925     *__result = __unary_op(*__first);
00926       return __result;
00927     }
00928 
00946   template<typename _InputIterator1, typename _InputIterator2,
00947        typename _OutputIterator, typename _BinaryOperation>
00948     _OutputIterator
00949     transform(_InputIterator1 __first1, _InputIterator1 __last1,
00950           _InputIterator2 __first2, _OutputIterator __result,
00951           _BinaryOperation __binary_op)
00952     {
00953       // concept requirements
00954       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00955       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00956       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00957             // "the type returned by a _BinaryOperation"
00958             __typeof__(__binary_op(*__first1,*__first2))>)
00959       __glibcxx_requires_valid_range(__first1, __last1);
00960 
00961       for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
00962     *__result = __binary_op(*__first1, *__first2);
00963       return __result;
00964     }
00965 
00978   template<typename _ForwardIterator, typename _Tp>
00979     void
00980     replace(_ForwardIterator __first, _ForwardIterator __last,
00981         const _Tp& __old_value, const _Tp& __new_value)
00982     {
00983       // concept requirements
00984       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00985                   _ForwardIterator>)
00986       __glibcxx_function_requires(_EqualOpConcept<
00987         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
00988       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
00989         typename iterator_traits<_ForwardIterator>::value_type>)
00990       __glibcxx_requires_valid_range(__first, __last);
00991 
00992       for ( ; __first != __last; ++__first)
00993     if (*__first == __old_value)
00994       *__first = __new_value;
00995     }
00996 
01009   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
01010     void
01011     replace_if(_ForwardIterator __first, _ForwardIterator __last,
01012            _Predicate __pred, const _Tp& __new_value)
01013     {
01014       // concept requirements
01015       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01016                   _ForwardIterator>)
01017       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
01018         typename iterator_traits<_ForwardIterator>::value_type>)
01019       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01020         typename iterator_traits<_ForwardIterator>::value_type>)
01021       __glibcxx_requires_valid_range(__first, __last);
01022 
01023       for ( ; __first != __last; ++__first)
01024     if (__pred(*__first))
01025       *__first = __new_value;
01026     }
01027 
01042   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
01043     _OutputIterator
01044     replace_copy(_InputIterator __first, _InputIterator __last,
01045          _OutputIterator __result,
01046          const _Tp& __old_value, const _Tp& __new_value)
01047     {
01048       // concept requirements
01049       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01050       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01051         typename iterator_traits<_InputIterator>::value_type>)
01052       __glibcxx_function_requires(_EqualOpConcept<
01053         typename iterator_traits<_InputIterator>::value_type, _Tp>)
01054       __glibcxx_requires_valid_range(__first, __last);
01055 
01056       for ( ; __first != __last; ++__first, ++__result)
01057     if (*__first == __old_value)
01058       *__result = __new_value;
01059     else
01060       *__result = *__first;
01061       return __result;
01062     }
01063 
01078   template<typename _InputIterator, typename _OutputIterator,
01079        typename _Predicate, typename _Tp>
01080     _OutputIterator
01081     replace_copy_if(_InputIterator __first, _InputIterator __last,
01082             _OutputIterator __result,
01083             _Predicate __pred, const _Tp& __new_value)
01084     {
01085       // concept requirements
01086       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01087       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01088         typename iterator_traits<_InputIterator>::value_type>)
01089       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01090         typename iterator_traits<_InputIterator>::value_type>)
01091       __glibcxx_requires_valid_range(__first, __last);
01092 
01093       for ( ; __first != __last; ++__first, ++__result)
01094     if (__pred(*__first))
01095       *__result = __new_value;
01096     else
01097       *__result = *__first;
01098       return __result;
01099     }
01100 
01112   template<typename _ForwardIterator, typename _Generator>
01113     void
01114     generate(_ForwardIterator __first, _ForwardIterator __last,
01115          _Generator __gen)
01116     {
01117       // concept requirements
01118       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
01119       __glibcxx_function_requires(_GeneratorConcept<_Generator,
01120         typename iterator_traits<_ForwardIterator>::value_type>)
01121       __glibcxx_requires_valid_range(__first, __last);
01122 
01123       for ( ; __first != __last; ++__first)
01124     *__first = __gen();
01125     }
01126 
01138   template<typename _OutputIterator, typename _Size, typename _Generator>
01139     _OutputIterator
01140     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
01141     {
01142       // concept requirements
01143       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01144             // "the type returned by a _Generator"
01145             __typeof__(__gen())>)
01146 
01147       for ( ; __n > 0; --__n, ++__first)
01148     *__first = __gen();
01149       return __first;
01150     }
01151 
01165   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
01166     _OutputIterator
01167     remove_copy(_InputIterator __first, _InputIterator __last,
01168         _OutputIterator __result, const _Tp& __value)
01169     {
01170       // concept requirements
01171       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01172       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01173         typename iterator_traits<_InputIterator>::value_type>)
01174       __glibcxx_function_requires(_EqualOpConcept<
01175         typename iterator_traits<_InputIterator>::value_type, _Tp>)
01176       __glibcxx_requires_valid_range(__first, __last);
01177 
01178       for ( ; __first != __last; ++__first)
01179     if (!(*__first == __value))
01180       {
01181         *__result = *__first;
01182         ++__result;
01183       }
01184       return __result;
01185     }
01186 
01201   template<typename _InputIterator, typename _OutputIterator,
01202        typename _Predicate>
01203     _OutputIterator
01204     remove_copy_if(_InputIterator __first, _InputIterator __last,
01205            _OutputIterator __result, _Predicate __pred)
01206     {
01207       // concept requirements
01208       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01209       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01210         typename iterator_traits<_InputIterator>::value_type>)
01211       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01212         typename iterator_traits<_InputIterator>::value_type>)
01213       __glibcxx_requires_valid_range(__first, __last);
01214 
01215       for ( ; __first != __last; ++__first)
01216     if (!__pred(*__first))
01217       {
01218         *__result = *__first;
01219         ++__result;
01220       }
01221       return __result;
01222     }
01223 
01240   template<typename _ForwardIterator, typename _Tp>
01241     _ForwardIterator
01242     remove(_ForwardIterator __first, _ForwardIterator __last,
01243        const _Tp& __value)
01244     {
01245       // concept requirements
01246       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01247                   _ForwardIterator>)
01248       __glibcxx_function_requires(_EqualOpConcept<
01249         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
01250       __glibcxx_requires_valid_range(__first, __last);
01251 
01252       __first = std::find(__first, __last, __value);
01253       _ForwardIterator __i = __first;
01254       return __first == __last ? __first
01255                    : std::remove_copy(++__i, __last,
01256                           __first, __value);
01257     }
01258 
01275   template<typename _ForwardIterator, typename _Predicate>
01276     _ForwardIterator
01277     remove_if(_ForwardIterator __first, _ForwardIterator __last,
01278           _Predicate __pred)
01279     {
01280       // concept requirements
01281       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01282                   _ForwardIterator>)
01283       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01284         typename iterator_traits<_ForwardIterator>::value_type>)
01285       __glibcxx_requires_valid_range(__first, __last);
01286 
01287       __first = std::find_if(__first, __last, __pred);
01288       _ForwardIterator __i = __first;
01289       return __first == __last ? __first
01290                    : std::remove_copy_if(++__i, __last,
01291                              __first, __pred);
01292     }
01293 
01301   template<typename _InputIterator, typename _OutputIterator>
01302     _OutputIterator
01303     __unique_copy(_InputIterator __first, _InputIterator __last,
01304           _OutputIterator __result,
01305           output_iterator_tag)
01306     {
01307       // concept requirements -- taken care of in dispatching function
01308       typename iterator_traits<_InputIterator>::value_type __value = *__first;
01309       *__result = __value;
01310       while (++__first != __last)
01311     if (!(__value == *__first))
01312       {
01313         __value = *__first;
01314         *++__result = __value;
01315       }
01316       return ++__result;
01317     }
01318 
01326   template<typename _InputIterator, typename _ForwardIterator>
01327     _ForwardIterator
01328     __unique_copy(_InputIterator __first, _InputIterator __last,
01329           _ForwardIterator __result,
01330           forward_iterator_tag)
01331     {
01332       // concept requirements -- taken care of in dispatching function
01333       *__result = *__first;
01334       while (++__first != __last)
01335     if (!(*__result == *__first))
01336       *++__result = *__first;
01337       return ++__result;
01338     }
01339 
01348   template<typename _InputIterator, typename _OutputIterator,
01349        typename _BinaryPredicate>
01350     _OutputIterator
01351     __unique_copy(_InputIterator __first, _InputIterator __last,
01352           _OutputIterator __result,
01353           _BinaryPredicate __binary_pred,
01354           output_iterator_tag)
01355     {
01356       // concept requirements -- iterators already checked
01357       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01358       typename iterator_traits<_InputIterator>::value_type,
01359       typename iterator_traits<_InputIterator>::value_type>)
01360 
01361       typename iterator_traits<_InputIterator>::value_type __value = *__first;
01362       *__result = __value;
01363       while (++__first != __last)
01364     if (!__binary_pred(__value, *__first))
01365       {
01366         __value = *__first;
01367         *++__result = __value;
01368       }
01369       return ++__result;
01370     }
01371 
01380   template<typename _InputIterator, typename _ForwardIterator,
01381        typename _BinaryPredicate>
01382     _ForwardIterator
01383     __unique_copy(_InputIterator __first, _InputIterator __last,
01384           _ForwardIterator __result,
01385           _BinaryPredicate __binary_pred,
01386           forward_iterator_tag)
01387     {
01388       // concept requirements -- iterators already checked
01389       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01390         typename iterator_traits<_ForwardIterator>::value_type,
01391         typename iterator_traits<_InputIterator>::value_type>)
01392 
01393       *__result = *__first;
01394       while (++__first != __last)
01395     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
01396       return ++__result;
01397     }
01398 
01412   template<typename _InputIterator, typename _OutputIterator>
01413     inline _OutputIterator
01414     unique_copy(_InputIterator __first, _InputIterator __last,
01415         _OutputIterator __result)
01416     {
01417       // concept requirements
01418       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01419       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01420         typename iterator_traits<_InputIterator>::value_type>)
01421       __glibcxx_function_requires(_EqualityComparableConcept<
01422         typename iterator_traits<_InputIterator>::value_type>)
01423       __glibcxx_requires_valid_range(__first, __last);
01424 
01425       typedef typename iterator_traits<_OutputIterator>::iterator_category
01426     _IterType;
01427 
01428       if (__first == __last) return __result;
01429       return std::__unique_copy(__first, __last, __result, _IterType());
01430     }
01431 
01447   template<typename _InputIterator, typename _OutputIterator,
01448        typename _BinaryPredicate>
01449     inline _OutputIterator
01450     unique_copy(_InputIterator __first, _InputIterator __last,
01451         _OutputIterator __result,
01452         _BinaryPredicate __binary_pred)
01453     {
01454       // concept requirements -- predicates checked later
01455       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01456       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01457         typename iterator_traits<_InputIterator>::value_type>)
01458       __glibcxx_requires_valid_range(__first, __last);
01459 
01460       typedef typename iterator_traits<_OutputIterator>::iterator_category
01461     _IterType;
01462 
01463       if (__first == __last) return __result;
01464       return std::__unique_copy(__first, __last, __result,
01465                 __binary_pred, _IterType());
01466     }
01467 
01481   template<typename _ForwardIterator>
01482     _ForwardIterator
01483     unique(_ForwardIterator __first, _ForwardIterator __last)
01484     {
01485       // concept requirements
01486       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01487                   _ForwardIterator>)
01488       __glibcxx_function_requires(_EqualityComparableConcept<
01489              typename iterator_traits<_ForwardIterator>::value_type>)
01490       __glibcxx_requires_valid_range(__first, __last);
01491 
01492       // Skip the beginning, if already unique.
01493       __first = std::adjacent_find(__first, __last);
01494       if (__first == __last)
01495     return __last;
01496 
01497       // Do the real copy work.
01498       _ForwardIterator __dest = __first;
01499       ++__first;
01500       while (++__first != __last)
01501     if (!(*__dest == *__first))
01502       *++__dest = *__first;
01503       return ++__dest;
01504     }
01505 
01520   template<typename _ForwardIterator, typename _BinaryPredicate>
01521     _ForwardIterator
01522     unique(_ForwardIterator __first, _ForwardIterator __last,
01523            _BinaryPredicate __binary_pred)
01524     {
01525       // concept requirements
01526       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01527                   _ForwardIterator>)
01528       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01529         typename iterator_traits<_ForwardIterator>::value_type,
01530         typename iterator_traits<_ForwardIterator>::value_type>)
01531       __glibcxx_requires_valid_range(__first, __last);
01532 
01533       // Skip the beginning, if already unique.
01534       __first = std::adjacent_find(__first, __last, __binary_pred);
01535       if (__first == __last)
01536     return __last;
01537 
01538       // Do the real copy work.
01539       _ForwardIterator __dest = __first;
01540       ++__first;
01541       while (++__first != __last)
01542     if (!__binary_pred(*__dest, *__first))
01543       *++__dest = *__first;
01544       return ++__dest;
01545     }
01546 
01554   template<typename _BidirectionalIterator>
01555     void
01556     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
01557           bidirectional_iterator_tag)
01558     {
01559       while (true)
01560     if (__first == __last || __first == --__last)
01561       return;
01562     else
01563       {
01564         std::iter_swap(__first, __last);
01565         ++__first;
01566       }
01567     }
01568 
01576   template<typename _RandomAccessIterator>
01577     void
01578     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
01579           random_access_iterator_tag)
01580     {
01581       if (__first == __last)
01582     return;
01583       --__last;
01584       while (__first < __last)
01585     {
01586       std::iter_swap(__first, __last);
01587       ++__first;
01588       --__last;
01589     }
01590     }
01591 
01603   template<typename _BidirectionalIterator>
01604     inline void
01605     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
01606     {
01607       // concept requirements
01608       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01609                   _BidirectionalIterator>)
01610       __glibcxx_requires_valid_range(__first, __last);
01611       std::__reverse(__first, __last, std::__iterator_category(__first));
01612     }
01613 
01629   template<typename _BidirectionalIterator, typename _OutputIterator>
01630     _OutputIterator
01631     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
01632                  _OutputIterator __result)
01633     {
01634       // concept requirements
01635       __glibcxx_function_requires(_BidirectionalIteratorConcept<
01636                   _BidirectionalIterator>)
01637       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01638         typename iterator_traits<_BidirectionalIterator>::value_type>)
01639       __glibcxx_requires_valid_range(__first, __last);
01640 
01641       while (__first != __last)
01642     {
01643       --__last;
01644       *__result = *__last;
01645       ++__result;
01646     }
01647       return __result;
01648     }
01649 
01650 
01657   template<typename _EuclideanRingElement>
01658     _EuclideanRingElement
01659     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
01660     {
01661       while (__n != 0)
01662     {
01663       _EuclideanRingElement __t = __m % __n;
01664       __m = __n;
01665       __n = __t;
01666     }
01667       return __m;
01668     }
01669 
01675   template<typename _ForwardIterator>
01676     void
01677     __rotate(_ForwardIterator __first,
01678          _ForwardIterator __middle,
01679          _ForwardIterator __last,
01680          forward_iterator_tag)
01681     {
01682       if (__first == __middle || __last  == __middle)
01683     return;
01684 
01685       _ForwardIterator __first2 = __middle;
01686       do
01687     {
01688       swap(*__first, *__first2);
01689       ++__first;
01690       ++__first2;
01691       if (__first == __middle)
01692         __middle = __first2;
01693     }
01694       while (__first2 != __last);
01695 
01696       __first2 = __middle;
01697 
01698       while (__first2 != __last)
01699     {
01700       swap(*__first, *__first2);
01701       ++__first;
01702       ++__first2;
01703       if (__first == __middle)
01704         __middle = __first2;
01705       else if (__first2 == __last)
01706         __first2 = __middle;
01707     }
01708     }
01709 
01715   template<typename _BidirectionalIterator>
01716     void
01717     __rotate(_BidirectionalIterator __first,
01718          _BidirectionalIterator __middle,
01719          _BidirectionalIterator __last,
01720           bidirectional_iterator_tag)
01721     {
01722       // concept requirements
01723       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01724                   _BidirectionalIterator>)
01725 
01726       if (__first == __middle || __last  == __middle)
01727     return;
01728 
01729       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01730       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01731 
01732       while (__first != __middle && __middle != __last)
01733     {
01734       swap(*__first, *--__last);
01735       ++__first;
01736     }
01737 
01738       if (__first == __middle)
01739     std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01740       else
01741     std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01742     }
01743 
01749   template<typename _RandomAccessIterator>
01750     void
01751     __rotate(_RandomAccessIterator __first,
01752          _RandomAccessIterator __middle,
01753          _RandomAccessIterator __last,
01754          random_access_iterator_tag)
01755     {
01756       // concept requirements
01757       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01758                   _RandomAccessIterator>)
01759 
01760       if (__first == __middle || __last  == __middle)
01761     return;
01762 
01763       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01764     _Distance;
01765       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01766     _ValueType;
01767 
01768       const _Distance __n = __last   - __first;
01769       const _Distance __k = __middle - __first;
01770       const _Distance __l = __n - __k;
01771 
01772       if (__k == __l)
01773     {
01774       std::swap_ranges(__first, __middle, __middle);
01775       return;
01776     }
01777 
01778       const _Distance __d = __gcd(__n, __k);
01779 
01780       for (_Distance __i = 0; __i < __d; __i++)
01781     {
01782       _ValueType __tmp = *__first;
01783       _RandomAccessIterator __p = __first;
01784 
01785       if (__k < __l)
01786         {
01787           for (_Distance __j = 0; __j < __l / __d; __j++)
01788         {
01789           if (__p > __first + __l)
01790             {
01791               *__p = *(__p - __l);
01792               __p -= __l;
01793             }
01794 
01795           *__p = *(__p + __k);
01796           __p += __k;
01797         }
01798         }
01799       else
01800         {
01801           for (_Distance __j = 0; __j < __k / __d - 1; __j ++)
01802         {
01803           if (__p < __last - __k)
01804             {
01805               *__p = *(__p + __k);
01806               __p += __k;
01807             }
01808           *__p = * (__p - __l);
01809           __p -= __l;
01810         }
01811         }
01812 
01813       *__p = __tmp;
01814       ++__first;
01815     }
01816     }
01817 
01836   template<typename _ForwardIterator>
01837     inline void
01838     rotate(_ForwardIterator __first, _ForwardIterator __middle,
01839        _ForwardIterator __last)
01840     {
01841       // concept requirements
01842       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01843                   _ForwardIterator>)
01844       __glibcxx_requires_valid_range(__first, __middle);
01845       __glibcxx_requires_valid_range(__middle, __last);
01846 
01847       typedef typename iterator_traits<_ForwardIterator>::iterator_category
01848     _IterType;
01849       std::__rotate(__first, __middle, __last, _IterType());
01850     }
01851 
01869   template<typename _ForwardIterator, typename _OutputIterator>
01870     _OutputIterator
01871     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
01872                 _ForwardIterator __last, _OutputIterator __result)
01873     {
01874       // concept requirements
01875       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
01876       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01877         typename iterator_traits<_ForwardIterator>::value_type>)
01878       __glibcxx_requires_valid_range(__first, __middle);
01879       __glibcxx_requires_valid_range(__middle, __last);
01880 
01881       return std::copy(__first, __middle,
01882                        std::copy(__middle, __last, __result));
01883     }
01884 
01895   template<typename _RandomAccessIterator>
01896     inline void
01897     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
01898     {
01899       // concept requirements
01900       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01901         _RandomAccessIterator>)
01902       __glibcxx_requires_valid_range(__first, __last);
01903 
01904       if (__first != __last)
01905     for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
01906       std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
01907     }
01908 
01922   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
01923     void
01924     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
01925            _RandomNumberGenerator& __rand)
01926     {
01927       // concept requirements
01928       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01929         _RandomAccessIterator>)
01930       __glibcxx_requires_valid_range(__first, __last);
01931 
01932       if (__first == __last)
01933     return;
01934       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
01935     std::iter_swap(__i, __first + __rand((__i - __first) + 1));
01936     }
01937 
01938 
01944   template<typename _ForwardIterator, typename _Predicate>
01945     _ForwardIterator
01946     __partition(_ForwardIterator __first, _ForwardIterator __last,
01947         _Predicate __pred,
01948         forward_iterator_tag)
01949     {
01950       if (__first == __last)
01951     return __first;
01952 
01953       while (__pred(*__first))
01954     if (++__first == __last)
01955       return __first;
01956 
01957       _ForwardIterator __next = __first;
01958 
01959       while (++__next != __last)
01960     if (__pred(*__next))
01961       {
01962         swap(*__first, *__next);
01963         ++__first;
01964       }
01965 
01966       return __first;
01967     }
01968 
01974   template<typename _BidirectionalIterator, typename _Predicate>
01975     _BidirectionalIterator
01976     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
01977         _Predicate __pred,
01978         bidirectional_iterator_tag)
01979     {
01980       while (true)
01981     {
01982       while (true)
01983         if (__first == __last)
01984           return __first;
01985         else if (__pred(*__first))
01986           ++__first;
01987         else
01988           break;
01989       --__last;
01990       while (true)
01991         if (__first == __last)
01992           return __first;
01993         else if (!__pred(*__last))
01994           --__last;
01995         else
01996           break;
01997       std::iter_swap(__first, __last);
01998       ++__first;
01999     }
02000     }
02001 
02016   template<typename _ForwardIterator, typename _Predicate>
02017     inline _ForwardIterator
02018     partition(_ForwardIterator __first, _ForwardIterator __last,
02019           _Predicate   __pred)
02020     {
02021       // concept requirements
02022       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
02023                   _ForwardIterator>)
02024       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
02025         typename iterator_traits<_ForwardIterator>::value_type>)
02026       __glibcxx_requires_valid_range(__first, __last);
02027 
02028       return std::__partition(__first, __last, __pred,
02029                   std::__iterator_category(__first));
02030     }
02031 
02032 
02038   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
02039     _ForwardIterator
02040     __inplace_stable_partition(_ForwardIterator __first,
02041                    _ForwardIterator __last,
02042                    _Predicate __pred, _Distance __len)
02043     {
02044       if (__len == 1)
02045     return __pred(*__first) ? __last : __first;
02046       _ForwardIterator __middle = __first;
02047       std::advance(__middle, __len / 2);
02048       _ForwardIterator __begin = std::__inplace_stable_partition(__first,
02049                                  __middle,
02050                                  __pred,
02051                                  __len / 2);
02052       _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
02053                                    __pred,
02054                                    __len
02055                                    - __len / 2);
02056       std::rotate(__begin, __middle, __end);
02057       std::advance(__begin, std::distance(__middle, __end));
02058       return __begin;
02059     }
02060 
02066   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
02067        typename _Distance>
02068     _ForwardIterator
02069     __stable_partition_adaptive(_ForwardIterator __first,
02070                 _ForwardIterator __last,
02071                 _Predicate __pred, _Distance __len,
02072                 _Pointer __buffer,
02073                 _Distance __buffer_size)
02074     {
02075       if (__len <= __buffer_size)
02076     {
02077       _ForwardIterator __result1 = __first;
02078       _Pointer __result2 = __buffer;
02079       for ( ; __first != __last ; ++__first)
02080         if (__pred(*__first))
02081           {
02082         *__result1 = *__first;
02083         ++__result1;
02084           }
02085         else
02086           {
02087         *__result2 = *__first;
02088         ++__result2;
02089           }
02090       std::copy(__buffer, __result2, __result1);
02091       return __result1;
02092     }
02093       else
02094     {
02095       _ForwardIterator __middle = __first;
02096       std::advance(__middle, __len / 2);
02097       _ForwardIterator __begin =
02098         std::__stable_partition_adaptive(__first, __middle, __pred,
02099                          __len / 2, __buffer,
02100                          __buffer_size);
02101       _ForwardIterator __end =
02102         std::__stable_partition_adaptive(__middle, __last, __pred,
02103                          __len - __len / 2,
02104                          __buffer, __buffer_size);
02105       std::rotate(__begin, __middle, __end);
02106       std::advance(__begin, std::distance(__middle, __end));
02107       return __begin;
02108     }
02109     }
02110 
02127   template<typename _ForwardIterator, typename _Predicate>
02128     _ForwardIterator
02129     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
02130              _Predicate __pred)
02131     {
02132       // concept requirements
02133       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
02134                   _ForwardIterator>)
02135       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
02136         typename iterator_traits<_ForwardIterator>::value_type>)
02137       __glibcxx_requires_valid_range(__first, __last);
02138 
02139       if (__first == __last)
02140     return __first;
02141       else
02142     {
02143       typedef typename iterator_traits<_ForwardIterator>::value_type
02144         _ValueType;
02145       typedef typename iterator_traits<_ForwardIterator>::difference_type
02146         _DistanceType;
02147 
02148       _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
02149                                 __last);
02150     if (__buf.size() > 0)
02151       return
02152         std::__stable_partition_adaptive(__first, __last, __pred,
02153                       _DistanceType(__buf.requested_size()),
02154                       __buf.begin(), __buf.size());
02155     else
02156       return
02157         std::__inplace_stable_partition(__first, __last, __pred,
02158                      _DistanceType(__buf.requested_size()));
02159     }
02160     }
02161 
02167   template<typename _RandomAccessIterator, typename _Tp>
02168     _RandomAccessIterator
02169     __unguarded_partition(_RandomAccessIterator __first,
02170               _RandomAccessIterator __last, _Tp __pivot)
02171     {
02172       while (true)
02173     {
02174       while (*__first < __pivot)
02175         ++__first;
02176       --__last;
02177       while (__pivot < *__last)
02178         --__last;
02179       if (!(__first < __last))
02180         return __first;
02181       std::iter_swap(__first, __last);
02182       ++__first;
02183     }
02184     }
02185 
02191   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
02192     _RandomAccessIterator
02193     __unguarded_partition(_RandomAccessIterator __first,
02194               _RandomAccessIterator __last,
02195               _Tp __pivot, _Compare __comp)
02196     {
02197       while (true)
02198     {
02199       while (__comp(*__first, __pivot))
02200         ++__first;
02201       --__last;
02202       while (__comp(__pivot, *__last))
02203         --__last;
02204       if (!(__first < __last))
02205         return __first;
02206       std::iter_swap(__first, __last);
02207       ++__first;
02208     }
02209     }
02210 
02217   enum { _S_threshold = 16 };
02218 
02224   template<typename _RandomAccessIterator, typename _Tp>
02225     void
02226     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
02227     {
02228       _RandomAccessIterator __next = __last;
02229       --__next;
02230       while (__val < *__next)
02231     {
02232       *__last = *__next;
02233       __last = __next;
02234       --__next;
02235     }
02236       *__last = __val;
02237     }
02238 
02244   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
02245     void
02246     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
02247                   _Compare __comp)
02248     {
02249       _RandomAccessIterator __next = __last;
02250       --__next;
02251       while (__comp(__val, *__next))
02252     {
02253       *__last = *__next;
02254       __last = __next;
02255       --__next;
02256     }
02257       *__last = __val;
02258     }
02259 
02265   template<typename _RandomAccessIterator>
02266     void
02267     __insertion_sort(_RandomAccessIterator __first,
02268              _RandomAccessIterator __last)
02269     {
02270       if (__first == __last)
02271     return;
02272 
02273       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02274     {
02275       typename iterator_traits<_RandomAccessIterator>::value_type
02276         __val = *__i;
02277       if (__val < *__first)
02278         {
02279           std::copy_backward(__first, __i, __i + 1);
02280           *__first = __val;
02281         }
02282       else
02283         std::__unguarded_linear_insert(__i, __val);
02284     }
02285     }
02286 
02292   template<typename _RandomAccessIterator, typename _Compare>
02293     void
02294     __insertion_sort(_RandomAccessIterator __first,
02295              _RandomAccessIterator __last, _Compare __comp)
02296     {
02297       if (__first == __last) return;
02298 
02299       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02300     {
02301       typename iterator_traits<_RandomAccessIterator>::value_type
02302         __val = *__i;
02303       if (__comp(__val, *__first))
02304         {
02305           std::copy_backward(__first, __i, __i + 1);
02306           *__first = __val;
02307         }
02308       else
02309         std::__unguarded_linear_insert(__i, __val, __comp);
02310     }
02311     }
02312 
02318   template<typename _RandomAccessIterator>
02319     inline void
02320     __unguarded_insertion_sort(_RandomAccessIterator __first,
02321                    _RandomAccessIterator __last)
02322     {
02323       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02324     _ValueType;
02325 
02326       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02327     std::__unguarded_linear_insert(__i, _ValueType(*__i));
02328     }
02329 
02335   template<typename _RandomAccessIterator, typename _Compare>
02336     inline void
02337     __unguarded_insertion_sort(_RandomAccessIterator __first,
02338                    _RandomAccessIterator __last, _Compare __comp)
02339     {
02340       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02341     _ValueType;
02342 
02343       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02344     std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
02345     }
02346 
02352   template<typename _RandomAccessIterator>
02353     void
02354     __final_insertion_sort(_RandomAccessIterator __first,
02355                _RandomAccessIterator __last)
02356     {
02357       if (__last - __first > int(_S_threshold))
02358     {
02359       std::__insertion_sort(__first, __first + int(_S_threshold));
02360       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
02361     }
02362       else
02363     std::__insertion_sort(__first, __last);
02364     }
02365 
02371   template<typename _RandomAccessIterator, typename _Compare>
02372     void
02373     __final_insertion_sort(_RandomAccessIterator __first,
02374                _RandomAccessIterator __last, _Compare __comp)
02375     {
02376       if (__last - __first > int(_S_threshold))
02377     {
02378       std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
02379       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
02380                       __comp);
02381     }
02382       else
02383     std::__insertion_sort(__first, __last, __comp);
02384     }
02385 
02391   template<typename _Size>
02392     inline _Size
02393     __lg(_Size __n)
02394     {
02395       _Size __k;
02396       for (__k = 0; __n != 1; __n >>= 1)
02397     ++__k;
02398       return __k;
02399     }
02400 
02416   template<typename _RandomAccessIterator>
02417     void
02418     partial_sort(_RandomAccessIterator __first,
02419          _RandomAccessIterator __middle,
02420          _RandomAccessIterator __last)
02421     {
02422       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02423     _ValueType;
02424 
02425       // concept requirements
02426       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02427         _RandomAccessIterator>)
02428       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
02429       __glibcxx_requires_valid_range(__first, __middle);
02430       __glibcxx_requires_valid_range(__middle, __last);
02431 
02432       std::make_heap(__first, __middle);
02433       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
02434     if (*__i < *__first)
02435       std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
02436       std::sort_heap(__first, __middle);
02437     }
02438 
02457   template<typename _RandomAccessIterator, typename _Compare>
02458     void
02459     partial_sort(_RandomAccessIterator __first,
02460          _RandomAccessIterator __middle,
02461          _RandomAccessIterator __last,
02462          _Compare __comp)
02463     {
02464       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02465     _ValueType;
02466 
02467       // concept requirements
02468       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02469         _RandomAccessIterator>)
02470       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02471                   _ValueType, _ValueType>)
02472       __glibcxx_requires_valid_range(__first, __middle);
02473       __glibcxx_requires_valid_range(__middle, __last);
02474 
02475       std::make_heap(__first, __middle, __comp);
02476       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
02477     if (__comp(*__i, *__first))
02478       std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
02479       std::sort_heap(__first, __middle, __comp);
02480     }
02481 
02499   template<typename _InputIterator, typename _RandomAccessIterator>
02500     _RandomAccessIterator
02501     partial_sort_copy(_InputIterator __first, _InputIterator __last,
02502               _RandomAccessIterator __result_first,
02503               _RandomAccessIterator __result_last)
02504     {
02505       typedef typename iterator_traits<_InputIterator>::value_type
02506     _InputValueType;
02507       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02508     _OutputValueType;
02509       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
02510     _DistanceType;
02511 
02512       // concept requirements
02513       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
02514       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
02515                   _OutputValueType>)
02516       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
02517       __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>)
02518       __glibcxx_requires_valid_range(__first, __last);
02519       __glibcxx_requires_valid_range(__result_first, __result_last);
02520 
02521       if (__result_first == __result_last)
02522     return __result_last;
02523       _RandomAccessIterator __result_real_last = __result_first;
02524       while(__first != __last && __result_real_last != __result_last)
02525     {
02526       *__result_real_last = *__first;
02527       ++__result_real_last;
02528       ++__first;
02529     }
02530       std::make_heap(__result_first, __result_real_last);
02531       while (__first != __last)
02532     {
02533       if (*__first < *__result_first)
02534         std::__adjust_heap(__result_first, _DistanceType(0),
02535                    _DistanceType(__result_real_last
02536                          - __result_first),
02537                    _InputValueType(*__first));
02538       ++__first;
02539     }
02540       std::sort_heap(__result_first, __result_real_last);
02541       return __result_real_last;
02542     }
02543 
02563   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
02564     _RandomAccessIterator
02565     partial_sort_copy(_InputIterator __first, _InputIterator __last,
02566               _RandomAccessIterator __result_first,
02567               _RandomAccessIterator __result_last,
02568               _Compare __comp)
02569     {
02570       typedef typename iterator_traits<_InputIterator>::value_type
02571     _InputValueType;
02572       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02573     _OutputValueType;
02574       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
02575     _DistanceType;
02576 
02577       // concept requirements
02578       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
02579       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02580                   _RandomAccessIterator>)
02581       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
02582                   _OutputValueType>)
02583       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02584                   _OutputValueType, _OutputValueType>)
02585       __glibcxx_requires_valid_range(__first, __last);
02586       __glibcxx_requires_valid_range(__result_first, __result_last);
02587 
02588       if (__result_first == __result_last)
02589     return __result_last;
02590       _RandomAccessIterator __result_real_last = __result_first;
02591       while(__first != __last && __result_real_last != __result_last)
02592     {
02593       *__result_real_last = *__first;
02594       ++__result_real_last;
02595       ++__first;
02596     }
02597       std::make_heap(__result_first, __result_real_last, __comp);
02598       while (__first != __last)
02599     {
02600       if (__comp(*__first, *__result_first))
02601         std::__adjust_heap(__result_first, _DistanceType(0),
02602                    _DistanceType(__result_real_last
02603                          - __result_first),
02604                    _InputValueType(*__first),
02605                    __comp);
02606       ++__first;
02607     }
02608       std::sort_heap(__result_first, __result_real_last, __comp);
02609       return __result_real_last;
02610     }
02611 
02617   template<typename _RandomAccessIterator, typename _Size>
02618     void
02619     __introsort_loop(_RandomAccessIterator __first,
02620              _RandomAccessIterator __last,
02621              _Size __depth_limit)
02622     {
02623       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02624     _ValueType;
02625 
02626       while (__last - __first > int(_S_threshold))
02627     {
02628       if (__depth_limit == 0)
02629         {
02630           std::partial_sort(__first, __last, __last);
02631           return;
02632         }
02633       --__depth_limit;
02634       _RandomAccessIterator __cut =
02635         std::__unguarded_partition(__first, __last,
02636                        _ValueType(std::__median(*__first,
02637                                 *(__first
02638                                   + (__last
02639                                      - __first)
02640                                   / 2),
02641                                 *(__last
02642                                   - 1))));
02643       std::__introsort_loop(__cut, __last, __depth_limit);
02644       __last = __cut;
02645     }
02646     }
02647 
02653   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02654     void
02655     __introsort_loop(_RandomAccessIterator __first,
02656              _RandomAccessIterator __last,
02657              _Size __depth_limit, _Compare __comp)
02658     {
02659       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02660     _ValueType;
02661 
02662       while (__last - __first > int(_S_threshold))
02663     {
02664       if (__depth_limit == 0)
02665         {
02666           std::partial_sort(__first, __last, __last, __comp);
02667           return;
02668         }
02669       --__depth_limit;
02670       _RandomAccessIterator __cut =
02671         std::__unguarded_partition(__first, __last,
02672                        _ValueType(std::__median(*__first,
02673                                 *(__first
02674                                   + (__last
02675                                      - __first)
02676                                   / 2),
02677                                 *(__last - 1),
02678                                 __comp)),
02679                        __comp);
02680       std::__introsort_loop(__cut, __last, __depth_limit, __comp);
02681       __last = __cut;
02682     }
02683     }
02684 
02698   template<typename _RandomAccessIterator>
02699     inline void
02700     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
02701     {
02702       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02703     _ValueType;
02704 
02705       // concept requirements
02706       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02707         _RandomAccessIterator>)
02708       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
02709       __glibcxx_requires_valid_range(__first, __last);
02710 
02711       if (__first != __last)
02712     {
02713       std::__introsort_loop(__first, __last, __lg(__last - __first) * 2);
02714       std::__final_insertion_sort(__first, __last);
02715     }
02716     }
02717 
02732   template<typename _RandomAccessIterator, typename _Compare>
02733     inline void
02734     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
02735      _Compare __comp)
02736     {
02737       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02738     _ValueType;
02739 
02740       // concept requirements
02741       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02742         _RandomAccessIterator>)
02743       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
02744                   _ValueType>)
02745       __glibcxx_requires_valid_range(__first, __last);
02746 
02747       if (__first != __last)
02748     {
02749       std::__introsort_loop(__first, __last, __lg(__last - __first) * 2,
02750                 __comp);
02751       std::__final_insertion_sort(__first, __last, __comp);
02752     }
02753     }
02754 
02765   template<typename _ForwardIterator, typename _Tp>
02766     _ForwardIterator
02767     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
02768         const _Tp& __val)
02769     {
02770       typedef typename iterator_traits<_ForwardIterator>::value_type
02771     _ValueType;
02772       typedef typename iterator_traits<_ForwardIterator>::difference_type
02773     _DistanceType;
02774 
02775       // concept requirements
02776       // Note that these are slightly stricter than those of the 4-argument
02777       // version, defined next.  The difference is in the strictness of the
02778       // comparison operations... so for looser checking, define your own
02779       // comparison function, as was intended.
02780       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02781       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02782       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
02783       __glibcxx_requires_partitioned(__first, __last, __val);
02784 
02785       _DistanceType __len = std::distance(__first, __last);
02786       _DistanceType __half;
02787       _ForwardIterator __middle;
02788 
02789       while (__len > 0)
02790     {
02791       __half = __len >> 1;
02792       __middle = __first;
02793       std::advance(__middle, __half);
02794       if (*__middle < __val)
02795         {
02796           __first = __middle;
02797           ++__first;
02798           __len = __len - __half - 1;
02799         }
02800       else
02801         __len = __half;
02802     }
02803       return __first;
02804     }
02805 
02820   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02821     _ForwardIterator
02822     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
02823         const _Tp& __val, _Compare __comp)
02824     {
02825       typedef typename iterator_traits<_ForwardIterator>::value_type
02826     _ValueType;
02827       typedef typename iterator_traits<_ForwardIterator>::difference_type
02828     _DistanceType;
02829 
02830       // concept requirements
02831       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02832       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02833                   _ValueType, _Tp>)
02834       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
02835 
02836       _DistanceType __len = std::distance(__first, __last);
02837       _DistanceType __half;
02838       _ForwardIterator __middle;
02839 
02840       while (__len > 0)
02841     {
02842       __half = __len >> 1;
02843       __middle = __first;
02844       std::advance(__middle, __half);
02845       if (__comp(*__middle, __val))
02846         {
02847           __first = __middle;
02848           ++__first;
02849           __len = __len - __half - 1;
02850         }
02851       else
02852         __len = __half;
02853     }
02854       return __first;
02855     }
02856 
02867   template<typename _ForwardIterator, typename _Tp>
02868     _ForwardIterator
02869     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02870         const _Tp& __val)
02871     {
02872       typedef typename iterator_traits<_ForwardIterator>::value_type
02873     _ValueType;
02874       typedef typename iterator_traits<_ForwardIterator>::difference_type
02875     _DistanceType;
02876 
02877       // concept requirements
02878       // See comments on lower_bound.
02879       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02880       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02881       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
02882       __glibcxx_requires_partitioned(__first, __last, __val);
02883 
02884       _DistanceType __len = std::distance(__first, __last);
02885       _DistanceType __half;
02886       _ForwardIterator __middle;
02887 
02888       while (__len > 0)
02889     {
02890       __half = __len >> 1;
02891       __middle = __first;
02892       std::advance(__middle, __half);
02893       if (__val < *__middle)
02894         __len = __half;
02895       else
02896         {
02897           __first = __middle;
02898           ++__first;
02899           __len = __len - __half - 1;
02900         }
02901     }
02902       return __first;
02903     }
02904 
02919   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02920     _ForwardIterator
02921     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02922         const _Tp& __val, _Compare __comp)
02923     {
02924       typedef typename iterator_traits<_ForwardIterator>::value_type
02925     _ValueType;
02926       typedef typename iterator_traits<_ForwardIterator>::difference_type
02927     _DistanceType;
02928 
02929       // concept requirements
02930       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02931       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02932                   _Tp, _ValueType>)
02933       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
02934 
02935       _DistanceType __len = std::distance(__first, __last);
02936       _DistanceType __half;
02937       _ForwardIterator __middle;
02938 
02939       while (__len > 0)
02940     {
02941       __half = __len >> 1;
02942       __middle = __first;
02943       std::advance(__middle, __half);
02944       if (__comp(__val, *__middle))
02945         __len = __half;
02946       else
02947         {
02948           __first = __middle;
02949           ++__first;
02950           __len = __len - __half - 1;
02951         }
02952     }
02953       return __first;
02954     }
02955 
02961   template<typename _BidirectionalIterator, typename _Distance>
02962     void
02963     __merge_without_buffer(_BidirectionalIterator __first,
02964                _BidirectionalIterator __middle,
02965                _BidirectionalIterator __last,
02966                _Distance __len1, _Distance __len2)
02967     {
02968       if (__len1 == 0 || __len2 == 0)
02969     return;
02970       if (__len1 + __len2 == 2)
02971     {
02972       if (*__middle < *__first)
02973         std::iter_swap(__first, __middle);
02974       return;
02975     }
02976       _BidirectionalIterator __first_cut = __first;
02977       _BidirectionalIterator __second_cut = __middle;
02978       _Distance __len11 = 0;
02979       _Distance __len22 = 0;
02980       if (__len1 > __len2)
02981     {
02982       __len11 = __len1 / 2;
02983       std::advance(__first_cut, __len11);
02984       __second_cut = std::lower_bound(__middle, __last, *__first_cut);
02985       __len22 = std::distance(__middle, __second_cut);
02986     }
02987       else
02988     {
02989       __len22 = __len2 / 2;
02990       std::advance(__second_cut, __len22);
02991       __first_cut = std::upper_bound(__first, __middle, *__second_cut);
02992       __len11 = std::distance(__first, __first_cut);
02993     }
02994       std::rotate(__first_cut, __middle, __second_cut);
02995       _BidirectionalIterator __new_middle = __first_cut;
02996       std::advance(__new_middle, std::distance(__middle, __second_cut));
02997       std::__merge_without_buffer(__first, __first_cut, __new_middle,
02998                   __len11, __len22);
02999       std::__merge_without_buffer(__new_middle, __second_cut, __last,
03000                   __len1 - __len11, __len2 - __len22);
03001     }
03002 
03008   template<typename _BidirectionalIterator, typename _Distance,
03009        typename _Compare>
03010     void
03011     __merge_without_buffer(_BidirectionalIterator __first,
03012                            _BidirectionalIterator __middle,
03013                _BidirectionalIterator __last,
03014                _Distance __len1, _Distance __len2,
03015                _Compare __comp)
03016     {
03017       if (__len1 == 0 || __len2 == 0)
03018     return;
03019       if (__len1 + __len2 == 2)
03020     {
03021       if (__comp(*__middle, *__first))
03022         std::iter_swap(__first, __middle);
03023       return;
03024     }
03025       _BidirectionalIterator __first_cut = __first;
03026       _BidirectionalIterator __second_cut = __middle;
03027       _Distance __len11 = 0;
03028       _Distance __len22 = 0;
03029       if (__len1 > __len2)
03030     {
03031       __len11 = __len1 / 2;
03032       std::advance(__first_cut, __len11);
03033       __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03034                       __comp);
03035       __len22 = std::distance(__middle, __second_cut);
03036     }
03037       else
03038     {
03039       __len22 = __len2 / 2;
03040       std::advance(__second_cut, __len22);
03041       __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03042                      __comp);
03043       __len11 = std::distance(__first, __first_cut);
03044     }
03045       std::rotate(__first_cut, __middle, __second_cut);
03046       _BidirectionalIterator __new_middle = __first_cut;
03047       std::advance(__new_middle, std::distance(__middle, __second_cut));
03048       std::__merge_without_buffer(__first, __first_cut, __new_middle,
03049                   __len11, __len22, __comp);
03050       std::__merge_without_buffer(__new_middle, __second_cut, __last,
03051                   __len1 - __len11, __len2 - __len22, __comp);
03052     }
03053 
03059   template<typename _RandomAccessIterator>
03060     void
03061     __inplace_stable_sort(_RandomAccessIterator __first,
03062               _RandomAccessIterator __last)
03063     {
03064       if (__last - __first < 15)
03065     {
03066       std::__insertion_sort(__first, __last);
03067       return;
03068     }
03069       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03070       std::__inplace_stable_sort(__first, __middle);
03071       std::__inplace_stable_sort(__middle, __last);
03072       std::__merge_without_buffer(__first, __middle, __last,
03073                   __middle - __first,
03074                   __last - __middle);
03075     }
03076 
03082   template<typename _RandomAccessIterator, typename _Compare>
03083     void
03084     __inplace_stable_sort(_RandomAccessIterator __first,
03085               _RandomAccessIterator __last, _Compare __comp)
03086     {
03087       if (__last - __first < 15)
03088     {
03089       std::__insertion_sort(__first, __last, __comp);
03090       return;
03091     }
03092       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03093       std::__inplace_stable_sort(__first, __middle, __comp);
03094       std::__inplace_stable_sort(__middle, __last, __comp);
03095       std::__merge_without_buffer(__first, __middle, __last,
03096                   __middle - __first,
03097                   __last - __middle,
03098                   __comp);
03099     }
03100 
03117   template<typename _InputIterator1, typename _InputIterator2,
03118        typename _OutputIterator>
03119     _OutputIterator
03120     merge(_InputIterator1 __first1, _InputIterator1 __last1,
03121       _InputIterator2 __first2, _InputIterator2 __last2,
03122       _OutputIterator __result)
03123     {
03124       // concept requirements
03125       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03126       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03127       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03128         typename iterator_traits<_InputIterator1>::value_type>)
03129       __glibcxx_function_requires(_SameTypeConcept<
03130         typename iterator_traits<_InputIterator1>::value_type,
03131         typename iterator_traits<_InputIterator2>::value_type>)
03132       __glibcxx_function_requires(_LessThanComparableConcept<
03133         typename iterator_traits<_InputIterator1>::value_type>)
03134       __glibcxx_requires_sorted(__first1, __last1);
03135       __glibcxx_requires_sorted(__first2, __last2);
03136 
03137       while (__first1 != __last1 && __first2 != __last2)
03138     {
03139       if (*__first2 < *__first1)
03140         {
03141           *__result = *__first2;
03142           ++__first2;
03143         }
03144       else
03145         {
03146           *__result = *__first1;
03147           ++__first1;
03148         }
03149       ++__result;
03150     }
03151       return std::copy(__first2, __last2, std::copy(__first1, __last1,
03152                             __result));
03153     }
03154 
03175   template<typename _InputIterator1, typename _InputIterator2,
03176        typename _OutputIterator, typename _Compare>
03177     _OutputIterator
03178     merge(_InputIterator1 __first1, _InputIterator1 __last1,
03179       _InputIterator2 __first2, _InputIterator2 __last2,
03180       _OutputIterator __result, _Compare __comp)
03181     {
03182       // concept requirements
03183       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03184       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03185       __glibcxx_function_requires(_SameTypeConcept<
03186         typename iterator_traits<_InputIterator1>::value_type,
03187         typename iterator_traits<_InputIterator2>::value_type>)
03188       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03189         typename iterator_traits<_InputIterator1>::value_type>)
03190       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03191         typename iterator_traits<_InputIterator1>::value_type,
03192         typename iterator_traits<_InputIterator2>::value_type>)
03193       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
03194       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
03195 
03196       while (__first1 != __last1 && __first2 != __last2)
03197     {
03198       if (__comp(*__first2, *__first1))
03199         {
03200           *__result = *__first2;
03201           ++__first2;
03202         }
03203       else
03204         {
03205           *__result = *__first1;
03206           ++__first1;
03207         }
03208       ++__result;
03209     }
03210       return std::copy(__first2, __last2, std::copy(__first1, __last1,
03211                             __result));
03212     }
03213 
03214   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03215        typename _Distance>
03216     void
03217     __merge_sort_loop(_RandomAccessIterator1 __first,
03218               _RandomAccessIterator1 __last,
03219               _RandomAccessIterator2 __result,
03220               _Distance __step_size)
03221     {
03222       const _Distance __two_step = 2 * __step_size;
03223 
03224       while (__last - __first >= __two_step)
03225     {
03226       __result = std::merge(__first, __first + __step_size,
03227                 __first + __step_size, __first + __two_step,
03228                 __result);
03229       __first += __two_step;
03230     }
03231 
03232       __step_size = std::min(_Distance(__last - __first), __step_size);
03233       std::merge(__first, __first + __step_size, __first + __step_size, __last,
03234          __result);
03235     }
03236 
03237   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03238        typename _Distance, typename _Compare>
03239     void
03240     __merge_sort_loop(_RandomAccessIterator1 __first,
03241               _RandomAccessIterator1 __last,
03242               _RandomAccessIterator2 __result, _Distance __step_size,
03243               _Compare __comp)
03244     {
03245       const _Distance __two_step = 2 * __step_size;
03246 
03247       while (__last - __first >= __two_step)
03248     {
03249       __result = std::merge(__first, __first + __step_size,
03250                 __first + __step_size, __first + __two_step,
03251                 __result,
03252                 __comp);
03253       __first += __two_step;
03254     }
03255       __step_size = std::min(_Distance(__last - __first), __step_size);
03256 
03257       std::merge(__first, __first + __step_size,
03258          __first + __step_size, __last,
03259          __result,
03260          __comp);
03261     }
03262 
03263   enum { _S_chunk_size = 7 };
03264 
03265   template<typename _RandomAccessIterator, typename _Distance>
03266     void
03267     __chunk_insertion_sort(_RandomAccessIterator __first,
03268                _RandomAccessIterator __last,
03269                _Distance __chunk_size)
03270     {
03271       while (__last - __first >= __chunk_size)
03272     {
03273       std::__insertion_sort(__first, __first + __chunk_size);
03274       __first += __chunk_size;
03275     }
03276       std::__insertion_sort(__first, __last);
03277     }
03278 
03279   template<typename _RandomAccessIterator, typename _Distance, typename _Compare>
03280     void
03281     __chunk_insertion_sort(_RandomAccessIterator __first,
03282                _RandomAccessIterator __last,
03283                _Distance __chunk_size, _Compare __comp)
03284     {
03285       while (__last - __first >= __chunk_size)
03286     {
03287       std::__insertion_sort(__first, __first + __chunk_size, __comp);
03288       __first += __chunk_size;
03289     }
03290       std::__insertion_sort(__first, __last, __comp);
03291     }
03292 
03293   template<typename _RandomAccessIterator, typename _Pointer>
03294     void
03295     __merge_sort_with_buffer(_RandomAccessIterator __first,
03296                  _RandomAccessIterator __last,
03297                              _Pointer __buffer)
03298     {
03299       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03300     _Distance;
03301 
03302       const _Distance __len = __last - __first;
03303       const _Pointer __buffer_last = __buffer + __len;
03304 
03305       _Distance __step_size = _S_chunk_size;
03306       std::__chunk_insertion_sort(__first, __last, __step_size);
03307 
03308       while (__step_size < __len)
03309     {
03310       std::__merge_sort_loop(__first, __last, __buffer, __step_size);
03311       __step_size *= 2;
03312       std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
03313       __step_size *= 2;
03314     }
03315     }
03316 
03317   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
03318     void
03319     __merge_sort_with_buffer(_RandomAccessIterator __first,
03320                  _RandomAccessIterator __last,
03321                              _Pointer __buffer, _Compare __comp)
03322     {
03323       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03324     _Distance;
03325 
03326       const _Distance __len = __last - __first;
03327       const _Pointer __buffer_last = __buffer + __len;
03328 
03329       _Distance __step_size = _S_chunk_size;
03330       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
03331 
03332       while (__step_size < __len)
03333     {
03334       std::__merge_sort_loop(__first, __last, __buffer,
03335                  __step_size, __comp);
03336       __step_size *= 2;
03337       std::__merge_sort_loop(__buffer, __buffer_last, __first,
03338                  __step_size, __comp);
03339       __step_size *= 2;
03340     }
03341     }
03342 
03348   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
03349        typename _BidirectionalIterator3>
03350     _BidirectionalIterator3
03351     __merge_backward(_BidirectionalIterator1 __first1,
03352              _BidirectionalIterator1 __last1,
03353              _BidirectionalIterator2 __first2,
03354              _BidirectionalIterator2 __last2,
03355              _BidirectionalIterator3 __result)
03356     {
03357       if (__first1 == __last1)
03358     return std::copy_backward(__first2, __last2, __result);
03359       if (__first2 == __last2)
03360     return std::copy_backward(__first1, __last1, __result);
03361       --__last1;
03362       --__last2;
03363       while (true)
03364     {
03365       if (*__last2 < *__last1)
03366         {
03367           *--__result = *__last1;
03368           if (__first1 == __last1)
03369         return std::copy_backward(__first2, ++__last2, __result);
03370           --__last1;
03371         }
03372       else
03373         {
03374           *--__result = *__last2;
03375           if (__first2 == __last2)
03376         return std::copy_backward(__first1, ++__last1, __result);
03377           --__last2;
03378         }
03379     }
03380     }
03381 
03387   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
03388        typename _BidirectionalIterator3, typename _Compare>
03389     _BidirectionalIterator3
03390     __merge_backward(_BidirectionalIterator1 __first1,
03391              _BidirectionalIterator1 __last1,
03392              _BidirectionalIterator2 __first2,
03393              _BidirectionalIterator2 __last2,
03394              _BidirectionalIterator3 __result,
03395              _Compare __comp)
03396     {
03397       if (__first1 == __last1)
03398     return std::copy_backward(__first2, __last2, __result);
03399       if (__first2 == __last2)
03400     return std::copy_backward(__first1, __last1, __result);
03401       --__last1;
03402       --__last2;
03403       while (true)
03404     {
03405       if (__comp(*__last2, *__last1))
03406         {
03407           *--__result = *__last1;
03408           if (__first1 == __last1)
03409         return std::copy_backward(__first2, ++__last2, __result);
03410           --__last1;
03411         }
03412       else
03413         {
03414           *--__result = *__last2;
03415           if (__first2 == __last2)
03416         return std::copy_backward(__first1, ++__last1, __result);
03417           --__last2;
03418         }
03419     }
03420     }
03421 
03427   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
03428        typename _Distance>
03429     _BidirectionalIterator1
03430     __rotate_adaptive(_BidirectionalIterator1 __first,
03431               _BidirectionalIterator1 __middle,
03432               _BidirectionalIterator1 __last,
03433               _Distance __len1, _Distance __len2,
03434               _BidirectionalIterator2 __buffer,
03435               _Distance __buffer_size)
03436     {
03437       _BidirectionalIterator2 __buffer_end;
03438       if (__len1 > __len2 && __len2 <= __buffer_size)
03439     {
03440       __buffer_end = std::copy(__middle, __last, __buffer);
03441       std::copy_backward(__first, __middle, __last);
03442       return std::copy(__buffer, __buffer_end, __first);
03443     }
03444       else if (__len1 <= __buffer_size)
03445     {
03446       __buffer_end = std::copy(__first, __middle, __buffer);
03447       std::copy(__middle, __last, __first);
03448       return std::copy_backward(__buffer, __buffer_end, __last);
03449     }
03450       else
03451     {
03452       std::rotate(__first, __middle, __last);
03453       std::advance(__first, std::distance(__middle, __last));
03454       return __first;
03455     }
03456     }
03457 
03463   template<typename _BidirectionalIterator, typename _Distance,
03464        typename _Pointer>
03465     void
03466     __merge_adaptive(_BidirectionalIterator __first,
03467                      _BidirectionalIterator __middle,
03468              _BidirectionalIterator __last,
03469              _Distance __len1, _Distance __len2,
03470              _Pointer __buffer, _Distance __buffer_size)
03471     {
03472       if (__len1 <= __len2 && __len1 <= __buffer_size)
03473     {
03474       _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
03475       std::merge(__buffer, __buffer_end, __middle, __last, __first);
03476     }
03477       else if (__len2 <= __buffer_size)
03478     {
03479       _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
03480       std::__merge_backward(__first, __middle, __buffer,
03481                 __buffer_end, __last);
03482     }
03483       else
03484     {
03485       _BidirectionalIterator __first_cut = __first;
03486       _BidirectionalIterator __second_cut = __middle;
03487       _Distance __len11 = 0;
03488       _Distance __len22 = 0;
03489       if (__len1 > __len2)
03490         {
03491           __len11 = __len1 / 2;
03492           std::advance(__first_cut, __len11);
03493           __second_cut = std::lower_bound(__middle, __last,
03494                           *__first_cut);
03495           __len22 = std::distance(__middle, __second_cut);
03496         }
03497       else
03498         {
03499           __len22 = __len2 / 2;
03500           std::advance(__second_cut, __len22);
03501           __first_cut = std::upper_bound(__first, __middle,
03502                          *__second_cut);
03503           __len11 = std::distance(__first, __first_cut);
03504         }
03505       _BidirectionalIterator __new_middle =
03506         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
03507                    __len1 - __len11, __len22, __buffer,
03508                    __buffer_size);
03509       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
03510                 __len22, __buffer, __buffer_size);
03511       std::__merge_adaptive(__new_middle, __second_cut, __last,
03512                 __len1 - __len11,
03513                 __len2 - __len22, __buffer, __buffer_size);
03514     }
03515     }
03516 
03522   template<typename _BidirectionalIterator, typename _Distance, typename _Pointer,
03523        typename _Compare>
03524     void
03525     __merge_adaptive(_BidirectionalIterator __first,
03526                      _BidirectionalIterator __middle,
03527              _BidirectionalIterator __last,
03528              _Distance __len1, _Distance __len2,
03529              _Pointer __buffer, _Distance __buffer_size,
03530              _Compare __comp)
03531     {
03532       if (__len1 <= __len2 && __len1 <= __buffer_size)
03533     {
03534       _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
03535       std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
03536     }
03537       else if (__len2 <= __buffer_size)
03538     {
03539       _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
03540       std::__merge_backward(__first, __middle, __buffer, __buffer_end,
03541                 __last, __comp);
03542     }
03543       else
03544     {
03545       _BidirectionalIterator __first_cut = __first;
03546       _BidirectionalIterator __second_cut = __middle;
03547       _Distance __len11 = 0;
03548       _Distance __len22 = 0;
03549       if (__len1 > __len2)
03550         {
03551           __len11 = __len1 / 2;
03552           std::advance(__first_cut, __len11);
03553           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03554                           __comp);
03555           __len22 = std::distance(__middle, __second_cut);
03556         }
03557       else
03558         {
03559           __len22 = __len2 / 2;
03560           std::advance(__second_cut, __len22);
03561           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03562                          __comp);
03563           __len11 = std::distance(__first, __first_cut);
03564         }
03565       _BidirectionalIterator __new_middle =
03566         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
03567                    __len1 - __len11, __len22, __buffer,
03568                    __buffer_size);
03569       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
03570                 __len22, __buffer, __buffer_size, __comp);
03571       std::__merge_adaptive(__new_middle, __second_cut, __last,
03572                 __len1 - __len11,
03573                 __len2 - __len22, __buffer,
03574                 __buffer_size, __comp);
03575     }
03576     }
03577 
03595   template<typename _BidirectionalIterator>
03596     void
03597     inplace_merge(_BidirectionalIterator __first,
03598           _BidirectionalIterator __middle,
03599           _BidirectionalIterator __last)
03600     {
03601       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03602           _ValueType;
03603       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03604           _DistanceType;
03605 
03606       // concept requirements
03607       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03608         _BidirectionalIterator>)
03609       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03610       __glibcxx_requires_sorted(__first, __middle);
03611       __glibcxx_requires_sorted(__middle, __last);
03612 
03613       if (__first == __middle || __middle == __last)
03614     return;
03615 
03616       _DistanceType __len1 = std::distance(__first, __middle);
03617       _DistanceType __len2 = std::distance(__middle, __last);
03618 
03619       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03620                                   __last);
03621       if (__buf.begin() == 0)
03622     std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
03623       else
03624     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03625                   __buf.begin(), _DistanceType(__buf.size()));
03626     }
03627 
03649   template<typename _BidirectionalIterator, typename _Compare>
03650     void
03651     inplace_merge(_BidirectionalIterator __first,
03652           _BidirectionalIterator __middle,
03653           _BidirectionalIterator __last,
03654           _Compare __comp)
03655     {
03656       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03657           _ValueType;
03658       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03659           _DistanceType;
03660 
03661       // concept requirements
03662       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03663         _BidirectionalIterator>)
03664       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03665         _ValueType, _ValueType>)
03666       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
03667       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
03668 
03669       if (__first == __middle || __middle == __last)
03670     return;
03671 
03672       const _DistanceType __len1 = std::distance(__first, __middle);
03673       const _DistanceType __len2 = std::distance(__middle, __last);
03674 
03675       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03676                                   __last);
03677       if (__buf.begin() == 0)
03678     std::__merge_without_buffer(__first, __middle, __last, __len1,
03679                     __len2, __comp);
03680       else
03681     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03682                   __buf.begin(), _DistanceType(__buf.size()),
03683                   __comp);
03684     }
03685 
03686   template<typename _RandomAccessIterator, typename _Pointer,
03687        typename _Distance>
03688     void
03689     __stable_sort_adaptive(_RandomAccessIterator __first,
03690                _RandomAccessIterator __last,
03691                            _Pointer __buffer, _Distance __buffer_size)
03692     {
03693       const _Distance __len = (__last - __first + 1) / 2;
03694       const _RandomAccessIterator __middle = __first + __len;
03695       if (__len > __buffer_size)
03696     {
03697       std::__stable_sort_adaptive(__first, __middle,
03698                       __buffer, __buffer_size);
03699       std::__stable_sort_adaptive(__middle, __last,
03700                       __buffer, __buffer_size);
03701     }
03702       else
03703     {
03704       std::__merge_sort_with_buffer(__first, __middle, __buffer);
03705       std::__merge_sort_with_buffer(__middle, __last, __buffer);
03706     }
03707       std::__merge_adaptive(__first, __middle, __last,
03708                 _Distance(__middle - __first),
03709                 _Distance(__last - __middle),
03710                 __buffer, __buffer_size);
03711     }
03712 
03713   template<typename _RandomAccessIterator, typename _Pointer,
03714        typename _Distance, typename _Compare>
03715     void
03716     __stable_sort_adaptive(_RandomAccessIterator __first,
03717                _RandomAccessIterator __last,
03718                            _Pointer __buffer, _Distance __buffer_size,
03719                            _Compare __comp)
03720     {
03721       const _Distance __len = (__last - __first + 1) / 2;
03722       const _RandomAccessIterator __middle = __first + __len;
03723       if (__len > __buffer_size)
03724     {
03725       std::__stable_sort_adaptive(__first, __middle, __buffer,
03726                       __buffer_size, __comp);
03727       std::__stable_sort_adaptive(__middle, __last, __buffer,
03728                       __buffer_size, __comp);
03729     }
03730       else
03731     {
03732       std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
03733       std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
03734     }
03735       std::__merge_adaptive(__first, __middle, __last,
03736                 _Distance(__middle - __first),
03737                 _Distance(__last - __middle),
03738                 __buffer, __buffer_size,
03739                 __comp);
03740     }
03741 
03758   template<typename _RandomAccessIterator>
03759     inline void
03760     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
03761     {
03762       typedef typename iterator_traits<_RandomAccessIterator>::value_type
03763     _ValueType;
03764       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03765     _DistanceType;
03766 
03767       // concept requirements
03768       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03769         _RandomAccessIterator>)
03770       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03771       __glibcxx_requires_valid_range(__first, __last);
03772 
03773       _Temporary_buffer<_RandomAccessIterator, _ValueType>
03774     buf(__first, __last);
03775       if (buf.begin() == 0)
03776     std::__inplace_stable_sort(__first, __last);
03777       else
03778     std::__stable_sort_adaptive(__first, __last, buf.begin(),
03779                     _DistanceType(buf.size()));
03780     }
03781 
03799   template<typename _RandomAccessIterator, typename _Compare>
03800     inline void
03801     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
03802         _Compare __comp)
03803     {
03804       typedef typename iterator_traits<_RandomAccessIterator>::value_type
03805     _ValueType;
03806       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03807     _DistanceType;
03808 
03809       // concept requirements
03810       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03811         _RandomAccessIterator>)
03812       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03813                   _ValueType,
03814                   _ValueType>)
03815       __glibcxx_requires_valid_range(__first, __last);
03816 
03817       _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last);
03818       if (buf.begin() == 0)
03819     std::__inplace_stable_sort(__first, __last, __comp);
03820       else
03821     std::__stable_sort_adaptive(__first, __last, buf.begin(),
03822                     _DistanceType(buf.size()), __comp);
03823     }
03824 
03840   template<typename _RandomAccessIterator>
03841     void
03842     nth_element(_RandomAccessIterator __first,
03843         _RandomAccessIterator __nth,
03844         _RandomAccessIterator __last)
03845     {
03846       typedef typename iterator_traits<_RandomAccessIterator>::value_type
03847     _ValueType;
03848 
03849       // concept requirements
03850       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03851                   _RandomAccessIterator>)
03852       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03853       __glibcxx_requires_valid_range(__first, __nth);
03854       __glibcxx_requires_valid_range(__nth, __last);
03855 
03856       while (__last - __first > 3)
03857     {
03858       _RandomAccessIterator __cut =
03859         std::__unguarded_partition(__first, __last,
03860                        _ValueType(std::__median(*__first,
03861                                 *(__first
03862                                   + (__last
03863                                      - __first)
03864                                   / 2),
03865                                 *(__last
03866                                   - 1))));
03867       if (__cut <= __nth)
03868         __first = __cut;
03869       else
03870         __last = __cut;
03871     }
03872       std::__insertion_sort(__first, __last);
03873     }
03874 
03891   template<typename _RandomAccessIterator, typename _Compare>
03892     void
03893     nth_element(_RandomAccessIterator __first,
03894         _RandomAccessIterator __nth,
03895         _RandomAccessIterator __last,
03896                 _Compare __comp)
03897     {
03898       typedef typename iterator_traits<_RandomAccessIterator>::value_type
03899     _ValueType;
03900 
03901       // concept requirements
03902       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03903                   _RandomAccessIterator>)
03904       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03905                   _ValueType, _ValueType>)
03906       __glibcxx_requires_valid_range(__first, __nth);
03907       __glibcxx_requires_valid_range(__nth, __last);
03908 
03909       while (__last - __first > 3)
03910     {
03911       _RandomAccessIterator __cut =
03912         std::__unguarded_partition(__first, __last,
03913                        _ValueType(std::__median(*__first,
03914                                 *(__first
03915                                   + (__last
03916                                      - __first)
03917                                   / 2),
03918                                 *(__last - 1),
03919                                   __comp)), __comp);
03920       if (__cut <= __nth)
03921         __first = __cut;
03922       else
03923         __last = __cut;
03924     }
03925       std::__insertion_sort(__first, __last, __comp);
03926     }
03927 
03944   template<typename _ForwardIterator, typename _Tp>
03945     pair<_ForwardIterator, _ForwardIterator>
03946     equal_range(_ForwardIterator __first, _ForwardIterator __last,
03947         const _Tp& __val)
03948     {
03949       typedef typename iterator_traits<_ForwardIterator>::value_type
03950     _ValueType;
03951       typedef typename iterator_traits<_ForwardIterator>::difference_type
03952     _DistanceType;
03953 
03954       // concept requirements
03955       // See comments on lower_bound.
03956       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03957       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
03958       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
03959       __glibcxx_requires_partitioned(__first, __last, __val);
03960 
03961       _DistanceType __len = std::distance(__first, __last);
03962       _DistanceType __half;
03963       _ForwardIterator __middle, __left, __right;
03964 
03965       while (__len > 0)
03966     {
03967       __half = __len >> 1;
03968       __middle = __first;
03969       std::advance(__middle, __half);
03970       if (*__middle < __val)
03971         {
03972           __first = __middle;
03973           ++__first;
03974           __len = __len - __half - 1;
03975         }
03976       else if (__val < *__middle)
03977         __len = __half;
03978       else
03979         {
03980           __left = std::lower_bound(__first, __middle, __val);
03981           std::advance(__first, __len);
03982           __right = std::upper_bound(++__middle, __first, __val);
03983           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
03984         }
03985     }
03986       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
03987     }
03988 
04006   template<typename _ForwardIterator, typename _Tp, typename _Compare>
04007     pair<_ForwardIterator, _ForwardIterator>
04008     equal_range(_ForwardIterator __first, _ForwardIterator __last,
04009         const _Tp& __val,
04010         _Compare __comp)
04011     {
04012       typedef typename iterator_traits<_ForwardIterator>::value_type
04013     _ValueType;
04014       typedef typename iterator_traits<_ForwardIterator>::difference_type
04015     _DistanceType;
04016 
04017       // concept requirements
04018       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04019       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04020                   _ValueType, _Tp>)
04021       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04022                   _Tp, _ValueType>)
04023       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
04024 
04025       _DistanceType __len = std::distance(__first, __last);
04026       _DistanceType __half;
04027       _ForwardIterator __middle, __left, __right;
04028 
04029       while (__len > 0)
04030     {
04031       __half = __len >> 1;
04032       __middle = __first;
04033       std::advance(__middle, __half);
04034       if (__comp(*__middle, __val))
04035         {
04036           __first = __middle;
04037           ++__first;
04038           __len = __len - __half - 1;
04039         }
04040       else if (__comp(__val, *__middle))
04041         __len = __half;
04042       else
04043         {
04044           __left = std::lower_bound(__first, __middle, __val, __comp);
04045           std::advance(__first, __len);
04046           __right = std::upper_bound(++__middle, __first, __val, __comp);
04047           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
04048         }
04049     }
04050       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
04051     }
04052 
04064   template<typename _ForwardIterator, typename _Tp>
04065     bool
04066     binary_search(_ForwardIterator __first, _ForwardIterator __last,
04067                   const _Tp& __val)
04068     {
04069       // concept requirements
04070       // See comments on lower_bound.
04071       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04072       __glibcxx_function_requires(_SameTypeConcept<_Tp,
04073         typename iterator_traits<_ForwardIterator>::value_type>)
04074       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
04075       __glibcxx_requires_partitioned(__first, __last, __val);
04076 
04077       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
04078       return __i != __last && !(__val < *__i);
04079     }
04080 
04096   template<typename _ForwardIterator, typename _Tp, typename _Compare>
04097     bool
04098     binary_search(_ForwardIterator __first, _ForwardIterator __last,
04099                   const _Tp& __val, _Compare __comp)
04100     {
04101       // concept requirements
04102       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04103       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04104         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04105       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
04106         typename iterator_traits<_ForwardIterator>::value_type>)
04107       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
04108 
04109       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
04110       return __i != __last && !__comp(__val, *__i);
04111     }
04112 
04113   // Set algorithms: includes, set_union, set_intersection, set_difference,
04114   // set_symmetric_difference.  All of these algorithms have the precondition
04115   // that their input ranges are sorted and the postcondition that their output
04116   // ranges are sorted.
04117 
04134   template<typename _InputIterator1, typename _InputIterator2>
04135     bool
04136     includes(_InputIterator1 __first1, _InputIterator1 __last1,
04137          _InputIterator2 __first2, _InputIterator2 __last2)
04138     {
04139       // concept requirements
04140       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04141       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04142       __glibcxx_function_requires(_SameTypeConcept<
04143         typename iterator_traits<_InputIterator1>::value_type,
04144         typename iterator_traits<_InputIterator2>::value_type>)
04145       __glibcxx_function_requires(_LessThanComparableConcept<
04146         typename iterator_traits<_InputIterator1>::value_type>)
04147       __glibcxx_requires_sorted(__first1, __last1);
04148       __glibcxx_requires_sorted(__first2, __last2);
04149 
04150       while (__first1 != __last1 && __first2 != __last2)
04151     if (*__first2 < *__first1)
04152       return false;
04153     else if(*__first1 < *__first2)
04154       ++__first1;
04155     else
04156       ++__first1, ++__first2;
04157 
04158       return __first2 == __last2;
04159     }
04160 
04180   template<typename _InputIterator1, typename _InputIterator2,
04181        typename _Compare>
04182     bool
04183     includes(_InputIterator1 __first1, _InputIterator1 __last1,
04184          _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
04185     {
04186       // concept requirements
04187       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04188       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04189       __glibcxx_function_requires(_SameTypeConcept<
04190         typename iterator_traits<_InputIterator1>::value_type,
04191         typename iterator_traits<_InputIterator2>::value_type>)
04192       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04193         typename iterator_traits<_InputIterator1>::value_type,
04194         typename iterator_traits<_InputIterator2>::value_type>)
04195       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04196       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04197 
04198       while (__first1 != __last1 && __first2 != __last2)
04199     if (__comp(*__first2, *__first1))
04200       return false;
04201     else if(__comp(*__first1, *__first2))
04202       ++__first1;
04203     else
04204       ++__first1, ++__first2;
04205 
04206       return __first2 == __last2;
04207     }
04208 
04226   template<typename _InputIterator1, typename _InputIterator2,
04227        typename _OutputIterator>
04228     _OutputIterator
04229     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
04230           _InputIterator2 __first2, _InputIterator2 __last2,
04231           _OutputIterator __result)
04232     {
04233       // concept requirements
04234       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04235       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04236       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04237         typename iterator_traits<_InputIterator1>::value_type>)
04238       __glibcxx_function_requires(_SameTypeConcept<
04239         typename iterator_traits<_InputIterator1>::value_type,
04240         typename iterator_traits<_InputIterator2>::value_type>)
04241       __glibcxx_function_requires(_LessThanComparableConcept<
04242         typename iterator_traits<_InputIterator1>::value_type>)
04243       __glibcxx_requires_sorted(__first1, __last1);
04244       __glibcxx_requires_sorted(__first2, __last2);
04245 
04246       while (__first1 != __last1 && __first2 != __last2)
04247     {
04248       if (*__first1 < *__first2)
04249         {
04250           *__result = *__first1;
04251           ++__first1;
04252         }
04253       else if (*__first2 < *__first1)
04254         {
04255           *__result = *__first2;
04256           ++__first2;
04257         }
04258       else
04259         {
04260           *__result = *__first1;
04261           ++__first1;
04262           ++__first2;
04263         }
04264       ++__result;
04265     }
04266       return std::copy(__first2, __last2, std::copy(__first1, __last1,
04267                             __result));
04268     }
04269 
04288   template<typename _InputIterator1, typename _InputIterator2,
04289        typename _OutputIterator, typename _Compare>
04290     _OutputIterator
04291     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
04292           _InputIterator2 __first2, _InputIterator2 __last2,
04293           _OutputIterator __result, _Compare __comp)
04294     {
04295       // concept requirements
04296       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04297       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04298       __glibcxx_function_requires(_SameTypeConcept<
04299         typename iterator_traits<_InputIterator1>::value_type,
04300         typename iterator_traits<_InputIterator2>::value_type>)
04301       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04302         typename iterator_traits<_InputIterator1>::value_type>)
04303       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04304         typename iterator_traits<_InputIterator1>::value_type,
04305         typename iterator_traits<_InputIterator2>::value_type>)
04306       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04307       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04308 
04309       while (__first1 != __last1 && __first2 != __last2)
04310     {
04311       if (__comp(*__first1, *__first2))
04312         {
04313           *__result = *__first1;
04314           ++__first1;
04315         }
04316       else if (__comp(*__first2, *__first1))
04317         {
04318           *__result = *__first2;
04319           ++__first2;
04320         }
04321       else
04322         {
04323           *__result = *__first1;
04324           ++__first1;
04325           ++__first2;
04326         }
04327       ++__result;
04328     }
04329       return std::copy(__first2, __last2, std::copy(__first1, __last1,
04330                             __result));
04331     }
04332 
04349   template<typename _InputIterator1, typename _InputIterator2,
04350        typename _OutputIterator>
04351     _OutputIterator
04352     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
04353              _InputIterator2 __first2, _InputIterator2 __last2,
04354              _OutputIterator __result)
04355     {
04356       // concept requirements
04357       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04358       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04359       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04360         typename iterator_traits<_InputIterator1>::value_type>)
04361       __glibcxx_function_requires(_SameTypeConcept<
04362         typename iterator_traits<_InputIterator1>::value_type,
04363         typename iterator_traits<_InputIterator2>::value_type>)
04364       __glibcxx_function_requires(_LessThanComparableConcept<
04365         typename iterator_traits<_InputIterator1>::value_type>)
04366       __glibcxx_requires_sorted(__first1, __last1);
04367       __glibcxx_requires_sorted(__first2, __last2);
04368 
04369       while (__first1 != __last1 && __first2 != __last2)
04370     if (*__first1 < *__first2)
04371       ++__first1;
04372     else if (*__first2 < *__first1)
04373       ++__first2;
04374     else
04375       {
04376         *__result = *__first1;
04377         ++__first1;
04378         ++__first2;
04379         ++__result;
04380       }
04381       return __result;
04382     }
04383 
04403   template<typename _InputIterator1, typename _InputIterator2,
04404        typename _OutputIterator, typename _Compare>
04405     _OutputIterator
04406     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
04407              _InputIterator2 __first2, _InputIterator2 __last2,
04408              _OutputIterator __result, _Compare __comp)
04409     {
04410       // concept requirements
04411       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04412       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04413       __glibcxx_function_requires(_SameTypeConcept<
04414         typename iterator_traits<_InputIterator1>::value_type,
04415         typename iterator_traits<_InputIterator2>::value_type>)
04416       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04417         typename iterator_traits<_InputIterator1>::value_type>)
04418       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04419         typename iterator_traits<_InputIterator1>::value_type,
04420         typename iterator_traits<_InputIterator2>::value_type>)
04421       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04422       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04423 
04424       while (__first1 != __last1 && __first2 != __last2)
04425     if (__comp(*__first1, *__first2))
04426       ++__first1;
04427     else if (__comp(*__first2, *__first1))
04428       ++__first2;
04429     else
04430       {
04431         *__result = *__first1;
04432         ++__first1;
04433         ++__first2;
04434         ++__result;
04435       }
04436       return __result;
04437     }
04438 
04457   template<typename _InputIterator1, typename _InputIterator2,
04458        typename _OutputIterator>
04459     _OutputIterator
04460     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
04461            _InputIterator2 __first2, _InputIterator2 __last2,
04462            _OutputIterator __result)
04463     {
04464       // concept requirements
04465       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04466       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04467       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04468         typename iterator_traits<_InputIterator1>::value_type>)
04469       __glibcxx_function_requires(_SameTypeConcept<
04470         typename iterator_traits<_InputIterator1>::value_type,
04471         typename iterator_traits<_InputIterator2>::value_type>)
04472       __glibcxx_function_requires(_LessThanComparableConcept<
04473         typename iterator_traits<_InputIterator1>::value_type>)
04474       __glibcxx_requires_sorted(__first1, __last1);
04475       __glibcxx_requires_sorted(__first2, __last2);
04476 
04477       while (__first1 != __last1 && __first2 != __last2)
04478     if (*__first1 < *__first2)
04479       {
04480         *__result = *__first1;
04481         ++__first1;
04482         ++__result;
04483       }
04484     else if (*__first2 < *__first1)
04485       ++__first2;
04486     else
04487       {
04488         ++__first1;
04489         ++__first2;
04490       }
04491       return std::copy(__first1, __last1, __result);
04492     }
04493 
04515   template<typename _InputIterator1, typename _InputIterator2,
04516        typename _OutputIterator, typename _Compare>
04517     _OutputIterator
04518     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
04519            _InputIterator2 __first2, _InputIterator2 __last2,
04520            _OutputIterator __result, _Compare __comp)
04521     {
04522       // concept requirements
04523       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04524       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04525       __glibcxx_function_requires(_SameTypeConcept<
04526         typename iterator_traits<_InputIterator1>::value_type,
04527         typename iterator_traits<_InputIterator2>::value_type>)
04528       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04529         typename iterator_traits<_InputIterator1>::value_type>)
04530       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04531         typename iterator_traits<_InputIterator1>::value_type,
04532         typename iterator_traits<_InputIterator2>::value_type>)
04533       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04534       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04535 
04536       while (__first1 != __last1 && __first2 != __last2)
04537     if (__comp(*__first1, *__first2))
04538       {
04539         *__result = *__first1;
04540         ++__first1;
04541         ++__result;
04542       }
04543     else if (__comp(*__first2, *__first1))
04544       ++__first2;
04545     else
04546       {
04547         ++__first1;
04548         ++__first2;
04549       }
04550       return std::copy(__first1, __last1, __result);
04551     }
04552 
04569   template<typename _InputIterator1, typename _InputIterator2,
04570        typename _OutputIterator>
04571     _OutputIterator
04572     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
04573                  _InputIterator2 __first2, _InputIterator2 __last2,
04574                  _OutputIterator __result)
04575     {
04576       // concept requirements
04577       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04578       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04579       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04580         typename iterator_traits<_InputIterator1>::value_type>)
04581       __glibcxx_function_requires(_SameTypeConcept<
04582         typename iterator_traits<_InputIterator1>::value_type,
04583         typename iterator_traits<_InputIterator2>::value_type>)
04584       __glibcxx_function_requires(_LessThanComparableConcept<
04585         typename iterator_traits<_InputIterator1>::value_type>)
04586       __glibcxx_requires_sorted(__first1, __last1);
04587       __glibcxx_requires_sorted(__first2, __last2);
04588 
04589       while (__first1 != __last1 && __first2 != __last2)
04590     if (*__first1 < *__first2)
04591       {
04592         *__result = *__first1;
04593         ++__first1;
04594         ++__result;
04595       }
04596     else if (*__first2 < *__first1)
04597       {
04598         *__result = *__first2;
04599         ++__first2;
04600         ++__result;
04601       }
04602     else
04603       {
04604         ++__first1;
04605         ++__first2;
04606       }
04607       return std::copy(__first2, __last2, std::copy(__first1,
04608                             __last1, __result));
04609     }
04610 
04630   template<typename _InputIterator1, typename _InputIterator2,
04631        typename _OutputIterator, typename _Compare>
04632     _OutputIterator
04633     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
04634                  _InputIterator2 __first2, _InputIterator2 __last2,
04635                  _OutputIterator __result,
04636                  _Compare __comp)
04637     {
04638       // concept requirements
04639       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04640       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04641       __glibcxx_function_requires(_SameTypeConcept<
04642         typename iterator_traits<_InputIterator1>::value_type,
04643         typename iterator_traits<_InputIterator2>::value_type>)
04644       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04645         typename iterator_traits<_InputIterator1>::value_type>)
04646       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04647         typename iterator_traits<_InputIterator1>::value_type,
04648         typename iterator_traits<_InputIterator2>::value_type>)
04649       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
04650       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
04651 
04652       while (__first1 != __last1 && __first2 != __last2)
04653     if (__comp(*__first1, *__first2))
04654       {
04655         *__result = *__first1;
04656         ++__first1;
04657         ++__result;
04658       }
04659     else if (__comp(*__first2, *__first1))
04660       {
04661         *__result = *__first2;
04662         ++__first2;
04663         ++__result;
04664       }
04665     else
04666       {
04667         ++__first1;
04668         ++__first2;
04669       }
04670       return std::copy(__first2, __last2, std::copy(__first1,
04671                             __last1, __result));
04672     }
04673 
04674   // min_element and max_element, with and without an explicitly supplied
04675   // comparison function.
04676 
04683   template<typename _ForwardIterator>
04684     _ForwardIterator
04685     max_element(_ForwardIterator __first, _ForwardIterator __last)
04686     {
04687       // concept requirements
04688       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04689       __glibcxx_function_requires(_LessThanComparableConcept<
04690         typename iterator_traits<_ForwardIterator>::value_type>)
04691       __glibcxx_requires_valid_range(__first, __last);
04692 
04693       if (__first == __last)
04694     return __first;
04695       _ForwardIterator __result = __first;
04696       while (++__first != __last)
04697     if (*__result < *__first)
04698       __result = __first;
04699       return __result;
04700     }
04701 
04710   template<typename _ForwardIterator, typename _Compare>
04711     _ForwardIterator
04712     max_element(_ForwardIterator __first, _ForwardIterator __last,
04713         _Compare __comp)
04714     {
04715       // concept requirements
04716       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04717       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04718         typename iterator_traits<_ForwardIterator>::value_type,
04719         typename iterator_traits<_ForwardIterator>::value_type>)
04720       __glibcxx_requires_valid_range(__first, __last);
04721 
04722       if (__first == __last) return __first;
04723       _ForwardIterator __result = __first;
04724       while (++__first != __last)
04725     if (__comp(*__result, *__first)) __result = __first;
04726       return __result;
04727     }
04728 
04735   template<typename _ForwardIterator>
04736     _ForwardIterator
04737     min_element(_ForwardIterator __first, _ForwardIterator __last)
04738     {
04739       // concept requirements
04740       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04741       __glibcxx_function_requires(_LessThanComparableConcept<
04742         typename iterator_traits<_ForwardIterator>::value_type>)
04743       __glibcxx_requires_valid_range(__first, __last);
04744 
04745       if (__first == __last)
04746     return __first;
04747       _ForwardIterator __result = __first;
04748       while (++__first != __last)
04749     if (*__first < *__result)
04750       __result = __first;
04751       return __result;
04752     }
04753 
04762   template<typename _ForwardIterator, typename _Compare>
04763     _ForwardIterator
04764     min_element(_ForwardIterator __first, _ForwardIterator __last,
04765         _Compare __comp)
04766     {
04767       // concept requirements
04768       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04769       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04770         typename iterator_traits<_ForwardIterator>::value_type,
04771         typename iterator_traits<_ForwardIterator>::value_type>)
04772       __glibcxx_requires_valid_range(__first, __last);
04773 
04774       if (__first == __last)
04775     return __first;
04776       _ForwardIterator __result = __first;
04777       while (++__first != __last)
04778     if (__comp(*__first, *__result))
04779       __result = __first;
04780       return __result;
04781     }
04782 
04783   // next_permutation and prev_permutation, with and without an explicitly
04784   // supplied comparison function.
04785 
04797   template<typename _BidirectionalIterator>
04798     bool
04799     next_permutation(_BidirectionalIterator __first,
04800              _BidirectionalIterator __last)
04801     {
04802       // concept requirements
04803       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04804                   _BidirectionalIterator>)
04805       __glibcxx_function_requires(_LessThanComparableConcept<
04806         typename iterator_traits<_BidirectionalIterator>::value_type>)
04807       __glibcxx_requires_valid_range(__first, __last);
04808 
04809       if (__first == __last)
04810     return false;
04811       _BidirectionalIterator __i = __first;
04812       ++__i;
04813       if (__i == __last)
04814     return false;
04815       __i = __last;
04816       --__i;
04817 
04818       for(;;)
04819     {
04820       _BidirectionalIterator __ii = __i;
04821       --__i;
04822       if (*__i < *__ii)
04823         {
04824           _BidirectionalIterator __j = __last;
04825           while (!(*__i < *--__j))
04826         {}
04827           std::iter_swap(__i, __j);
04828           std::reverse(__ii, __last);
04829           return true;
04830         }
04831       if (__i == __first)
04832         {
04833           std::reverse(__first, __last);
04834           return false;
04835         }
04836     }
04837     }
04838 
04853   template<typename _BidirectionalIterator, typename _Compare>
04854     bool
04855     next_permutation(_BidirectionalIterator __first,
04856              _BidirectionalIterator __last, _Compare __comp)
04857     {
04858       // concept requirements
04859       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04860                   _BidirectionalIterator>)
04861       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04862         typename iterator_traits<_BidirectionalIterator>::value_type,
04863         typename iterator_traits<_BidirectionalIterator>::value_type>)
04864       __glibcxx_requires_valid_range(__first, __last);
04865 
04866       if (__first == __last)
04867     return false;
04868       _BidirectionalIterator __i = __first;
04869       ++__i;
04870       if (__i == __last)
04871     return false;
04872       __i = __last;
04873       --__i;
04874 
04875       for(;;)
04876     {
04877       _BidirectionalIterator __ii = __i;
04878       --__i;
04879       if (__comp(*__i, *__ii))
04880         {
04881           _BidirectionalIterator __j = __last;
04882           while (!__comp(*__i, *--__j))
04883         {}
04884           std::iter_swap(__i, __j);
04885           std::reverse(__ii, __last);
04886           return true;
04887         }
04888       if (__i == __first)
04889         {
04890           std::reverse(__first, __last);
04891           return false;
04892         }
04893     }
04894     }
04895 
04908   template<typename _BidirectionalIterator>
04909     bool
04910     prev_permutation(_BidirectionalIterator __first,
04911              _BidirectionalIterator __last)
04912     {
04913       // concept requirements
04914       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04915                   _BidirectionalIterator>)
04916       __glibcxx_function_requires(_LessThanComparableConcept<
04917         typename iterator_traits<_BidirectionalIterator>::value_type>)
04918       __glibcxx_requires_valid_range(__first, __last);
04919 
04920       if (__first == __last)
04921     return false;
04922       _BidirectionalIterator __i = __first;
04923       ++__i;
04924       if (__i == __last)
04925     return false;
04926       __i = __last;
04927       --__i;
04928 
04929       for(;;)
04930     {
04931       _BidirectionalIterator __ii = __i;
04932       --__i;
04933       if (*__ii < *__i)
04934         {
04935           _BidirectionalIterator __j = __last;
04936           while (!(*--__j < *__i))
04937         {}
04938           std::iter_swap(__i, __j);
04939           std::reverse(__ii, __last);
04940           return true;
04941         }
04942       if (__i == __first)
04943         {
04944           std::reverse(__first, __last);
04945           return false;
04946         }
04947     }
04948     }
04949 
04964   template<typename _BidirectionalIterator, typename _Compare>
04965     bool
04966     prev_permutation(_BidirectionalIterator __first,
04967              _BidirectionalIterator __last, _Compare __comp)
04968     {
04969       // concept requirements
04970       __glibcxx_function_requires(_BidirectionalIteratorConcept<
04971                   _BidirectionalIterator>)
04972       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04973         typename iterator_traits<_BidirectionalIterator>::value_type,
04974         typename iterator_traits<_BidirectionalIterator>::value_type>)
04975       __glibcxx_requires_valid_range(__first, __last);
04976 
04977       if (__first == __last)
04978     return false;
04979       _BidirectionalIterator __i = __first;
04980       ++__i;
04981       if (__i == __last)
04982     return false;
04983       __i = __last;
04984       --__i;
04985 
04986       for(;;)
04987     {
04988       _BidirectionalIterator __ii = __i;
04989       --__i;
04990       if (__comp(*__ii, *__i))
04991         {
04992           _BidirectionalIterator __j = __last;
04993           while (!__comp(*--__j, *__i))
04994         {}
04995           std::iter_swap(__i, __j);
04996           std::reverse(__ii, __last);
04997           return true;
04998         }
04999       if (__i == __first)
05000         {
05001           std::reverse(__first, __last);
05002           return false;
05003         }
05004     }
05005     }
05006 
05007   // find_first_of, with and without an explicitly supplied comparison function.
05008 
05023   template<typename _InputIterator, typename _ForwardIterator>
05024     _InputIterator
05025     find_first_of(_InputIterator __first1, _InputIterator __last1,
05026           _ForwardIterator __first2, _ForwardIterator __last2)
05027     {
05028       // concept requirements
05029       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
05030       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05031       __glibcxx_function_requires(_EqualOpConcept<
05032         typename iterator_traits<_InputIterator>::value_type,
05033         typename iterator_traits<_ForwardIterator>::value_type>)
05034       __glibcxx_requires_valid_range(__first1, __last1);
05035       __glibcxx_requires_valid_range(__first2, __last2);
05036 
05037       for ( ; __first1 != __last1; ++__first1)
05038     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
05039       if (*__first1 == *__iter)
05040         return __first1;
05041       return __last1;
05042     }
05043 
05059   template<typename _InputIterator, typename _ForwardIterator,
05060        typename _BinaryPredicate>
05061     _InputIterator
05062     find_first_of(_InputIterator __first1, _InputIterator __last1,
05063           _ForwardIterator __first2, _ForwardIterator __last2,
05064           _BinaryPredicate __comp)
05065     {
05066       // concept requirements
05067       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
05068       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05069       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
05070         typename iterator_traits<_InputIterator>::value_type,
05071         typename iterator_traits<_ForwardIterator>::value_type>)
05072       __glibcxx_requires_valid_range(__first1, __last1);
05073       __glibcxx_requires_valid_range(__first2, __last2);
05074 
05075       for ( ; __first1 != __last1; ++__first1)
05076     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
05077       if (__comp(*__first1, *__iter))
05078         return __first1;
05079       return __last1;
05080     }
05081 
05082 
05083   // find_end, with and without an explicitly supplied comparison function.
05084   // Search [first2, last2) as a subsequence in [first1, last1), and return
05085   // the *last* possible match.  Note that find_end for bidirectional iterators
05086   // is much faster than for forward iterators.
05087 
05088   // find_end for forward iterators.
05089   template<typename _ForwardIterator1, typename _ForwardIterator2>
05090     _ForwardIterator1
05091     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
05092            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
05093            forward_iterator_tag, forward_iterator_tag)
05094     {
05095       if (__first2 == __last2)
05096     return __last1;
05097       else
05098     {
05099       _ForwardIterator1 __result = __last1;
05100       while (1)
05101         {
05102           _ForwardIterator1 __new_result
05103         = std::search(__first1, __last1, __first2, __last2);
05104           if (__new_result == __last1)
05105         return __result;
05106           else
05107         {
05108           __result = __new_result;
05109           __first1 = __new_result;
05110           ++__first1;
05111         }
05112         }
05113     }
05114     }
05115 
05116   template<typename _ForwardIterator1, typename _ForwardIterator2,
05117        typename _BinaryPredicate>
05118     _ForwardIterator1
05119     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
05120            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
05121            forward_iterator_tag, forward_iterator_tag,
05122            _BinaryPredicate __comp)
05123     {
05124       if (__first2 == __last2)
05125     return __last1;
05126       else
05127     {
05128       _ForwardIterator1 __result = __last1;
05129       while (1)
05130         {
05131           _ForwardIterator1 __new_result
05132         = std::search(__first1, __last1, __first2, __last2, __comp);
05133           if (__new_result == __last1)
05134         return __result;
05135           else
05136         {
05137           __result = __new_result;
05138           __first1 = __new_result;
05139           ++__first1;
05140         }
05141         }
05142     }
05143     }
05144 
05145   // find_end for bidirectional iterators.  Requires partial specialization.
05146   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
05147     _BidirectionalIterator1
05148     __find_end(_BidirectionalIterator1 __first1,
05149            _BidirectionalIterator1 __last1,
05150            _BidirectionalIterator2 __first2,
05151            _BidirectionalIterator2 __last2,
05152            bidirectional_iterator_tag, bidirectional_iterator_tag)
05153     {
05154       // concept requirements
05155       __glibcxx_function_requires(_BidirectionalIteratorConcept<
05156                   _BidirectionalIterator1>)
05157       __glibcxx_function_requires(_BidirectionalIteratorConcept<
05158                   _BidirectionalIterator2>)
05159 
05160       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
05161       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
05162 
05163       _RevIterator1 __rlast1(__first1);
05164       _RevIterator2 __rlast2(__first2);
05165       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
05166                         _RevIterator2(__last2), __rlast2);
05167 
05168       if (__rresult == __rlast1)
05169     return __last1;
05170       else
05171     {
05172       _BidirectionalIterator1 __result = __rresult.base();
05173       std::advance(__result, -std::distance(__first2, __last2));
05174       return __result;
05175     }
05176     }
05177 
05178   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
05179        typename _BinaryPredicate>
05180     _BidirectionalIterator1
05181     __find_end(_BidirectionalIterator1 __first1,
05182            _BidirectionalIterator1 __last1,
05183            _BidirectionalIterator2 __first2,
05184            _BidirectionalIterator2 __last2,
05185            bidirectional_iterator_tag, bidirectional_iterator_tag,
05186            _BinaryPredicate __comp)
05187     {
05188       // concept requirements
05189       __glibcxx_function_requires(_BidirectionalIteratorConcept<
05190                   _BidirectionalIterator1>)
05191       __glibcxx_function_requires(_BidirectionalIteratorConcept<
05192                   _BidirectionalIterator2>)
05193 
05194       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
05195       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
05196 
05197       _RevIterator1 __rlast1(__first1);
05198       _RevIterator2 __rlast2(__first2);
05199       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
05200                         _RevIterator2(__last2), __rlast2,
05201                         __comp);
05202 
05203       if (__rresult == __rlast1)
05204     return __last1;
05205       else
05206     {
05207       _BidirectionalIterator1 __result = __rresult.base();
05208       std::advance(__result, -std::distance(__first2, __last2));
05209       return __result;
05210     }
05211     }
05212 
05213   // Dispatching functions for find_end.
05214 
05239   template<typename _ForwardIterator1, typename _ForwardIterator2>
05240     inline _ForwardIterator1
05241     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
05242          _ForwardIterator2 __first2, _ForwardIterator2 __last2)
05243     {
05244       // concept requirements
05245       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
05246       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
05247       __glibcxx_function_requires(_EqualOpConcept<
05248         typename iterator_traits<_ForwardIterator1>::value_type,
05249         typename iterator_traits<_ForwardIterator2>::value_type>)
05250       __glibcxx_requires_valid_range(__first1, __last1);
05251       __glibcxx_requires_valid_range(__first2, __last2);
05252 
05253       return std::__find_end(__first1, __last1, __first2, __last2,
05254                  std::__iterator_category(__first1),
05255                  std::__iterator_category(__first2));
05256     }
05257 
05284   template<typename _ForwardIterator1, typename _ForwardIterator2,
05285        typename _BinaryPredicate>
05286     inline _ForwardIterator1
05287     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
05288          _ForwardIterator2 __first2, _ForwardIterator2 __last2,
05289          _BinaryPredicate __comp)
05290     {
05291       // concept requirements
05292       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
05293       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
05294       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
05295         typename iterator_traits<_ForwardIterator1>::value_type,
05296         typename iterator_traits<_ForwardIterator2>::value_type>)
05297       __glibcxx_requires_valid_range(__first1, __last1);
05298       __glibcxx_requires_valid_range(__first2, __last2);
05299 
05300       return std::__find_end(__first1, __last1, __first2, __last2,
05301                  std::__iterator_category(__first1),
05302                  std::__iterator_category(__first2),
05303                  __comp);
05304     }
05305 
05306 } // namespace std
05307 
05308 #endif /* _ALGO_H */