test: epoc32/include/stdapis/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 _STLP_BEGIN_NAMESPACE

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

    36 void __merge_without_buffer(_BidirectionalIter __first,

    37                             _BidirectionalIter __middle,

    38                             _BidirectionalIter __last,

    39                             _Distance __len1, _Distance __len2,

    40                             _Compare __comp);

    43 template <class _BidirectionalIter1, class _BidirectionalIter2,

    44           class _BidirectionalIter3, class _Compare>

    45 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,

    46                                      _BidirectionalIter1 __last1,

    47                                      _BidirectionalIter2 __first2,

    48                                      _BidirectionalIter2 __last2,

    49                                      _BidirectionalIter3 __result,

    50                                      _Compare __comp);

    52 template <class _Tp>

    53 # if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))

    54 inline

    55 # endif

    56 const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {

    57   if (__a < __b)

    58     if (__b < __c)

    59       return __b;

    60     else if (__a < __c)

    61       return __c;

    62     else

    63       return __a;

    64   else if (__a < __c)

    65     return __a;

    66   else if (__b < __c)

    67     return __c;

    68   else

    69     return __b;

    70 }

    72 template <class _Tp, class _Compare>

    73 # if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))

    74 inline

    75 # endif

    76 const _Tp&

    77 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {

    78   if (__comp(__a, __b))

    79     if (__comp(__b, __c))

    80       return __b;

    81     else if (__comp(__a, __c))

    82       return __c;

    83     else

    84       return __a;

    85   else if (__comp(__a, __c))

    86     return __a;

    87   else if (__comp(__b, __c))

    88     return __c;

    89   else

    90     return __b;

    91 }

    93 template <class _ForwardIter1, class _ForwardIter2>

    94 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,

    95                      _ForwardIter2 __first2, _ForwardIter2 __last2)

    96 {

    97   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

    98   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

    99   // Test for empty ranges

   100   if (__first1 == __last1 || __first2 == __last2)

   101     return __first1;

   103   // Test for a pattern of length 1.

   104   _ForwardIter2 __tmp(__first2);

   105   ++__tmp;

   106   if (__tmp == __last2)

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

   109   // General case.

   110   _ForwardIter2 __p1 = __first2;

   111   ++__p1;

   113   _ForwardIter1 __current = __first1;

   115   while (__first1 != __last1) {

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

   117     if (__first1 == __last1)

   118       return __last1;

   120     _ForwardIter2 __p = __p1;

   121     __current = __first1;

   122     if (++__current == __last1)

   123       return __last1;

   125     while (*__current == *__p) {

   126       if (++__p == __last2)

   127         return __first1;

   128       if (++__current == __last1)

   129         return __last1;

   130     }

   132     ++__first1;

   133   }

   134   return __first1;

   135 }

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

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

   140 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

   141                       _Integer __count, const _Tp& __val) {

   142   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   143   if (__count <= 0)

   144     return __first;

   145   else {

   146     __first = find(__first, __last, __val);

   147     while (__first != __last) {

   148       _Integer __n = __count - 1;

   149       _ForwardIter __i = __first;

   150       ++__i;

   151       while (__i != __last && __n != 0 && *__i == __val) {

   152         ++__i;

   153         --__n;

   154       }

   155       if (__n == 0)

   156         return __first;

   157       else

   158         __first = find(__i, __last, __val);

   159     }

   160     return __last;

   161   }

   162 }

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

   165 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

   166                       _Integer __count, const _Tp& __val,

   167                       _BinaryPred __binary_pred) {

   168   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   169   if (__count <= 0)

   170     return __first;

   171   else {

   172     while (__first != __last) {

   173       if (__binary_pred(*__first, __val))

   174         break;

   175       ++__first;

   176     }

   177     while (__first != __last) {

   178       _Integer __n = __count - 1;

   179       _ForwardIter __i = __first;

   180       ++__i;

   181       while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {

   182         ++__i;

   183         --__n;

   184       }

   185       if (__n == 0)

   186         return __first;

   187       else {

   188         while (__i != __last) {

   189           if (__binary_pred(*__i, __val))

   190             break;

   191           ++__i;

   192         }

   193         __first = __i;

   194       }

   195     }

   196     return __last;

   197   }

   198 }

   200 template <class _ForwardIter1, class _ForwardIter2>

   201 _ForwardIter1

   202 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,

   203          _ForwardIter2 __first2, _ForwardIter2 __last2)

   204 {

   205   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

   206   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

   207   return __find_end(__first1, __last1, __first2, __last2,

   208 # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

   209                     _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),

   210                     _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),

   211 # else

   212 		    forward_iterator_tag(),

   213                     forward_iterator_tag(),

   214 # endif

   215                     __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))

   216     );

   217 }

   219 // unique and unique_copy

   220 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,

   221 					    class _Tp>

   222 _STLP_INLINE_LOOP _OutputIterator

   223 __unique_copy(_InputIterator __first, _InputIterator __last,

   224               _OutputIterator __result,

   225               _BinaryPredicate __binary_pred, _Tp*) {

   226   _Tp __val = *__first;

   227  _STLP_PUSH_STACK_ITEM(_Tp, &__val)

   228   *__result = __val;

   229   while (++__first != __last)

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

   231       __val = *__first;

   232       *++__result = __val;

   233     }

   234   return ++__result;

   235 }

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

   238 inline _OutputIter

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

   240               _BinaryPredicate __binary_pred, const output_iterator_tag &) {

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

   242 }

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

   245 _STLP_INLINE_LOOP _ForwardIter

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

   247               _BinaryPredicate __binary_pred, const forward_iterator_tag &) {

   248   *__result = *__first;

   249   while (++__first != __last)

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

   251   return ++__result;

   252 }

   254 # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)

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

   256 inline _BidirectionalIterator

   257 __unique_copy(_InputIterator __first, _InputIterator __last,

   258               _BidirectionalIterator __result, _BinaryPredicate __binary_pred,

   259               const bidirectional_iterator_tag &) {

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

   261 }

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

   264 inline _RandomAccessIterator

   265 __unique_copy(_InputIterator __first, _InputIterator __last,

   266               _RandomAccessIterator __result, _BinaryPredicate __binary_pred,

   267               const random_access_iterator_tag &) {

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

   269 }

   270 # endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */

   273 template <class _InputIter, class _OutputIter>

   274 _OutputIter

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

   276   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   277   if (__first == __last) return __result;

   278   return __unique_copy(__first, __last, __result, __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),

   279                        _STLP_ITERATOR_CATEGORY(__result, _OutputIter));

   280 }

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

   283 _OutputIter

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

   285             _BinaryPredicate __binary_pred) {

   286   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   287   if (__first == __last) return __result;

   288   return __unique_copy(__first, __last, __result, __binary_pred,

   289                        _STLP_ITERATOR_CATEGORY(__result, _OutputIter));

   290 }

   292 // rotate and rotate_copy, and their auxiliary functions

   294 template <class _ForwardIter, class _Distance>

   295 _ForwardIter __rotate(_ForwardIter __first,

   296                       _ForwardIter __middle,

   297                       _ForwardIter __last,

   298                       _Distance*,

   299                       const forward_iterator_tag &) {

   300   if (__first == __middle)

   301     return __last;

   302   if (__last  == __middle)

   303     return __first;

   305   _ForwardIter __first2 = __middle;

   306   do {

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

   308     if (__first == __middle)

   309       __middle = __first2;

   310   } while (__first2 != __last);

   312   _ForwardIter __new_middle = __first;

   314   __first2 = __middle;

   316   while (__first2 != __last) {

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

   318     if (__first == __middle)

   319       __middle = __first2;

   320     else if (__first2 == __last)

   321       __first2 = __middle;

   322   }

   324   return __new_middle;

   325 }

   327 template <class _BidirectionalIter, class _Distance>

   328 _BidirectionalIter __rotate(_BidirectionalIter __first,

   329                             _BidirectionalIter __middle,

   330                             _BidirectionalIter __last,

   331                             _Distance*,

   332                             const bidirectional_iterator_tag &) {

   333   if (__first == __middle)

   334     return __last;

   335   if (__last  == __middle)

   336     return __first;

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

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

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

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

   344   if (__first == __middle) {

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

   346     return __last;

   347   }

   348   else {

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

   350     return __first;

   351   }

   352 }

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

   355 _RandomAccessIter __rotate(_RandomAccessIter __first,

   356                            _RandomAccessIter __middle,

   357                            _RandomAccessIter __last,

   358                            _Distance *, _Tp *) {

   360   _Distance __n = __last   - __first;

   361   _Distance __k = __middle - __first;

   362   _Distance __l = __n - __k;

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

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

   366     return __last;

   368   if (__k == __l) {

   369     swap_ranges(__first, __middle, __middle);

   370     return __result;

   371   }

   373   _Distance __d = __gcd(__n, __k);

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

   376     _Tp __tmp = *__first;

   377     _STLP_PUSH_STACK_ITEM(_Tp, &__tmp)

   378     _RandomAccessIter __p = __first;

   380     if (__k < __l) {

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

   382 	if (__p > __first + __l) {

   383           *__p = *(__p - __l);

   384           __p -= __l;

   385         }

   387         *__p = *(__p + __k);

   388         __p += __k;

   389       }

   390     }

   392     else {

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

   394         if (__p < __last - __k) {

   395           *__p = *(__p + __k);

   396           __p += __k;

   397         }

   399         *__p = * (__p - __l);

   400         __p -= __l;

   401       }

   402     }

   404     *__p = __tmp;

   405     ++__first;

   406   }

   408   return __result;

   409 }

   411 template <class _RandomAccessIter, class _Distance>

   412 inline _RandomAccessIter

   413 __rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,

   414          _Distance * __dis, const random_access_iterator_tag &) {

   415   return __rotate(__first, __middle, __last,

   416                   __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));

   417 }

   419 template <class _ForwardIter>

   420 _ForwardIter

   421 rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {

   422   _STLP_DEBUG_CHECK(__check_range(__first, __middle))

   423   _STLP_DEBUG_CHECK(__check_range(__middle, __last))

   424   return __rotate(__first, __middle, __last,

   425                   _STLP_DISTANCE_TYPE(__first, _ForwardIter),

   426                   _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   427 }

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

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

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

   433 template <class _Distance>

   434 inline _Distance __random_number(_Distance __n) {

   435 #ifdef _STLP_NO_DRAND48

   436   return rand() % __n;

   437 #else

   438   return lrand48() % __n;

   439 #endif

   440 }

   442 template <class _RandomAccessIter>

   443 void random_shuffle(_RandomAccessIter __first,

   444 		    _RandomAccessIter __last) {

   445   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   446   if (__first == __last) return;

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

   448     iter_swap(__i, __first + __random_number((__i - __first) + 1));

   449 }

   451 template <class _RandomAccessIter, class _RandomNumberGenerator>

   452 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,

   453                     _RandomNumberGenerator& __rand) {

   454   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   455   if (__first == __last) return;

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

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

   458 }

   460 # ifndef _STLP_NO_EXTENSIONS

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

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

   465 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

   466                             _OutputIter __stl_out, const _Distance __n)

   467 {

   468   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   469   _Distance __remaining = distance(__first, __last);

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

   472   while (__m > 0) {

   473     if (__random_number(__remaining) < __m) {

   474       *__stl_out = *__first;

   475       ++__stl_out;

   476       --__m;

   477     }

   479     --__remaining;

   480     ++__first;

   481   }

   482   return __stl_out;

   483 }

   486 template <class _ForwardIter, class _OutputIter, class _Distance,

   487           class _RandomNumberGenerator>

   488 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

   489                             _OutputIter __stl_out, const _Distance __n,

   490                             _RandomNumberGenerator& __rand)

   491 {

   492   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   493   _Distance __remaining = distance(__first, __last);

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

   496   while (__m > 0) {

   497     if (__rand(__remaining) < __m) {

   498       *__stl_out = *__first;

   499       ++__stl_out;

   500       --__m;

   501     }

   503     --__remaining;

   504     ++__first;

   505   }

   506   return __stl_out;

   507 }

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

   510 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,

   511                                   _RandomAccessIter __stl_out,

   512                                   const _Distance __n)

   513 {

   514   _Distance __m = 0;

   515   _Distance __t = __n;

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

   517     __stl_out[__m] = *__first;

   519   while (__first != __last) {

   520     ++__t;

   521     _Distance __M = __random_number(__t);

   522     if (__M < __n)

   523       __stl_out[__M] = *__first;

   524     ++__first;

   525   }

   527   return __stl_out + __m;

   528 }

   530 template <class _InputIter, class _RandomAccessIter,

   531           class _RandomNumberGenerator, class _Distance>

   532 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,

   533                                   _RandomAccessIter __stl_out,

   534                                   _RandomNumberGenerator& __rand,

   535                                   const _Distance __n)

   536 {

   537   _Distance __m = 0;

   538   _Distance __t = __n;

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

   540     __stl_out[__m] = *__first;

   542   while (__first != __last) {

   543     ++__t;

   544     _Distance __M = __rand(__t);

   545     if (__M < __n)

   546       __stl_out[__M] = *__first;

   547     ++__first;

   548   }

   550   return __stl_out + __m;

   551 }

   553 template <class _InputIter, class _RandomAccessIter>

   554 _RandomAccessIter

   555 random_sample(_InputIter __first, _InputIter __last,

   556               _RandomAccessIter __out_first, _RandomAccessIter __out_last)

   557 {

   558   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   559   _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))

   560   return __random_sample(__first, __last,

   561                          __out_first, __out_last - __out_first);

   562 }

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

   565 _RandomAccessIter

   566 random_sample(_InputIter __first, _InputIter __last,

   567               _RandomAccessIter __out_first, _RandomAccessIter __out_last,

   568               _RandomNumberGenerator& __rand)

   569 {

   570   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   571   _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))

   572   return __random_sample(__first, __last,

   573                          __out_first, __rand,

   574                          __out_last - __out_first);

   575 }

   577 # endif /* _STLP_NO_EXTENSIONS */

   579 // partition, stable_partition, and their auxiliary functions

   581 template <class _ForwardIter, class _Predicate>

   582 _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,

   583                                            _ForwardIter __last,

   584                                            _Predicate   __pred,

   585                                            const forward_iterator_tag &) {

   586   if (__first == __last) return __first;

   588   while (__pred(*__first))

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

   591   _ForwardIter __next = __first;

   593   while (++__next != __last)

   594     if (__pred(*__next)) {

   595       swap(*__first, *__next);

   596       ++__first;

   597     }

   598   return __first;

   599 }

   601 /* bug fix- start*/

   603 template <class _ForwardIter>

   604 _ForwardIter

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

   606   _STLP_DEBUG_CHECK(__check_range(__first, __middle))

   607   _STLP_DEBUG_CHECK(__check_range(__middle, __last))

   608   return __rotate_aux(__first, __middle, __last,

   609                       _STLP_DISTANCE_TYPE(__first, _ForwardIter),

   610                       _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   611 }

   613 template <class _ForwardIter, class _Distance>

   614 _ForwardIter __rotate_aux(_ForwardIter __first,

   615                           _ForwardIter __middle,

   616                           _ForwardIter __last,

   617                           _Distance*,

   618                           const forward_iterator_tag &) {

   619   if (__first == __middle)

   620     return __last;

   621   if (__last  == __middle)

   622     return __first;

   624   _ForwardIter __first2 = __middle;

   625   do {

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

   627     if (__first == __middle)

   628       __middle = __first2;

   629   } while (__first2 != __last);

   631   _ForwardIter __new_middle = __first;

   633   __first2 = __middle;

   635   while (__first2 != __last) {

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

   637     if (__first == __middle)

   638       __middle = __first2;

   639     else if (__first2 == __last)

   640       __first2 = __middle;

   641   }

   643   return __new_middle;

   644 }

   647 template <class _ForwardIter, class _Pointer, class _Predicate,

   648           class _Distance>

   649 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,

   650                                          _ForwardIter __last,

   651                                          _Predicate __pred, _Distance __len,

   652                                          _Pointer __buffer, _Distance __buffer_size,

   653                                          bool __pred_of_first, bool __pred_of_before_last) {

   654   if (__len <= __buffer_size) {

   655     _ForwardIter __result1 = __first;

   656     _Pointer __result2 = __buffer;

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

   658       *__result2 = *__first;

   659       ++__result2; ++__first; --__len;

   660     }

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

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

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

   664         *__result1 = *__first;

   665         ++__result1;

   666       }

   667       else {

   668         *__result2 = *__first;

   669         ++__result2;

   670       }

   671     }

   672     copy(__buffer, __result2, __result1);

   673     return __result1;

   674   }

   675   else {

   676     _ForwardIter __middle = __first;

   677     _Distance __half_len = __len / 2;

   678     advance(__middle, __half_len);

   679     return __rotate(__stable_partition_adaptive(

   680                           __first, __middle, __pred,

   681                           __half_len, __buffer, __buffer_size,

   682                           __pred_of_first, false),

   683                     __middle,

   684                     __stable_partition_adaptive(

   685                           __middle, __last, __pred,

   686                           __len - __half_len, __buffer, __buffer_size,

   687                           true, __pred_of_before_last));

   688   }

   689 }

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

   693 _ForwardIter __inplace_stable_partition(_ForwardIter __first,

   694                                         _ForwardIter __last,

   695                                         _Predicate __pred, _Distance __len,

   696                                         bool __pred_of_first, bool __pred_of_before_last) {

   697   if (__len == 1)

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

   699   _ForwardIter __middle = __first;

   700   _Distance __half_len = __len / 2;

   701   advance(__middle, __half_len);

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

   703                   __middle,

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

   705 }

   709 template <class _ForwardIter, class _Predicate>

   710 _ForwardIter

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

   712   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   713   for (;;) {

   714     if (__first == __last)

   715       return __first;

   716     else if (__pred(*__first))

   717       ++__first;

   718     else

   719       break;

   720   }

   721   return  __stable_partition_aux(__first, __last, __pred,

   722                                            _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   723 }

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

   727 inline _ForwardIter

   728 __stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,

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

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

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

   732     __stable_partition_adaptive(__first, __last, __pred,

   733                                 _Distance(__buf.requested_size()),

   734                                 __buf.begin(), __buf.size(),

   735                                 false, __pred_of_before_last)  :

   736     __inplace_stable_partition(__first, __last, __pred,

   737                                _Distance(__buf.requested_size()),

   738                                false, __pred_of_before_last);

   740 }

   742 template <class _ForwardIter, class _Predicate>

   743 _ForwardIter

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

   745                        const forward_iterator_tag &) {

   746   return __stable_partition_aux_aux(__first, __last, __pred,

   747                                     _STLP_VALUE_TYPE(__first, _ForwardIter),

   748                                     _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   749 }

   752 /* bug fix- end*/

   756 template <class _BidirectionalIter, class _Predicate>

   757 _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,

   758                                                  _BidirectionalIter __last,

   759                                                  _Predicate __pred,

   760                                                  const bidirectional_iterator_tag &) {

   761   while (true) {

   762     while (true)

   763       if (__first == __last)

   764         return __first;

   765       else if (__pred(*__first))

   766         ++__first;

   767       else

   768         break;

   769     --__last;

   770     while (true)

   771       if (__first == __last)

   772         return __first;

   773       else if (!__pred(*__last))

   774         --__last;

   775       else

   776         break;

   777     iter_swap(__first, __last);

   778     ++__first;

   779   }

   780 }

   782 # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)

   783 template <class _BidirectionalIter, class _Predicate>

   784 inline

   785 _BidirectionalIter __partition(_BidirectionalIter __first,

   786                                _BidirectionalIter __last,

   787 			       _Predicate __pred,

   788 			       const random_access_iterator_tag &) {

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

   790 }

   791 # endif

   793 template <class _ForwardIter, class _Predicate>

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

   795   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   796   return __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

   797 }

   799 /*

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

   801 _ForwardIter __inplace_stable_partition(_ForwardIter __first,

   802                                         _ForwardIter __last,

   803                                         _Predicate __pred, _Distance __len) {

   804   if (__len == 1)

   805     return __pred(*__first) ? __last : __first;

   806   _ForwardIter __middle = __first;

   807   advance(__middle, __len / 2);

   808   return rotate(__inplace_stable_partition(__first, __middle, __pred,

   809                                            __len / 2),

   810                 __middle,

   811                 __inplace_stable_partition(__middle, __last, __pred,

   812                                            __len - __len / 2));

   813 }

   816 template <class _ForwardIter, class _Pointer, class _Predicate,

   817           class _Distance>

   818 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,

   819                                          _ForwardIter __last,

   820                                          _Predicate __pred, _Distance __len,

   821                                          _Pointer __buffer,

   822                                          _Distance __buffer_size)

   823 {

   824   if (__len <= __buffer_size) {

   825     _ForwardIter __result1 = __first;

   826     _Pointer __result2 = __buffer;

   827     for ( ; __first != __last ; ++__first)

   828       if (__pred(*__first)) {

   829         *__result1 = *__first;

   830         ++__result1;

   831       }

   832       else {

   833         *__result2 = *__first;

   834         ++__result2;

   835       }

   836     copy(__buffer, __result2, __result1);

   837     return __result1;

   838   }

   839   else {

   840     _ForwardIter __middle = __first;

   841     advance(__middle, __len / 2);

   842     return rotate(__stable_partition_adaptive(

   843                           __first, __middle, __pred,

   844                           _Distance(__len / 2), __buffer, __buffer_size),

   845                     __middle,

   846                     __stable_partition_adaptive(

   847                           __middle, __last, __pred,

   848                           _Distance(__len - __len / 2), __buffer, __buffer_size));

   849   }

   850 }

   851 */ //bug fix

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

   853 inline _ForwardIter

   854 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last,

   855                        _Predicate __pred, _Tp*, _Distance*)

   856 {

   857   typedef _Temporary_buffer<_ForwardIter, _Tp> _TmpBuf;

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

   859   _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);

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

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

   863     __stable_partition_adaptive(__first, __last, __pred,

   864 				_Distance(__buf.requested_size()),

   865 				__buf.begin(), _Distance(__buf.size()))  :

   866     __inplace_stable_partition(__first, __last, __pred,

   867 			       _Distance(__buf.requested_size()));

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

   869 }

   870 /*

   871 template <class _ForwardIter, class _Predicate>

   872 _ForwardIter

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

   874   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   875   if (__first == __last)

   876     return __first;

   877   else

   878     return __stable_partition_aux(__first, __last, __pred,

   879                                   _STLP_VALUE_TYPE(__first, _ForwardIter),

   880                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   881 }

   882 */ //bug fix

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

   884 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,

   885                                         _RandomAccessIter __last,

   886                                         _Tp __pivot, _Compare __comp)

   887 {

   888   _STLP_PUSH_STACK_ITEM(_Tp, &__pivot)

   889   while (true) {

   890     while (__comp(*__first, __pivot))

   891       ++__first;

   892     --__last;

   893     while (__comp(__pivot, *__last))

   894       --__last;

   895     if (!(__first < __last))

   896       return __first;

   897     iter_swap(__first, __last);

   898     ++__first;

   899   }

   900 }

   902 // sort() and its auxiliary functions.

   904 # define  __stl_threshold  16

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

   907 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,

   908                                _Compare __comp) {

   909    _STLP_PUSH_STACK_ITEM(_Tp, &__val)

   910   _RandomAccessIter __next = __last;

   911   --__next;

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

   913     *__last = *__next;

   914     __last = __next;

   915     --__next;

   916   }

   917   *__last = __val;

   918 }

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

   921 inline void __linear_insert(_RandomAccessIter __first,

   922                             _RandomAccessIter __last, _Tp __val, _Compare __comp) {

   923   _STLP_PUSH_STACK_ITEM(_Tp, &__val)

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

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

   926     *__first = __val;

   927   }

   928   else

   929     __unguarded_linear_insert(__last, __val, __comp);

   930 }

   932 template <class _RandomAccessIter, class _Compare>

   933 void __insertion_sort(_RandomAccessIter __first,

   934                       _RandomAccessIter __last, _Compare __comp) {

   935   if (__first == __last) return;

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

   937     __linear_insert(__first, __i, *__i, __comp);	//*TY 12/26/1998 - supply *__i as __val

   938 }

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

   941 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,

   942                                     _RandomAccessIter __last,

   943                                     _Tp*, _Compare __comp) {

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

   945     __unguarded_linear_insert(__i, _Tp(*__i), __comp);

   946 }

   948 template <class _RandomAccessIter, class _Compare>

   949 inline void __unguarded_insertion_sort(_RandomAccessIter __first,

   950                                        _RandomAccessIter __last,

   951                                        _Compare __comp) {

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

   953 }

   955 template <class _RandomAccessIter, class _Compare>

   956 void __final_insertion_sort(_RandomAccessIter __first,

   957                             _RandomAccessIter __last, _Compare __comp) {

   958   if (__last - __first > __stl_threshold) {

   959     __insertion_sort(__first, __first + __stl_threshold, __comp);

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

   961   }

   962   else

   963     __insertion_sort(__first, __last, __comp);

   964 }

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

   967 void __introsort_loop(_RandomAccessIter __first,

   968                       _RandomAccessIter __last, _Tp*,

   969                       _Size __depth_limit, _Compare __comp)

   970 {

   971   while (__last - __first > __stl_threshold) {

   972     if (__depth_limit == 0) {

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

   974       return;

   975     }

   976     --__depth_limit;

   977     _RandomAccessIter __cut =

   978       __unguarded_partition(__first, __last,

   979                             _Tp(__median(*__first,

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

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

   982        __comp);

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

   984     __last = __cut;

   985   }

   986 }

   988 template <class _RandomAccessIter>

   989 void sort(_RandomAccessIter __first, _RandomAccessIter __last) {

   990   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   991   if (__first != __last) {

   992     __introsort_loop(__first, __last,

   993                      _STLP_VALUE_TYPE(__first, _RandomAccessIter),

   994                      __lg(__last - __first) * 2, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)) );

   995     __final_insertion_sort(__first, __last, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

   996   }

   997 }

   999 template <class _RandomAccessIter, class _Compare>

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

  1001   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1002   if (__first != __last) {

  1003     __introsort_loop(__first, __last,

  1004                      _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1005                      __lg(__last - __first) * 2,

  1006                      __comp);

  1007     __final_insertion_sort(__first, __last, __comp);

  1008   }

  1009 }

  1011 // stable_sort() and its auxiliary functions.

  1013 template <class _RandomAccessIter, class _Compare>

  1014 void __inplace_stable_sort(_RandomAccessIter __first,

  1015                            _RandomAccessIter __last, _Compare __comp) {

  1016   if (__last - __first < 15) {

  1017     __insertion_sort(__first, __last, __comp);

  1018     return;

  1019   }

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

  1021   __inplace_stable_sort(__first, __middle, __comp);

  1022   __inplace_stable_sort(__middle, __last, __comp);

  1023   __merge_without_buffer(__first, __middle, __last,

  1024                          __middle - __first,

  1025                          __last - __middle,

  1026                          __comp);

  1027 }

  1029 template <class _RandomAccessIter1, class _RandomAccessIter2,

  1030           class _Distance, class _Compare>

  1031 void __merge_sort_loop(_RandomAccessIter1 __first,

  1032                        _RandomAccessIter1 __last,

  1033                        _RandomAccessIter2 __result, _Distance __step_size,

  1034                        _Compare __comp) {

  1035   _Distance __two_step = 2 * __step_size;

  1037   while (__last - __first >= __two_step) {

  1038     __result = merge(__first, __first + __step_size,

  1039                      __first + __step_size, __first + __two_step,

  1040                      __result,

  1041                      __comp);

  1042     __first += __two_step;

  1043   }

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

  1046   merge(__first, __first + __step_size,

  1047         __first + __step_size, __last,

  1048         __result,

  1049         __comp);

  1050 }

  1052 const int __stl_chunk_size = 7;

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

  1055 void __chunk_insertion_sort(_RandomAccessIter __first,

  1056                             _RandomAccessIter __last,

  1057                             _Distance __chunk_size, _Compare __comp)

  1058 {

  1059   while (__last - __first >= __chunk_size) {

  1060     __insertion_sort(__first, __first + __chunk_size, __comp);

  1061     __first += __chunk_size;

  1062   }

  1063   __insertion_sort(__first, __last, __comp);

  1064 }

  1066 template <class _RandomAccessIter, class _Pointer, class _Distance,

  1067           class _Compare>

  1068 void __merge_sort_with_buffer(_RandomAccessIter __first,

  1069                               _RandomAccessIter __last, _Pointer __buffer,

  1070                               _Distance*, _Compare __comp) {

  1071   _Distance __len = __last - __first;

  1072   _Pointer __buffer_last = __buffer + __len;

  1074   _Distance __step_size = __stl_chunk_size;

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

  1077   while (__step_size < __len) {

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

  1079     __step_size *= 2;

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

  1081     __step_size *= 2;

  1082   }

  1083 }

  1085 template <class _BidirectionalIter1, class _BidirectionalIter2,

  1086           class _Distance>

  1087 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,

  1088                                       _BidirectionalIter1 __middle,

  1089                                       _BidirectionalIter1 __last,

  1090                                       _Distance __len1, _Distance __len2,

  1091                                       _BidirectionalIter2 __buffer,

  1092                                       _Distance __buffer_size) {

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

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

  1095     copy_backward(__first, __middle, __last);

  1096     return copy(__buffer, __buffer_end, __first);

  1097   }

  1098   else if (__len1 <= __buffer_size) {

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

  1100     copy(__middle, __last, __first);

  1101     return copy_backward(__buffer, __buffer_end, __last);

  1102   }

  1103   else

  1104     return rotate(__first, __middle, __last);

  1105 }

  1107 template <class _BidirectionalIter, class _Distance, class _Pointer,

  1108           class _Compare>

  1109 void __merge_adaptive(_BidirectionalIter __first,

  1110                       _BidirectionalIter __middle,

  1111                       _BidirectionalIter __last,

  1112                       _Distance __len1, _Distance __len2,

  1113                       _Pointer __buffer, _Distance __buffer_size,

  1114                       _Compare __comp) {

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

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

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

  1118   }

  1119   else if (__len2 <= __buffer_size) {

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

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

  1122                      __comp);

  1123   }

  1124   else {

  1125     _BidirectionalIter __first_cut = __first;

  1126     _BidirectionalIter __second_cut = __middle;

  1127     _Distance __len11 = 0;

  1128     _Distance __len22 = 0;

  1129     if (__len1 > __len2) {

  1130       __len11 = __len1 / 2;

  1131       advance(__first_cut, __len11);

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

  1133       __len22 += distance(__middle, __second_cut);

  1134     }

  1135     else {

  1136       __len22 = __len2 / 2;

  1137       advance(__second_cut, __len22);

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

  1139       __len11 += distance(__first, __first_cut);

  1140     }

  1141     _BidirectionalIter __new_middle =

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

  1143                         __len22, __buffer, __buffer_size);

  1144     __merge_adaptive(__first, __first_cut, __new_middle, __len11,

  1145                      __len22, __buffer, __buffer_size, __comp);

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

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

  1148   }

  1149 }

  1151 template <class _RandomAccessIter, class _Pointer, class _Distance,

  1152           class _Compare>

  1153 void __stable_sort_adaptive(_RandomAccessIter __first,

  1154                             _RandomAccessIter __last, _Pointer __buffer,

  1155                             _Distance __buffer_size, _Compare __comp) {

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

  1157   _RandomAccessIter __middle = __first + __len;

  1158   if (__len > __buffer_size) {

  1159     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,

  1160                            __comp);

  1161     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,

  1162                            __comp);

  1163   }

  1164   else {

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

  1166                                __comp);

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

  1168                                __comp);

  1169   }

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

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

  1172                    __comp);

  1173 }

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

  1176 void __stable_sort_aux(_RandomAccessIter __first,

  1177 			      _RandomAccessIter __last, _Tp*, _Distance*,

  1178 			      _Compare __comp) {

  1180   typedef _Temporary_buffer<_RandomAccessIter, _Tp> _TmpBuf;

  1181   _TmpBuf __buf(__first, __last);

  1182   _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);

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

  1185     __inplace_stable_sort(__first, __last, __comp);

  1186   else

  1187     __stable_sort_adaptive(__first, __last, __buf.begin(),

  1188                            _Distance(__buf.size()),

  1189                            __comp);

  1190 }

  1192 template <class _RandomAccessIter>

  1193 void stable_sort(_RandomAccessIter __first,

  1194 		 _RandomAccessIter __last) {

  1195   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1196   __stable_sort_aux(__first, __last,

  1197                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1198                     _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),

  1199                     __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

  1200 }

  1202 template <class _RandomAccessIter, class _Compare>

  1203 void stable_sort(_RandomAccessIter __first,

  1204 		 _RandomAccessIter __last, _Compare __comp) {

  1205   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1206   __stable_sort_aux(__first, __last,

  1207                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1208                     _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),

  1209                     __comp);

  1210 }

  1212 // partial_sort, partial_sort_copy, and auxiliary functions.

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

  1215 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,

  1216                     _RandomAccessIter __last, _Tp*, _Compare __comp) {

  1217   make_heap(__first, __middle, __comp);

  1218   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)

  1219     if (__comp(*__i, *__first))

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

  1221                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));

  1222   sort_heap(__first, __middle, __comp);

  1223 }

  1226 template <class _RandomAccessIter>

  1227 void

  1228 partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last) {

  1229   _STLP_DEBUG_CHECK(__check_range(__first, __middle))

  1230   _STLP_DEBUG_CHECK(__check_range(__middle, __last))

  1231   __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1232                  __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

  1233 }

  1235 template <class _RandomAccessIter, class _Compare>

  1236 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,

  1237                   _RandomAccessIter __last, _Compare __comp) {

  1238   _STLP_DEBUG_CHECK(__check_range(__first, __middle))

  1239   _STLP_DEBUG_CHECK(__check_range(__middle, __last))

  1240   __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);

  1241 }

  1243 template <class _InputIter, class _RandomAccessIter, class _Compare,

  1244           class _Distance, class _Tp>

  1245 _RandomAccessIter __partial_sort_copy(_InputIter __first,

  1246                                          _InputIter __last,

  1247                                          _RandomAccessIter __result_first,

  1248                                          _RandomAccessIter __result_last,

  1249                                          _Compare __comp, _Distance*, _Tp*) {

  1250   if (__result_first == __result_last) return __result_last;

  1251   _RandomAccessIter __result_real_last = __result_first;

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

  1253     *__result_real_last = *__first;

  1254     ++__result_real_last;

  1255     ++__first;

  1256   }

  1257   make_heap(__result_first, __result_real_last, __comp);

  1258   while (__first != __last) {

  1259     if (__comp(*__first, *__result_first))

  1260       __adjust_heap(__result_first, _Distance(0),

  1261                     _Distance(__result_real_last - __result_first),

  1262                     _Tp(*__first),

  1263                     __comp);

  1264     ++__first;

  1265   }

  1266   sort_heap(__result_first, __result_real_last, __comp);

  1267   return __result_real_last;

  1268 }

  1270 template <class _InputIter, class _RandomAccessIter>

  1271 _RandomAccessIter

  1272 partial_sort_copy(_InputIter __first, _InputIter __last,

  1273                   _RandomAccessIter __result_first, _RandomAccessIter __result_last) {

  1274   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1275   _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))

  1276   return __partial_sort_copy(__first, __last, __result_first, __result_last,

  1277                              __less(_STLP_VALUE_TYPE(__first, _InputIter)),

  1278                              _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),

  1279                              _STLP_VALUE_TYPE(__first, _InputIter));

  1280 }

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

  1283 _RandomAccessIter

  1284 partial_sort_copy(_InputIter __first, _InputIter __last,

  1285                   _RandomAccessIter __result_first,

  1286                   _RandomAccessIter __result_last, _Compare __comp) {

  1287   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1288   _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))

  1289   return __partial_sort_copy(__first, __last, __result_first, __result_last,

  1290                              __comp,

  1291                              _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),

  1292                              _STLP_VALUE_TYPE(__first, _InputIter));

  1293 }

  1295 // nth_element() and its auxiliary functions.

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

  1298 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

  1299                    _RandomAccessIter __last, _Tp*, _Compare __comp) {

  1300   while (__last - __first > 3) {

  1301     _RandomAccessIter __cut =

  1302       __unguarded_partition(__first, __last,

  1303                             _Tp(__median(*__first,

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

  1305                                          *(__last - 1),

  1306                                          __comp)),

  1307                             __comp);

  1308     if (__cut <= __nth)

  1309       __first = __cut;

  1310     else

  1311       __last = __cut;

  1312   }

  1313   __insertion_sort(__first, __last, __comp);

  1314 }

  1317 template <class _RandomAccessIter>

  1318 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

  1319                  _RandomAccessIter __last) {

  1320   _STLP_DEBUG_CHECK(__check_range(__first, __nth))

  1321   _STLP_DEBUG_CHECK(__check_range(__nth, __last))

  1322   __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),

  1323                 __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));

  1324 }

  1326 template <class _RandomAccessIter, class _Compare>

  1327 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

  1328                  _RandomAccessIter __last, _Compare __comp) {

  1329   _STLP_DEBUG_CHECK(__check_range(__first, __nth))

  1330   _STLP_DEBUG_CHECK(__check_range(__nth, __last))

  1331   __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);

  1332 }

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

  1336 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>

  1337 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,

  1338                            const _Tp& __val, _Compare __comp, _Distance*)

  1339 {

  1340   _Distance __len = distance(__first, __last);

  1341   _Distance __half;

  1343   while (__len > 0) {

  1344     __half = __len >> 1;

  1345     _ForwardIter __middle = __first;

  1346     advance(__middle, __half);

  1347     if (__comp(__val, *__middle))

  1348       __len = __half;

  1349     else {

  1350       __first = __middle;

  1351       ++__first;

  1352       __len = __len - __half - 1;

  1353     }

  1354   }

  1355   return __first;

  1356 }

  1358 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>

  1359 pair<_ForwardIter, _ForwardIter>

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

  1361               _Compare __comp, _Distance*)

  1362 {

  1363   _Distance __len = distance(__first, __last);

  1364   _Distance __half;

  1366   while (__len > 0) {

  1367     __half = __len >> 1;

  1368     _ForwardIter __middle = __first;

  1369     advance(__middle, __half);

  1370     if (__comp(*__middle, __val)) {

  1371       __first = __middle;

  1372       ++__first;

  1373       __len = __len - __half - 1;

  1374     }

  1375     else if (__comp(__val, *__middle))

  1376       __len = __half;

  1377     else {

  1378       _ForwardIter __left = lower_bound(__first, __middle, __val, __comp);

  1379       advance(__first, __len);

  1380       _ForwardIter __right = upper_bound(++__middle, __first, __val, __comp);

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

  1382     }

  1383   }

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

  1385 }

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

  1388 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,

  1389                   _InputIter2 __first2, _InputIter2 __last2,

  1390                   _OutputIter __result) {

  1391   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1392   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

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

  1394     if (*__first2 < *__first1) {

  1395       *__result = *__first2;

  1396       ++__first2;

  1397     }

  1398     else {

  1399       *__result = *__first1;

  1400       ++__first1;

  1401     }

  1402     ++__result;

  1403   }

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

  1405 }

  1407 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1408           class _Compare>

  1409 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,

  1410                   _InputIter2 __first2, _InputIter2 __last2,

  1411                   _OutputIter __result, _Compare __comp) {

  1412   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1413   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

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

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

  1416       *__result = *__first2;

  1417       ++__first2;

  1418     }

  1419     else {

  1420       *__result = *__first1;

  1421       ++__first1;

  1422     }

  1423     ++__result;

  1424   }

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

  1426 }

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

  1429 void __merge_without_buffer(_BidirectionalIter __first,

  1430                             _BidirectionalIter __middle,

  1431                             _BidirectionalIter __last,

  1432                             _Distance __len1, _Distance __len2,

  1433                             _Compare __comp) {

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

  1435     return;

  1436   if (__len1 + __len2 == 2) {

  1437     if (__comp(*__middle, *__first))

  1438       iter_swap(__first, __middle);

  1439     return;

  1440   }

  1441   _BidirectionalIter __first_cut = __first;

  1442   _BidirectionalIter __second_cut = __middle;

  1443   _Distance __len11 = 0;

  1444   _Distance __len22 = 0;

  1445   if (__len1 > __len2) {

  1446     __len11 = __len1 / 2;

  1447     advance(__first_cut, __len11);

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

  1449     __len22 += distance(__middle, __second_cut);

  1450   }

  1451   else {

  1452     __len22 = __len2 / 2;

  1453     advance(__second_cut, __len22);

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

  1455     __len11 +=distance(__first, __first_cut);

  1456   }

  1457   _BidirectionalIter __new_middle

  1458     = rotate(__first_cut, __middle, __second_cut);

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

  1460                          __comp);

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

  1462                          __len2 - __len22, __comp);

  1463 }

  1465 template <class _BidirectionalIter1, class _BidirectionalIter2,

  1466           class _BidirectionalIter3, class _Compare>

  1467 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,

  1468                                      _BidirectionalIter1 __last1,

  1469                                      _BidirectionalIter2 __first2,

  1470                                      _BidirectionalIter2 __last2,

  1471                                      _BidirectionalIter3 __result,

  1472                                      _Compare __comp) {

  1473   if (__first1 == __last1)

  1474     return copy_backward(__first2, __last2, __result);

  1475   if (__first2 == __last2)

  1476     return copy_backward(__first1, __last1, __result);

  1477   --__last1;

  1478   --__last2;

  1479   while (true) {

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

  1481       *--__result = *__last1;

  1482       if (__first1 == __last1)

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

  1484       --__last1;

  1485     }

  1486     else {

  1487       *--__result = *__last2;

  1488       if (__first2 == __last2)

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

  1490       --__last2;

  1491     }

  1492   }

  1493 }

  1495 template <class _BidirectionalIter, class _Tp,

  1496           class _Distance, class _Compare>

  1497 inline void __inplace_merge_aux(_BidirectionalIter __first,

  1498                                 _BidirectionalIter __middle,

  1499                                 _BidirectionalIter __last, _Tp*, _Distance*,

  1500                                 _Compare __comp) {

  1501   _Distance __len1 = distance(__first, __middle);

  1502   _Distance __len2 = distance(__middle, __last);

  1504   typedef _Temporary_buffer<_BidirectionalIter, _Tp> _TmpBuf;

  1505   _TmpBuf __buf(__first, __last);

  1506   _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);

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

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

  1510   else

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

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

  1513                      __comp);

  1514 }

  1516 template <class _BidirectionalIter>

  1517 void inplace_merge(_BidirectionalIter __first,

  1518 		   _BidirectionalIter __middle,

  1519 		   _BidirectionalIter __last) {

  1520   _STLP_DEBUG_CHECK(__check_range(__first, __middle))

  1521   _STLP_DEBUG_CHECK(__check_range(__middle, __last))

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

  1523     return;

  1524   __inplace_merge_aux(__first, __middle, __last,

  1525                       _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),

  1526                       __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));

  1527 }

  1529 template <class _BidirectionalIter, class _Compare>

  1530 void inplace_merge(_BidirectionalIter __first,

  1531 		   _BidirectionalIter __middle,

  1532 		   _BidirectionalIter __last, _Compare __comp) {

  1533   _STLP_DEBUG_CHECK(__check_range(__first, __middle))

  1534   _STLP_DEBUG_CHECK(__check_range(__middle, __last))

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

  1536     return;

  1537   __inplace_merge_aux(__first, __middle, __last,

  1538                       _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),

  1539                       __comp);

  1540 }

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

  1544 bool __includes(_InputIter1 __first1, _InputIter1 __last1,

  1545                 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {

  1546   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1547   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

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

  1549     if (__comp(*__first2, *__first1))

  1550       return false;

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

  1552       ++__first1;

  1553     else

  1554       ++__first1, ++__first2;

  1556   return __first2 == __last2;

  1557 }

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

  1560 bool includes(_InputIter1 __first1, _InputIter1 __last1,

  1561               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {

  1562   return __includes(__first1, __last1, __first2, __last2, __comp);

  1563 }

  1565 template <class _InputIter1, class _InputIter2>

  1566 bool includes(_InputIter1 __first1, _InputIter1 __last1,

  1567               _InputIter2 __first2, _InputIter2 __last2) {

  1568   return __includes(__first1, __last1, __first2, __last2, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1569 }

  1571 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1572           class _Compare>

  1573 _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,

  1574                         _InputIter2 __first2, _InputIter2 __last2,

  1575                         _OutputIter __result, _Compare __comp) {

  1576   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1577   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

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

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

  1580       *__result = *__first1;

  1581       ++__first1;

  1582     }

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

  1584       *__result = *__first2;

  1585       ++__first2;

  1586     }

  1587     else {

  1588       *__result = *__first1;

  1589       ++__first1;

  1590       ++__first2;

  1591     }

  1592     ++__result;

  1593   }

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

  1595 }

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

  1598 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,

  1599                       _InputIter2 __first2, _InputIter2 __last2,

  1600                       _OutputIter __result) {

  1601   return __set_union(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1602 }

  1604 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1605           class _Compare>

  1606 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,

  1607                       _InputIter2 __first2, _InputIter2 __last2,

  1608                       _OutputIter __result, _Compare __comp) {

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

  1610 }

  1612 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1613           class _Compare>

  1614 _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,

  1615                                _InputIter2 __first2, _InputIter2 __last2,

  1616                                _OutputIter __result, _Compare __comp) {

  1617   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1618   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

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

  1620     if (__comp(*__first1, *__first2))

  1621       ++__first1;

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

  1623       ++__first2;

  1624     else {

  1625       *__result = *__first1;

  1626       ++__first1;

  1627       ++__first2;

  1628       ++__result;

  1629     }

  1630   return __result;

  1631 }

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

  1634 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,

  1635                              _InputIter2 __first2, _InputIter2 __last2,

  1636                              _OutputIter __result) {

  1637   return __set_intersection(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1638 }

  1640 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1641           class _Compare>

  1642 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,

  1643                              _InputIter2 __first2, _InputIter2 __last2,

  1644                              _OutputIter __result, _Compare __comp) {

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

  1646 }

  1648 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1649           class _Compare>

  1650 _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,

  1651                              _InputIter2 __first2, _InputIter2 __last2,

  1652                              _OutputIter __result, _Compare __comp) {

  1653   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1654   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

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

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

  1657       *__result = *__first1;

  1658       ++__first1;

  1659       ++__result;

  1660     }

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

  1662       ++__first2;

  1663     else {

  1664       ++__first1;

  1665       ++__first2;

  1666     }

  1667   return copy(__first1, __last1, __result);

  1668 }

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

  1671 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,

  1672                            _InputIter2 __first2, _InputIter2 __last2,

  1673                            _OutputIter __result) {

  1674   return __set_difference(__first1, __last1, __first2, __last2, __result,

  1675                           __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1676 }

  1678 template <class _InputIter1, class _InputIter2, class _OutputIter,

  1679           class _Compare>

  1680 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,

  1681                            _InputIter2 __first2, _InputIter2 __last2,

  1682                            _OutputIter __result, _Compare __comp) {

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

  1684 }

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

  1687 _OutputIter

  1688 __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

  1689                            _InputIter2 __first2, _InputIter2 __last2,

  1690                            _OutputIter __result, _Compare __comp) {

  1691   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  1692   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

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

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

  1695       *__result = *__first1;

  1696       ++__first1;

  1697       ++__result;

  1698     }

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

  1700       *__result = *__first2;

  1701       ++__first2;

  1702       ++__result;

  1703     }

  1704     else {

  1705       ++__first1;

  1706       ++__first2;

  1707     }

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

  1709 }

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

  1712 _OutputIter

  1713 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

  1714                          _InputIter2 __first2, _InputIter2 __last2,

  1715                          _OutputIter __result) {

  1716   return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,

  1717                                     __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));

  1718 }

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

  1721 _OutputIter

  1722 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

  1723                          _InputIter2 __first2, _InputIter2 __last2,

  1724                          _OutputIter __result,

  1725                          _Compare __comp) {

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

  1727 }

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

  1730 // comparison function.

  1732 template <class _ForwardIter, class _Compare>

  1733 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,

  1734                             _Compare __comp) {

  1735   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1736   if (__first == __last) return __first;

  1737   _ForwardIter __result = __first;

  1738   while (++__first != __last)

  1739     if (__comp(*__result, *__first)) __result = __first;

  1740   return __result;

  1741 }

  1743 template <class _ForwardIter>

  1744 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {

  1745   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1746   if (__first == __last) return __first;

  1747   _ForwardIter __result = __first;

  1748   while (++__first != __last)

  1749     if (*__result < *__first)

  1750       __result = __first;

  1751   return __result;

  1752 }

  1754 template <class _ForwardIter>

  1755 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {

  1756   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1757   if (__first == __last) return __first;

  1758   _ForwardIter __result = __first;

  1759   while (++__first != __last)

  1760     if (*__first < *__result)

  1761       __result = __first;

  1762   return __result;

  1763 }

  1765 template <class _ForwardIter, class _Compare>

  1766 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,

  1767                             _Compare __comp) {

  1768   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1769   if (__first == __last) return __first;

  1770   _ForwardIter __result = __first;

  1771   while (++__first != __last)

  1772     if (__comp(*__first, *__result)) __result = __first;

  1773   return __result;

  1774 }

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

  1777 // supplied comparison function.

  1778 template <class _BidirectionalIter, class _Compare>

  1779 bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

  1780                         _Compare __comp) {

  1781   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1782   if (__first == __last)

  1783     return false;

  1784   _BidirectionalIter __i = __first;

  1785   ++__i;

  1786   if (__i == __last)

  1787     return false;

  1788   __i = __last;

  1789   --__i;

  1791   for(;;) {

  1792     _BidirectionalIter __ii = __i;

  1793     --__i;

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

  1795       _BidirectionalIter __j = __last;

  1796       while (!__comp(*__i, *--__j))

  1797         {}

  1798       iter_swap(__i, __j);

  1799       reverse(__ii, __last);

  1800       return true;

  1801     }

  1802     if (__i == __first) {

  1803       reverse(__first, __last);

  1804       return false;

  1805     }

  1806   }

  1807 #if defined(_STLP_NEED_UNREACHABLE_RETURN)

  1808     return 0;

  1809 #endif

  1810 }

  1812 template <class _BidirectionalIter>

  1813 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {

  1814   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1815   return __next_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));

  1816 }

  1818 template <class _BidirectionalIter, class _Compare>

  1819 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

  1820                       _Compare __comp) {

  1821   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1822   return __next_permutation(__first, __last, __comp);

  1823 }

  1825 template <class _BidirectionalIter, class _Compare>

  1826 bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

  1827                       _Compare __comp) {

  1828   if (__first == __last)

  1829     return false;

  1830   _BidirectionalIter __i = __first;

  1831   ++__i;

  1832   if (__i == __last)

  1833     return false;

  1834   __i = __last;

  1835   --__i;

  1837   for(;;) {

  1838     _BidirectionalIter __ii = __i;

  1839     --__i;

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

  1841       _BidirectionalIter __j = __last;

  1842       while (!__comp(*--__j, *__i))

  1843         {}

  1844       iter_swap(__i, __j);

  1845       reverse(__ii, __last);

  1846       return true;

  1847     }

  1848     if (__i == __first) {

  1849       reverse(__first, __last);

  1850       return false;

  1851     }

  1852   }

  1853 #if defined(_STLP_NEED_UNREACHABLE_RETURN)

  1854     return 0;

  1855 #endif

  1856 }

  1858 template <class _BidirectionalIter>

  1859 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {

  1860   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1861   return __prev_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));

  1862 }

  1864 template <class _BidirectionalIter, class _Compare>

  1865 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

  1866                       _Compare __comp) {

  1867   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1868   return __prev_permutation(__first, __last, __comp);

  1869 }

  1871 # ifndef _STLP_NO_EXTENSIONS

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

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

  1875 // standard.

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

  1879 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,

  1880                _Distance __n)

  1881 {

  1882   _Distance __parent = 0;

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

  1884     if (__comp(__first[__parent], __first[__child]))

  1885       return false;

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

  1887       ++__parent;

  1888   }

  1889   return true;

  1890 }

  1892 template <class _RandomAccessIter>

  1893 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)

  1894 {

  1895   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

  1897 }

  1899 template <class _RandomAccessIter, class _StrictWeakOrdering>

  1900 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,

  1901 	     _StrictWeakOrdering __comp)

  1902 {

  1903   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1904   return __is_heap(__first, __comp, __last - __first);

  1905 }

  1908 template <class _ForwardIter, class _StrictWeakOrdering>

  1909 bool __is_sorted(_ForwardIter __first, _ForwardIter __last,

  1910                  _StrictWeakOrdering __comp)

  1911 {

  1912   _STLP_DEBUG_CHECK(__check_range(__first, __last))

  1913   if (__first == __last)

  1914     return true;

  1916   _ForwardIter __next = __first;

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

  1918     if (__comp(*__next, *__first))

  1919       return false;

  1920   }

  1922   return true;

  1923 }

  1925 # endif /* _STLP_NO_EXTENSIONS */

  1927 _STLP_END_NAMESPACE

  1929 # undef __stl_threshold

  1931 #endif /* _STLP_ALGO_C */

  1932 // Local Variables:

  1933 // mode:C++

  1934 // End:

author	William Roberts <williamr@symbian.org>
	Tue, 16 Mar 2010 16:12:26 +0000
branch	Symbian2
changeset 2	2fe1408b6811
parent 0	061f57f2323e
permissions	-rw-r--r--