test: epoc32/include/tools/stlport/stl/

     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  */

    26 #ifndef _STLP_ALGO_C

    27 #define _STLP_ALGO_C

    29 #if !defined (_STLP_INTERNAL_ALGO_H)

    30 #  include <stl/_algo.h>

    31 #endif

    33 #ifndef _STLP_INTERNAL_TEMPBUF_H

    34 #  include <stl/_tempbuf.h>

    35 #endif

    37 _STLP_BEGIN_NAMESPACE

    39 _STLP_MOVE_TO_PRIV_NAMESPACE

    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);

    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);

    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 }

    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 }

   109 _STLP_MOVE_TO_STD_NAMESPACE

   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;

   120   // Test for a pattern of length 1.

   121   _ForwardIter2 __tmp(__first2);

   122   ++__tmp;

   123   if (__tmp == __last2)

   124     return find(__first1, __last1, *__first2);

   126   // General case.

   127   _ForwardIter2 __p1 = __first2;

   128   ++__p1;

   130   _ForwardIter1 __current;// = __first1;

   132   while (__first1 != __last1) {

   133     __first1 = find(__first1, __last1, *__first2);

   134     if (__first1 == __last1)

   135       return __last1;

   137     _ForwardIter2 __p = __p1;

   138     __current = __first1;

   139     if (++__current == __last1)

   140       return __last1;

   142     while (*__current == *__p) {

   143       if (++__p == __last2)

   144         return __first1;

   145       if (++__current == __last1)

   146         return __last1;

   147     }

   149     ++__first1;

   150   }

   151   return __first1;

   152 }

   154 _STLP_MOVE_TO_PRIV_NAMESPACE

   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;

   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;

   172     while ( !__pred(*__lookAhead, __val) ) { // the skip loop...

   173       if (__tailSize < __pattSize)

   174         return __last;

   176       __lookAhead += __pattSize;

   177       __tailSize -= __pattSize;

   178     }

   180     if ( __skipOffset == 0 ) {

   181       return (__lookAhead - __skipOffset); //Success

   182     }

   184     __remainder = __skipOffset;

   186     for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {

   187       if (--__remainder == 0)

   188         return (__lookAhead - __skipOffset); //Success

   189     }

   191     if (__remainder > __tailSize)

   192       return __last; //failure

   194     __lookAhead += __remainder;

   195     __tailSize -= __remainder;

   197     while ( __pred(*__lookAhead, __val) ) {

   198       __prevRemainder = __remainder;

   199       __backTrack = __lookAhead;

   201       do {

   202         if (--__remainder == 0)

   203           return (__lookAhead - __skipOffset); //Success

   204       } while (__pred(*--__backTrack, __val));

   206       //adjust remainder for next comparison

   207       __remainder += __pattSize - __prevRemainder;

   209       if (__remainder > __tailSize)

   210         return __last; //failure

   212       __lookAhead += __remainder;

   213       __tailSize -= __remainder;

   214     }

   216     //__lookAhead here is always pointing to the element of the last mismatch.

   217   }

   219   return __last; //failure

   220 }

   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 }

   246 _STLP_MOVE_TO_STD_NAMESPACE

   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 }

   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 }

   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 }

   293 // unique and unique_copy

   294 _STLP_MOVE_TO_PRIV_NAMESPACE

   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 }

   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 }

   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 }

   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 }

   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 */

   347 _STLP_MOVE_TO_STD_NAMESPACE

   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 }

   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 }

   369 // rotate and rotate_copy, and their auxiliary functions

   370 _STLP_MOVE_TO_PRIV_NAMESPACE

   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;

   383   _ForwardIter __first2 = __middle;

   384   do {

   385     swap(*__first++, *__first2++);

   386     if (__first == __middle)

   387       __middle = __first2;

   388   } while (__first2 != __last);

   390   _ForwardIter __new_middle = __first;

   392   __first2 = __middle;

   394   while (__first2 != __last) {

   395     swap (*__first++, *__first2++);

   396     if (__first == __middle)

   397       __middle = __first2;

   398     else if (__first2 == __last)

   399       __first2 = __middle;

   400   }

   402   return __new_middle;

   403 }

   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;

   416   __reverse(__first,  __middle, bidirectional_iterator_tag());

   417   __reverse(__middle, __last,   bidirectional_iterator_tag());

   419   while (__first != __middle && __middle != __last)

   420     swap (*__first++, *--__last);

   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 }

   432 template <class _RandomAccessIter, class _Distance, class _Tp>

   433 _RandomAccessIter __rotate_aux(_RandomAccessIter __first,

   434                                _RandomAccessIter __middle,

   435                                _RandomAccessIter __last,

   436                                _Distance *, _Tp *) {

   438   _Distance __n = __last   - __first;

   439   _Distance __k = __middle - __first;

   440   _Distance __l = __n - __k;

   441   _RandomAccessIter __result = __first + (__last - __middle);

   443   if (__k == 0)  /* __first == middle */

   444     return __last;

   446   if (__k == __l) {

   447     swap_ranges(__first, __middle, __middle);

   448     return __result;

   449   }

   451   _Distance __d = __gcd(__n, __k);

   453   for (_Distance __i = 0; __i < __d; __i++) {

   454     _Tp __tmp = *__first;

   455     _RandomAccessIter __p = __first;

   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         }

   464         *__p = *(__p + __k);

   465         __p += __k;

   466       }

   467     }

   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         }

   476         *__p = * (__p - __l);

   477         __p -= __l;

   478       }

   479     }

   481     *__p = __tmp;

   482     ++__first;

   483   }

   485   return __result;

   486 }

   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 }

   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 }

   506 _STLP_MOVE_TO_STD_NAMESPACE

   508 template <class _ForwardIter>

   509 void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {

   510   _STLP_PRIV __rotate(__first, __middle, __last);

   511 }

   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

   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 }

   527 _STLP_MOVE_TO_STD_NAMESPACE

   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 }

   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 }

   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);

   556   while (__m > 0) {

   557     if (_STLP_PRIV __random_number(__remaining) < __m) {

   558       *__out_ite = *__first;

   559       ++__out_ite;

   560       --__m;

   561     }

   563     --__remaining;

   564     ++__first;

   565   }

   566   return __out_ite;

   567 }

   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);

   579   while (__m > 0) {

   580     if (__rand(__remaining) < __m) {

   581       *__out_ite = *__first;

   582       ++__out_ite;

   583       --__m;

   584     }

   586     --__remaining;

   587     ++__first;

   588   }

   589   return __out_ite;

   590 }

   592 _STLP_MOVE_TO_PRIV_NAMESPACE

   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;

   603   while (__first != __last) {

   604     ++__t;

   605     _Distance __M = __random_number(__t);

   606     if (__M < __n)

   607       __out_ite[__M] = *__first;

   608     ++__first;

   609   }

   611   return __out_ite + __m;

   612 }

   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;

   625   while (__first != __last) {

   626     ++__t;

   627     _Distance __M = __rand(__t);

   628     if (__M < __n)

   629       __out_ite[__M] = *__first;

   630     ++__first;

   631   }

   633   return __out_ite + __m;

   634 }

   636 _STLP_MOVE_TO_STD_NAMESPACE

   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 }

   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 }

   660 #endif /* _STLP_NO_EXTENSIONS */

   662 // partition, stable_partition, and their auxiliary functions

   663 _STLP_MOVE_TO_PRIV_NAMESPACE

   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;

   672   while (__pred(*__first))

   673     if (++__first == __last) return __first;

   675   _ForwardIter __next = __first;

   677   while (++__next != __last) {

   678     if (__pred(*__next)) {

   679       swap(*__first, *__next);

   680       ++__first;

   681     }

   682   }

   683   return __first;

   684 }

   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 }

   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

   725 _STLP_MOVE_TO_STD_NAMESPACE

   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 }

   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

   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 }

   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 }

   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 }

   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 }

   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 }

   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

   854 _STLP_MOVE_TO_STD_NAMESPACE

   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 }

   872 _STLP_MOVE_TO_PRIV_NAMESPACE

   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 }

   895 // sort() and its auxiliary functions.

   896 #define __stl_threshold  16

   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 }

   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 }

   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 }

   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 }

   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 }

   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 }

   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 }

   982 _STLP_MOVE_TO_STD_NAMESPACE

   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 }

   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 }

  1008 // stable_sort() and its auxiliary functions.

  1009 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  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;

  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);

  1044   merge(__first, __first + __step_size,

  1045         __first + __step_size, __last,

  1046         __result,

  1047         __comp);

  1048 }

  1050 const int __stl_chunk_size = 7;

  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 }

  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;

  1072   _Distance __step_size = __stl_chunk_size;

  1073   __chunk_insertion_sort(__first, __last, __step_size, __comp);

  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 }

  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 }

  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 }

  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 }

  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 }

  1186 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1208 // partial_sort, partial_sort_copy, and auxiliary functions.

  1209 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  1225 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1244 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  1275 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1302 // nth_element() and its auxiliary functions.

  1303 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  1324 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1343 // Binary search (lower_bound, upper_bound, equal_range, binary_search).

  1344 _STLP_MOVE_TO_PRIV_NAMESPACE

  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;

  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 }

  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;

  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 }

  1408 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1452 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  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 }

  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);

  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 }

  1542 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1570 _STLP_MOVE_TO_PRIV_NAMESPACE

  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;

  1587   return __first2 == __last2;

  1588 }

  1590 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1605 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  1635 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1653 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  1678 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1696 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  1721 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1739 _STLP_MOVE_TO_PRIV_NAMESPACE

  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 }

  1768 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1788 // min_element and max_element, with and without an explicitly supplied

  1789 // comparison function.

  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 }

  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 }

  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 }

  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 }

  1843 // next_permutation and prev_permutation, with and without an explicitly

  1844 // supplied comparison function.

  1845 _STLP_MOVE_TO_PRIV_NAMESPACE

  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;

  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 }

  1881 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1897 _STLP_MOVE_TO_PRIV_NAMESPACE

  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;

  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 }

  1932 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1948 #if !defined (_STLP_NO_EXTENSIONS)

  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

  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 }

  1970 _STLP_MOVE_TO_STD_NAMESPACE

  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 }

  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 }

  1986 _STLP_MOVE_TO_PRIV_NAMESPACE

  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;

  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   }

  2003   return true;

  2004 }

  2006 _STLP_MOVE_TO_STD_NAMESPACE

  2007 #endif /* _STLP_NO_EXTENSIONS */

  2009 _STLP_END_NAMESPACE

  2011 #undef __stl_threshold

  2013 #endif /* _STLP_ALGO_C */

  2014 // Local Variables:

  2015 // mode:C++

  2016 // End:

author	William Roberts <williamr@symbian.org>
	Wed, 31 Mar 2010 12:33:34 +0100 (2010-03-31)
branch	Symbian3
changeset 4	837f303aceeb
permissions	-rw-r--r--