epoc32/include/tools/stlport/stl/_algo.c
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100 (2010-03-31)
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     1 /*
     2  *
     3  * Copyright (c) 1994
     4  * Hewlett-Packard Company
     5  *
     6  * Copyright (c) 1996,1997
     7  * Silicon Graphics Computer Systems, Inc.
     8  *
     9  * Copyright (c) 1997
    10  * Moscow Center for SPARC Technology
    11  *
    12  * Copyright (c) 1999
    13  * Boris Fomitchev
    14  *
    15  * This material is provided "as is", with absolutely no warranty expressed
    16  * or implied. Any use is at your own risk.
    17  *
    18  * Permission to use or copy this software for any purpose is hereby granted
    19  * without fee, provided the above notices are retained on all copies.
    20  * Permission to modify the code and to distribute modified code is granted,
    21  * provided the above notices are retained, and a notice that the code was
    22  * modified is included with the above copyright notice.
    23  *
    24  */
    25 
    26 #ifndef _STLP_ALGO_C
    27 #define _STLP_ALGO_C
    28 
    29 #if !defined (_STLP_INTERNAL_ALGO_H)
    30 #  include <stl/_algo.h>
    31 #endif
    32 
    33 #ifndef _STLP_INTERNAL_TEMPBUF_H
    34 #  include <stl/_tempbuf.h>
    35 #endif
    36 
    37 _STLP_BEGIN_NAMESPACE
    38 
    39 _STLP_MOVE_TO_PRIV_NAMESPACE
    40 
    41 template <class _BidirectionalIter, class _Distance, class _Compare>
    42 void __merge_without_buffer(_BidirectionalIter __first,
    43                             _BidirectionalIter __middle,
    44                             _BidirectionalIter __last,
    45                             _Distance __len1, _Distance __len2,
    46                             _Compare __comp);
    47 
    48 
    49 template <class _BidirectionalIter1, class _BidirectionalIter2,
    50           class _BidirectionalIter3, class _Compare>
    51 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
    52                                      _BidirectionalIter1 __last1,
    53                                      _BidirectionalIter2 __first2,
    54                                      _BidirectionalIter2 __last2,
    55                                      _BidirectionalIter3 __result,
    56                                      _Compare __comp);
    57 
    58 template <class _Tp>
    59 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
    60 inline
    61 #endif
    62 const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
    63   if (__a < __b)
    64     if (__b < __c)
    65       return __b;
    66     else if (__a < __c)
    67       return __c;
    68     else
    69       return __a;
    70   else if (__a < __c)
    71     return __a;
    72   else if (__b < __c)
    73     return __c;
    74   else
    75     return __b;
    76 }
    77 
    78 template <class _Tp, class _Compare>
    79 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
    80 inline
    81 #endif
    82 const _Tp&
    83 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
    84   if (__comp(__a, __b)) {
    85     _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
    86     if (__comp(__b, __c)) {
    87       _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
    88       return __b;
    89     }
    90     else if (__comp(__a, __c)) {
    91       _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
    92       return __c;
    93     }
    94     else
    95       return __a;
    96   }
    97   else if (__comp(__a, __c)) {
    98     _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
    99     return __a;
   100   }
   101   else if (__comp(__b, __c)) {
   102     _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
   103     return __c;
   104   }
   105   else
   106     return __b;
   107 }
   108 
   109 _STLP_MOVE_TO_STD_NAMESPACE
   110 
   111 template <class _ForwardIter1, class _ForwardIter2>
   112 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
   113                      _ForwardIter2 __first2, _ForwardIter2 __last2) {
   114   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
   115   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
   116   // Test for empty ranges
   117   if (__first1 == __last1 || __first2 == __last2)
   118     return __first1;
   119 
   120   // Test for a pattern of length 1.
   121   _ForwardIter2 __tmp(__first2);
   122   ++__tmp;
   123   if (__tmp == __last2)
   124     return find(__first1, __last1, *__first2);
   125 
   126   // General case.
   127   _ForwardIter2 __p1 = __first2;
   128   ++__p1;
   129 
   130   _ForwardIter1 __current;// = __first1;
   131 
   132   while (__first1 != __last1) {
   133     __first1 = find(__first1, __last1, *__first2);
   134     if (__first1 == __last1)
   135       return __last1;
   136 
   137     _ForwardIter2 __p = __p1;
   138     __current = __first1;
   139     if (++__current == __last1)
   140       return __last1;
   141 
   142     while (*__current == *__p) {
   143       if (++__p == __last2)
   144         return __first1;
   145       if (++__current == __last1)
   146         return __last1;
   147     }
   148 
   149     ++__first1;
   150   }
   151   return __first1;
   152 }
   153 
   154 _STLP_MOVE_TO_PRIV_NAMESPACE
   155 
   156 template <class _RandomAccessIter, class _Integer, class _Tp,
   157           class _BinaryPred, class _Distance>
   158 _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
   159                              _Integer __count, const _Tp& __val, _BinaryPred __pred,
   160                              _Distance*, const random_access_iterator_tag &)
   161 {
   162   _Distance __tailSize = __last - __first;
   163   const _Distance __pattSize = __count;
   164   const _Distance __skipOffset = __pattSize - 1;
   165   _RandomAccessIter __backTrack;
   166   _Distance __remainder, __prevRemainder;
   167 
   168   for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop...
   169     //__lookAhead here is always pointing to the last element of next possible match.
   170     __tailSize -= __pattSize;
   171 
   172     while ( !__pred(*__lookAhead, __val) ) { // the skip loop...
   173       if (__tailSize < __pattSize)
   174         return __last;
   175 
   176       __lookAhead += __pattSize;
   177       __tailSize -= __pattSize;
   178     }
   179 
   180     if ( __skipOffset == 0 ) {
   181       return (__lookAhead - __skipOffset); //Success
   182     }
   183 
   184     __remainder = __skipOffset;
   185 
   186     for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {
   187       if (--__remainder == 0)
   188         return (__lookAhead - __skipOffset); //Success
   189     }
   190 
   191     if (__remainder > __tailSize)
   192       return __last; //failure
   193 
   194     __lookAhead += __remainder;
   195     __tailSize -= __remainder;
   196 
   197     while ( __pred(*__lookAhead, __val) ) {
   198       __prevRemainder = __remainder;
   199       __backTrack = __lookAhead;
   200 
   201       do {
   202         if (--__remainder == 0)
   203           return (__lookAhead - __skipOffset); //Success
   204       } while (__pred(*--__backTrack, __val));
   205 
   206       //adjust remainder for next comparison
   207       __remainder += __pattSize - __prevRemainder;
   208 
   209       if (__remainder > __tailSize)
   210         return __last; //failure
   211 
   212       __lookAhead += __remainder;
   213       __tailSize -= __remainder;
   214     }
   215 
   216     //__lookAhead here is always pointing to the element of the last mismatch.
   217   }
   218 
   219   return __last; //failure
   220 }
   221 
   222 template <class _ForwardIter, class _Integer, class _Tp,
   223           class _Distance, class _BinaryPred>
   224 _ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,
   225                         _Integer __count, const _Tp& __val, _BinaryPred __pred,
   226                         _Distance*, const forward_iterator_tag &) {
   227   for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}
   228   while (__first != __last) {
   229     _Integer __n = __count - 1;
   230     _ForwardIter __i = __first;
   231     ++__i;
   232     while (__i != __last && __n != 0 && __pred(*__i, __val)) {
   233       ++__i;
   234       --__n;
   235     }
   236     if (__n == 0)
   237       return __first;
   238     else if (__i != __last)
   239       for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}
   240     else
   241       break;
   242   }
   243   return __last;
   244 }
   245 
   246 _STLP_MOVE_TO_STD_NAMESPACE
   247 
   248 // search_n.  Search for __count consecutive copies of __val.
   249 template <class _ForwardIter, class _Integer, class _Tp>
   250 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
   251                       _Integer __count, const _Tp& __val) {
   252   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   253   if (__count <= 0)
   254     return __first;
   255   if (__count == 1)
   256     //We use find when __count == 1 to use potential find overload.
   257     return find(__first, __last, __val);
   258   return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(),
   259                                _STLP_DISTANCE_TYPE(__first, _ForwardIter),
   260                                _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   261 }
   262 
   263 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
   264 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
   265                       _Integer __count, const _Tp& __val,
   266                       _BinaryPred __binary_pred) {
   267   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   268   if (__count <= 0)
   269     return __first;
   270   return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred,
   271                                _STLP_DISTANCE_TYPE(__first, _ForwardIter),
   272                                _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   273 }
   274 
   275 template <class _ForwardIter1, class _ForwardIter2>
   276 _ForwardIter1
   277 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
   278          _ForwardIter2 __first2, _ForwardIter2 __last2) {
   279   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
   280   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
   281   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
   282 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
   283                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
   284                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
   285 #else
   286                                forward_iterator_tag(),
   287                                forward_iterator_tag(),
   288 #endif
   289                                _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
   290     );
   291 }
   292 
   293 // unique and unique_copy
   294 _STLP_MOVE_TO_PRIV_NAMESPACE
   295 
   296 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
   297           class _Tp>
   298 _STLP_INLINE_LOOP _OutputIterator
   299 __unique_copy(_InputIterator __first, _InputIterator __last,
   300               _OutputIterator __result,
   301               _BinaryPredicate __binary_pred, _Tp*) {
   302   _Tp __val = *__first;
   303   *__result = __val;
   304   while (++__first != __last)
   305     if (!__binary_pred(__val, *__first)) {
   306       __val = *__first;
   307       *++__result = __val;
   308     }
   309   return ++__result;
   310 }
   311 
   312 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
   313 inline _OutputIter
   314 __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
   315               _BinaryPredicate __binary_pred, const output_iterator_tag &) {
   316   return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));
   317 }
   318 
   319 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
   320 _STLP_INLINE_LOOP _ForwardIter
   321 __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,
   322               _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
   323   *__result = *__first;
   324   while (++__first != __last)
   325     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
   326   return ++__result;
   327 }
   328 
   329 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
   330 template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
   331 inline _BidirectionalIterator
   332 __unique_copy(_InputIterator __first, _InputIterator __last,
   333               _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
   334               const bidirectional_iterator_tag &) {
   335   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
   336 }
   337 
   338 template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
   339 inline _RandomAccessIterator
   340 __unique_copy(_InputIterator __first, _InputIterator __last,
   341               _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
   342               const random_access_iterator_tag &) {
   343   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
   344 }
   345 #endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
   346 
   347 _STLP_MOVE_TO_STD_NAMESPACE
   348 
   349 template <class _InputIter, class _OutputIter>
   350 _OutputIter
   351 unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
   352   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   353   if (__first == __last) return __result;
   354   return _STLP_PRIV __unique_copy(__first, __last, __result,
   355                                   _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
   356                                   _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
   357 }
   358 
   359 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
   360 _OutputIter
   361 unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
   362             _BinaryPredicate __binary_pred) {
   363   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   364   if (__first == __last) return __result;
   365   return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,
   366                                   _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
   367 }
   368 
   369 // rotate and rotate_copy, and their auxiliary functions
   370 _STLP_MOVE_TO_PRIV_NAMESPACE
   371 
   372 template <class _ForwardIter, class _Distance>
   373 _ForwardIter __rotate_aux(_ForwardIter __first,
   374                           _ForwardIter __middle,
   375                           _ForwardIter __last,
   376                           _Distance*,
   377                           const forward_iterator_tag &) {
   378   if (__first == __middle)
   379     return __last;
   380   if (__last  == __middle)
   381     return __first;
   382 
   383   _ForwardIter __first2 = __middle;
   384   do {
   385     swap(*__first++, *__first2++);
   386     if (__first == __middle)
   387       __middle = __first2;
   388   } while (__first2 != __last);
   389 
   390   _ForwardIter __new_middle = __first;
   391 
   392   __first2 = __middle;
   393 
   394   while (__first2 != __last) {
   395     swap (*__first++, *__first2++);
   396     if (__first == __middle)
   397       __middle = __first2;
   398     else if (__first2 == __last)
   399       __first2 = __middle;
   400   }
   401 
   402   return __new_middle;
   403 }
   404 
   405 template <class _BidirectionalIter, class _Distance>
   406 _BidirectionalIter __rotate_aux(_BidirectionalIter __first,
   407                                 _BidirectionalIter __middle,
   408                                 _BidirectionalIter __last,
   409                                 _Distance*,
   410                                 const bidirectional_iterator_tag &) {
   411   if (__first == __middle)
   412     return __last;
   413   if (__last  == __middle)
   414     return __first;
   415 
   416   __reverse(__first,  __middle, bidirectional_iterator_tag());
   417   __reverse(__middle, __last,   bidirectional_iterator_tag());
   418 
   419   while (__first != __middle && __middle != __last)
   420     swap (*__first++, *--__last);
   421 
   422   if (__first == __middle) {
   423     __reverse(__middle, __last,   bidirectional_iterator_tag());
   424     return __last;
   425   }
   426   else {
   427     __reverse(__first,  __middle, bidirectional_iterator_tag());
   428     return __first;
   429   }
   430 }
   431 
   432 template <class _RandomAccessIter, class _Distance, class _Tp>
   433 _RandomAccessIter __rotate_aux(_RandomAccessIter __first,
   434                                _RandomAccessIter __middle,
   435                                _RandomAccessIter __last,
   436                                _Distance *, _Tp *) {
   437 
   438   _Distance __n = __last   - __first;
   439   _Distance __k = __middle - __first;
   440   _Distance __l = __n - __k;
   441   _RandomAccessIter __result = __first + (__last - __middle);
   442 
   443   if (__k == 0)  /* __first == middle */
   444     return __last;
   445 
   446   if (__k == __l) {
   447     swap_ranges(__first, __middle, __middle);
   448     return __result;
   449   }
   450 
   451   _Distance __d = __gcd(__n, __k);
   452 
   453   for (_Distance __i = 0; __i < __d; __i++) {
   454     _Tp __tmp = *__first;
   455     _RandomAccessIter __p = __first;
   456 
   457     if (__k < __l) {
   458       for (_Distance __j = 0; __j < __l/__d; __j++) {
   459         if (__p > __first + __l) {
   460           *__p = *(__p - __l);
   461           __p -= __l;
   462         }
   463 
   464         *__p = *(__p + __k);
   465         __p += __k;
   466       }
   467     }
   468 
   469     else {
   470       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
   471         if (__p < __last - __k) {
   472           *__p = *(__p + __k);
   473           __p += __k;
   474         }
   475 
   476         *__p = * (__p - __l);
   477         __p -= __l;
   478       }
   479     }
   480 
   481     *__p = __tmp;
   482     ++__first;
   483   }
   484 
   485   return __result;
   486 }
   487 
   488 template <class _RandomAccessIter, class _Distance>
   489 inline _RandomAccessIter
   490 __rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
   491              _Distance * __dis, const random_access_iterator_tag &) {
   492   return __rotate_aux(__first, __middle, __last,
   493                       __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
   494 }
   495 
   496 template <class _ForwardIter>
   497 _ForwardIter
   498 __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
   499   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
   500   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
   501   return __rotate_aux(__first, __middle, __last,
   502                       _STLP_DISTANCE_TYPE(__first, _ForwardIter),
   503                       _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   504 }
   505 
   506 _STLP_MOVE_TO_STD_NAMESPACE
   507 
   508 template <class _ForwardIter>
   509 void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
   510   _STLP_PRIV __rotate(__first, __middle, __last);
   511 }
   512 
   513 // Return a random number in the range [0, __n).  This function encapsulates
   514 // whether we're using rand (part of the standard C library) or lrand48
   515 // (not standard, but a much better choice whenever it's available).
   516 _STLP_MOVE_TO_PRIV_NAMESPACE
   517 
   518 template <class _Distance>
   519 inline _Distance __random_number(_Distance __n) {
   520 #ifdef _STLP_NO_DRAND48
   521   return rand() % __n;
   522 #else
   523   return lrand48() % __n;
   524 #endif
   525 }
   526 
   527 _STLP_MOVE_TO_STD_NAMESPACE
   528 
   529 template <class _RandomAccessIter>
   530 void random_shuffle(_RandomAccessIter __first,
   531                     _RandomAccessIter __last) {
   532   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   533   if (__first == __last) return;
   534   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
   535     iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1));
   536 }
   537 
   538 template <class _RandomAccessIter, class _RandomNumberGenerator>
   539 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
   540                     _RandomNumberGenerator &__rand) {
   541   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   542   if (__first == __last) return;
   543   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
   544     iter_swap(__i, __first + __rand((__i - __first) + 1));
   545 }
   546 
   547 #if !defined (_STLP_NO_EXTENSIONS)
   548 // random_sample and random_sample_n (extensions, not part of the standard).
   549 template <class _ForwardIter, class _OutputIter, class _Distance>
   550 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
   551                             _OutputIter __out_ite, const _Distance __n) {
   552   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   553   _Distance __remaining = distance(__first, __last);
   554   _Distance __m = (min) (__n, __remaining);
   555 
   556   while (__m > 0) {
   557     if (_STLP_PRIV __random_number(__remaining) < __m) {
   558       *__out_ite = *__first;
   559       ++__out_ite;
   560       --__m;
   561     }
   562 
   563     --__remaining;
   564     ++__first;
   565   }
   566   return __out_ite;
   567 }
   568 
   569 
   570 template <class _ForwardIter, class _OutputIter, class _Distance,
   571           class _RandomNumberGenerator>
   572 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
   573                             _OutputIter __out_ite, const _Distance __n,
   574                             _RandomNumberGenerator& __rand) {
   575   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   576   _Distance __remaining = distance(__first, __last);
   577   _Distance __m = (min) (__n, __remaining);
   578 
   579   while (__m > 0) {
   580     if (__rand(__remaining) < __m) {
   581       *__out_ite = *__first;
   582       ++__out_ite;
   583       --__m;
   584     }
   585 
   586     --__remaining;
   587     ++__first;
   588   }
   589   return __out_ite;
   590 }
   591 
   592 _STLP_MOVE_TO_PRIV_NAMESPACE
   593 
   594 template <class _InputIter, class _RandomAccessIter, class _Distance>
   595 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
   596                                   _RandomAccessIter __out_ite,
   597                                   const _Distance __n) {
   598   _Distance __m = 0;
   599   _Distance __t = __n;
   600   for ( ; __first != __last && __m < __n; ++__m, ++__first)
   601     __out_ite[__m] = *__first;
   602 
   603   while (__first != __last) {
   604     ++__t;
   605     _Distance __M = __random_number(__t);
   606     if (__M < __n)
   607       __out_ite[__M] = *__first;
   608     ++__first;
   609   }
   610 
   611   return __out_ite + __m;
   612 }
   613 
   614 template <class _InputIter, class _RandomAccessIter,
   615           class _RandomNumberGenerator, class _Distance>
   616 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
   617                                   _RandomAccessIter __out_ite,
   618                                   _RandomNumberGenerator& __rand,
   619                                   const _Distance __n) {
   620   _Distance __m = 0;
   621   _Distance __t = __n;
   622   for ( ; __first != __last && __m < __n; ++__m, ++__first)
   623     __out_ite[__m] = *__first;
   624 
   625   while (__first != __last) {
   626     ++__t;
   627     _Distance __M = __rand(__t);
   628     if (__M < __n)
   629       __out_ite[__M] = *__first;
   630     ++__first;
   631   }
   632 
   633   return __out_ite + __m;
   634 }
   635 
   636 _STLP_MOVE_TO_STD_NAMESPACE
   637 
   638 template <class _InputIter, class _RandomAccessIter>
   639 _RandomAccessIter
   640 random_sample(_InputIter __first, _InputIter __last,
   641               _RandomAccessIter __out_first, _RandomAccessIter __out_last) {
   642   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   643   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
   644   return _STLP_PRIV __random_sample(__first, __last,
   645                                     __out_first, __out_last - __out_first);
   646 }
   647 
   648 template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
   649 _RandomAccessIter
   650 random_sample(_InputIter __first, _InputIter __last,
   651               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
   652               _RandomNumberGenerator& __rand) {
   653   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   654   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
   655   return _STLP_PRIV __random_sample(__first, __last,
   656                                     __out_first, __rand,
   657                                     __out_last - __out_first);
   658 }
   659 
   660 #endif /* _STLP_NO_EXTENSIONS */
   661 
   662 // partition, stable_partition, and their auxiliary functions
   663 _STLP_MOVE_TO_PRIV_NAMESPACE
   664 
   665 template <class _ForwardIter, class _Predicate>
   666 _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
   667                                            _ForwardIter __last,
   668                                            _Predicate   __pred,
   669                                            const forward_iterator_tag &) {
   670   if (__first == __last) return __first;
   671 
   672   while (__pred(*__first))
   673     if (++__first == __last) return __first;
   674 
   675   _ForwardIter __next = __first;
   676 
   677   while (++__next != __last) {
   678     if (__pred(*__next)) {
   679       swap(*__first, *__next);
   680       ++__first;
   681     }
   682   }
   683   return __first;
   684 }
   685 
   686 template <class _BidirectionalIter, class _Predicate>
   687 _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
   688                                                  _BidirectionalIter __last,
   689                                                  _Predicate __pred,
   690                                                  const bidirectional_iterator_tag &) {
   691   for (;;) {
   692     for (;;) {
   693       if (__first == __last)
   694         return __first;
   695       else if (__pred(*__first))
   696         ++__first;
   697       else
   698         break;
   699     }
   700     --__last;
   701     for (;;) {
   702       if (__first == __last)
   703         return __first;
   704       else if (!__pred(*__last))
   705         --__last;
   706       else
   707         break;
   708     }
   709     iter_swap(__first, __last);
   710     ++__first;
   711   }
   712 }
   713 
   714 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
   715 template <class _BidirectionalIter, class _Predicate>
   716 inline
   717 _BidirectionalIter __partition(_BidirectionalIter __first,
   718                                _BidirectionalIter __last,
   719                                _Predicate __pred,
   720                                const random_access_iterator_tag &) {
   721   return __partition(__first, __last, __pred, bidirectional_iterator_tag());
   722 }
   723 #endif
   724 
   725 _STLP_MOVE_TO_STD_NAMESPACE
   726 
   727 template <class _ForwardIter, class _Predicate>
   728 _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred) {
   729   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   730   return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   731 }
   732 
   733 
   734 /* __pred_of_first: false if we know that __pred(*__first) is false,
   735  *                  true when we don't know the result of __pred(*__first).
   736  * __not_pred_of_before_last: true if we know that __pred(*--__last) is true,
   737  *                            false when we don't know the result of __pred(*--__last).
   738  */
   739 _STLP_MOVE_TO_PRIV_NAMESPACE
   740 
   741 template <class _ForwardIter, class _Predicate, class _Distance>
   742 _ForwardIter __inplace_stable_partition(_ForwardIter __first,
   743                                         _ForwardIter __last,
   744                                         _Predicate __pred, _Distance __len,
   745                                         bool __pred_of_first, bool __pred_of_before_last) {
   746   if (__len == 1)
   747     return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
   748   _ForwardIter __middle = __first;
   749   _Distance __half_len = __len / 2;
   750   advance(__middle, __half_len);
   751   return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
   752                   __middle,
   753                   __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
   754 }
   755 
   756 template <class _ForwardIter, class _Pointer, class _Predicate,
   757           class _Distance>
   758 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
   759                                          _ForwardIter __last,
   760                                          _Predicate __pred, _Distance __len,
   761                                          _Pointer __buffer, _Distance __buffer_size,
   762                                          bool __pred_of_first, bool __pred_of_before_last) {
   763   if (__len <= __buffer_size) {
   764     _ForwardIter __result1 = __first;
   765     _Pointer __result2 = __buffer;
   766     if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {
   767       *__result2 = *__first;
   768       ++__result2; ++__first; --__len;
   769     }
   770     for (; __first != __last ; ++__first, --__len) {
   771       if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||
   772           ((__len != 1) && __pred(*__first))){
   773         *__result1 = *__first;
   774         ++__result1;
   775       }
   776       else {
   777         *__result2 = *__first;
   778         ++__result2;
   779       }
   780     }
   781     copy(__buffer, __result2, __result1);
   782     return __result1;
   783   }
   784   else {
   785     _ForwardIter __middle = __first;
   786     _Distance __half_len = __len / 2;
   787     advance(__middle, __half_len);
   788     return __rotate(__stable_partition_adaptive(
   789                           __first, __middle, __pred,
   790                           __half_len, __buffer, __buffer_size,
   791                           __pred_of_first, false),
   792                     __middle,
   793                     __stable_partition_adaptive(
   794                           __middle, __last, __pred,
   795                           __len - __half_len, __buffer, __buffer_size,
   796                           true, __pred_of_before_last));
   797   }
   798 }
   799 
   800 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
   801 inline _ForwardIter
   802 __stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
   803                            _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {
   804   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
   805   _STLP_MPWFIX_TRY    //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
   806   return (__buf.size() > 0) ?
   807     __stable_partition_adaptive(__first, __last, __pred,
   808                                 _Distance(__buf.requested_size()),
   809                                 __buf.begin(), __buf.size(),
   810                                 false, __pred_of_before_last)  :
   811     __inplace_stable_partition(__first, __last, __pred,
   812                                _Distance(__buf.requested_size()),
   813                                false, __pred_of_before_last);
   814   _STLP_MPWFIX_CATCH  //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
   815 }
   816 
   817 template <class _ForwardIter, class _Predicate>
   818 _ForwardIter
   819 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
   820                        const forward_iterator_tag &) {
   821   return __stable_partition_aux_aux(__first, __last, __pred,
   822                                     _STLP_VALUE_TYPE(__first, _ForwardIter),
   823                                     _STLP_DISTANCE_TYPE(__first, _ForwardIter));
   824 }
   825 
   826 template <class _BidirectIter, class _Predicate>
   827 _BidirectIter
   828 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
   829                        const bidirectional_iterator_tag &) {
   830   for (--__last;;) {
   831     if (__first == __last)
   832       return __first;
   833     else if (!__pred(*__last))
   834       --__last;
   835     else
   836       break;
   837   }
   838   ++__last;
   839   //Here we know that __pred(*--__last) is true
   840   return __stable_partition_aux_aux(__first, __last, __pred,
   841                                     _STLP_VALUE_TYPE(__first, _BidirectIter),
   842                                     _STLP_DISTANCE_TYPE(__first, _BidirectIter), true);
   843 }
   844 
   845 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
   846 template <class _BidirectIter, class _Predicate>
   847 _BidirectIter
   848 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
   849                        const random_access_iterator_tag &) {
   850   return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag());
   851 }
   852 #endif
   853 
   854 _STLP_MOVE_TO_STD_NAMESPACE
   855 
   856 template <class _ForwardIter, class _Predicate>
   857 _ForwardIter
   858 stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
   859   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   860   for (;;) {
   861     if (__first == __last)
   862       return __first;
   863     else if (__pred(*__first))
   864       ++__first;
   865     else
   866       break;
   867   }
   868   return _STLP_PRIV __stable_partition_aux(__first, __last, __pred,
   869                                            _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   870 }
   871 
   872 _STLP_MOVE_TO_PRIV_NAMESPACE
   873 
   874 template <class _RandomAccessIter, class _Tp, class _Compare>
   875 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
   876                                         _RandomAccessIter __last,
   877                                         _Tp __pivot, _Compare __comp) {
   878   for (;;) {
   879     while (__comp(*__first, __pivot)) {
   880       _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
   881       ++__first;
   882     }
   883     --__last;
   884     while (__comp(__pivot, *__last)) {
   885       _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
   886       --__last;
   887     }
   888     if (!(__first < __last))
   889       return __first;
   890     iter_swap(__first, __last);
   891     ++__first;
   892   }
   893 }
   894 
   895 // sort() and its auxiliary functions.
   896 #define __stl_threshold  16
   897 
   898 template <class _RandomAccessIter, class _Tp, class _Compare>
   899 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
   900                                _Compare __comp) {
   901   _RandomAccessIter __next = __last;
   902   --__next;
   903   while (__comp(__val, *__next)) {
   904     _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
   905     *__last = *__next;
   906     __last = __next;
   907     --__next;
   908   }
   909   *__last = __val;
   910 }
   911 
   912 template <class _RandomAccessIter, class _Tp, class _Compare>
   913 inline void __linear_insert(_RandomAccessIter __first,
   914                             _RandomAccessIter __last, _Tp __val, _Compare __comp) {
   915   //*TY 12/26/1998 - added __val as a paramter
   916   //  _Tp __val = *__last;        //*TY 12/26/1998 - __val supplied by caller
   917   if (__comp(__val, *__first)) {
   918     _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
   919     copy_backward(__first, __last, __last + 1);
   920     *__first = __val;
   921   }
   922   else
   923     __unguarded_linear_insert(__last, __val, __comp);
   924 }
   925 
   926 template <class _RandomAccessIter, class _Tp, class _Compare>
   927 void __insertion_sort(_RandomAccessIter __first,
   928                       _RandomAccessIter __last,
   929                       _Tp *, _Compare __comp) {
   930   if (__first == __last) return;
   931   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
   932     __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp);  //*TY 12/26/1998 - supply *__i as __val
   933 }
   934 
   935 template <class _RandomAccessIter, class _Tp, class _Compare>
   936 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
   937                                     _RandomAccessIter __last,
   938                                     _Tp*, _Compare __comp) {
   939   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
   940     __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);
   941 }
   942 
   943 template <class _RandomAccessIter, class _Compare>
   944 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
   945                                        _RandomAccessIter __last,
   946                                        _Compare __comp) {
   947   __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
   948 }
   949 
   950 template <class _RandomAccessIter, class _Compare>
   951 void __final_insertion_sort(_RandomAccessIter __first,
   952                             _RandomAccessIter __last, _Compare __comp) {
   953   if (__last - __first > __stl_threshold) {
   954     __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
   955     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
   956   }
   957   else
   958     __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
   959 }
   960 
   961 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
   962 void __introsort_loop(_RandomAccessIter __first,
   963                       _RandomAccessIter __last, _Tp*,
   964                       _Size __depth_limit, _Compare __comp) {
   965   while (__last - __first > __stl_threshold) {
   966     if (__depth_limit == 0) {
   967       partial_sort(__first, __last, __last, __comp);
   968       return;
   969     }
   970     --__depth_limit;
   971     _RandomAccessIter __cut =
   972       __unguarded_partition(__first, __last,
   973                             _Tp(__median(*__first,
   974                                          *(__first + (__last - __first)/2),
   975                                          *(__last - 1), __comp)),
   976        __comp);
   977     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
   978     __last = __cut;
   979   }
   980 }
   981 
   982 _STLP_MOVE_TO_STD_NAMESPACE
   983 
   984 template <class _RandomAccessIter>
   985 void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
   986   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   987   if (__first != __last) {
   988     _STLP_PRIV __introsort_loop(__first, __last,
   989                                 _STLP_VALUE_TYPE(__first, _RandomAccessIter),
   990                                 _STLP_PRIV __lg(__last - __first) * 2,
   991                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
   992     _STLP_PRIV __final_insertion_sort(__first, __last,
   993                                       _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
   994   }
   995 }
   996 
   997 template <class _RandomAccessIter, class _Compare>
   998 void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
   999   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1000   if (__first != __last) {
  1001     _STLP_PRIV __introsort_loop(__first, __last,
  1002                                 _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1003                                 _STLP_PRIV __lg(__last - __first) * 2, __comp);
  1004     _STLP_PRIV __final_insertion_sort(__first, __last, __comp);
  1005   }
  1006 }
  1007 
  1008 // stable_sort() and its auxiliary functions.
  1009 _STLP_MOVE_TO_PRIV_NAMESPACE
  1010 
  1011 template <class _RandomAccessIter, class _Compare>
  1012 void __inplace_stable_sort(_RandomAccessIter __first,
  1013                            _RandomAccessIter __last, _Compare __comp) {
  1014   if (__last - __first < 15) {
  1015     __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  1016     return;
  1017   }
  1018   _RandomAccessIter __middle = __first + (__last - __first) / 2;
  1019   __inplace_stable_sort(__first, __middle, __comp);
  1020   __inplace_stable_sort(__middle, __last, __comp);
  1021   __merge_without_buffer(__first, __middle, __last,
  1022                          __middle - __first,
  1023                          __last - __middle,
  1024                          __comp);
  1025 }
  1026 
  1027 template <class _RandomAccessIter1, class _RandomAccessIter2,
  1028           class _Distance, class _Compare>
  1029 void __merge_sort_loop(_RandomAccessIter1 __first,
  1030                        _RandomAccessIter1 __last,
  1031                        _RandomAccessIter2 __result, _Distance __step_size,
  1032                        _Compare __comp) {
  1033   _Distance __two_step = 2 * __step_size;
  1034 
  1035   while (__last - __first >= __two_step) {
  1036     __result = merge(__first, __first + __step_size,
  1037                      __first + __step_size, __first + __two_step,
  1038                      __result,
  1039                      __comp);
  1040     __first += __two_step;
  1041   }
  1042   __step_size = (min) (_Distance(__last - __first), __step_size);
  1043 
  1044   merge(__first, __first + __step_size,
  1045         __first + __step_size, __last,
  1046         __result,
  1047         __comp);
  1048 }
  1049 
  1050 const int __stl_chunk_size = 7;
  1051 
  1052 template <class _RandomAccessIter, class _Distance, class _Compare>
  1053 void __chunk_insertion_sort(_RandomAccessIter __first,
  1054                             _RandomAccessIter __last,
  1055                             _Distance __chunk_size, _Compare __comp) {
  1056   while (__last - __first >= __chunk_size) {
  1057     __insertion_sort(__first, __first + __chunk_size,
  1058                      _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  1059     __first += __chunk_size;
  1060   }
  1061   __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  1062 }
  1063 
  1064 template <class _RandomAccessIter, class _Pointer, class _Distance,
  1065           class _Compare>
  1066 void __merge_sort_with_buffer(_RandomAccessIter __first,
  1067                               _RandomAccessIter __last, _Pointer __buffer,
  1068                               _Distance*, _Compare __comp) {
  1069   _Distance __len = __last - __first;
  1070   _Pointer __buffer_last = __buffer + __len;
  1071 
  1072   _Distance __step_size = __stl_chunk_size;
  1073   __chunk_insertion_sort(__first, __last, __step_size, __comp);
  1074 
  1075   while (__step_size < __len) {
  1076     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
  1077     __step_size *= 2;
  1078     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
  1079     __step_size *= 2;
  1080   }
  1081 }
  1082 
  1083 template <class _BidirectionalIter1, class _BidirectionalIter2,
  1084           class _Distance>
  1085 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
  1086                                       _BidirectionalIter1 __middle,
  1087                                       _BidirectionalIter1 __last,
  1088                                       _Distance __len1, _Distance __len2,
  1089                                       _BidirectionalIter2 __buffer,
  1090                                       _Distance __buffer_size) {
  1091   if (__len1 > __len2 && __len2 <= __buffer_size) {
  1092     _BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);
  1093     copy_backward(__first, __middle, __last);
  1094     return copy(__buffer, __buffer_end, __first);
  1095   }
  1096   else if (__len1 <= __buffer_size) {
  1097     _BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);
  1098     copy(__middle, __last, __first);
  1099     return copy_backward(__buffer, __buffer_end, __last);
  1100   }
  1101   else
  1102     return __rotate(__first, __middle, __last);
  1103 }
  1104 
  1105 template <class _BidirectionalIter, class _Distance, class _Pointer,
  1106           class _Compare>
  1107 void __merge_adaptive(_BidirectionalIter __first,
  1108                       _BidirectionalIter __middle,
  1109                       _BidirectionalIter __last,
  1110                       _Distance __len1, _Distance __len2,
  1111                       _Pointer __buffer, _Distance __buffer_size,
  1112                       _Compare __comp) {
  1113   if (__len1 <= __len2 && __len1 <= __buffer_size) {
  1114     _Pointer __buffer_end = copy(__first, __middle, __buffer);
  1115     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  1116   }
  1117   else if (__len2 <= __buffer_size) {
  1118     _Pointer __buffer_end = copy(__middle, __last, __buffer);
  1119     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
  1120                      __comp);
  1121   }
  1122   else {
  1123     _BidirectionalIter __first_cut = __first;
  1124     _BidirectionalIter __second_cut = __middle;
  1125     _Distance __len11 = 0;
  1126     _Distance __len22 = 0;
  1127     if (__len1 > __len2) {
  1128       __len11 = __len1 / 2;
  1129       advance(__first_cut, __len11);
  1130       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  1131       __len22 += distance(__middle, __second_cut);
  1132     }
  1133     else {
  1134       __len22 = __len2 / 2;
  1135       advance(__second_cut, __len22);
  1136       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  1137       __len11 += distance(__first, __first_cut);
  1138     }
  1139     _BidirectionalIter __new_middle =
  1140       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
  1141                         __len22, __buffer, __buffer_size);
  1142     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  1143                      __len22, __buffer, __buffer_size, __comp);
  1144     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  1145                      __len2 - __len22, __buffer, __buffer_size, __comp);
  1146   }
  1147 }
  1148 
  1149 template <class _RandomAccessIter, class _Pointer, class _Distance,
  1150           class _Compare>
  1151 void __stable_sort_adaptive(_RandomAccessIter __first,
  1152                             _RandomAccessIter __last, _Pointer __buffer,
  1153                             _Distance __buffer_size, _Compare __comp) {
  1154   _Distance __len = (__last - __first + 1) / 2;
  1155   _RandomAccessIter __middle = __first + __len;
  1156   if (__len > __buffer_size) {
  1157     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
  1158                            __comp);
  1159     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
  1160                            __comp);
  1161   }
  1162   else {
  1163     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
  1164                                __comp);
  1165     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
  1166                                __comp);
  1167   }
  1168   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
  1169                    _Distance(__last - __middle), __buffer, __buffer_size,
  1170                    __comp);
  1171 }
  1172 
  1173 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
  1174 void __stable_sort_aux(_RandomAccessIter __first,
  1175                        _RandomAccessIter __last, _Tp*, _Distance*,
  1176                        _Compare __comp) {
  1177   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
  1178   if (buf.begin() == 0)
  1179     __inplace_stable_sort(__first, __last, __comp);
  1180   else
  1181     __stable_sort_adaptive(__first, __last, buf.begin(),
  1182                            _Distance(buf.size()),
  1183                            __comp);
  1184 }
  1185 
  1186 _STLP_MOVE_TO_STD_NAMESPACE
  1187 
  1188 template <class _RandomAccessIter>
  1189 void stable_sort(_RandomAccessIter __first,
  1190                  _RandomAccessIter __last) {
  1191   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1192   _STLP_PRIV __stable_sort_aux(__first, __last,
  1193                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1194                                _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
  1195                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1196 }
  1197 
  1198 template <class _RandomAccessIter, class _Compare>
  1199 void stable_sort(_RandomAccessIter __first,
  1200                  _RandomAccessIter __last, _Compare __comp) {
  1201   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1202   _STLP_PRIV __stable_sort_aux(__first, __last,
  1203                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1204                                _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
  1205                                __comp);
  1206 }
  1207 
  1208 // partial_sort, partial_sort_copy, and auxiliary functions.
  1209 _STLP_MOVE_TO_PRIV_NAMESPACE
  1210 
  1211 template <class _RandomAccessIter, class _Tp, class _Compare>
  1212 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
  1213                     _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1214   make_heap(__first, __middle, __comp);
  1215   for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {
  1216     if (__comp(*__i, *__first)) {
  1217       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1218       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
  1219                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
  1220     }
  1221   }
  1222   sort_heap(__first, __middle, __comp);
  1223 }
  1224 
  1225 _STLP_MOVE_TO_STD_NAMESPACE
  1226 
  1227 template <class _RandomAccessIter>
  1228 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
  1229                   _RandomAccessIter __last) {
  1230   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  1231   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  1232   _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1233                             _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1234 }
  1235 
  1236 template <class _RandomAccessIter, class _Compare>
  1237 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
  1238                   _RandomAccessIter __last, _Compare __comp) {
  1239   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  1240   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  1241   _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  1242 }
  1243 
  1244 _STLP_MOVE_TO_PRIV_NAMESPACE
  1245 
  1246 template <class _InputIter, class _RandomAccessIter, class _Compare,
  1247           class _Distance, class _Tp>
  1248 _RandomAccessIter __partial_sort_copy(_InputIter __first,
  1249                                       _InputIter __last,
  1250                                       _RandomAccessIter __result_first,
  1251                                       _RandomAccessIter __result_last,
  1252                                       _Compare __comp, _Distance*, _Tp*) {
  1253   if (__result_first == __result_last) return __result_last;
  1254   _RandomAccessIter __result_real_last = __result_first;
  1255   while(__first != __last && __result_real_last != __result_last) {
  1256     *__result_real_last = *__first;
  1257     ++__result_real_last;
  1258     ++__first;
  1259   }
  1260   make_heap(__result_first, __result_real_last, __comp);
  1261   while (__first != __last) {
  1262     if (__comp(*__first, *__result_first)) {
  1263       _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1264       __adjust_heap(__result_first, _Distance(0),
  1265                     _Distance(__result_real_last - __result_first),
  1266                     _Tp(*__first),
  1267                     __comp);
  1268     }
  1269     ++__first;
  1270   }
  1271   sort_heap(__result_first, __result_real_last, __comp);
  1272   return __result_real_last;
  1273 }
  1274 
  1275 _STLP_MOVE_TO_STD_NAMESPACE
  1276 
  1277 template <class _InputIter, class _RandomAccessIter>
  1278 _RandomAccessIter
  1279 partial_sort_copy(_InputIter __first, _InputIter __last,
  1280                   _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
  1281   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1282   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
  1283   return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
  1284                                         _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),
  1285                                         _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
  1286                                         _STLP_VALUE_TYPE(__first, _InputIter));
  1287 }
  1288 
  1289 template <class _InputIter, class _RandomAccessIter, class _Compare>
  1290 _RandomAccessIter
  1291 partial_sort_copy(_InputIter __first, _InputIter __last,
  1292                   _RandomAccessIter __result_first,
  1293                   _RandomAccessIter __result_last, _Compare __comp) {
  1294   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1295   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
  1296   return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
  1297                                         __comp,
  1298                                         _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
  1299                                         _STLP_VALUE_TYPE(__first, _InputIter));
  1300 }
  1301 
  1302 // nth_element() and its auxiliary functions.
  1303 _STLP_MOVE_TO_PRIV_NAMESPACE
  1304 
  1305 template <class _RandomAccessIter, class _Tp, class _Compare>
  1306 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1307                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1308   while (__last - __first > 3) {
  1309     _RandomAccessIter __cut =
  1310       __unguarded_partition(__first, __last,
  1311                             _Tp(__median(*__first,
  1312                                          *(__first + (__last - __first)/2),
  1313                                          *(__last - 1),
  1314                                          __comp)),
  1315                             __comp);
  1316     if (__cut <= __nth)
  1317       __first = __cut;
  1318     else
  1319       __last = __cut;
  1320   }
  1321   __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  1322 }
  1323 
  1324 _STLP_MOVE_TO_STD_NAMESPACE
  1325 
  1326 template <class _RandomAccessIter>
  1327 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1328                  _RandomAccessIter __last) {
  1329   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
  1330   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
  1331   _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1332                            _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1333 }
  1334 
  1335 template <class _RandomAccessIter, class _Compare>
  1336 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1337                  _RandomAccessIter __last, _Compare __comp) {
  1338   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
  1339   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
  1340   _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  1341 }
  1342 
  1343 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
  1344 _STLP_MOVE_TO_PRIV_NAMESPACE
  1345 
  1346 template <class _ForwardIter, class _Tp,
  1347           class _Compare1, class _Compare2, class _Distance>
  1348 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  1349                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
  1350   _Distance __len = distance(__first, __last);
  1351   _Distance __half;
  1352 
  1353   while (__len > 0) {
  1354     __half = __len >> 1;
  1355     _ForwardIter __middle = __first;
  1356     advance(__middle, __half);
  1357     if (__comp2(__val, *__middle)) {
  1358       _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1359       __len = __half;
  1360     }
  1361     else {
  1362       __first = __middle;
  1363       ++__first;
  1364       __len = __len - __half - 1;
  1365     }
  1366   }
  1367   return __first;
  1368 }
  1369 
  1370 template <class _ForwardIter, class _Tp,
  1371           class _Compare1, class _Compare2, class _Distance>
  1372 pair<_ForwardIter, _ForwardIter>
  1373 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  1374               _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {
  1375   _Distance __len = distance(__first, __last);
  1376   _Distance __half;
  1377 
  1378   while (__len > 0) {
  1379     __half = __len >> 1;
  1380     _ForwardIter __middle = __first;
  1381     advance(__middle, __half);
  1382     if (__comp1(*__middle, __val)) {
  1383       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1384       __first = __middle;
  1385       ++__first;
  1386       __len = __len - __half - 1;
  1387     }
  1388     else if (__comp2(__val, *__middle)) {
  1389       _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1390       __len = __half;
  1391     }
  1392     else {
  1393       _ForwardIter __left = __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);
  1394       //Small optim: If lower_bound haven't found an equivalent value
  1395       //there is no need to call upper_bound.
  1396       if (__comp1(*__left, __val)) {
  1397         _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1398         return pair<_ForwardIter, _ForwardIter>(__left, __left);
  1399       }
  1400       advance(__first, __len);
  1401       _ForwardIter __right = __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);
  1402       return pair<_ForwardIter, _ForwardIter>(__left, __right);
  1403     }
  1404   }
  1405   return pair<_ForwardIter, _ForwardIter>(__first, __first);
  1406 }
  1407 
  1408 _STLP_MOVE_TO_STD_NAMESPACE
  1409 
  1410 template <class _InputIter1, class _InputIter2, class _OutputIter>
  1411 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  1412                   _InputIter2 __first2, _InputIter2 __last2,
  1413                   _OutputIter __result) {
  1414   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1415   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1416   while (__first1 != __last1 && __first2 != __last2) {
  1417     if (*__first2 < *__first1) {
  1418       *__result = *__first2;
  1419       ++__first2;
  1420     }
  1421     else {
  1422       *__result = *__first1;
  1423       ++__first1;
  1424     }
  1425     ++__result;
  1426   }
  1427   return copy(__first2, __last2, copy(__first1, __last1, __result));
  1428 }
  1429 
  1430 template <class _InputIter1, class _InputIter2, class _OutputIter,
  1431           class _Compare>
  1432 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  1433                   _InputIter2 __first2, _InputIter2 __last2,
  1434                   _OutputIter __result, _Compare __comp) {
  1435   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1436   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1437   while (__first1 != __last1 && __first2 != __last2) {
  1438     if (__comp(*__first2, *__first1)) {
  1439       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1440       *__result = *__first2;
  1441       ++__first2;
  1442     }
  1443     else {
  1444       *__result = *__first1;
  1445       ++__first1;
  1446     }
  1447     ++__result;
  1448   }
  1449   return copy(__first2, __last2, copy(__first1, __last1, __result));
  1450 }
  1451 
  1452 _STLP_MOVE_TO_PRIV_NAMESPACE
  1453 
  1454 template <class _BidirectionalIter, class _Distance, class _Compare>
  1455 void __merge_without_buffer(_BidirectionalIter __first,
  1456                             _BidirectionalIter __middle,
  1457                             _BidirectionalIter __last,
  1458                             _Distance __len1, _Distance __len2,
  1459                             _Compare __comp) {
  1460   if (__len1 == 0 || __len2 == 0)
  1461     return;
  1462   if (__len1 + __len2 == 2) {
  1463     if (__comp(*__middle, *__first)) {
  1464       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1465       iter_swap(__first, __middle);
  1466     }
  1467     return;
  1468   }
  1469   _BidirectionalIter __first_cut = __first;
  1470   _BidirectionalIter __second_cut = __middle;
  1471   _Distance __len11 = 0;
  1472   _Distance __len22 = 0;
  1473   if (__len1 > __len2) {
  1474     __len11 = __len1 / 2;
  1475     advance(__first_cut, __len11);
  1476     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  1477     __len22 += distance(__middle, __second_cut);
  1478   }
  1479   else {
  1480     __len22 = __len2 / 2;
  1481     advance(__second_cut, __len22);
  1482     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  1483     __len11 +=distance(__first, __first_cut);
  1484   }
  1485   _BidirectionalIter __new_middle
  1486     = __rotate(__first_cut, __middle, __second_cut);
  1487   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
  1488                          __comp);
  1489   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
  1490                          __len2 - __len22, __comp);
  1491 }
  1492 
  1493 template <class _BidirectionalIter1, class _BidirectionalIter2,
  1494           class _BidirectionalIter3, class _Compare>
  1495 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  1496                                      _BidirectionalIter1 __last1,
  1497                                      _BidirectionalIter2 __first2,
  1498                                      _BidirectionalIter2 __last2,
  1499                                      _BidirectionalIter3 __result,
  1500                                      _Compare __comp) {
  1501   if (__first1 == __last1)
  1502     return copy_backward(__first2, __last2, __result);
  1503   if (__first2 == __last2)
  1504     return copy_backward(__first1, __last1, __result);
  1505   --__last1;
  1506   --__last2;
  1507   for (;;) {
  1508     if (__comp(*__last2, *__last1)) {
  1509       _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1510       *--__result = *__last1;
  1511       if (__first1 == __last1)
  1512         return copy_backward(__first2, ++__last2, __result);
  1513       --__last1;
  1514     }
  1515     else {
  1516       *--__result = *__last2;
  1517       if (__first2 == __last2)
  1518         return copy_backward(__first1, ++__last1, __result);
  1519       --__last2;
  1520     }
  1521   }
  1522 }
  1523 
  1524 template <class _BidirectionalIter, class _Tp,
  1525           class _Distance, class _Compare>
  1526 inline void __inplace_merge_aux(_BidirectionalIter __first,
  1527                                 _BidirectionalIter __middle,
  1528                                 _BidirectionalIter __last, _Tp*, _Distance*,
  1529                                 _Compare __comp) {
  1530   _Distance __len1 = distance(__first, __middle);
  1531   _Distance __len2 = distance(__middle, __last);
  1532 
  1533   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  1534   if (__buf.begin() == 0)
  1535     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  1536   else
  1537     __merge_adaptive(__first, __middle, __last, __len1, __len2,
  1538                      __buf.begin(), _Distance(__buf.size()),
  1539                      __comp);
  1540 }
  1541 
  1542 _STLP_MOVE_TO_STD_NAMESPACE
  1543 
  1544 template <class _BidirectionalIter>
  1545 void inplace_merge(_BidirectionalIter __first,
  1546                    _BidirectionalIter __middle,
  1547                    _BidirectionalIter __last) {
  1548   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  1549   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  1550   if (__first == __middle || __middle == __last)
  1551     return;
  1552   _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
  1553                                  _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
  1554                                  _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1555 }
  1556 
  1557 template <class _BidirectionalIter, class _Compare>
  1558 void inplace_merge(_BidirectionalIter __first,
  1559                    _BidirectionalIter __middle,
  1560                    _BidirectionalIter __last, _Compare __comp) {
  1561   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  1562   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  1563   if (__first == __middle || __middle == __last)
  1564     return;
  1565   _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
  1566                                  _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
  1567                                  __comp);
  1568 }
  1569 
  1570 _STLP_MOVE_TO_PRIV_NAMESPACE
  1571 
  1572 template <class _InputIter1, class _InputIter2, class _Compare>
  1573 bool __includes(_InputIter1 __first1, _InputIter1 __last1,
  1574                 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  1575   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1576   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1577   while (__first1 != __last1 && __first2 != __last2)
  1578     if (__comp(*__first2, *__first1)) {
  1579       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1580       return false;
  1581     }
  1582     else if (__comp(*__first1, *__first2))
  1583       ++__first1;
  1584     else
  1585       ++__first1, ++__first2;
  1586 
  1587   return __first2 == __last2;
  1588 }
  1589 
  1590 _STLP_MOVE_TO_STD_NAMESPACE
  1591 
  1592 template <class _InputIter1, class _InputIter2, class _Compare>
  1593 bool includes(_InputIter1 __first1, _InputIter1 __last1,
  1594               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  1595   return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp);
  1596 }
  1597 
  1598 template <class _InputIter1, class _InputIter2>
  1599 bool includes(_InputIter1 __first1, _InputIter1 __last1,
  1600               _InputIter2 __first2, _InputIter2 __last2) {
  1601   return _STLP_PRIV __includes(__first1, __last1, __first2, __last2,
  1602                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1603 }
  1604 
  1605 _STLP_MOVE_TO_PRIV_NAMESPACE
  1606 
  1607 template <class _InputIter1, class _InputIter2, class _OutputIter,
  1608           class _Compare>
  1609 _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
  1610                         _InputIter2 __first2, _InputIter2 __last2,
  1611                         _OutputIter __result, _Compare __comp) {
  1612   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1613   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1614   while (__first1 != __last1 && __first2 != __last2) {
  1615     if (__comp(*__first1, *__first2)) {
  1616       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1617       *__result = *__first1;
  1618       ++__first1;
  1619     }
  1620     else if (__comp(*__first2, *__first1)) {
  1621       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1622       *__result = *__first2;
  1623       ++__first2;
  1624     }
  1625     else {
  1626       *__result = *__first1;
  1627       ++__first1;
  1628       ++__first2;
  1629     }
  1630     ++__result;
  1631   }
  1632   return copy(__first2, __last2, copy(__first1, __last1, __result));
  1633 }
  1634 
  1635 _STLP_MOVE_TO_STD_NAMESPACE
  1636 
  1637 template <class _InputIter1, class _InputIter2, class _OutputIter>
  1638 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  1639                       _InputIter2 __first2, _InputIter2 __last2,
  1640                       _OutputIter __result) {
  1641   return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result,
  1642                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1643 }
  1644 
  1645 template <class _InputIter1, class _InputIter2, class _OutputIter,
  1646           class _Compare>
  1647 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  1648                       _InputIter2 __first2, _InputIter2 __last2,
  1649                       _OutputIter __result, _Compare __comp) {
  1650   return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp);
  1651 }
  1652 
  1653 _STLP_MOVE_TO_PRIV_NAMESPACE
  1654 
  1655 template <class _InputIter1, class _InputIter2, class _OutputIter,
  1656           class _Compare>
  1657 _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1658                                _InputIter2 __first2, _InputIter2 __last2,
  1659                                _OutputIter __result, _Compare __comp) {
  1660   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1661   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1662   while (__first1 != __last1 && __first2 != __last2)
  1663     if (__comp(*__first1, *__first2)) {
  1664       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1665       ++__first1;
  1666     }
  1667     else if (__comp(*__first2, *__first1))
  1668       ++__first2;
  1669     else {
  1670       *__result = *__first1;
  1671       ++__first1;
  1672       ++__first2;
  1673       ++__result;
  1674     }
  1675   return __result;
  1676 }
  1677 
  1678 _STLP_MOVE_TO_STD_NAMESPACE
  1679 
  1680 template <class _InputIter1, class _InputIter2, class _OutputIter>
  1681 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1682                              _InputIter2 __first2, _InputIter2 __last2,
  1683                              _OutputIter __result) {
  1684   return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result,
  1685                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1686 }
  1687 
  1688 template <class _InputIter1, class _InputIter2, class _OutputIter,
  1689           class _Compare>
  1690 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1691                              _InputIter2 __first2, _InputIter2 __last2,
  1692                              _OutputIter __result, _Compare __comp) {
  1693   return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
  1694 }
  1695 
  1696 _STLP_MOVE_TO_PRIV_NAMESPACE
  1697 
  1698 template <class _InputIter1, class _InputIter2, class _OutputIter,
  1699           class _Compare>
  1700 _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1701                              _InputIter2 __first2, _InputIter2 __last2,
  1702                              _OutputIter __result, _Compare __comp) {
  1703   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1704   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1705   while (__first1 != __last1 && __first2 != __last2)
  1706     if (__comp(*__first1, *__first2)) {
  1707       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1708       *__result = *__first1;
  1709       ++__first1;
  1710       ++__result;
  1711     }
  1712     else if (__comp(*__first2, *__first1))
  1713       ++__first2;
  1714     else {
  1715       ++__first1;
  1716       ++__first2;
  1717     }
  1718   return copy(__first1, __last1, __result);
  1719 }
  1720 
  1721 _STLP_MOVE_TO_STD_NAMESPACE
  1722 
  1723 template <class _InputIter1, class _InputIter2, class _OutputIter>
  1724 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1725                            _InputIter2 __first2, _InputIter2 __last2,
  1726                            _OutputIter __result) {
  1727   return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result,
  1728                                      _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1729 }
  1730 
  1731 template <class _InputIter1, class _InputIter2, class _OutputIter,
  1732           class _Compare>
  1733 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1734                            _InputIter2 __first2, _InputIter2 __last2,
  1735                            _OutputIter __result, _Compare __comp) {
  1736   return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
  1737 }
  1738 
  1739 _STLP_MOVE_TO_PRIV_NAMESPACE
  1740 
  1741 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
  1742 _OutputIter
  1743 __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1744                            _InputIter2 __first2, _InputIter2 __last2,
  1745                            _OutputIter __result, _Compare __comp) {
  1746   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1747   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1748   while (__first1 != __last1 && __first2 != __last2) {
  1749     if (__comp(*__first1, *__first2)) {
  1750       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1751       *__result = *__first1;
  1752       ++__first1;
  1753       ++__result;
  1754     }
  1755     else if (__comp(*__first2, *__first1)) {
  1756       *__result = *__first2;
  1757       ++__first2;
  1758       ++__result;
  1759     }
  1760     else {
  1761       ++__first1;
  1762       ++__first2;
  1763     }
  1764   }
  1765   return copy(__first2, __last2, copy(__first1, __last1, __result));
  1766 }
  1767 
  1768 _STLP_MOVE_TO_STD_NAMESPACE
  1769 
  1770 template <class _InputIter1, class _InputIter2, class _OutputIter>
  1771 _OutputIter
  1772 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1773                          _InputIter2 __first2, _InputIter2 __last2,
  1774                          _OutputIter __result) {
  1775   return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
  1776                                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1777 }
  1778 
  1779 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
  1780 _OutputIter
  1781 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1782                          _InputIter2 __first2, _InputIter2 __last2,
  1783                          _OutputIter __result,
  1784                          _Compare __comp) {
  1785   return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
  1786 }
  1787 
  1788 // min_element and max_element, with and without an explicitly supplied
  1789 // comparison function.
  1790 
  1791 template <class _ForwardIter>
  1792 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
  1793   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1794   if (__first == __last) return __first;
  1795   _ForwardIter __result = __first;
  1796   while (++__first != __last)
  1797     if (*__result < *__first)
  1798       __result = __first;
  1799   return __result;
  1800 }
  1801 
  1802 template <class _ForwardIter, class _Compare>
  1803 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
  1804                          _Compare __comp) {
  1805   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1806   if (__first == __last) return __first;
  1807   _ForwardIter __result = __first;
  1808   while (++__first != __last) {
  1809     if (__comp(*__result, *__first)) {
  1810       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1811       __result = __first;
  1812     }
  1813   }
  1814   return __result;
  1815 }
  1816 
  1817 template <class _ForwardIter>
  1818 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
  1819   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1820   if (__first == __last) return __first;
  1821   _ForwardIter __result = __first;
  1822   while (++__first != __last)
  1823     if (*__first < *__result)
  1824       __result = __first;
  1825   return __result;
  1826 }
  1827 
  1828 template <class _ForwardIter, class _Compare>
  1829 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
  1830                          _Compare __comp) {
  1831   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1832   if (__first == __last) return __first;
  1833   _ForwardIter __result = __first;
  1834   while (++__first != __last) {
  1835     if (__comp(*__first, *__result)) {
  1836       _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1837       __result = __first;
  1838     }
  1839   }
  1840   return __result;
  1841 }
  1842 
  1843 // next_permutation and prev_permutation, with and without an explicitly
  1844 // supplied comparison function.
  1845 _STLP_MOVE_TO_PRIV_NAMESPACE
  1846 
  1847 template <class _BidirectionalIter, class _Compare>
  1848 bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1849                         _Compare __comp) {
  1850   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1851   if (__first == __last)
  1852     return false;
  1853   _BidirectionalIter __i = __first;
  1854   ++__i;
  1855   if (__i == __last)
  1856     return false;
  1857   __i = __last;
  1858   --__i;
  1859 
  1860   for(;;) {
  1861     _BidirectionalIter __ii = __i;
  1862     --__i;
  1863     if (__comp(*__i, *__ii)) {
  1864       _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1865       _BidirectionalIter __j = __last;
  1866       while (!__comp(*__i, *--__j)) {}
  1867       iter_swap(__i, __j);
  1868       reverse(__ii, __last);
  1869       return true;
  1870     }
  1871     if (__i == __first) {
  1872       reverse(__first, __last);
  1873       return false;
  1874     }
  1875   }
  1876 #if defined (_STLP_NEED_UNREACHABLE_RETURN)
  1877     return false;
  1878 #endif
  1879 }
  1880 
  1881 _STLP_MOVE_TO_STD_NAMESPACE
  1882 
  1883 template <class _BidirectionalIter>
  1884 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  1885   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1886   return _STLP_PRIV __next_permutation(__first, __last,
  1887                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1888 }
  1889 
  1890 template <class _BidirectionalIter, class _Compare>
  1891 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1892                       _Compare __comp) {
  1893   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1894   return _STLP_PRIV __next_permutation(__first, __last, __comp);
  1895 }
  1896 
  1897 _STLP_MOVE_TO_PRIV_NAMESPACE
  1898 
  1899 template <class _BidirectionalIter, class _Compare>
  1900 bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1901                         _Compare __comp) {
  1902   if (__first == __last)
  1903     return false;
  1904   _BidirectionalIter __i = __first;
  1905   ++__i;
  1906   if (__i == __last)
  1907     return false;
  1908   __i = __last;
  1909   --__i;
  1910 
  1911   for(;;) {
  1912     _BidirectionalIter __ii = __i;
  1913     --__i;
  1914     if (__comp(*__ii, *__i)) {
  1915       _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1916       _BidirectionalIter __j = __last;
  1917       while (!__comp(*--__j, *__i)) {}
  1918       iter_swap(__i, __j);
  1919       reverse(__ii, __last);
  1920       return true;
  1921     }
  1922     if (__i == __first) {
  1923       reverse(__first, __last);
  1924       return false;
  1925     }
  1926   }
  1927 #if defined (_STLP_NEED_UNREACHABLE_RETURN)
  1928     return false;
  1929 #endif
  1930 }
  1931 
  1932 _STLP_MOVE_TO_STD_NAMESPACE
  1933 
  1934 template <class _BidirectionalIter>
  1935 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  1936   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1937   return _STLP_PRIV __prev_permutation(__first, __last,
  1938                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1939 }
  1940 
  1941 template <class _BidirectionalIter, class _Compare>
  1942 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1943                       _Compare __comp) {
  1944   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1945   return _STLP_PRIV __prev_permutation(__first, __last, __comp);
  1946 }
  1947 
  1948 #if !defined (_STLP_NO_EXTENSIONS)
  1949 
  1950 // is_heap, a predicate testing whether or not a range is
  1951 // a heap.  This function is an extension, not part of the C++
  1952 // standard.
  1953 _STLP_MOVE_TO_PRIV_NAMESPACE
  1954 
  1955 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
  1956 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
  1957                _Distance __n) {
  1958   _Distance __parent = 0;
  1959   for (_Distance __child = 1; __child < __n; ++__child) {
  1960     if (__comp(__first[__parent], __first[__child])) {
  1961       _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1962       return false;
  1963     }
  1964     if ((__child & 1) == 0)
  1965       ++__parent;
  1966   }
  1967   return true;
  1968 }
  1969 
  1970 _STLP_MOVE_TO_STD_NAMESPACE
  1971 
  1972 template <class _RandomAccessIter>
  1973 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) {
  1974   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1975   return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
  1976 }
  1977 
  1978 template <class _RandomAccessIter, class _StrictWeakOrdering>
  1979 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
  1980              _StrictWeakOrdering __comp) {
  1981   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1982   return _STLP_PRIV __is_heap(__first, __comp, __last - __first);
  1983 }
  1984 
  1985 
  1986 _STLP_MOVE_TO_PRIV_NAMESPACE
  1987 
  1988 template <class _ForwardIter, class _StrictWeakOrdering>
  1989 bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
  1990                  _StrictWeakOrdering __comp) {
  1991   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1992   if (__first == __last)
  1993     return true;
  1994 
  1995   _ForwardIter __next = __first;
  1996   for (++__next; __next != __last; __first = __next, ++__next) {
  1997     if (__comp(*__next, *__first)) {
  1998       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1999       return false;
  2000     }
  2001   }
  2002 
  2003   return true;
  2004 }
  2005 
  2006 _STLP_MOVE_TO_STD_NAMESPACE
  2007 #endif /* _STLP_NO_EXTENSIONS */
  2008 
  2009 _STLP_END_NAMESPACE
  2010 
  2011 #undef __stl_threshold
  2012 
  2013 #endif /* _STLP_ALGO_C */
  2014 // Local Variables:
  2015 // mode:C++
  2016 // End: