test: epoc32/include/stdapis/stlportv5/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 __p1(__first2);

   123   if ( ++__p1 == __last2 )

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

   126   // General case.

   128   for ( ; ; ) { // __first1 != __last1 will be checked in find below

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

   130     if (__first1 == __last1)

   131       return __last1;

   133     _ForwardIter2 __p = __p1;

   134     _ForwardIter1 __current = __first1;

   135     if (++__current == __last1)

   136       return __last1;

   138     while (*__current == *__p) {

   139       if (++__p == __last2)

   140         return __first1;

   141       if (++__current == __last1)

   142         return __last1;

   143     }

   145     ++__first1;

   146   }

   147   return __first1;

   148 }

   150 _STLP_MOVE_TO_PRIV_NAMESPACE

   152 template <class _RandomAccessIter, class _Integer, class _Tp,

   153           class _BinaryPred, class _Distance>

   154 _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,

   155                              _Integer __count, const _Tp& __val, _BinaryPred __pred,

   156                              _Distance*, const random_access_iterator_tag &)

   157 {

   158   _Distance __tailSize = __last - __first;

   159   const _Distance __pattSize = __count;

   160   const _Distance __skipOffset = __pattSize - 1;

   161   _RandomAccessIter __backTrack;

   162   _Distance __remainder, __prevRemainder;

   164   for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop...

   165     //__lookAhead here is always pointing to the last element of next possible match.

   166     __tailSize -= __pattSize;

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

   169       if (__tailSize < __pattSize)

   170         return __last;

   172       __lookAhead += __pattSize;

   173       __tailSize -= __pattSize;

   174     }

   176     if ( __skipOffset == 0 ) {

   177       return (__lookAhead - __skipOffset); //Success

   178     }

   180     __remainder = __skipOffset;

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

   183       if (--__remainder == 0)

   184         return (__lookAhead - __skipOffset); //Success

   185     }

   187     if (__remainder > __tailSize)

   188       return __last; //failure

   190     __lookAhead += __remainder;

   191     __tailSize -= __remainder;

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

   194       __prevRemainder = __remainder;

   195       __backTrack = __lookAhead;

   197       do {

   198         if (--__remainder == 0)

   199           return (__lookAhead - __skipOffset); //Success

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

   202       //adjust remainder for next comparison

   203       __remainder += __pattSize - __prevRemainder;

   205       if (__remainder > __tailSize)

   206         return __last; //failure

   208       __lookAhead += __remainder;

   209       __tailSize -= __remainder;

   210     }

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

   213   }

   215   return __last; //failure

   216 }

   218 template <class _ForwardIter, class _Integer, class _Tp,

   219           class _Distance, class _BinaryPred>

   220 _ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,

   221                         _Integer __count, const _Tp& __val, _BinaryPred __pred,

   222                         _Distance*, const forward_iterator_tag &) {

   223   for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}

   224   while (__first != __last) {

   225     _Integer __n = __count - 1;

   226     _ForwardIter __i = __first;

   227     ++__i;

   228     while (__i != __last && __n != 0 && __pred(*__i, __val)) {

   229       ++__i;

   230       --__n;

   231     }

   232     if (__n == 0)

   233       return __first;

   234     else if (__i != __last)

   235       for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}

   236     else

   237       break;

   238   }

   239   return __last;

   240 }

   242 _STLP_MOVE_TO_STD_NAMESPACE

   244 // search_n.  Search for __count consecutive copies of __val.

   245 template <class _ForwardIter, class _Integer, class _Tp>

   246 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

   247                       _Integer __count, const _Tp& __val) {

   248   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   249   if (__count <= 0)

   250     return __first;

   251   if (__count == 1)

   252     //We use find when __count == 1 to use potential find overload.

   253     return find(__first, __last, __val);

   254   return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(),

   255                                _STLP_DISTANCE_TYPE(__first, _ForwardIter),

   256                                _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   257 }

   259 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>

   260 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

   261                       _Integer __count, const _Tp& __val,

   262                       _BinaryPred __binary_pred) {

   263   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   264   if (__count <= 0)

   265     return __first;

   266   return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred,

   267                                _STLP_DISTANCE_TYPE(__first, _ForwardIter),

   268                                _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   269 }

   271 template <class _ForwardIter1, class _ForwardIter2>

   272 _ForwardIter1

   273 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,

   274          _ForwardIter2 __first2, _ForwardIter2 __last2) {

   275   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

   276   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

   277   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,

   278 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

   279                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),

   280                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),

   281 #else

   282                                forward_iterator_tag(),

   283                                forward_iterator_tag(),

   284 #endif

   285                                _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))

   286     );

   287 }

   289 // unique and unique_copy

   290 _STLP_MOVE_TO_PRIV_NAMESPACE

   292 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,

   293           class _Tp>

   294 _STLP_INLINE_LOOP _OutputIterator

   295 __unique_copy(_InputIterator __first, _InputIterator __last,

   296               _OutputIterator __result,

   297               _BinaryPredicate __binary_pred, _Tp*) {

   298   _Tp __val = *__first;

   299   *__result = __val;

   300   while (++__first != __last)

   301     if (!__binary_pred(__val, *__first)) {

   302       __val = *__first;

   303       *++__result = __val;

   304     }

   305   return ++__result;

   306 }

   308 template <class _InputIter, class _OutputIter, class _BinaryPredicate>

   309 inline _OutputIter

   310 __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,

   311               _BinaryPredicate __binary_pred, const output_iterator_tag &) {

   312   return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));

   313 }

   315 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>

   316 _STLP_INLINE_LOOP _ForwardIter

   317 __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,

   318               _BinaryPredicate __binary_pred, const forward_iterator_tag &) {

   319   *__result = *__first;

   320   while (++__first != __last)

   321     if (!__binary_pred(*__result, *__first)) *++__result = *__first;

   322   return ++__result;

   323 }

   325 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)

   326 template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>

   327 inline _BidirectionalIterator

   328 __unique_copy(_InputIterator __first, _InputIterator __last,

   329               _BidirectionalIterator __result, _BinaryPredicate __binary_pred,

   330               const bidirectional_iterator_tag &) {

   331   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());

   332 }

   334 template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>

   335 inline _RandomAccessIterator

   336 __unique_copy(_InputIterator __first, _InputIterator __last,

   337               _RandomAccessIterator __result, _BinaryPredicate __binary_pred,

   338               const random_access_iterator_tag &) {

   339   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());

   340 }

   341 #endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */

   343 _STLP_MOVE_TO_STD_NAMESPACE

   345 template <class _InputIter, class _OutputIter>

   346 _OutputIter

   347 unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {

   348   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   349   if (__first == __last) return __result;

   350   return _STLP_PRIV __unique_copy(__first, __last, __result,

   351                                   _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),

   352                                   _STLP_ITERATOR_CATEGORY(__result, _OutputIter));

   353 }

   355 template <class _InputIter, class _OutputIter, class _BinaryPredicate>

   356 _OutputIter

   357 unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,

   358             _BinaryPredicate __binary_pred) {

   359   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   360   if (__first == __last) return __result;

   361   return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,

   362                                   _STLP_ITERATOR_CATEGORY(__result, _OutputIter));

   363 }

   365 // rotate and rotate_copy, and their auxiliary functions

   366 _STLP_MOVE_TO_PRIV_NAMESPACE

   368 template <class _ForwardIter, class _Distance>

   369 _ForwardIter __rotate_aux(_ForwardIter __first,

   370                           _ForwardIter __middle,

   371                           _ForwardIter __last,

   372                           _Distance*,

   373                           const forward_iterator_tag &) {

   374   if (__first == __middle)

   375     return __last;

   376   if (__last  == __middle)

   377     return __first;

   379   _ForwardIter __first2 = __middle;

   380   do {

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

   382     if (__first == __middle)

   383       __middle = __first2;

   384   } while (__first2 != __last);

   386   _ForwardIter __new_middle = __first;

   388   __first2 = __middle;

   390   while (__first2 != __last) {

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

   392     if (__first == __middle)

   393       __middle = __first2;

   394     else if (__first2 == __last)

   395       __first2 = __middle;

   396   }

   398   return __new_middle;

   399 }

   401 template <class _BidirectionalIter, class _Distance>

   402 _BidirectionalIter __rotate_aux(_BidirectionalIter __first,

   403                                 _BidirectionalIter __middle,

   404                                 _BidirectionalIter __last,

   405                                 _Distance*,

   406                                 const bidirectional_iterator_tag &) {

   407   if (__first == __middle)

   408     return __last;

   409   if (__last  == __middle)

   410     return __first;

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

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

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

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

   418   if (__first == __middle) {

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

   420     return __last;

   421   }

   422   else {

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

   424     return __first;

   425   }

   426 }

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

   429 _RandomAccessIter __rotate_aux(_RandomAccessIter __first,

   430                                _RandomAccessIter __middle,

   431                                _RandomAccessIter __last,

   432                                _Distance *, _Tp *) {

   434   _Distance __n = __last   - __first;

   435   _Distance __k = __middle - __first;

   436   _Distance __l = __n - __k;

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

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

   440     return __last;

   442   if (__k == __l) {

   443     swap_ranges(__first, __middle, __middle);

   444     return __result;

   445   }

   447   _Distance __d = __gcd(__n, __k);

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

   450     _Tp __tmp = *__first;

   451     _RandomAccessIter __p = __first;

   453     if (__k < __l) {

   454       for (_Distance __j = 0; __j < __l/__d; __j++) {

   455         if (__p > __first + __l) {

   456           *__p = *(__p - __l);

   457           __p -= __l;

   458         }

   460         *__p = *(__p + __k);

   461         __p += __k;

   462       }

   463     }

   465     else {

   466       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {

   467         if (__p < __last - __k) {

   468           *__p = *(__p + __k);

   469           __p += __k;

   470         }

   472         *__p = * (__p - __l);

   473         __p -= __l;

   474       }

   475     }

   477     *__p = __tmp;

   478     ++__first;

   479   }

   481   return __result;

   482 }

   484 template <class _RandomAccessIter, class _Distance>

   485 inline _RandomAccessIter

   486 __rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,

   487              _Distance * __dis, const random_access_iterator_tag &) {

   488   return __rotate_aux(__first, __middle, __last,

   489                       __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));

   490 }

   492 template <class _ForwardIter>

   493 _ForwardIter

   494 __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {

   495   _STLP_DEBUG_CHECK(__check_range(__first, __middle))

   496   _STLP_DEBUG_CHECK(__check_range(__middle, __last))

   497   return __rotate_aux(__first, __middle, __last,

   498                       _STLP_DISTANCE_TYPE(__first, _ForwardIter),

   499                       _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   500 }

   502 _STLP_MOVE_TO_STD_NAMESPACE

   504 template <class _ForwardIter>

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

   506   _STLP_PRIV __rotate(__first, __middle, __last);

   507 }

   509 // Return a random number in the range [0, __n).  This function encapsulates

   510 // whether we're using rand (part of the standard C library) or lrand48

   511 // (not standard, but a much better choice whenever it's available).

   512 _STLP_MOVE_TO_PRIV_NAMESPACE

   514 template <class _Distance>

   515 inline _Distance __random_number(_Distance __n) {

   516 #ifdef _STLP_NO_DRAND48

   517   return rand() % __n;

   518 #else

   519   return lrand48() % __n;

   520 #endif

   521 }

   523 _STLP_MOVE_TO_STD_NAMESPACE

   525 template <class _RandomAccessIter>

   526 void random_shuffle(_RandomAccessIter __first,

   527                     _RandomAccessIter __last) {

   528   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   529   if (__first == __last) return;

   530   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)

   531     iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1));

   532 }

   534 template <class _RandomAccessIter, class _RandomNumberGenerator>

   535 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,

   536                     _RandomNumberGenerator &__rand) {

   537   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   538   if (__first == __last) return;

   539   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)

   540     iter_swap(__i, __first + __rand((__i - __first) + 1));

   541 }

   543 #if !defined (_STLP_NO_EXTENSIONS)

   544 // random_sample and random_sample_n (extensions, not part of the standard).

   545 template <class _ForwardIter, class _OutputIter, class _Distance>

   546 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

   547                             _OutputIter __out_ite, const _Distance __n) {

   548   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   549   _Distance __remaining = distance(__first, __last);

   550   _Distance __m = (min) (__n, __remaining);

   552   while (__m > 0) {

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

   554       *__out_ite = *__first;

   555       ++__out_ite;

   556       --__m;

   557     }

   559     --__remaining;

   560     ++__first;

   561   }

   562   return __out_ite;

   563 }

   566 template <class _ForwardIter, class _OutputIter, class _Distance,

   567           class _RandomNumberGenerator>

   568 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

   569                             _OutputIter __out_ite, const _Distance __n,

   570                             _RandomNumberGenerator& __rand) {

   571   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   572   _Distance __remaining = distance(__first, __last);

   573   _Distance __m = (min) (__n, __remaining);

   575   while (__m > 0) {

   576     if (__rand(__remaining) < __m) {

   577       *__out_ite = *__first;

   578       ++__out_ite;

   579       --__m;

   580     }

   582     --__remaining;

   583     ++__first;

   584   }

   585   return __out_ite;

   586 }

   588 _STLP_MOVE_TO_PRIV_NAMESPACE

   590 template <class _InputIter, class _RandomAccessIter, class _Distance>

   591 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,

   592                                   _RandomAccessIter __out_ite,

   593                                   const _Distance __n) {

   594   _Distance __m = 0;

   595   _Distance __t = __n;

   596   for ( ; __first != __last && __m < __n; ++__m, ++__first)

   597     __out_ite[__m] = *__first;

   599   while (__first != __last) {

   600     ++__t;

   601     _Distance __M = __random_number(__t);

   602     if (__M < __n)

   603       __out_ite[__M] = *__first;

   604     ++__first;

   605   }

   607   return __out_ite + __m;

   608 }

   610 template <class _InputIter, class _RandomAccessIter,

   611           class _RandomNumberGenerator, class _Distance>

   612 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,

   613                                   _RandomAccessIter __out_ite,

   614                                   _RandomNumberGenerator& __rand,

   615                                   const _Distance __n) {

   616   _Distance __m = 0;

   617   _Distance __t = __n;

   618   for ( ; __first != __last && __m < __n; ++__m, ++__first)

   619     __out_ite[__m] = *__first;

   621   while (__first != __last) {

   622     ++__t;

   623     _Distance __M = __rand(__t);

   624     if (__M < __n)

   625       __out_ite[__M] = *__first;

   626     ++__first;

   627   }

   629   return __out_ite + __m;

   630 }

   632 _STLP_MOVE_TO_STD_NAMESPACE

   634 template <class _InputIter, class _RandomAccessIter>

   635 _RandomAccessIter

   636 random_sample(_InputIter __first, _InputIter __last,

   637               _RandomAccessIter __out_first, _RandomAccessIter __out_last) {

   638   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   639   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))

   640   return _STLP_PRIV __random_sample(__first, __last,

   641                                     __out_first, __out_last - __out_first);

   642 }

   644 template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>

   645 _RandomAccessIter

   646 random_sample(_InputIter __first, _InputIter __last,

   647               _RandomAccessIter __out_first, _RandomAccessIter __out_last,

   648               _RandomNumberGenerator& __rand) {

   649   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   650   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))

   651   return _STLP_PRIV __random_sample(__first, __last,

   652                                     __out_first, __rand,

   653                                     __out_last - __out_first);

   654 }

   656 #endif /* _STLP_NO_EXTENSIONS */

   658 // partition, stable_partition, and their auxiliary functions

   659 _STLP_MOVE_TO_PRIV_NAMESPACE

   661 template <class _ForwardIter, class _Predicate>

   662 _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,

   663                                            _ForwardIter __last,

   664                                            _Predicate   __pred,

   665                                            const forward_iterator_tag &) {

   666   if (__first == __last) return __first;

   668   while (__pred(*__first))

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

   671   _ForwardIter __next = __first;

   673   while (++__next != __last) {

   674     if (__pred(*__next)) {

   675       swap(*__first, *__next);

   676       ++__first;

   677     }

   678   }

   679   return __first;

   680 }

   682 template <class _BidirectionalIter, class _Predicate>

   683 _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,

   684                                                  _BidirectionalIter __last,

   685                                                  _Predicate __pred,

   686                                                  const bidirectional_iterator_tag &) {

   687   for (;;) {

   688     for (;;) {

   689       if (__first == __last)

   690         return __first;

   691       else if (__pred(*__first))

   692         ++__first;

   693       else

   694         break;

   695     }

   696     --__last;

   697     for (;;) {

   698       if (__first == __last)

   699         return __first;

   700       else if (!__pred(*__last))

   701         --__last;

   702       else

   703         break;

   704     }

   705     iter_swap(__first, __last);

   706     ++__first;

   707   }

   708 }

   710 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)

   711 template <class _BidirectionalIter, class _Predicate>

   712 inline

   713 _BidirectionalIter __partition(_BidirectionalIter __first,

   714                                _BidirectionalIter __last,

   715                                _Predicate __pred,

   716                                const random_access_iterator_tag &) {

   717   return __partition(__first, __last, __pred, bidirectional_iterator_tag());

   718 }

   719 #endif

   721 _STLP_MOVE_TO_STD_NAMESPACE

   723 template <class _ForwardIter, class _Predicate>

   724 _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred) {

   725   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   726   return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   727 }

   730 /* __pred_of_first: false if we know that __pred(*__first) is false,

   731  *                  true when we don't know the result of __pred(*__first).

   732  * __not_pred_of_before_last: true if we know that __pred(*--__last) is true,

   733  *                            false when we don't know the result of __pred(*--__last).

   734  */

   735 _STLP_MOVE_TO_PRIV_NAMESPACE

   737 template <class _ForwardIter, class _Predicate, class _Distance>

   738 _ForwardIter __inplace_stable_partition(_ForwardIter __first,

   739                                         _ForwardIter __last,

   740                                         _Predicate __pred, _Distance __len,

   741                                         bool __pred_of_first, bool __pred_of_before_last) {

   742   if (__len == 1)

   743     return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;

   744   _ForwardIter __middle = __first;

   745   _Distance __half_len = __len / 2;

   746   advance(__middle, __half_len);

   747   return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),

   748                   __middle,

   749                   __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));

   750 }

   752 template <class _ForwardIter, class _Pointer, class _Predicate,

   753           class _Distance>

   754 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,

   755                                          _ForwardIter __last,

   756                                          _Predicate __pred, _Distance __len,

   757                                          _Pointer __buffer, _Distance __buffer_size,

   758                                          bool __pred_of_first, bool __pred_of_before_last) {

   759   if (__len <= __buffer_size) {

   760     _ForwardIter __result1 = __first;

   761     _Pointer __result2 = __buffer;

   762     if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {

   763       *__result2 = *__first;

   764       ++__result2; ++__first; --__len;

   765     }

   766     for (; __first != __last ; ++__first, --__len) {

   767       if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||

   768           ((__len != 1) && __pred(*__first))){

   769         *__result1 = *__first;

   770         ++__result1;

   771       }

   772       else {

   773         *__result2 = *__first;

   774         ++__result2;

   775       }

   776     }

   777     copy(__buffer, __result2, __result1);

   778     return __result1;

   779   }

   780   else {

   781     _ForwardIter __middle = __first;

   782     _Distance __half_len = __len / 2;

   783     advance(__middle, __half_len);

   784     return __rotate(__stable_partition_adaptive(

   785                           __first, __middle, __pred,

   786                           __half_len, __buffer, __buffer_size,

   787                           __pred_of_first, false),

   788                     __middle,

   789                     __stable_partition_adaptive(

   790                           __middle, __last, __pred,

   791                           __len - __half_len, __buffer, __buffer_size,

   792                           true, __pred_of_before_last));

   793   }

   794 }

   796 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>

   797 inline _ForwardIter

   798 __stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,

   799                            _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {

   800   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);

   801   _STLP_MPWFIX_TRY    //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present

   802   return (__buf.size() > 0) ?

   803     __stable_partition_adaptive(__first, __last, __pred,

   804                                 _Distance(__buf.requested_size()),

   805                                 __buf.begin(), __buf.size(),

   806                                 false, __pred_of_before_last)  :

   807     __inplace_stable_partition(__first, __last, __pred,

   808                                _Distance(__buf.requested_size()),

   809                                false, __pred_of_before_last);

   810   _STLP_MPWFIX_CATCH  //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present

   811 }

   813 template <class _ForwardIter, class _Predicate>

   814 _ForwardIter

   815 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,

   816                        const forward_iterator_tag &) {

   817   return __stable_partition_aux_aux(__first, __last, __pred,

   818                                     _STLP_VALUE_TYPE(__first, _ForwardIter),

   819                                     _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   820 }

   822 template <class _BidirectIter, class _Predicate>

   823 _BidirectIter

   824 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,

   825                        const bidirectional_iterator_tag &) {

   826   for (--__last;;) {

   827     if (__first == __last)

   828       return __first;

   829     else if (!__pred(*__last))

   830       --__last;

   831     else

   832       break;

   833   }

   834   ++__last;

   835   //Here we know that __pred(*--__last) is true

   836   return __stable_partition_aux_aux(__first, __last, __pred,

   837                                     _STLP_VALUE_TYPE(__first, _BidirectIter),

   838                                     _STLP_DISTANCE_TYPE(__first, _BidirectIter), true);

   839 }

   841 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)

   842 template <class _BidirectIter, class _Predicate>

   843 _BidirectIter

   844 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,

   845                        const random_access_iterator_tag &) {

   846   return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag());

   847 }

   848 #endif

   850 _STLP_MOVE_TO_STD_NAMESPACE

   852 template <class _ForwardIter, class _Predicate>

   853 _ForwardIter

   854 stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {

   855   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   856   for (;;) {

   857     if (__first == __last)

   858       return __first;

   859     else if (__pred(*__first))

   860       ++__first;

   861     else

   862       break;

   863   }

   864   return _STLP_PRIV __stable_partition_aux(__first, __last, __pred,

   865                                            _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   866 }

   868 _STLP_MOVE_TO_PRIV_NAMESPACE

   870 template <class _RandomAccessIter, class _Tp, class _Compare>

   871 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,

   872                                         _RandomAccessIter __last,

   873                                         _Tp __pivot, _Compare __comp) {

   874   for (;;) {

   875     while (__comp(*__first, __pivot)) {

   876       _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

   877       ++__first;

   878     }

   879     --__last;

   880     while (__comp(__pivot, *__last)) {

   881       _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

   882       --__last;

   883     }

   884     if (!(__first < __last))

   885       return __first;

   886     iter_swap(__first, __last);

   887     ++__first;

   888   }

   889 }

   891 // sort() and its auxiliary functions.

   892 #define __stl_threshold  16

   894 template <class _RandomAccessIter, class _Tp, class _Compare>

   895 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,

   896                                _Compare __comp) {

   897   _RandomAccessIter __next = __last;

   898   --__next;

   899   while (__comp(__val, *__next)) {

   900     _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

   901     *__last = *__next;

   902     __last = __next;

   903     --__next;

   904   }

   905   *__last = __val;

   906 }

   908 template <class _RandomAccessIter, class _Tp, class _Compare>

   909 inline void __linear_insert(_RandomAccessIter __first,

   910                             _RandomAccessIter __last, _Tp __val, _Compare __comp) {

   911   //*TY 12/26/1998 - added __val as a paramter

   912   //  _Tp __val = *__last;        //*TY 12/26/1998 - __val supplied by caller

   913   if (__comp(__val, *__first)) {

   914     _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

   915     copy_backward(__first, __last, __last + 1);

   916     *__first = __val;

   917   }

   918   else

   919     __unguarded_linear_insert(__last, __val, __comp);

   920 }

   922 template <class _RandomAccessIter, class _Tp, class _Compare>

   923 void __insertion_sort(_RandomAccessIter __first,

   924                       _RandomAccessIter __last,

   925                       _Tp *, _Compare __comp) {

   926   if (__first == __last) return;

   927   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)

   928     __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp);  //*TY 12/26/1998 - supply *__i as __val

   929 }

   931 template <class _RandomAccessIter, class _Tp, class _Compare>

   932 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,

   933                                     _RandomAccessIter __last,

   934                                     _Tp*, _Compare __comp) {

   935   for (_RandomAccessIter __i = __first; __i != __last; ++__i)

   936     __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);

   937 }

   939 template <class _RandomAccessIter, class _Compare>

   940 inline void __unguarded_insertion_sort(_RandomAccessIter __first,

   941                                        _RandomAccessIter __last,

   942                                        _Compare __comp) {

   943   __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);

   944 }

   946 template <class _RandomAccessIter, class _Compare>

   947 void __final_insertion_sort(_RandomAccessIter __first,

   948                             _RandomAccessIter __last, _Compare __comp) {

   949   if (__last - __first > __stl_threshold) {

   950     __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);

   951     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);

   952   }

   953   else

   954     __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);

   955 }

   957 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>

   958 void __introsort_loop(_RandomAccessIter __first,

   959                       _RandomAccessIter __last, _Tp*,

   960                       _Size __depth_limit, _Compare __comp) {

   961   while (__last - __first > __stl_threshold) {

   962     if (__depth_limit == 0) {

   963       partial_sort(__first, __last, __last, __comp);

   964       return;

   965     }

   966     --__depth_limit;

   967     _RandomAccessIter __cut =

   968       __unguarded_partition(__first, __last,

   969                             _Tp(__median(*__first,

   970                                          *(__first + (__last - __first)/2),

   971                                          *(__last - 1), __comp)),

   972        __comp);

   973     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);

   974     __last = __cut;

   975   }

   976 }

   978 _STLP_MOVE_TO_STD_NAMESPACE

   980 template <class _RandomAccessIter>

   981 void sort(_RandomAccessIter __first, _RandomAccessIter __last) {

   982   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   983   if (__first != __last) {

   984     _STLP_PRIV __introsort_loop(__first, __last,

   985                                 _STLP_VALUE_TYPE(__first, _RandomAccessIter),

   986                                 _STLP_PRIV __lg(__last - __first) * 2,

   987                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

   988     _STLP_PRIV __final_insertion_sort(__first, __last,

   989                                       _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

   990   }

   991 }

   993 template <class _RandomAccessIter, class _Compare>

   994 void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {

   995   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   996   if (__first != __last) {

   997     _STLP_PRIV __introsort_loop(__first, __last,

   998                                 _STLP_VALUE_TYPE(__first, _RandomAccessIter),

   999                                 _STLP_PRIV __lg(__last - __first) * 2, __comp);

  1000     _STLP_PRIV __final_insertion_sort(__first, __last, __comp);

  1001   }

  1002 }

  1004 // stable_sort() and its auxiliary functions.

  1005 _STLP_MOVE_TO_PRIV_NAMESPACE

  1007 template <class _RandomAccessIter, class _Compare>

  1008 void __inplace_stable_sort(_RandomAccessIter __first,

  1009                            _RandomAccessIter __last, _Compare __comp) {

  1010   if (__last - __first < 15) {

  1011     __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);

  1012     return;

  1013   }

  1014   _RandomAccessIter __middle = __first + (__last - __first) / 2;

  1015   __inplace_stable_sort(__first, __middle, __comp);

  1016   __inplace_stable_sort(__middle, __last, __comp);

  1017   __merge_without_buffer(__first, __middle, __last,

  1018                          __middle - __first,

  1019                          __last - __middle,

  1020                          __comp);

  1021 }

  1023 template <class _RandomAccessIter1, class _RandomAccessIter2,

  1024           class _Distance, class _Compare>

  1025 void __merge_sort_loop(_RandomAccessIter1 __first,

  1026                        _RandomAccessIter1 __last,

  1027                        _RandomAccessIter2 __result, _Distance __step_size,

  1028                        _Compare __comp) {

  1029   _Distance __two_step = 2 * __step_size;

  1031   while (__last - __first >= __two_step) {

  1032     __result = merge(__first, __first + __step_size,

  1033                      __first + __step_size, __first + __two_step,

  1034                      __result,

  1035                      __comp);

  1036     __first += __two_step;

  1037   }

  1038   __step_size = (min) (_Distance(__last - __first), __step_size);

  1040   merge(__first, __first + __step_size,

  1041         __first + __step_size, __last,

  1042         __result,

  1043         __comp);

  1044 }

  1046 const int __stl_chunk_size = 7;

  1048 template <class _RandomAccessIter, class _Distance, class _Compare>

  1049 void __chunk_insertion_sort(_RandomAccessIter __first,

  1050                             _RandomAccessIter __last,

  1051                             _Distance __chunk_size, _Compare __comp) {

  1052   while (__last - __first >= __chunk_size) {

  1053     __insertion_sort(__first, __first + __chunk_size,

  1054                      _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);

  1055     __first += __chunk_size;

  1056   }

  1057   __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);

  1058 }

  1060 template <class _RandomAccessIter, class _Pointer, class _Distance,

  1061           class _Compare>

  1062 void __merge_sort_with_buffer(_RandomAccessIter __first,

  1063                               _RandomAccessIter __last, _Pointer __buffer,

  1064                               _Distance*, _Compare __comp) {

  1065   _Distance __len = __last - __first;

  1066   _Pointer __buffer_last = __buffer + __len;

  1068   _Distance __step_size = __stl_chunk_size;

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

  1071   while (__step_size < __len) {

  1072     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);

  1073     __step_size *= 2;

  1074     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);

  1075     __step_size *= 2;

  1076   }

  1077 }

  1079 template <class _BidirectionalIter1, class _BidirectionalIter2,

  1080           class _Distance>

  1081 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,

  1082                                       _BidirectionalIter1 __middle,

  1083                                       _BidirectionalIter1 __last,

  1084                                       _Distance __len1, _Distance __len2,

  1085                                       _BidirectionalIter2 __buffer,

  1086                                       _Distance __buffer_size) {

  1087   if (__len1 > __len2 && __len2 <= __buffer_size) {

  1088     _BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);

  1089     copy_backward(__first, __middle, __last);

  1090     return copy(__buffer, __buffer_end, __first);

  1091   }

  1092   else if (__len1 <= __buffer_size) {

  1093     _BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);

  1094     copy(__middle, __last, __first);

  1095     return copy_backward(__buffer, __buffer_end, __last);

  1096   }

  1097   else

  1098     return __rotate(__first, __middle, __last);

  1099 }

  1101 template <class _BidirectionalIter, class _Distance, class _Pointer,

  1102           class _Compare>

  1103 void __merge_adaptive(_BidirectionalIter __first,

  1104                       _BidirectionalIter __middle,

  1105                       _BidirectionalIter __last,

  1106                       _Distance __len1, _Distance __len2,

  1107                       _Pointer __buffer, _Distance __buffer_size,

  1108                       _Compare __comp) {

  1109   if (__len1 <= __len2 && __len1 <= __buffer_size) {

  1110     _Pointer __buffer_end = copy(__first, __middle, __buffer);

  1111     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);

  1112   }

  1113   else if (__len2 <= __buffer_size) {

  1114     _Pointer __buffer_end = copy(__middle, __last, __buffer);

  1115     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,

  1116                      __comp);

  1117   }

  1118   else {

  1119     _BidirectionalIter __first_cut = __first;

  1120     _BidirectionalIter __second_cut = __middle;

  1121     _Distance __len11 = 0;

  1122     _Distance __len22 = 0;

  1123     if (__len1 > __len2) {

  1124       __len11 = __len1 / 2;

  1125       advance(__first_cut, __len11);

  1126       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);

  1127       __len22 += distance(__middle, __second_cut);

  1128     }

  1129     else {

  1130       __len22 = __len2 / 2;

  1131       advance(__second_cut, __len22);

  1132       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);

  1133       __len11 += distance(__first, __first_cut);

  1134     }

  1135     _BidirectionalIter __new_middle =

  1136       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,

  1137                         __len22, __buffer, __buffer_size);

  1138     __merge_adaptive(__first, __first_cut, __new_middle, __len11,

  1139                      __len22, __buffer, __buffer_size, __comp);

  1140     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,

  1141                      __len2 - __len22, __buffer, __buffer_size, __comp);

  1142   }

  1143 }

  1145 template <class _RandomAccessIter, class _Pointer, class _Distance,

  1146           class _Compare>

  1147 void __stable_sort_adaptive(_RandomAccessIter __first,

  1148                             _RandomAccessIter __last, _Pointer __buffer,

  1149                             _Distance __buffer_size, _Compare __comp) {

  1150   _Distance __len = (__last - __first + 1) / 2;

  1151   _RandomAccessIter __middle = __first + __len;

  1152   if (__len > __buffer_size) {

  1153     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,

  1154                            __comp);

  1155     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,

  1156                            __comp);

  1157   }

  1158   else {

  1159     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,

  1160                                __comp);

  1161     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,

  1162                                __comp);

  1163   }

  1164   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),

  1165                    _Distance(__last - __middle), __buffer, __buffer_size,

  1166                    __comp);

  1167 }

  1169 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>

  1170 void __stable_sort_aux(_RandomAccessIter __first,

  1171                        _RandomAccessIter __last, _Tp*, _Distance*,

  1172                        _Compare __comp) {

  1173   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);

  1174   if (buf.begin() == 0)

  1175     __inplace_stable_sort(__first, __last, __comp);

  1176   else

  1177     __stable_sort_adaptive(__first, __last, buf.begin(),

  1178                            _Distance(buf.size()),

  1179                            __comp);

  1180 }

  1182 _STLP_MOVE_TO_STD_NAMESPACE

  1184 template <class _RandomAccessIter>

  1185 void stable_sort(_RandomAccessIter __first,

  1186                  _RandomAccessIter __last) {

  1187   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1188   _STLP_PRIV __stable_sort_aux(__first, __last,

  1189                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1190                                _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),

  1191                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

  1192 }

  1194 template <class _RandomAccessIter, class _Compare>

  1195 void stable_sort(_RandomAccessIter __first,

  1196                  _RandomAccessIter __last, _Compare __comp) {

  1197   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1198   _STLP_PRIV __stable_sort_aux(__first, __last,

  1199                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1200                                _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),

  1201                                __comp);

  1202 }

  1204 // partial_sort, partial_sort_copy, and auxiliary functions.

  1205 _STLP_MOVE_TO_PRIV_NAMESPACE

  1207 template <class _RandomAccessIter, class _Tp, class _Compare>

  1208 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,

  1209                     _RandomAccessIter __last, _Tp*, _Compare __comp) {

  1210   make_heap(__first, __middle, __comp);

  1211   for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {

  1212     if (__comp(*__i, *__first)) {

  1213       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1214       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,

  1215                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));

  1216     }

  1217   }

  1218   sort_heap(__first, __middle, __comp);

  1219 }

  1221 _STLP_MOVE_TO_STD_NAMESPACE

  1223 template <class _RandomAccessIter>

  1224 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,

  1225                   _RandomAccessIter __last) {

  1226   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))

  1227   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))

  1228   _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1229                             _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

  1230 }

  1232 template <class _RandomAccessIter, class _Compare>

  1233 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,

  1234                   _RandomAccessIter __last, _Compare __comp) {

  1235   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))

  1236   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))

  1237   _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);

  1238 }

  1240 _STLP_MOVE_TO_PRIV_NAMESPACE

  1242 template <class _InputIter, class _RandomAccessIter, class _Compare,

  1243           class _Distance, class _Tp>

  1244 _RandomAccessIter __partial_sort_copy(_InputIter __first,

  1245                                       _InputIter __last,

  1246                                       _RandomAccessIter __result_first,

  1247                                       _RandomAccessIter __result_last,

  1248                                       _Compare __comp, _Distance*, _Tp*) {

  1249   if (__result_first == __result_last) return __result_last;

  1250   _RandomAccessIter __result_real_last = __result_first;

  1251   while(__first != __last && __result_real_last != __result_last) {

  1252     *__result_real_last = *__first;

  1253     ++__result_real_last;

  1254     ++__first;

  1255   }

  1256   make_heap(__result_first, __result_real_last, __comp);

  1257   while (__first != __last) {

  1258     if (__comp(*__first, *__result_first)) {

  1259       _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1260       __adjust_heap(__result_first, _Distance(0),

  1261                     _Distance(__result_real_last - __result_first),

  1262                     _Tp(*__first),

  1263                     __comp);

  1264     }

  1265     ++__first;

  1266   }

  1267   sort_heap(__result_first, __result_real_last, __comp);

  1268   return __result_real_last;

  1269 }

  1271 _STLP_MOVE_TO_STD_NAMESPACE

  1273 template <class _InputIter, class _RandomAccessIter>

  1274 _RandomAccessIter

  1275 partial_sort_copy(_InputIter __first, _InputIter __last,

  1276                   _RandomAccessIter __result_first, _RandomAccessIter __result_last) {

  1277   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1278   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))

  1279   return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,

  1280                                         _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),

  1281                                         _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),

  1282                                         _STLP_VALUE_TYPE(__first, _InputIter));

  1283 }

  1285 template <class _InputIter, class _RandomAccessIter, class _Compare>

  1286 _RandomAccessIter

  1287 partial_sort_copy(_InputIter __first, _InputIter __last,

  1288                   _RandomAccessIter __result_first,

  1289                   _RandomAccessIter __result_last, _Compare __comp) {

  1290   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1291   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))

  1292   return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,

  1293                                         __comp,

  1294                                         _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),

  1295                                         _STLP_VALUE_TYPE(__first, _InputIter));

  1296 }

  1298 // nth_element() and its auxiliary functions.

  1299 _STLP_MOVE_TO_PRIV_NAMESPACE

  1301 template <class _RandomAccessIter, class _Tp, class _Compare>

  1302 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

  1303                    _RandomAccessIter __last, _Tp*, _Compare __comp) {

  1304   while (__last - __first > 3) {

  1305     _RandomAccessIter __cut =

  1306       __unguarded_partition(__first, __last,

  1307                             _Tp(__median(*__first,

  1308                                          *(__first + (__last - __first)/2),

  1309                                          *(__last - 1),

  1310                                          __comp)),

  1311                             __comp);

  1312     if (__cut <= __nth)

  1313       __first = __cut;

  1314     else

  1315       __last = __cut;

  1316   }

  1317   __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);

  1318 }

  1320 _STLP_MOVE_TO_STD_NAMESPACE

  1322 template <class _RandomAccessIter>

  1323 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

  1324                  _RandomAccessIter __last) {

  1325   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))

  1326   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))

  1327   _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1328                            _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

  1329 }

  1331 template <class _RandomAccessIter, class _Compare>

  1332 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

  1333                  _RandomAccessIter __last, _Compare __comp) {

  1334   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))

  1335   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))

  1336   _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);

  1337 }

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

  1340 _STLP_MOVE_TO_PRIV_NAMESPACE

  1342 template <class _ForwardIter, class _Tp,

  1343           class _Compare1, class _Compare2, class _Distance>

  1344 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,

  1345                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {

  1346   _Distance __len = distance(__first, __last);

  1347   _Distance __half;

  1349   while (__len > 0) {

  1350     __half = __len >> 1;

  1351     _ForwardIter __middle = __first;

  1352     advance(__middle, __half);

  1353     if (__comp2(__val, *__middle)) {

  1354       _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1355       __len = __half;

  1356     }

  1357     else {

  1358       __first = __middle;

  1359       ++__first;

  1360       __len = __len - __half - 1;

  1361     }

  1362   }

  1363   return __first;

  1364 }

  1366 template <class _ForwardIter, class _Tp,

  1367           class _Compare1, class _Compare2, class _Distance>

  1368 pair<_ForwardIter, _ForwardIter>

  1369 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,

  1370               _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {

  1371   _Distance __len = distance(__first, __last);

  1372   _Distance __half;

  1374   while (__len > 0) {

  1375     __half = __len >> 1;

  1376     _ForwardIter __middle = __first;

  1377     advance(__middle, __half);

  1378     if (__comp1(*__middle, __val)) {

  1379       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1380       __first = __middle;

  1381       ++__first;

  1382       __len = __len - __half - 1;

  1383     }

  1384     else if (__comp2(__val, *__middle)) {

  1385       _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1386       __len = __half;

  1387     }

  1388     else {

  1389       _ForwardIter __left = __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);

  1390       //Small optim: If lower_bound haven't found an equivalent value

  1391       //there is no need to call upper_bound.

  1392       if (__comp1(*__left, __val)) {

  1393         _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1394         return pair<_ForwardIter, _ForwardIter>(__left, __left);

  1395       }

  1396       advance(__first, __len);

  1397       _ForwardIter __right = __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);

  1398       return pair<_ForwardIter, _ForwardIter>(__left, __right);

  1399     }

  1400   }

  1401   return pair<_ForwardIter, _ForwardIter>(__first, __first);

  1402 }

  1404 _STLP_MOVE_TO_STD_NAMESPACE

  1406 template <class _InputIter1, class _InputIter2, class _OutputIter>

  1407 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,

  1408                   _InputIter2 __first2, _InputIter2 __last2,

  1409                   _OutputIter __result) {

  1410   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

  1411   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

  1412   while (__first1 != __last1 && __first2 != __last2) {

  1413     if (*__first2 < *__first1) {

  1414       *__result = *__first2;

  1415       ++__first2;

  1416     }

  1417     else {

  1418       *__result = *__first1;

  1419       ++__first1;

  1420     }

  1421     ++__result;

  1422   }

  1423   return copy(__first2, __last2, copy(__first1, __last1, __result));

  1424 }

  1426 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1427           class _Compare>

  1428 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,

  1429                   _InputIter2 __first2, _InputIter2 __last2,

  1430                   _OutputIter __result, _Compare __comp) {

  1431   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

  1432   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

  1433   while (__first1 != __last1 && __first2 != __last2) {

  1434     if (__comp(*__first2, *__first1)) {

  1435       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1436       *__result = *__first2;

  1437       ++__first2;

  1438     }

  1439     else {

  1440       *__result = *__first1;

  1441       ++__first1;

  1442     }

  1443     ++__result;

  1444   }

  1445   return copy(__first2, __last2, copy(__first1, __last1, __result));

  1446 }

  1448 _STLP_MOVE_TO_PRIV_NAMESPACE

  1450 template <class _BidirectionalIter, class _Distance, class _Compare>

  1451 void __merge_without_buffer(_BidirectionalIter __first,

  1452                             _BidirectionalIter __middle,

  1453                             _BidirectionalIter __last,

  1454                             _Distance __len1, _Distance __len2,

  1455                             _Compare __comp) {

  1456   if (__len1 == 0 || __len2 == 0)

  1457     return;

  1458   if (__len1 + __len2 == 2) {

  1459     if (__comp(*__middle, *__first)) {

  1460       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1461       iter_swap(__first, __middle);

  1462     }

  1463     return;

  1464   }

  1465   _BidirectionalIter __first_cut = __first;

  1466   _BidirectionalIter __second_cut = __middle;

  1467   _Distance __len11 = 0;

  1468   _Distance __len22 = 0;

  1469   if (__len1 > __len2) {

  1470     __len11 = __len1 / 2;

  1471     advance(__first_cut, __len11);

  1472     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);

  1473     __len22 += distance(__middle, __second_cut);

  1474   }

  1475   else {

  1476     __len22 = __len2 / 2;

  1477     advance(__second_cut, __len22);

  1478     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);

  1479     __len11 +=distance(__first, __first_cut);

  1480   }

  1481   _BidirectionalIter __new_middle

  1482     = __rotate(__first_cut, __middle, __second_cut);

  1483   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,

  1484                          __comp);

  1485   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,

  1486                          __len2 - __len22, __comp);

  1487 }

  1489 template <class _BidirectionalIter1, class _BidirectionalIter2,

  1490           class _BidirectionalIter3, class _Compare>

  1491 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,

  1492                                      _BidirectionalIter1 __last1,

  1493                                      _BidirectionalIter2 __first2,

  1494                                      _BidirectionalIter2 __last2,

  1495                                      _BidirectionalIter3 __result,

  1496                                      _Compare __comp) {

  1497   if (__first1 == __last1)

  1498     return copy_backward(__first2, __last2, __result);

  1499   if (__first2 == __last2)

  1500     return copy_backward(__first1, __last1, __result);

  1501   --__last1;

  1502   --__last2;

  1503   for (;;) {

  1504     if (__comp(*__last2, *__last1)) {

  1505       _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1506       *--__result = *__last1;

  1507       if (__first1 == __last1)

  1508         return copy_backward(__first2, ++__last2, __result);

  1509       --__last1;

  1510     }

  1511     else {

  1512       *--__result = *__last2;

  1513       if (__first2 == __last2)

  1514         return copy_backward(__first1, ++__last1, __result);

  1515       --__last2;

  1516     }

  1517   }

  1518 }

  1520 template <class _BidirectionalIter, class _Tp,

  1521           class _Distance, class _Compare>

  1522 inline void __inplace_merge_aux(_BidirectionalIter __first,

  1523                                 _BidirectionalIter __middle,

  1524                                 _BidirectionalIter __last, _Tp*, _Distance*,

  1525                                 _Compare __comp) {

  1526   _Distance __len1 = distance(__first, __middle);

  1527   _Distance __len2 = distance(__middle, __last);

  1529   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);

  1530   if (__buf.begin() == 0)

  1531     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);

  1532   else

  1533     __merge_adaptive(__first, __middle, __last, __len1, __len2,

  1534                      __buf.begin(), _Distance(__buf.size()),

  1535                      __comp);

  1536 }

  1538 _STLP_MOVE_TO_STD_NAMESPACE

  1540 template <class _BidirectionalIter>

  1541 void inplace_merge(_BidirectionalIter __first,

  1542                    _BidirectionalIter __middle,

  1543                    _BidirectionalIter __last) {

  1544   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))

  1545   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))

  1546   if (__first == __middle || __middle == __last)

  1547     return;

  1548   _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,

  1549                                  _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),

  1550                                  _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));

  1551 }

  1553 template <class _BidirectionalIter, class _Compare>

  1554 void inplace_merge(_BidirectionalIter __first,

  1555                    _BidirectionalIter __middle,

  1556                    _BidirectionalIter __last, _Compare __comp) {

  1557   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))

  1558   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))

  1559   if (__first == __middle || __middle == __last)

  1560     return;

  1561   _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,

  1562                                  _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),

  1563                                  __comp);

  1564 }

  1566 _STLP_MOVE_TO_PRIV_NAMESPACE

  1568 template <class _InputIter1, class _InputIter2, class _Compare>

  1569 bool __includes(_InputIter1 __first1, _InputIter1 __last1,

  1570                 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {

  1571   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1572   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

  1573   while (__first1 != __last1 && __first2 != __last2)

  1574     if (__comp(*__first2, *__first1)) {

  1575       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1576       return false;

  1577     }

  1578     else if (__comp(*__first1, *__first2))

  1579       ++__first1;

  1580     else

  1581       ++__first1, ++__first2;

  1583   return __first2 == __last2;

  1584 }

  1586 _STLP_MOVE_TO_STD_NAMESPACE

  1588 template <class _InputIter1, class _InputIter2, class _Compare>

  1589 bool includes(_InputIter1 __first1, _InputIter1 __last1,

  1590               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {

  1591   return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp);

  1592 }

  1594 template <class _InputIter1, class _InputIter2>

  1595 bool includes(_InputIter1 __first1, _InputIter1 __last1,

  1596               _InputIter2 __first2, _InputIter2 __last2) {

  1597   return _STLP_PRIV __includes(__first1, __last1, __first2, __last2,

  1598                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1599 }

  1601 _STLP_MOVE_TO_PRIV_NAMESPACE

  1603 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1604           class _Compare>

  1605 _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,

  1606                         _InputIter2 __first2, _InputIter2 __last2,

  1607                         _OutputIter __result, _Compare __comp) {

  1608   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1609   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

  1610   while (__first1 != __last1 && __first2 != __last2) {

  1611     if (__comp(*__first1, *__first2)) {

  1612       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1613       *__result = *__first1;

  1614       ++__first1;

  1615     }

  1616     else if (__comp(*__first2, *__first1)) {

  1617       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1618       *__result = *__first2;

  1619       ++__first2;

  1620     }

  1621     else {

  1622       *__result = *__first1;

  1623       ++__first1;

  1624       ++__first2;

  1625     }

  1626     ++__result;

  1627   }

  1628   return copy(__first2, __last2, copy(__first1, __last1, __result));

  1629 }

  1631 _STLP_MOVE_TO_STD_NAMESPACE

  1633 template <class _InputIter1, class _InputIter2, class _OutputIter>

  1634 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,

  1635                       _InputIter2 __first2, _InputIter2 __last2,

  1636                       _OutputIter __result) {

  1637   return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result,

  1638                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1639 }

  1641 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1642           class _Compare>

  1643 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,

  1644                       _InputIter2 __first2, _InputIter2 __last2,

  1645                       _OutputIter __result, _Compare __comp) {

  1646   return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp);

  1647 }

  1649 _STLP_MOVE_TO_PRIV_NAMESPACE

  1651 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1652           class _Compare>

  1653 _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,

  1654                                _InputIter2 __first2, _InputIter2 __last2,

  1655                                _OutputIter __result, _Compare __comp) {

  1656   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1657   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

  1658   while (__first1 != __last1 && __first2 != __last2)

  1659     if (__comp(*__first1, *__first2)) {

  1660       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1661       ++__first1;

  1662     }

  1663     else if (__comp(*__first2, *__first1))

  1664       ++__first2;

  1665     else {

  1666       *__result = *__first1;

  1667       ++__first1;

  1668       ++__first2;

  1669       ++__result;

  1670     }

  1671   return __result;

  1672 }

  1674 _STLP_MOVE_TO_STD_NAMESPACE

  1676 template <class _InputIter1, class _InputIter2, class _OutputIter>

  1677 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,

  1678                              _InputIter2 __first2, _InputIter2 __last2,

  1679                              _OutputIter __result) {

  1680   return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result,

  1681                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1682 }

  1684 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1685           class _Compare>

  1686 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,

  1687                              _InputIter2 __first2, _InputIter2 __last2,

  1688                              _OutputIter __result, _Compare __comp) {

  1689   return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);

  1690 }

  1692 _STLP_MOVE_TO_PRIV_NAMESPACE

  1694 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1695           class _Compare>

  1696 _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,

  1697                              _InputIter2 __first2, _InputIter2 __last2,

  1698                              _OutputIter __result, _Compare __comp) {

  1699   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1700   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

  1701   while (__first1 != __last1 && __first2 != __last2)

  1702     if (__comp(*__first1, *__first2)) {

  1703       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1704       *__result = *__first1;

  1705       ++__first1;

  1706       ++__result;

  1707     }

  1708     else if (__comp(*__first2, *__first1))

  1709       ++__first2;

  1710     else {

  1711       ++__first1;

  1712       ++__first2;

  1713     }

  1714   return copy(__first1, __last1, __result);

  1715 }

  1717 _STLP_MOVE_TO_STD_NAMESPACE

  1719 template <class _InputIter1, class _InputIter2, class _OutputIter>

  1720 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,

  1721                            _InputIter2 __first2, _InputIter2 __last2,

  1722                            _OutputIter __result) {

  1723   return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result,

  1724                                      _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1725 }

  1727 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1728           class _Compare>

  1729 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,

  1730                            _InputIter2 __first2, _InputIter2 __last2,

  1731                            _OutputIter __result, _Compare __comp) {

  1732   return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp);

  1733 }

  1735 _STLP_MOVE_TO_PRIV_NAMESPACE

  1737 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>

  1738 _OutputIter

  1739 __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

  1740                            _InputIter2 __first2, _InputIter2 __last2,

  1741                            _OutputIter __result, _Compare __comp) {

  1742   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1743   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

  1744   while (__first1 != __last1 && __first2 != __last2) {

  1745     if (__comp(*__first1, *__first2)) {

  1746       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1747       *__result = *__first1;

  1748       ++__first1;

  1749       ++__result;

  1750     }

  1751     else if (__comp(*__first2, *__first1)) {

  1752       *__result = *__first2;

  1753       ++__first2;

  1754       ++__result;

  1755     }

  1756     else {

  1757       ++__first1;

  1758       ++__first2;

  1759     }

  1760   }

  1761   return copy(__first2, __last2, copy(__first1, __last1, __result));

  1762 }

  1764 _STLP_MOVE_TO_STD_NAMESPACE

  1766 template <class _InputIter1, class _InputIter2, class _OutputIter>

  1767 _OutputIter

  1768 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

  1769                          _InputIter2 __first2, _InputIter2 __last2,

  1770                          _OutputIter __result) {

  1771   return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,

  1772                                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1773 }

  1775 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>

  1776 _OutputIter

  1777 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

  1778                          _InputIter2 __first2, _InputIter2 __last2,

  1779                          _OutputIter __result,

  1780                          _Compare __comp) {

  1781   return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);

  1782 }

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

  1785 // comparison function.

  1787 template <class _ForwardIter>

  1788 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {

  1789   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1790   if (__first == __last) return __first;

  1791   _ForwardIter __result = __first;

  1792   while (++__first != __last)

  1793     if (*__result < *__first)

  1794       __result = __first;

  1795   return __result;

  1796 }

  1798 template <class _ForwardIter, class _Compare>

  1799 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,

  1800                          _Compare __comp) {

  1801   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1802   if (__first == __last) return __first;

  1803   _ForwardIter __result = __first;

  1804   while (++__first != __last) {

  1805     if (__comp(*__result, *__first)) {

  1806       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1807       __result = __first;

  1808     }

  1809   }

  1810   return __result;

  1811 }

  1813 template <class _ForwardIter>

  1814 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {

  1815   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1816   if (__first == __last) return __first;

  1817   _ForwardIter __result = __first;

  1818   while (++__first != __last)

  1819     if (*__first < *__result)

  1820       __result = __first;

  1821   return __result;

  1822 }

  1824 template <class _ForwardIter, class _Compare>

  1825 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,

  1826                          _Compare __comp) {

  1827   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1828   if (__first == __last) return __first;

  1829   _ForwardIter __result = __first;

  1830   while (++__first != __last) {

  1831     if (__comp(*__first, *__result)) {

  1832       _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1833       __result = __first;

  1834     }

  1835   }

  1836   return __result;

  1837 }

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

  1840 // supplied comparison function.

  1841 _STLP_MOVE_TO_PRIV_NAMESPACE

  1843 template <class _BidirectionalIter, class _Compare>

  1844 bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

  1845                         _Compare __comp) {

  1846   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1847   if (__first == __last)

  1848     return false;

  1849   _BidirectionalIter __i = __first;

  1850   ++__i;

  1851   if (__i == __last)

  1852     return false;

  1853   __i = __last;

  1854   --__i;

  1856   for(;;) {

  1857     _BidirectionalIter __ii = __i;

  1858     --__i;

  1859     if (__comp(*__i, *__ii)) {

  1860       _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1861       _BidirectionalIter __j = __last;

  1862       while (!__comp(*__i, *--__j)) {}

  1863       iter_swap(__i, __j);

  1864       reverse(__ii, __last);

  1865       return true;

  1866     }

  1867     if (__i == __first) {

  1868       reverse(__first, __last);

  1869       return false;

  1870     }

  1871   }

  1872 #if defined (_STLP_NEED_UNREACHABLE_RETURN)

  1873     return false;

  1874 #endif

  1875 }

  1877 _STLP_MOVE_TO_STD_NAMESPACE

  1879 template <class _BidirectionalIter>

  1880 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {

  1881   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1882   return _STLP_PRIV __next_permutation(__first, __last,

  1883                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));

  1884 }

  1886 template <class _BidirectionalIter, class _Compare>

  1887 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

  1888                       _Compare __comp) {

  1889   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1890   return _STLP_PRIV __next_permutation(__first, __last, __comp);

  1891 }

  1893 _STLP_MOVE_TO_PRIV_NAMESPACE

  1895 template <class _BidirectionalIter, class _Compare>

  1896 bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

  1897                         _Compare __comp) {

  1898   if (__first == __last)

  1899     return false;

  1900   _BidirectionalIter __i = __first;

  1901   ++__i;

  1902   if (__i == __last)

  1903     return false;

  1904   __i = __last;

  1905   --__i;

  1907   for(;;) {

  1908     _BidirectionalIter __ii = __i;

  1909     --__i;

  1910     if (__comp(*__ii, *__i)) {

  1911       _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1912       _BidirectionalIter __j = __last;

  1913       while (!__comp(*--__j, *__i)) {}

  1914       iter_swap(__i, __j);

  1915       reverse(__ii, __last);

  1916       return true;

  1917     }

  1918     if (__i == __first) {

  1919       reverse(__first, __last);

  1920       return false;

  1921     }

  1922   }

  1923 #if defined (_STLP_NEED_UNREACHABLE_RETURN)

  1924     return false;

  1925 #endif

  1926 }

  1928 _STLP_MOVE_TO_STD_NAMESPACE

  1930 template <class _BidirectionalIter>

  1931 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {

  1932   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1933   return _STLP_PRIV __prev_permutation(__first, __last,

  1934                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));

  1935 }

  1937 template <class _BidirectionalIter, class _Compare>

  1938 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

  1939                       _Compare __comp) {

  1940   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1941   return _STLP_PRIV __prev_permutation(__first, __last, __comp);

  1942 }

  1944 #if !defined (_STLP_NO_EXTENSIONS)

  1946 // is_heap, a predicate testing whether or not a range is

  1947 // a heap.  This function is an extension, not part of the C++

  1948 // standard.

  1949 _STLP_MOVE_TO_PRIV_NAMESPACE

  1951 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>

  1952 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,

  1953                _Distance __n) {

  1954   _Distance __parent = 0;

  1955   for (_Distance __child = 1; __child < __n; ++__child) {

  1956     if (__comp(__first[__parent], __first[__child])) {

  1957       _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1958       return false;

  1959     }

  1960     if ((__child & 1) == 0)

  1961       ++__parent;

  1962   }

  1963   return true;

  1964 }

  1966 _STLP_MOVE_TO_STD_NAMESPACE

  1968 template <class _RandomAccessIter>

  1969 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) {

  1970   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1971   return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);

  1972 }

  1974 template <class _RandomAccessIter, class _StrictWeakOrdering>

  1975 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,

  1976              _StrictWeakOrdering __comp) {

  1977   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  1978   return _STLP_PRIV __is_heap(__first, __comp, __last - __first);

  1979 }

  1982 _STLP_MOVE_TO_PRIV_NAMESPACE

  1984 template <class _ForwardIter, class _StrictWeakOrdering>

  1985 bool __is_sorted(_ForwardIter __first, _ForwardIter __last,

  1986                  _StrictWeakOrdering __comp) {

  1987   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1988   if (__first == __last)

  1989     return true;

  1991   _ForwardIter __next = __first;

  1992   for (++__next; __next != __last; __first = __next, ++__next) {

  1993     if (__comp(*__next, *__first)) {

  1994       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

  1995       return false;

  1996     }

  1997   }

  1999   return true;

  2000 }

  2002 _STLP_MOVE_TO_STD_NAMESPACE

  2003 #endif /* _STLP_NO_EXTENSIONS */

  2005 _STLP_END_NAMESPACE

  2007 #undef __stl_threshold

  2009 #endif /* _STLP_ALGO_C */

  2010 // Local Variables:

  2011 // mode:C++

  2012 // End:

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