epoc32/include/stdapis/stlport/stl/_algo.c
branchSymbian3
changeset 4 837f303aceeb
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/stlport/stl/_algo.c	Wed Mar 31 12:33:34 2010 +0100
     1.3 @@ -0,0 +1,1934 @@
     1.4 +/*
     1.5 + *
     1.6 + * Copyright (c) 1994
     1.7 + * Hewlett-Packard Company
     1.8 + *
     1.9 + * Copyright (c) 1996,1997
    1.10 + * Silicon Graphics Computer Systems, Inc.
    1.11 + *
    1.12 + * Copyright (c) 1997
    1.13 + * Moscow Center for SPARC Technology
    1.14 + *
    1.15 + * Copyright (c) 1999 
    1.16 + * Boris Fomitchev
    1.17 + *
    1.18 + * This material is provided "as is", with absolutely no warranty expressed
    1.19 + * or implied. Any use is at your own risk.
    1.20 + *
    1.21 + * Permission to use or copy this software for any purpose is hereby granted 
    1.22 + * without fee, provided the above notices are retained on all copies.
    1.23 + * Permission to modify the code and to distribute modified code is granted,
    1.24 + * provided the above notices are retained, and a notice that the code was
    1.25 + * modified is included with the above copyright notice.
    1.26 + *
    1.27 + */
    1.28 +
    1.29 +#ifndef _STLP_ALGO_C
    1.30 +# define _STLP_ALGO_C
    1.31 +
    1.32 +# if !defined (_STLP_INTERNAL_ALGO_H)
    1.33 +#  include <stl/_algo.h>
    1.34 +# endif
    1.35 +
    1.36 +_STLP_BEGIN_NAMESPACE
    1.37 +
    1.38 +template <class _BidirectionalIter, class _Distance, class _Compare>
    1.39 +void __merge_without_buffer(_BidirectionalIter __first,
    1.40 +                            _BidirectionalIter __middle,
    1.41 +                            _BidirectionalIter __last,
    1.42 +                            _Distance __len1, _Distance __len2,
    1.43 +                            _Compare __comp);
    1.44 +
    1.45 +
    1.46 +template <class _BidirectionalIter1, class _BidirectionalIter2,
    1.47 +          class _BidirectionalIter3, class _Compare>
    1.48 +_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
    1.49 +                                     _BidirectionalIter1 __last1,
    1.50 +                                     _BidirectionalIter2 __first2,
    1.51 +                                     _BidirectionalIter2 __last2,
    1.52 +                                     _BidirectionalIter3 __result,
    1.53 +                                     _Compare __comp);
    1.54 +
    1.55 +template <class _Tp>
    1.56 +# if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
    1.57 +inline 
    1.58 +# endif
    1.59 +const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
    1.60 +  if (__a < __b)
    1.61 +    if (__b < __c)
    1.62 +      return __b;
    1.63 +    else if (__a < __c)
    1.64 +      return __c;
    1.65 +    else
    1.66 +      return __a;
    1.67 +  else if (__a < __c)
    1.68 +    return __a;
    1.69 +  else if (__b < __c)
    1.70 +    return __c;
    1.71 +  else
    1.72 +    return __b;
    1.73 +}
    1.74 +
    1.75 +template <class _Tp, class _Compare>
    1.76 +# if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
    1.77 +inline 
    1.78 +# endif
    1.79 +const _Tp&
    1.80 +__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
    1.81 +  if (__comp(__a, __b))
    1.82 +    if (__comp(__b, __c))
    1.83 +      return __b;
    1.84 +    else if (__comp(__a, __c))
    1.85 +      return __c;
    1.86 +    else
    1.87 +      return __a;
    1.88 +  else if (__comp(__a, __c))
    1.89 +    return __a;
    1.90 +  else if (__comp(__b, __c))
    1.91 +    return __c;
    1.92 +  else
    1.93 +    return __b;
    1.94 +}
    1.95 +
    1.96 +template <class _ForwardIter1, class _ForwardIter2>
    1.97 +_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
    1.98 +                     _ForwardIter2 __first2, _ForwardIter2 __last2) 
    1.99 +{
   1.100 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
   1.101 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
   1.102 +  // Test for empty ranges
   1.103 +  if (__first1 == __last1 || __first2 == __last2)
   1.104 +    return __first1;
   1.105 +
   1.106 +  // Test for a pattern of length 1.
   1.107 +  _ForwardIter2 __tmp(__first2);
   1.108 +  ++__tmp;
   1.109 +  if (__tmp == __last2)
   1.110 +    return find(__first1, __last1, *__first2);
   1.111 +
   1.112 +  // General case.
   1.113 +  _ForwardIter2 __p1 = __first2; 
   1.114 +  ++__p1;
   1.115 +
   1.116 +  _ForwardIter1 __current = __first1;
   1.117 +
   1.118 +  while (__first1 != __last1) {
   1.119 +    __first1 = find(__first1, __last1, *__first2);
   1.120 +    if (__first1 == __last1)
   1.121 +      return __last1;
   1.122 +
   1.123 +    _ForwardIter2 __p = __p1;
   1.124 +    __current = __first1; 
   1.125 +    if (++__current == __last1)
   1.126 +      return __last1;
   1.127 +
   1.128 +    while (*__current == *__p) {
   1.129 +      if (++__p == __last2)
   1.130 +        return __first1;
   1.131 +      if (++__current == __last1)
   1.132 +        return __last1;
   1.133 +    }
   1.134 +
   1.135 +    ++__first1;
   1.136 +  }
   1.137 +  return __first1;
   1.138 +}
   1.139 +
   1.140 +// search_n.  Search for __count consecutive copies of __val.
   1.141 +
   1.142 +template <class _ForwardIter, class _Integer, class _Tp>
   1.143 +_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
   1.144 +                      _Integer __count, const _Tp& __val) {
   1.145 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.146 +  if (__count <= 0)
   1.147 +    return __first;
   1.148 +  else {
   1.149 +    __first = find(__first, __last, __val);
   1.150 +    while (__first != __last) {
   1.151 +      _Integer __n = __count - 1;
   1.152 +      _ForwardIter __i = __first;
   1.153 +      ++__i;
   1.154 +      while (__i != __last && __n != 0 && *__i == __val) {
   1.155 +        ++__i;
   1.156 +        --__n;
   1.157 +      }
   1.158 +      if (__n == 0)
   1.159 +        return __first;
   1.160 +      else
   1.161 +        __first = find(__i, __last, __val);
   1.162 +    }
   1.163 +    return __last;
   1.164 +  }
   1.165 +}
   1.166 +
   1.167 +template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
   1.168 +_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
   1.169 +                      _Integer __count, const _Tp& __val,
   1.170 +                      _BinaryPred __binary_pred) {
   1.171 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.172 +  if (__count <= 0)
   1.173 +    return __first;
   1.174 +  else {
   1.175 +    while (__first != __last) {
   1.176 +      if (__binary_pred(*__first, __val))
   1.177 +        break;
   1.178 +      ++__first;
   1.179 +    }
   1.180 +    while (__first != __last) {
   1.181 +      _Integer __n = __count - 1;
   1.182 +      _ForwardIter __i = __first;
   1.183 +      ++__i;
   1.184 +      while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
   1.185 +        ++__i;
   1.186 +        --__n;
   1.187 +      }
   1.188 +      if (__n == 0)
   1.189 +        return __first;
   1.190 +      else {
   1.191 +        while (__i != __last) {
   1.192 +          if (__binary_pred(*__i, __val))
   1.193 +            break;
   1.194 +          ++__i;
   1.195 +        }
   1.196 +        __first = __i;
   1.197 +      }
   1.198 +    }
   1.199 +    return __last;
   1.200 +  }
   1.201 +} 
   1.202 +
   1.203 +template <class _ForwardIter1, class _ForwardIter2>
   1.204 +_ForwardIter1 
   1.205 +find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
   1.206 +         _ForwardIter2 __first2, _ForwardIter2 __last2)
   1.207 +{
   1.208 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
   1.209 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
   1.210 +  return __find_end(__first1, __last1, __first2, __last2,
   1.211 +# if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
   1.212 +                    _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
   1.213 +                    _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
   1.214 +# else
   1.215 +		    forward_iterator_tag(),
   1.216 +                    forward_iterator_tag(),
   1.217 +# endif
   1.218 +                    __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
   1.219 +    );
   1.220 +}
   1.221 +
   1.222 +// unique and unique_copy
   1.223 +template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
   1.224 +					    class _Tp>
   1.225 +_STLP_INLINE_LOOP _OutputIterator 
   1.226 +__unique_copy(_InputIterator __first, _InputIterator __last,
   1.227 +              _OutputIterator __result,
   1.228 +              _BinaryPredicate __binary_pred, _Tp*) {
   1.229 +  _Tp __val = *__first;
   1.230 + _STLP_PUSH_STACK_ITEM(_Tp, &__val)
   1.231 +  *__result = __val;
   1.232 +  while (++__first != __last)
   1.233 +    if (!__binary_pred(__val, *__first)) {
   1.234 +      __val = *__first;
   1.235 +      *++__result = __val;
   1.236 +    }
   1.237 +  return ++__result;
   1.238 +}
   1.239 +
   1.240 +template <class _InputIter, class _OutputIter, class _BinaryPredicate>
   1.241 +inline _OutputIter 
   1.242 +__unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
   1.243 +              _BinaryPredicate __binary_pred, const output_iterator_tag &) {
   1.244 +  return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));
   1.245 +}
   1.246 +
   1.247 +template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
   1.248 +_STLP_INLINE_LOOP _ForwardIter 
   1.249 +__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, 
   1.250 +              _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
   1.251 +  *__result = *__first;
   1.252 +  while (++__first != __last)
   1.253 +    if (!__binary_pred(*__result, *__first)) *++__result = *__first;
   1.254 +  return ++__result;
   1.255 +}
   1.256 +
   1.257 +# if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
   1.258 +template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
   1.259 +inline _BidirectionalIterator 
   1.260 +__unique_copy(_InputIterator __first, _InputIterator __last,
   1.261 +              _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
   1.262 +              const bidirectional_iterator_tag &) {
   1.263 +  return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
   1.264 +}
   1.265 +
   1.266 +template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
   1.267 +inline _RandomAccessIterator 
   1.268 +__unique_copy(_InputIterator __first, _InputIterator __last,
   1.269 +              _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
   1.270 +              const random_access_iterator_tag &) {
   1.271 +  return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
   1.272 +}
   1.273 +# endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
   1.274 +
   1.275 +
   1.276 +template <class _InputIter, class _OutputIter>
   1.277 +_OutputIter 
   1.278 +unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
   1.279 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.280 +  if (__first == __last) return __result;
   1.281 +  return __unique_copy(__first, __last, __result, __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
   1.282 +                       _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
   1.283 +}
   1.284 +
   1.285 +template <class _InputIter, class _OutputIter, class _BinaryPredicate>
   1.286 +_OutputIter 
   1.287 +unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
   1.288 +            _BinaryPredicate __binary_pred) {
   1.289 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.290 +  if (__first == __last) return __result;
   1.291 +  return __unique_copy(__first, __last, __result, __binary_pred,
   1.292 +                       _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
   1.293 +}
   1.294 +
   1.295 +// rotate and rotate_copy, and their auxiliary functions
   1.296 +
   1.297 +template <class _ForwardIter, class _Distance>
   1.298 +_ForwardIter __rotate(_ForwardIter __first,
   1.299 +                      _ForwardIter __middle,
   1.300 +                      _ForwardIter __last,
   1.301 +                      _Distance*,
   1.302 +                      const forward_iterator_tag &) {
   1.303 +  if (__first == __middle)
   1.304 +    return __last;
   1.305 +  if (__last  == __middle)
   1.306 +    return __first;
   1.307 +
   1.308 +  _ForwardIter __first2 = __middle;
   1.309 +  do {
   1.310 +    swap(*__first++, *__first2++);
   1.311 +    if (__first == __middle)
   1.312 +      __middle = __first2;
   1.313 +  } while (__first2 != __last);
   1.314 +
   1.315 +  _ForwardIter __new_middle = __first;
   1.316 +
   1.317 +  __first2 = __middle;
   1.318 +
   1.319 +  while (__first2 != __last) {
   1.320 +    swap (*__first++, *__first2++);
   1.321 +    if (__first == __middle)
   1.322 +      __middle = __first2;
   1.323 +    else if (__first2 == __last)
   1.324 +      __first2 = __middle;
   1.325 +  }
   1.326 +
   1.327 +  return __new_middle;
   1.328 +}
   1.329 +
   1.330 +template <class _BidirectionalIter, class _Distance>
   1.331 +_BidirectionalIter __rotate(_BidirectionalIter __first,
   1.332 +                            _BidirectionalIter __middle,
   1.333 +                            _BidirectionalIter __last,
   1.334 +                            _Distance*,
   1.335 +                            const bidirectional_iterator_tag &) {
   1.336 +  if (__first == __middle)
   1.337 +    return __last;
   1.338 +  if (__last  == __middle)
   1.339 +    return __first;
   1.340 +
   1.341 +  __reverse(__first,  __middle, bidirectional_iterator_tag());
   1.342 +  __reverse(__middle, __last,   bidirectional_iterator_tag());
   1.343 +
   1.344 +  while (__first != __middle && __middle != __last)
   1.345 +    swap (*__first++, *--__last);
   1.346 +
   1.347 +  if (__first == __middle) {
   1.348 +    __reverse(__middle, __last,   bidirectional_iterator_tag());
   1.349 +    return __last;
   1.350 +  }
   1.351 +  else {
   1.352 +    __reverse(__first,  __middle, bidirectional_iterator_tag());
   1.353 +    return __first;
   1.354 +  }
   1.355 +}
   1.356 +
   1.357 +template <class _RandomAccessIter, class _Distance, class _Tp>
   1.358 +_RandomAccessIter __rotate(_RandomAccessIter __first,
   1.359 +                           _RandomAccessIter __middle,
   1.360 +                           _RandomAccessIter __last,
   1.361 +                           _Distance *, _Tp *) {
   1.362 +
   1.363 +  _Distance __n = __last   - __first;
   1.364 +  _Distance __k = __middle - __first;
   1.365 +  _Distance __l = __n - __k;
   1.366 +  _RandomAccessIter __result = __first + (__last - __middle);
   1.367 +
   1.368 +  if (__k==0)  /* __first == middle */
   1.369 +    return __last;
   1.370 +
   1.371 +  if (__k == __l) {
   1.372 +    swap_ranges(__first, __middle, __middle);
   1.373 +    return __result;
   1.374 +  }
   1.375 +
   1.376 +  _Distance __d = __gcd(__n, __k);
   1.377 +
   1.378 +  for (_Distance __i = 0; __i < __d; __i++) {
   1.379 +    _Tp __tmp = *__first;
   1.380 +    _STLP_PUSH_STACK_ITEM(_Tp, &__tmp)
   1.381 +    _RandomAccessIter __p = __first;
   1.382 +
   1.383 +    if (__k < __l) {
   1.384 +      for (_Distance __j = 0; __j < __l/__d; __j++) {
   1.385 +	if (__p > __first + __l) {
   1.386 +          *__p = *(__p - __l);
   1.387 +          __p -= __l;
   1.388 +        }
   1.389 +
   1.390 +        *__p = *(__p + __k);
   1.391 +        __p += __k;
   1.392 +      }
   1.393 +    }
   1.394 +
   1.395 +    else {
   1.396 +      for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
   1.397 +        if (__p < __last - __k) {
   1.398 +          *__p = *(__p + __k);
   1.399 +          __p += __k;
   1.400 +        }
   1.401 +
   1.402 +        *__p = * (__p - __l);
   1.403 +        __p -= __l;
   1.404 +      }
   1.405 +    }
   1.406 +
   1.407 +    *__p = __tmp;
   1.408 +    ++__first;
   1.409 +  }
   1.410 +
   1.411 +  return __result;
   1.412 +}
   1.413 +
   1.414 +template <class _RandomAccessIter, class _Distance>
   1.415 +inline _RandomAccessIter 
   1.416 +__rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
   1.417 +         _Distance * __dis, const random_access_iterator_tag &) {
   1.418 +  return __rotate(__first, __middle, __last,
   1.419 +                  __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
   1.420 +}
   1.421 +
   1.422 +template <class _ForwardIter>
   1.423 +_ForwardIter 
   1.424 +rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
   1.425 +  _STLP_DEBUG_CHECK(__check_range(__first, __middle))
   1.426 +  _STLP_DEBUG_CHECK(__check_range(__middle, __last))
   1.427 +  return __rotate(__first, __middle, __last,
   1.428 +                  _STLP_DISTANCE_TYPE(__first, _ForwardIter),
   1.429 +                  _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   1.430 +}
   1.431 +
   1.432 +// Return a random number in the range [0, __n).  This function encapsulates
   1.433 +// whether we're using rand (part of the standard C library) or lrand48
   1.434 +// (not standard, but a much better choice whenever it's available).
   1.435 +
   1.436 +template <class _Distance>
   1.437 +inline _Distance __random_number(_Distance __n) {
   1.438 +#ifdef _STLP_NO_DRAND48
   1.439 +  return rand() % __n;
   1.440 +#else
   1.441 +  return lrand48() % __n;
   1.442 +#endif
   1.443 +}
   1.444 +
   1.445 +template <class _RandomAccessIter>
   1.446 +void random_shuffle(_RandomAccessIter __first,
   1.447 +		    _RandomAccessIter __last) {
   1.448 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.449 +  if (__first == __last) return;
   1.450 +  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
   1.451 +    iter_swap(__i, __first + __random_number((__i - __first) + 1));
   1.452 +}
   1.453 +
   1.454 +template <class _RandomAccessIter, class _RandomNumberGenerator>
   1.455 +void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
   1.456 +                    _RandomNumberGenerator& __rand) {
   1.457 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.458 +  if (__first == __last) return;
   1.459 +  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
   1.460 +    iter_swap(__i, __first + __rand((__i - __first) + 1));
   1.461 +}
   1.462 +
   1.463 +# ifndef _STLP_NO_EXTENSIONS
   1.464 +
   1.465 +// random_sample and random_sample_n (extensions, not part of the standard).
   1.466 +
   1.467 +template <class _ForwardIter, class _OutputIter, class _Distance>
   1.468 +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
   1.469 +                            _OutputIter __stl_out, const _Distance __n)
   1.470 +{
   1.471 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.472 +  _Distance __remaining = distance(__first, __last);
   1.473 +  _Distance __m = (min) (__n, __remaining);
   1.474 +
   1.475 +  while (__m > 0) {
   1.476 +    if (__random_number(__remaining) < __m) {
   1.477 +      *__stl_out = *__first;
   1.478 +      ++__stl_out;
   1.479 +      --__m;
   1.480 +    }
   1.481 +
   1.482 +    --__remaining;
   1.483 +    ++__first;
   1.484 +  }
   1.485 +  return __stl_out;
   1.486 +}
   1.487 +
   1.488 +
   1.489 +template <class _ForwardIter, class _OutputIter, class _Distance,
   1.490 +          class _RandomNumberGenerator>
   1.491 +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
   1.492 +                            _OutputIter __stl_out, const _Distance __n,
   1.493 +                            _RandomNumberGenerator& __rand)
   1.494 +{
   1.495 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.496 +  _Distance __remaining = distance(__first, __last);
   1.497 +  _Distance __m = (min) (__n, __remaining);
   1.498 +
   1.499 +  while (__m > 0) {
   1.500 +    if (__rand(__remaining) < __m) {
   1.501 +      *__stl_out = *__first;
   1.502 +      ++__stl_out;
   1.503 +      --__m;
   1.504 +    }
   1.505 +
   1.506 +    --__remaining;
   1.507 +    ++__first;
   1.508 +  }
   1.509 +  return __stl_out;
   1.510 +}
   1.511 +
   1.512 +template <class _InputIter, class _RandomAccessIter, class _Distance>
   1.513 +_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
   1.514 +                                  _RandomAccessIter __stl_out,
   1.515 +                                  const _Distance __n)
   1.516 +{
   1.517 +  _Distance __m = 0;
   1.518 +  _Distance __t = __n;
   1.519 +  for ( ; __first != __last && __m < __n; ++__m, ++__first) 
   1.520 +    __stl_out[__m] = *__first;
   1.521 +
   1.522 +  while (__first != __last) {
   1.523 +    ++__t;
   1.524 +    _Distance __M = __random_number(__t);
   1.525 +    if (__M < __n)
   1.526 +      __stl_out[__M] = *__first;
   1.527 +    ++__first;
   1.528 +  }
   1.529 +
   1.530 +  return __stl_out + __m;
   1.531 +}
   1.532 +
   1.533 +template <class _InputIter, class _RandomAccessIter,
   1.534 +          class _RandomNumberGenerator, class _Distance>
   1.535 +_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
   1.536 +                                  _RandomAccessIter __stl_out,
   1.537 +                                  _RandomNumberGenerator& __rand,
   1.538 +                                  const _Distance __n)
   1.539 +{
   1.540 +  _Distance __m = 0;
   1.541 +  _Distance __t = __n;
   1.542 +  for ( ; __first != __last && __m < __n; ++__m, ++__first)
   1.543 +    __stl_out[__m] = *__first;
   1.544 +
   1.545 +  while (__first != __last) {
   1.546 +    ++__t;
   1.547 +    _Distance __M = __rand(__t);
   1.548 +    if (__M < __n)
   1.549 +      __stl_out[__M] = *__first;
   1.550 +    ++__first;
   1.551 +  }
   1.552 +
   1.553 +  return __stl_out + __m;
   1.554 +}
   1.555 +
   1.556 +template <class _InputIter, class _RandomAccessIter>
   1.557 +_RandomAccessIter
   1.558 +random_sample(_InputIter __first, _InputIter __last,
   1.559 +              _RandomAccessIter __out_first, _RandomAccessIter __out_last) 
   1.560 +{
   1.561 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.562 +  _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))
   1.563 +  return __random_sample(__first, __last,
   1.564 +                         __out_first, __out_last - __out_first);
   1.565 +}
   1.566 +
   1.567 +template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
   1.568 +_RandomAccessIter
   1.569 +random_sample(_InputIter __first, _InputIter __last,
   1.570 +              _RandomAccessIter __out_first, _RandomAccessIter __out_last,
   1.571 +              _RandomNumberGenerator& __rand) 
   1.572 +{
   1.573 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.574 +  _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))
   1.575 +  return __random_sample(__first, __last,
   1.576 +                         __out_first, __rand,
   1.577 +                         __out_last - __out_first);
   1.578 +}
   1.579 +
   1.580 +# endif /* _STLP_NO_EXTENSIONS */
   1.581 +
   1.582 +// partition, stable_partition, and their auxiliary functions
   1.583 +
   1.584 +template <class _ForwardIter, class _Predicate>
   1.585 +_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
   1.586 +                                           _ForwardIter __last,
   1.587 +                                           _Predicate   __pred,
   1.588 +                                           const forward_iterator_tag &) {
   1.589 +  if (__first == __last) return __first;
   1.590 +
   1.591 +  while (__pred(*__first))
   1.592 +    if (++__first == __last) return __first;
   1.593 +
   1.594 +  _ForwardIter __next = __first;
   1.595 +
   1.596 +  while (++__next != __last)
   1.597 +    if (__pred(*__next)) {
   1.598 +      swap(*__first, *__next);
   1.599 +      ++__first;
   1.600 +    }
   1.601 +  return __first;
   1.602 +}
   1.603 +
   1.604 +/* bug fix- start*/
   1.605 +
   1.606 +template <class _ForwardIter>
   1.607 +_ForwardIter
   1.608 +__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
   1.609 +  _STLP_DEBUG_CHECK(__check_range(__first, __middle))
   1.610 +  _STLP_DEBUG_CHECK(__check_range(__middle, __last))
   1.611 +  return __rotate_aux(__first, __middle, __last,
   1.612 +                      _STLP_DISTANCE_TYPE(__first, _ForwardIter),
   1.613 +                      _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   1.614 +}
   1.615 +
   1.616 +template <class _ForwardIter, class _Distance>
   1.617 +_ForwardIter __rotate_aux(_ForwardIter __first,
   1.618 +                          _ForwardIter __middle,
   1.619 +                          _ForwardIter __last,
   1.620 +                          _Distance*,
   1.621 +                          const forward_iterator_tag &) {
   1.622 +  if (__first == __middle)
   1.623 +    return __last;
   1.624 +  if (__last  == __middle)
   1.625 +    return __first;
   1.626 +
   1.627 +  _ForwardIter __first2 = __middle;
   1.628 +  do {
   1.629 +    swap(*__first++, *__first2++);
   1.630 +    if (__first == __middle)
   1.631 +      __middle = __first2;
   1.632 +  } while (__first2 != __last);
   1.633 +
   1.634 +  _ForwardIter __new_middle = __first;
   1.635 +
   1.636 +  __first2 = __middle;
   1.637 +
   1.638 +  while (__first2 != __last) {
   1.639 +    swap (*__first++, *__first2++);
   1.640 +    if (__first == __middle)
   1.641 +      __middle = __first2;
   1.642 +    else if (__first2 == __last)
   1.643 +      __first2 = __middle;
   1.644 +  }
   1.645 +
   1.646 +  return __new_middle;
   1.647 +}
   1.648 +
   1.649 +
   1.650 +template <class _ForwardIter, class _Pointer, class _Predicate,
   1.651 +          class _Distance>
   1.652 +_ForwardIter __stable_partition_adaptive(_ForwardIter __first,
   1.653 +                                         _ForwardIter __last,
   1.654 +                                         _Predicate __pred, _Distance __len,
   1.655 +                                         _Pointer __buffer, _Distance __buffer_size,
   1.656 +                                         bool __pred_of_first, bool __pred_of_before_last) {
   1.657 +  if (__len <= __buffer_size) {
   1.658 +    _ForwardIter __result1 = __first;
   1.659 +    _Pointer __result2 = __buffer;
   1.660 +    if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {
   1.661 +      *__result2 = *__first;
   1.662 +      ++__result2; ++__first; --__len;
   1.663 +    }
   1.664 +    for (; __first != __last ; ++__first, --__len) {
   1.665 +      if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||
   1.666 +          ((__len != 1) && __pred(*__first))){
   1.667 +        *__result1 = *__first;
   1.668 +        ++__result1;
   1.669 +      }
   1.670 +      else {
   1.671 +        *__result2 = *__first;
   1.672 +        ++__result2;
   1.673 +      }
   1.674 +    }
   1.675 +    copy(__buffer, __result2, __result1);
   1.676 +    return __result1;
   1.677 +  }
   1.678 +  else {
   1.679 +    _ForwardIter __middle = __first;
   1.680 +    _Distance __half_len = __len / 2;
   1.681 +    advance(__middle, __half_len);
   1.682 +    return __rotate(__stable_partition_adaptive(
   1.683 +                          __first, __middle, __pred,
   1.684 +                          __half_len, __buffer, __buffer_size,
   1.685 +                          __pred_of_first, false),
   1.686 +                    __middle,
   1.687 +                    __stable_partition_adaptive(
   1.688 +                          __middle, __last, __pred,
   1.689 +                          __len - __half_len, __buffer, __buffer_size,
   1.690 +                          true, __pred_of_before_last));
   1.691 +  }
   1.692 +}
   1.693 +
   1.694 +
   1.695 +template <class _ForwardIter, class _Predicate, class _Distance>
   1.696 +_ForwardIter __inplace_stable_partition(_ForwardIter __first,
   1.697 +                                        _ForwardIter __last,
   1.698 +                                        _Predicate __pred, _Distance __len,
   1.699 +                                        bool __pred_of_first, bool __pred_of_before_last) {
   1.700 +  if (__len == 1)
   1.701 +    return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
   1.702 +  _ForwardIter __middle = __first;
   1.703 +  _Distance __half_len = __len / 2;
   1.704 +  advance(__middle, __half_len);
   1.705 +  return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
   1.706 +                  __middle,
   1.707 +                  __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
   1.708 +}
   1.709 +
   1.710 +
   1.711 +
   1.712 +template <class _ForwardIter, class _Predicate>
   1.713 +_ForwardIter
   1.714 +stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
   1.715 +  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   1.716 +  for (;;) {
   1.717 +    if (__first == __last)
   1.718 +      return __first;
   1.719 +    else if (__pred(*__first))
   1.720 +      ++__first;
   1.721 +    else
   1.722 +      break;
   1.723 +  }
   1.724 +  return  __stable_partition_aux(__first, __last, __pred,
   1.725 +                                           _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   1.726 +}
   1.727 +
   1.728 +
   1.729 +template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
   1.730 +inline _ForwardIter
   1.731 +__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
   1.732 +                           _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {
   1.733 +  _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
   1.734 +  return (__buf.size() > 0) ?
   1.735 +    __stable_partition_adaptive(__first, __last, __pred,
   1.736 +                                _Distance(__buf.requested_size()),
   1.737 +                                __buf.begin(), __buf.size(),
   1.738 +                                false, __pred_of_before_last)  :
   1.739 +    __inplace_stable_partition(__first, __last, __pred,
   1.740 +                               _Distance(__buf.requested_size()),
   1.741 +                               false, __pred_of_before_last);
   1.742 +
   1.743 +}
   1.744 +
   1.745 +template <class _ForwardIter, class _Predicate>
   1.746 +_ForwardIter
   1.747 +__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
   1.748 +                       const forward_iterator_tag &) {
   1.749 +  return __stable_partition_aux_aux(__first, __last, __pred,
   1.750 +                                    _STLP_VALUE_TYPE(__first, _ForwardIter),
   1.751 +                                    _STLP_DISTANCE_TYPE(__first, _ForwardIter));
   1.752 +}
   1.753 +
   1.754 +
   1.755 +/* bug fix- end*/
   1.756 +
   1.757 +
   1.758 +
   1.759 +template <class _BidirectionalIter, class _Predicate>
   1.760 +_STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
   1.761 +                                                 _BidirectionalIter __last,
   1.762 +                                                 _Predicate __pred,
   1.763 +                                                 const bidirectional_iterator_tag &) {
   1.764 +  while (true) {
   1.765 +    while (true)
   1.766 +      if (__first == __last)
   1.767 +        return __first;
   1.768 +      else if (__pred(*__first))
   1.769 +        ++__first;
   1.770 +      else
   1.771 +        break;
   1.772 +    --__last;
   1.773 +    while (true)
   1.774 +      if (__first == __last)
   1.775 +        return __first;
   1.776 +      else if (!__pred(*__last))
   1.777 +        --__last;
   1.778 +      else
   1.779 +        break;
   1.780 +    iter_swap(__first, __last);
   1.781 +    ++__first;
   1.782 +  }
   1.783 +}
   1.784 +
   1.785 +# if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
   1.786 +template <class _BidirectionalIter, class _Predicate>
   1.787 +inline
   1.788 +_BidirectionalIter __partition(_BidirectionalIter __first,
   1.789 +                               _BidirectionalIter __last,
   1.790 +			       _Predicate __pred,
   1.791 +			       const random_access_iterator_tag &) {
   1.792 +  return __partition(__first, __last, __pred, bidirectional_iterator_tag());
   1.793 +}
   1.794 +# endif
   1.795 +
   1.796 +template <class _ForwardIter, class _Predicate>
   1.797 +_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred) {
   1.798 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.799 +  return __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
   1.800 +}
   1.801 +
   1.802 +/*
   1.803 +template <class _ForwardIter, class _Predicate, class _Distance>
   1.804 +_ForwardIter __inplace_stable_partition(_ForwardIter __first,
   1.805 +                                        _ForwardIter __last,
   1.806 +                                        _Predicate __pred, _Distance __len) {
   1.807 +  if (__len == 1)
   1.808 +    return __pred(*__first) ? __last : __first;
   1.809 +  _ForwardIter __middle = __first;
   1.810 +  advance(__middle, __len / 2);
   1.811 +  return rotate(__inplace_stable_partition(__first, __middle, __pred, 
   1.812 +                                           __len / 2),
   1.813 +                __middle,
   1.814 +                __inplace_stable_partition(__middle, __last, __pred,
   1.815 +                                           __len - __len / 2));
   1.816 +}
   1.817 +
   1.818 +
   1.819 +template <class _ForwardIter, class _Pointer, class _Predicate, 
   1.820 +          class _Distance>
   1.821 +_ForwardIter __stable_partition_adaptive(_ForwardIter __first,
   1.822 +                                         _ForwardIter __last,
   1.823 +                                         _Predicate __pred, _Distance __len,
   1.824 +                                         _Pointer __buffer,
   1.825 +                                         _Distance __buffer_size) 
   1.826 +{
   1.827 +  if (__len <= __buffer_size) {
   1.828 +    _ForwardIter __result1 = __first;
   1.829 +    _Pointer __result2 = __buffer;
   1.830 +    for ( ; __first != __last ; ++__first)
   1.831 +      if (__pred(*__first)) {
   1.832 +        *__result1 = *__first;
   1.833 +        ++__result1;
   1.834 +      }
   1.835 +      else {
   1.836 +        *__result2 = *__first;
   1.837 +        ++__result2;
   1.838 +      }
   1.839 +    copy(__buffer, __result2, __result1);
   1.840 +    return __result1;
   1.841 +  }
   1.842 +  else {
   1.843 +    _ForwardIter __middle = __first;
   1.844 +    advance(__middle, __len / 2);
   1.845 +    return rotate(__stable_partition_adaptive(
   1.846 +                          __first, __middle, __pred,
   1.847 +                          _Distance(__len / 2), __buffer, __buffer_size),
   1.848 +                    __middle,
   1.849 +                    __stable_partition_adaptive(
   1.850 +                          __middle, __last, __pred,
   1.851 +                          _Distance(__len - __len / 2), __buffer, __buffer_size));
   1.852 +  }
   1.853 +}
   1.854 +*/ //bug fix
   1.855 +template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
   1.856 +inline _ForwardIter
   1.857 +__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, 
   1.858 +                       _Predicate __pred, _Tp*, _Distance*)
   1.859 +{
   1.860 +  typedef _Temporary_buffer<_ForwardIter, _Tp> _TmpBuf;
   1.861 +  _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
   1.862 +  _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
   1.863 +
   1.864 +  _STLP_MPWFIX_TRY		//*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
   1.865 +  return (__buf.size() > 0) ?
   1.866 +    __stable_partition_adaptive(__first, __last, __pred,
   1.867 +				_Distance(__buf.requested_size()),
   1.868 +				__buf.begin(), _Distance(__buf.size()))  :
   1.869 +    __inplace_stable_partition(__first, __last, __pred, 
   1.870 +			       _Distance(__buf.requested_size()));
   1.871 +  _STLP_MPWFIX_CATCH	//*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
   1.872 +}
   1.873 +/*
   1.874 +template <class _ForwardIter, class _Predicate>
   1.875 +_ForwardIter 
   1.876 +stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
   1.877 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.878 +  if (__first == __last)
   1.879 +    return __first;
   1.880 +  else
   1.881 +    return __stable_partition_aux(__first, __last, __pred,
   1.882 +                                  _STLP_VALUE_TYPE(__first, _ForwardIter),
   1.883 +                                  _STLP_DISTANCE_TYPE(__first, _ForwardIter));
   1.884 +}
   1.885 +*/ //bug fix
   1.886 +template <class _RandomAccessIter, class _Tp, class _Compare>
   1.887 +_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 
   1.888 +                                        _RandomAccessIter __last, 
   1.889 +                                        _Tp __pivot, _Compare __comp) 
   1.890 +{
   1.891 +  _STLP_PUSH_STACK_ITEM(_Tp, &__pivot)
   1.892 +  while (true) {
   1.893 +    while (__comp(*__first, __pivot))
   1.894 +      ++__first;
   1.895 +    --__last;
   1.896 +    while (__comp(__pivot, *__last))
   1.897 +      --__last;
   1.898 +    if (!(__first < __last))
   1.899 +      return __first;
   1.900 +    iter_swap(__first, __last);
   1.901 +    ++__first;
   1.902 +  }
   1.903 +}
   1.904 +
   1.905 +// sort() and its auxiliary functions. 
   1.906 +
   1.907 +# define  __stl_threshold  16
   1.908 +
   1.909 +template <class _RandomAccessIter, class _Tp, class _Compare>
   1.910 +void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, 
   1.911 +                               _Compare __comp) {
   1.912 +   _STLP_PUSH_STACK_ITEM(_Tp, &__val)
   1.913 +  _RandomAccessIter __next = __last;
   1.914 +  --__next;  
   1.915 +  while (__comp(__val, *__next)) {
   1.916 +    *__last = *__next;
   1.917 +    __last = __next;
   1.918 +    --__next;
   1.919 +  }
   1.920 +  *__last = __val;
   1.921 +}
   1.922 +
   1.923 +template <class _RandomAccessIter, class _Tp, class _Compare>
   1.924 +inline void __linear_insert(_RandomAccessIter __first, 
   1.925 +                            _RandomAccessIter __last, _Tp __val, _Compare __comp) {
   1.926 +  _STLP_PUSH_STACK_ITEM(_Tp, &__val)
   1.927 +  if (__comp(__val, *__first)) {
   1.928 +    copy_backward(__first, __last, __last + 1);
   1.929 +    *__first = __val;
   1.930 +  }
   1.931 +  else
   1.932 +    __unguarded_linear_insert(__last, __val, __comp);
   1.933 +}
   1.934 +
   1.935 +template <class _RandomAccessIter, class _Compare>
   1.936 +void __insertion_sort(_RandomAccessIter __first,
   1.937 +                      _RandomAccessIter __last, _Compare __comp) {
   1.938 +  if (__first == __last) return;
   1.939 +  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
   1.940 +    __linear_insert(__first, __i, *__i, __comp);	//*TY 12/26/1998 - supply *__i as __val
   1.941 +}
   1.942 +
   1.943 +template <class _RandomAccessIter, class _Tp, class _Compare>
   1.944 +void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 
   1.945 +                                    _RandomAccessIter __last,
   1.946 +                                    _Tp*, _Compare __comp) {
   1.947 +  for (_RandomAccessIter __i = __first; __i != __last; ++__i)
   1.948 +    __unguarded_linear_insert(__i, _Tp(*__i), __comp);
   1.949 +}
   1.950 +
   1.951 +template <class _RandomAccessIter, class _Compare>
   1.952 +inline void __unguarded_insertion_sort(_RandomAccessIter __first, 
   1.953 +                                       _RandomAccessIter __last,
   1.954 +                                       _Compare __comp) {
   1.955 +  __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
   1.956 +}
   1.957 +
   1.958 +template <class _RandomAccessIter, class _Compare>
   1.959 +void __final_insertion_sort(_RandomAccessIter __first, 
   1.960 +                            _RandomAccessIter __last, _Compare __comp) {
   1.961 +  if (__last - __first > __stl_threshold) {
   1.962 +    __insertion_sort(__first, __first + __stl_threshold, __comp);
   1.963 +    __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
   1.964 +  }
   1.965 +  else
   1.966 +    __insertion_sort(__first, __last, __comp);
   1.967 +}
   1.968 +
   1.969 +template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
   1.970 +void __introsort_loop(_RandomAccessIter __first,
   1.971 +                      _RandomAccessIter __last, _Tp*,
   1.972 +                      _Size __depth_limit, _Compare __comp)
   1.973 +{
   1.974 +  while (__last - __first > __stl_threshold) {
   1.975 +    if (__depth_limit == 0) {
   1.976 +      partial_sort(__first, __last, __last, __comp);
   1.977 +      return;
   1.978 +    }
   1.979 +    --__depth_limit;
   1.980 +    _RandomAccessIter __cut =
   1.981 +      __unguarded_partition(__first, __last,
   1.982 +                            _Tp(__median(*__first,
   1.983 +                                         *(__first + (__last - __first)/2),
   1.984 +                                         *(__last - 1), __comp)),
   1.985 +       __comp);
   1.986 +    __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
   1.987 +    __last = __cut;
   1.988 +  }
   1.989 +}
   1.990 +
   1.991 +template <class _RandomAccessIter>
   1.992 +void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
   1.993 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
   1.994 +  if (__first != __last) {
   1.995 +    __introsort_loop(__first, __last,
   1.996 +                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),
   1.997 +                     __lg(__last - __first) * 2, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)) );
   1.998 +    __final_insertion_sort(__first, __last, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
   1.999 +  }
  1.1000 +}
  1.1001 +
  1.1002 +template <class _RandomAccessIter, class _Compare>
  1.1003 +void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
  1.1004 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1005 +  if (__first != __last) {
  1.1006 +    __introsort_loop(__first, __last,
  1.1007 +                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1.1008 +                     __lg(__last - __first) * 2,
  1.1009 +                     __comp);
  1.1010 +    __final_insertion_sort(__first, __last, __comp);
  1.1011 +  }
  1.1012 +}
  1.1013 +
  1.1014 +// stable_sort() and its auxiliary functions.
  1.1015 +
  1.1016 +template <class _RandomAccessIter, class _Compare>
  1.1017 +void __inplace_stable_sort(_RandomAccessIter __first,
  1.1018 +                           _RandomAccessIter __last, _Compare __comp) {
  1.1019 +  if (__last - __first < 15) {
  1.1020 +    __insertion_sort(__first, __last, __comp);
  1.1021 +    return;
  1.1022 +  }
  1.1023 +  _RandomAccessIter __middle = __first + (__last - __first) / 2;
  1.1024 +  __inplace_stable_sort(__first, __middle, __comp);
  1.1025 +  __inplace_stable_sort(__middle, __last, __comp);
  1.1026 +  __merge_without_buffer(__first, __middle, __last,
  1.1027 +                         __middle - __first,
  1.1028 +                         __last - __middle,
  1.1029 +                         __comp);
  1.1030 +}
  1.1031 +
  1.1032 +template <class _RandomAccessIter1, class _RandomAccessIter2,
  1.1033 +          class _Distance, class _Compare>
  1.1034 +void __merge_sort_loop(_RandomAccessIter1 __first,
  1.1035 +                       _RandomAccessIter1 __last, 
  1.1036 +                       _RandomAccessIter2 __result, _Distance __step_size,
  1.1037 +                       _Compare __comp) {
  1.1038 +  _Distance __two_step = 2 * __step_size;
  1.1039 +
  1.1040 +  while (__last - __first >= __two_step) {
  1.1041 +    __result = merge(__first, __first + __step_size,
  1.1042 +                     __first + __step_size, __first + __two_step,
  1.1043 +                     __result,
  1.1044 +                     __comp);
  1.1045 +    __first += __two_step;
  1.1046 +  }
  1.1047 +  __step_size = (min) (_Distance(__last - __first), __step_size);
  1.1048 +
  1.1049 +  merge(__first, __first + __step_size,
  1.1050 +        __first + __step_size, __last,
  1.1051 +        __result,
  1.1052 +        __comp);
  1.1053 +}
  1.1054 +
  1.1055 +const int __stl_chunk_size = 7;
  1.1056 +        
  1.1057 +template <class _RandomAccessIter, class _Distance, class _Compare>
  1.1058 +void __chunk_insertion_sort(_RandomAccessIter __first, 
  1.1059 +                            _RandomAccessIter __last,
  1.1060 +                            _Distance __chunk_size, _Compare __comp)
  1.1061 +{
  1.1062 +  while (__last - __first >= __chunk_size) {
  1.1063 +    __insertion_sort(__first, __first + __chunk_size, __comp);
  1.1064 +    __first += __chunk_size;
  1.1065 +  }
  1.1066 +  __insertion_sort(__first, __last, __comp);
  1.1067 +}
  1.1068 +
  1.1069 +template <class _RandomAccessIter, class _Pointer, class _Distance,
  1.1070 +          class _Compare>
  1.1071 +void __merge_sort_with_buffer(_RandomAccessIter __first, 
  1.1072 +                              _RandomAccessIter __last, _Pointer __buffer,
  1.1073 +                              _Distance*, _Compare __comp) {
  1.1074 +  _Distance __len = __last - __first;
  1.1075 +  _Pointer __buffer_last = __buffer + __len;
  1.1076 +
  1.1077 +  _Distance __step_size = __stl_chunk_size;
  1.1078 +  __chunk_insertion_sort(__first, __last, __step_size, __comp);
  1.1079 +
  1.1080 +  while (__step_size < __len) {
  1.1081 +    __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
  1.1082 +    __step_size *= 2;
  1.1083 +    __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
  1.1084 +    __step_size *= 2;
  1.1085 +  }
  1.1086 +}
  1.1087 +
  1.1088 +template <class _BidirectionalIter1, class _BidirectionalIter2,
  1.1089 +          class _Distance>
  1.1090 +_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
  1.1091 +                                      _BidirectionalIter1 __middle,
  1.1092 +                                      _BidirectionalIter1 __last,
  1.1093 +                                      _Distance __len1, _Distance __len2,
  1.1094 +                                      _BidirectionalIter2 __buffer,
  1.1095 +                                      _Distance __buffer_size) {
  1.1096 +  if (__len1 > __len2 && __len2 <= __buffer_size) {
  1.1097 +    _BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);
  1.1098 +    copy_backward(__first, __middle, __last);
  1.1099 +    return copy(__buffer, __buffer_end, __first);
  1.1100 +  }
  1.1101 +  else if (__len1 <= __buffer_size) {
  1.1102 +    _BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);
  1.1103 +    copy(__middle, __last, __first);
  1.1104 +    return copy_backward(__buffer, __buffer_end, __last);
  1.1105 +  }
  1.1106 +  else
  1.1107 +    return rotate(__first, __middle, __last);
  1.1108 +}
  1.1109 +
  1.1110 +template <class _BidirectionalIter, class _Distance, class _Pointer,
  1.1111 +          class _Compare>
  1.1112 +void __merge_adaptive(_BidirectionalIter __first, 
  1.1113 +                      _BidirectionalIter __middle, 
  1.1114 +                      _BidirectionalIter __last,
  1.1115 +                      _Distance __len1, _Distance __len2,
  1.1116 +                      _Pointer __buffer, _Distance __buffer_size,
  1.1117 +                      _Compare __comp) {
  1.1118 +  if (__len1 <= __len2 && __len1 <= __buffer_size) {
  1.1119 +    _Pointer __buffer_end = copy(__first, __middle, __buffer);
  1.1120 +    merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  1.1121 +  }
  1.1122 +  else if (__len2 <= __buffer_size) {
  1.1123 +    _Pointer __buffer_end = copy(__middle, __last, __buffer);
  1.1124 +    __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
  1.1125 +                     __comp);
  1.1126 +  }
  1.1127 +  else {
  1.1128 +    _BidirectionalIter __first_cut = __first;
  1.1129 +    _BidirectionalIter __second_cut = __middle;
  1.1130 +    _Distance __len11 = 0;
  1.1131 +    _Distance __len22 = 0;
  1.1132 +    if (__len1 > __len2) {
  1.1133 +      __len11 = __len1 / 2;
  1.1134 +      advance(__first_cut, __len11);
  1.1135 +      __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  1.1136 +      __len22 += distance(__middle, __second_cut);   
  1.1137 +    }
  1.1138 +    else {
  1.1139 +      __len22 = __len2 / 2;
  1.1140 +      advance(__second_cut, __len22);
  1.1141 +      __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  1.1142 +      __len11 += distance(__first, __first_cut);
  1.1143 +    }
  1.1144 +    _BidirectionalIter __new_middle =
  1.1145 +      __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
  1.1146 +                        __len22, __buffer, __buffer_size);
  1.1147 +    __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  1.1148 +                     __len22, __buffer, __buffer_size, __comp);
  1.1149 +    __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  1.1150 +                     __len2 - __len22, __buffer, __buffer_size, __comp);
  1.1151 +  }
  1.1152 +}
  1.1153 +
  1.1154 +template <class _RandomAccessIter, class _Pointer, class _Distance, 
  1.1155 +          class _Compare>
  1.1156 +void __stable_sort_adaptive(_RandomAccessIter __first, 
  1.1157 +                            _RandomAccessIter __last, _Pointer __buffer,
  1.1158 +                            _Distance __buffer_size, _Compare __comp) {
  1.1159 +  _Distance __len = (__last - __first + 1) / 2;
  1.1160 +  _RandomAccessIter __middle = __first + __len;
  1.1161 +  if (__len > __buffer_size) {
  1.1162 +    __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 
  1.1163 +                           __comp);
  1.1164 +    __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 
  1.1165 +                           __comp);
  1.1166 +  }
  1.1167 +  else {
  1.1168 +    __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
  1.1169 +                               __comp);
  1.1170 +    __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
  1.1171 +                               __comp);
  1.1172 +  }
  1.1173 +  __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 
  1.1174 +                   _Distance(__last - __middle), __buffer, __buffer_size,
  1.1175 +                   __comp);
  1.1176 +}
  1.1177 +
  1.1178 +template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
  1.1179 +void __stable_sort_aux(_RandomAccessIter __first,
  1.1180 +			      _RandomAccessIter __last, _Tp*, _Distance*,
  1.1181 +			      _Compare __comp) {
  1.1182 +
  1.1183 +  typedef _Temporary_buffer<_RandomAccessIter, _Tp> _TmpBuf;
  1.1184 +  _TmpBuf __buf(__first, __last);
  1.1185 +  _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
  1.1186 +
  1.1187 +  if (__buf.begin() == 0)
  1.1188 +    __inplace_stable_sort(__first, __last, __comp);
  1.1189 +  else 
  1.1190 +    __stable_sort_adaptive(__first, __last, __buf.begin(),
  1.1191 +                           _Distance(__buf.size()),
  1.1192 +                           __comp);
  1.1193 +}
  1.1194 +
  1.1195 +template <class _RandomAccessIter>
  1.1196 +void stable_sort(_RandomAccessIter __first,
  1.1197 +		 _RandomAccessIter __last) {
  1.1198 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1199 +  __stable_sort_aux(__first, __last,
  1.1200 +                    _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1.1201 +                    _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
  1.1202 +                    __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1.1203 +}
  1.1204 +
  1.1205 +template <class _RandomAccessIter, class _Compare>
  1.1206 +void stable_sort(_RandomAccessIter __first,
  1.1207 +		 _RandomAccessIter __last, _Compare __comp) {
  1.1208 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1209 +  __stable_sort_aux(__first, __last,
  1.1210 +                    _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1.1211 +                    _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), 
  1.1212 +                    __comp);
  1.1213 +}
  1.1214 +
  1.1215 +// partial_sort, partial_sort_copy, and auxiliary functions.
  1.1216 +
  1.1217 +template <class _RandomAccessIter, class _Tp, class _Compare>
  1.1218 +void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
  1.1219 +                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1.1220 +  make_heap(__first, __middle, __comp);
  1.1221 +  for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
  1.1222 +    if (__comp(*__i, *__first))
  1.1223 +      __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
  1.1224 +                 _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
  1.1225 +  sort_heap(__first, __middle, __comp);
  1.1226 +}
  1.1227 +
  1.1228 +
  1.1229 +template <class _RandomAccessIter>
  1.1230 +void 
  1.1231 +partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last) {
  1.1232 +  _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  1.1233 +  _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  1.1234 +  __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 
  1.1235 +                 __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1.1236 +}
  1.1237 +
  1.1238 +template <class _RandomAccessIter, class _Compare>
  1.1239 +void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
  1.1240 +                  _RandomAccessIter __last, _Compare __comp) {
  1.1241 +  _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  1.1242 +  _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  1.1243 +  __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  1.1244 +}
  1.1245 +
  1.1246 +template <class _InputIter, class _RandomAccessIter, class _Compare,
  1.1247 +          class _Distance, class _Tp>
  1.1248 +_RandomAccessIter __partial_sort_copy(_InputIter __first,
  1.1249 +                                         _InputIter __last,
  1.1250 +                                         _RandomAccessIter __result_first,
  1.1251 +                                         _RandomAccessIter __result_last,
  1.1252 +                                         _Compare __comp, _Distance*, _Tp*) {
  1.1253 +  if (__result_first == __result_last) return __result_last;
  1.1254 +  _RandomAccessIter __result_real_last = __result_first;
  1.1255 +  while(__first != __last && __result_real_last != __result_last) {
  1.1256 +    *__result_real_last = *__first;
  1.1257 +    ++__result_real_last;
  1.1258 +    ++__first;
  1.1259 +  }
  1.1260 +  make_heap(__result_first, __result_real_last, __comp);
  1.1261 +  while (__first != __last) {
  1.1262 +    if (__comp(*__first, *__result_first))
  1.1263 +      __adjust_heap(__result_first, _Distance(0),
  1.1264 +                    _Distance(__result_real_last - __result_first),
  1.1265 +                    _Tp(*__first),
  1.1266 +                    __comp);
  1.1267 +    ++__first;
  1.1268 +  }
  1.1269 +  sort_heap(__result_first, __result_real_last, __comp);
  1.1270 +  return __result_real_last;
  1.1271 +}
  1.1272 +
  1.1273 +template <class _InputIter, class _RandomAccessIter>
  1.1274 +_RandomAccessIter
  1.1275 +partial_sort_copy(_InputIter __first, _InputIter __last,
  1.1276 +                  _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
  1.1277 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1278 +  _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))
  1.1279 +  return __partial_sort_copy(__first, __last, __result_first, __result_last, 
  1.1280 +                             __less(_STLP_VALUE_TYPE(__first, _InputIter)),
  1.1281 +                             _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
  1.1282 +                             _STLP_VALUE_TYPE(__first, _InputIter));
  1.1283 +}
  1.1284 +
  1.1285 +template <class _InputIter, class _RandomAccessIter, class _Compare>
  1.1286 +_RandomAccessIter
  1.1287 +partial_sort_copy(_InputIter __first, _InputIter __last,
  1.1288 +                  _RandomAccessIter __result_first,
  1.1289 +                  _RandomAccessIter __result_last, _Compare __comp) {
  1.1290 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1291 +  _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))
  1.1292 +  return __partial_sort_copy(__first, __last, __result_first, __result_last,
  1.1293 +                             __comp,
  1.1294 +                             _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
  1.1295 +                             _STLP_VALUE_TYPE(__first, _InputIter));
  1.1296 +}
  1.1297 +
  1.1298 +// nth_element() and its auxiliary functions.  
  1.1299 +
  1.1300 +template <class _RandomAccessIter, class _Tp, class _Compare>
  1.1301 +void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1.1302 +                   _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1.1303 +  while (__last - __first > 3) {
  1.1304 +    _RandomAccessIter __cut =
  1.1305 +      __unguarded_partition(__first, __last,
  1.1306 +                            _Tp(__median(*__first,
  1.1307 +                                         *(__first + (__last - __first)/2), 
  1.1308 +                                         *(__last - 1),
  1.1309 +                                         __comp)),
  1.1310 +                            __comp);
  1.1311 +    if (__cut <= __nth)
  1.1312 +      __first = __cut;
  1.1313 +    else 
  1.1314 +      __last = __cut;
  1.1315 +  }
  1.1316 +  __insertion_sort(__first, __last, __comp);
  1.1317 +}
  1.1318 +
  1.1319 +
  1.1320 +template <class _RandomAccessIter>
  1.1321 +void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1.1322 +                 _RandomAccessIter __last) {
  1.1323 +  _STLP_DEBUG_CHECK(__check_range(__first, __nth))
  1.1324 +  _STLP_DEBUG_CHECK(__check_range(__nth, __last))
  1.1325 +  __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 
  1.1326 +                __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1.1327 +}
  1.1328 +
  1.1329 +template <class _RandomAccessIter, class _Compare>
  1.1330 +void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1.1331 +                 _RandomAccessIter __last, _Compare __comp) {
  1.1332 +  _STLP_DEBUG_CHECK(__check_range(__first, __nth))
  1.1333 +  _STLP_DEBUG_CHECK(__check_range(__nth, __last))
  1.1334 +  __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  1.1335 +}
  1.1336 +
  1.1337 +// Binary search (lower_bound, upper_bound, equal_range, binary_search).
  1.1338 +
  1.1339 +template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  1.1340 +_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
  1.1341 +                           const _Tp& __val, _Compare __comp, _Distance*)
  1.1342 +{
  1.1343 +  _Distance __len = distance(__first, __last);
  1.1344 +  _Distance __half;
  1.1345 +
  1.1346 +  while (__len > 0) {
  1.1347 +    __half = __len >> 1;
  1.1348 +    _ForwardIter __middle = __first;
  1.1349 +    advance(__middle, __half);
  1.1350 +    if (__comp(__val, *__middle))
  1.1351 +      __len = __half;
  1.1352 +    else {
  1.1353 +      __first = __middle;
  1.1354 +      ++__first;
  1.1355 +      __len = __len - __half - 1;
  1.1356 +    }
  1.1357 +  }
  1.1358 +  return __first;
  1.1359 +}
  1.1360 +
  1.1361 +template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  1.1362 +pair<_ForwardIter, _ForwardIter>
  1.1363 +__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  1.1364 +              _Compare __comp, _Distance*)
  1.1365 +{
  1.1366 +  _Distance __len = distance(__first, __last);
  1.1367 +  _Distance __half;
  1.1368 +
  1.1369 +  while (__len > 0) {
  1.1370 +    __half = __len >> 1;
  1.1371 +    _ForwardIter __middle = __first;
  1.1372 +    advance(__middle, __half);
  1.1373 +    if (__comp(*__middle, __val)) {
  1.1374 +      __first = __middle;
  1.1375 +      ++__first;
  1.1376 +      __len = __len - __half - 1;
  1.1377 +    }
  1.1378 +    else if (__comp(__val, *__middle))
  1.1379 +      __len = __half;
  1.1380 +    else {
  1.1381 +      _ForwardIter __left = lower_bound(__first, __middle, __val, __comp);
  1.1382 +      advance(__first, __len);
  1.1383 +      _ForwardIter __right = upper_bound(++__middle, __first, __val, __comp);
  1.1384 +      return pair<_ForwardIter, _ForwardIter>(__left, __right);
  1.1385 +    }
  1.1386 +  }
  1.1387 +  return pair<_ForwardIter, _ForwardIter>(__first, __first);
  1.1388 +}           
  1.1389 +
  1.1390 +template <class _InputIter1, class _InputIter2, class _OutputIter>
  1.1391 +_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  1.1392 +                  _InputIter2 __first2, _InputIter2 __last2,
  1.1393 +                  _OutputIter __result) {
  1.1394 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1.1395 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1.1396 +  while (__first1 != __last1 && __first2 != __last2) {
  1.1397 +    if (*__first2 < *__first1) {
  1.1398 +      *__result = *__first2;
  1.1399 +      ++__first2;
  1.1400 +    }
  1.1401 +    else {
  1.1402 +      *__result = *__first1;
  1.1403 +      ++__first1;
  1.1404 +    }
  1.1405 +    ++__result;
  1.1406 +  }
  1.1407 +  return copy(__first2, __last2, copy(__first1, __last1, __result));
  1.1408 +}
  1.1409 +
  1.1410 +template <class _InputIter1, class _InputIter2, class _OutputIter,
  1.1411 +          class _Compare>
  1.1412 +_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  1.1413 +                  _InputIter2 __first2, _InputIter2 __last2,
  1.1414 +                  _OutputIter __result, _Compare __comp) {
  1.1415 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1.1416 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1.1417 +  while (__first1 != __last1 && __first2 != __last2) {
  1.1418 +    if (__comp(*__first2, *__first1)) {
  1.1419 +      *__result = *__first2;
  1.1420 +      ++__first2;
  1.1421 +    }
  1.1422 +    else {
  1.1423 +      *__result = *__first1;
  1.1424 +      ++__first1;
  1.1425 +    }
  1.1426 +    ++__result;
  1.1427 +  }
  1.1428 +  return copy(__first2, __last2, copy(__first1, __last1, __result));
  1.1429 +}
  1.1430 +
  1.1431 +template <class _BidirectionalIter, class _Distance, class _Compare>
  1.1432 +void __merge_without_buffer(_BidirectionalIter __first,
  1.1433 +                            _BidirectionalIter __middle,
  1.1434 +                            _BidirectionalIter __last,
  1.1435 +                            _Distance __len1, _Distance __len2,
  1.1436 +                            _Compare __comp) {
  1.1437 +  if (__len1 == 0 || __len2 == 0)
  1.1438 +    return;
  1.1439 +  if (__len1 + __len2 == 2) {
  1.1440 +    if (__comp(*__middle, *__first))
  1.1441 +      iter_swap(__first, __middle);
  1.1442 +    return;
  1.1443 +  }
  1.1444 +  _BidirectionalIter __first_cut = __first;
  1.1445 +  _BidirectionalIter __second_cut = __middle;
  1.1446 +  _Distance __len11 = 0;
  1.1447 +  _Distance __len22 = 0;
  1.1448 +  if (__len1 > __len2) {
  1.1449 +    __len11 = __len1 / 2;
  1.1450 +    advance(__first_cut, __len11);
  1.1451 +    __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  1.1452 +    __len22 += distance(__middle, __second_cut);
  1.1453 +  }
  1.1454 +  else {
  1.1455 +    __len22 = __len2 / 2;
  1.1456 +    advance(__second_cut, __len22);
  1.1457 +    __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  1.1458 +    __len11 +=distance(__first, __first_cut);
  1.1459 +  }
  1.1460 +  _BidirectionalIter __new_middle
  1.1461 +    = rotate(__first_cut, __middle, __second_cut);
  1.1462 +  __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
  1.1463 +                         __comp);
  1.1464 +  __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
  1.1465 +                         __len2 - __len22, __comp);
  1.1466 +}
  1.1467 +
  1.1468 +template <class _BidirectionalIter1, class _BidirectionalIter2,
  1.1469 +          class _BidirectionalIter3, class _Compare>
  1.1470 +_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  1.1471 +                                     _BidirectionalIter1 __last1,
  1.1472 +                                     _BidirectionalIter2 __first2,
  1.1473 +                                     _BidirectionalIter2 __last2,
  1.1474 +                                     _BidirectionalIter3 __result,
  1.1475 +                                     _Compare __comp) {
  1.1476 +  if (__first1 == __last1)
  1.1477 +    return copy_backward(__first2, __last2, __result);
  1.1478 +  if (__first2 == __last2)
  1.1479 +    return copy_backward(__first1, __last1, __result);
  1.1480 +  --__last1;
  1.1481 +  --__last2;
  1.1482 +  while (true) {
  1.1483 +    if (__comp(*__last2, *__last1)) {
  1.1484 +      *--__result = *__last1;
  1.1485 +      if (__first1 == __last1)
  1.1486 +        return copy_backward(__first2, ++__last2, __result);
  1.1487 +      --__last1;
  1.1488 +    }
  1.1489 +    else {
  1.1490 +      *--__result = *__last2;
  1.1491 +      if (__first2 == __last2)
  1.1492 +        return copy_backward(__first1, ++__last1, __result);
  1.1493 +      --__last2;
  1.1494 +    }
  1.1495 +  }
  1.1496 +}
  1.1497 +
  1.1498 +template <class _BidirectionalIter, class _Tp, 
  1.1499 +          class _Distance, class _Compare>
  1.1500 +inline void __inplace_merge_aux(_BidirectionalIter __first,
  1.1501 +                                _BidirectionalIter __middle,
  1.1502 +                                _BidirectionalIter __last, _Tp*, _Distance*,
  1.1503 +                                _Compare __comp) {
  1.1504 +  _Distance __len1 = distance(__first, __middle);
  1.1505 +  _Distance __len2 = distance(__middle, __last);
  1.1506 +
  1.1507 +  typedef _Temporary_buffer<_BidirectionalIter, _Tp> _TmpBuf;
  1.1508 +  _TmpBuf __buf(__first, __last);
  1.1509 +  _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
  1.1510 +
  1.1511 +  if (__buf.begin() == 0)
  1.1512 +    __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  1.1513 +  else
  1.1514 +    __merge_adaptive(__first, __middle, __last, __len1, __len2,
  1.1515 +                     __buf.begin(), _Distance(__buf.size()),
  1.1516 +                     __comp);
  1.1517 +}
  1.1518 +
  1.1519 +template <class _BidirectionalIter>
  1.1520 +void inplace_merge(_BidirectionalIter __first,
  1.1521 +		   _BidirectionalIter __middle,
  1.1522 +		   _BidirectionalIter __last) {
  1.1523 +  _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  1.1524 +  _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  1.1525 +  if (__first == __middle || __middle == __last)
  1.1526 +    return;
  1.1527 +  __inplace_merge_aux(__first, __middle, __last,
  1.1528 +                      _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
  1.1529 +                      __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1.1530 +}
  1.1531 +
  1.1532 +template <class _BidirectionalIter, class _Compare>
  1.1533 +void inplace_merge(_BidirectionalIter __first,
  1.1534 +		   _BidirectionalIter __middle,
  1.1535 +		   _BidirectionalIter __last, _Compare __comp) {
  1.1536 +  _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  1.1537 +  _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  1.1538 +  if (__first == __middle || __middle == __last)
  1.1539 +    return;
  1.1540 +  __inplace_merge_aux(__first, __middle, __last,
  1.1541 +                      _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
  1.1542 +                      __comp);
  1.1543 +}
  1.1544 +
  1.1545 +
  1.1546 +template <class _InputIter1, class _InputIter2, class _Compare>
  1.1547 +bool __includes(_InputIter1 __first1, _InputIter1 __last1,
  1.1548 +                _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  1.1549 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1.1550 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1.1551 +  while (__first1 != __last1 && __first2 != __last2)
  1.1552 +    if (__comp(*__first2, *__first1))
  1.1553 +      return false;
  1.1554 +    else if(__comp(*__first1, *__first2)) 
  1.1555 +      ++__first1;
  1.1556 +    else
  1.1557 +      ++__first1, ++__first2;
  1.1558 +
  1.1559 +  return __first2 == __last2;
  1.1560 +}
  1.1561 +
  1.1562 +template <class _InputIter1, class _InputIter2, class _Compare>
  1.1563 +bool includes(_InputIter1 __first1, _InputIter1 __last1,
  1.1564 +              _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  1.1565 +  return __includes(__first1, __last1, __first2, __last2, __comp);
  1.1566 +}
  1.1567 +
  1.1568 +template <class _InputIter1, class _InputIter2>
  1.1569 +bool includes(_InputIter1 __first1, _InputIter1 __last1,
  1.1570 +              _InputIter2 __first2, _InputIter2 __last2) {
  1.1571 +  return __includes(__first1, __last1, __first2, __last2, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1.1572 +}
  1.1573 +
  1.1574 +template <class _InputIter1, class _InputIter2, class _OutputIter,
  1.1575 +          class _Compare>
  1.1576 +_OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
  1.1577 +                        _InputIter2 __first2, _InputIter2 __last2,
  1.1578 +                        _OutputIter __result, _Compare __comp) {
  1.1579 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1.1580 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1.1581 +  while (__first1 != __last1 && __first2 != __last2) {
  1.1582 +    if (__comp(*__first1, *__first2)) {
  1.1583 +      *__result = *__first1;
  1.1584 +      ++__first1;
  1.1585 +    }
  1.1586 +    else if (__comp(*__first2, *__first1)) {
  1.1587 +      *__result = *__first2;
  1.1588 +      ++__first2;
  1.1589 +    }
  1.1590 +    else {
  1.1591 +      *__result = *__first1;
  1.1592 +      ++__first1;
  1.1593 +      ++__first2;
  1.1594 +    }
  1.1595 +    ++__result;
  1.1596 +  }
  1.1597 +  return copy(__first2, __last2, copy(__first1, __last1, __result));
  1.1598 +}
  1.1599 +
  1.1600 +template <class _InputIter1, class _InputIter2, class _OutputIter>
  1.1601 +_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  1.1602 +                      _InputIter2 __first2, _InputIter2 __last2,
  1.1603 +                      _OutputIter __result) {
  1.1604 +  return __set_union(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
  1.1605 +}
  1.1606 +
  1.1607 +template <class _InputIter1, class _InputIter2, class _OutputIter,
  1.1608 +          class _Compare>
  1.1609 +_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  1.1610 +                      _InputIter2 __first2, _InputIter2 __last2,
  1.1611 +                      _OutputIter __result, _Compare __comp) {
  1.1612 +  return __set_union(__first1, __last1, __first2, __last2, __result, __comp);
  1.1613 +}
  1.1614 +
  1.1615 +template <class _InputIter1, class _InputIter2, class _OutputIter,
  1.1616 +          class _Compare>
  1.1617 +_OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1.1618 +                               _InputIter2 __first2, _InputIter2 __last2,
  1.1619 +                               _OutputIter __result, _Compare __comp) {
  1.1620 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1.1621 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1.1622 +  while (__first1 != __last1 && __first2 != __last2)
  1.1623 +    if (__comp(*__first1, *__first2))
  1.1624 +      ++__first1;
  1.1625 +    else if (__comp(*__first2, *__first1))
  1.1626 +      ++__first2;
  1.1627 +    else {
  1.1628 +      *__result = *__first1;
  1.1629 +      ++__first1;
  1.1630 +      ++__first2;
  1.1631 +      ++__result;
  1.1632 +    }
  1.1633 +  return __result;
  1.1634 +}
  1.1635 +
  1.1636 +template <class _InputIter1, class _InputIter2, class _OutputIter>
  1.1637 +_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1.1638 +                             _InputIter2 __first2, _InputIter2 __last2,
  1.1639 +                             _OutputIter __result) {
  1.1640 +  return __set_intersection(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
  1.1641 +}
  1.1642 +
  1.1643 +template <class _InputIter1, class _InputIter2, class _OutputIter,
  1.1644 +          class _Compare>
  1.1645 +_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1.1646 +                             _InputIter2 __first2, _InputIter2 __last2,
  1.1647 +                             _OutputIter __result, _Compare __comp) {
  1.1648 +  return __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
  1.1649 +}
  1.1650 +
  1.1651 +template <class _InputIter1, class _InputIter2, class _OutputIter, 
  1.1652 +          class _Compare>
  1.1653 +_OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1.1654 +                             _InputIter2 __first2, _InputIter2 __last2, 
  1.1655 +                             _OutputIter __result, _Compare __comp) {
  1.1656 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1.1657 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1.1658 +  while (__first1 != __last1 && __first2 != __last2)
  1.1659 +    if (__comp(*__first1, *__first2)) {
  1.1660 +      *__result = *__first1;
  1.1661 +      ++__first1;
  1.1662 +      ++__result;
  1.1663 +    }
  1.1664 +    else if (__comp(*__first2, *__first1))
  1.1665 +      ++__first2;
  1.1666 +    else {
  1.1667 +      ++__first1;
  1.1668 +      ++__first2;
  1.1669 +    }
  1.1670 +  return copy(__first1, __last1, __result);
  1.1671 +}
  1.1672 +
  1.1673 +template <class _InputIter1, class _InputIter2, class _OutputIter>
  1.1674 +_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1.1675 +                           _InputIter2 __first2, _InputIter2 __last2,
  1.1676 +                           _OutputIter __result) {
  1.1677 +  return __set_difference(__first1, __last1, __first2, __last2, __result, 
  1.1678 +                          __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
  1.1679 +}
  1.1680 +
  1.1681 +template <class _InputIter1, class _InputIter2, class _OutputIter, 
  1.1682 +          class _Compare>
  1.1683 +_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1.1684 +                           _InputIter2 __first2, _InputIter2 __last2, 
  1.1685 +                           _OutputIter __result, _Compare __comp) {
  1.1686 +  return __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
  1.1687 +}
  1.1688 +
  1.1689 +template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
  1.1690 +_OutputIter 
  1.1691 +__set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1.1692 +                           _InputIter2 __first2, _InputIter2 __last2,
  1.1693 +                           _OutputIter __result, _Compare __comp) {
  1.1694 +  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1.1695 +  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1.1696 +  while (__first1 != __last1 && __first2 != __last2)
  1.1697 +    if (__comp(*__first1, *__first2)) {
  1.1698 +      *__result = *__first1;
  1.1699 +      ++__first1;
  1.1700 +      ++__result;
  1.1701 +    }
  1.1702 +    else if (__comp(*__first2, *__first1)) {
  1.1703 +      *__result = *__first2;
  1.1704 +      ++__first2;
  1.1705 +      ++__result;
  1.1706 +    }
  1.1707 +    else {
  1.1708 +      ++__first1;
  1.1709 +      ++__first2;
  1.1710 +    }
  1.1711 +  return copy(__first2, __last2, copy(__first1, __last1, __result));
  1.1712 +}
  1.1713 +
  1.1714 +template <class _InputIter1, class _InputIter2, class _OutputIter>
  1.1715 +_OutputIter 
  1.1716 +set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1.1717 +                         _InputIter2 __first2, _InputIter2 __last2,
  1.1718 +                         _OutputIter __result) {
  1.1719 +  return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
  1.1720 +                                    __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
  1.1721 +}
  1.1722 +
  1.1723 +template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
  1.1724 +_OutputIter 
  1.1725 +set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1.1726 +                         _InputIter2 __first2, _InputIter2 __last2,
  1.1727 +                         _OutputIter __result,
  1.1728 +                         _Compare __comp) {
  1.1729 +  return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
  1.1730 +}
  1.1731 +
  1.1732 +// min_element and max_element, with and without an explicitly supplied
  1.1733 +// comparison function.
  1.1734 +
  1.1735 +template <class _ForwardIter, class _Compare>
  1.1736 +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
  1.1737 +                            _Compare __comp) {
  1.1738 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1739 +  if (__first == __last) return __first;
  1.1740 +  _ForwardIter __result = __first;
  1.1741 +  while (++__first != __last) 
  1.1742 +    if (__comp(*__result, *__first)) __result = __first;
  1.1743 +  return __result;
  1.1744 +}
  1.1745 +
  1.1746 +template <class _ForwardIter>
  1.1747 +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
  1.1748 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1749 +  if (__first == __last) return __first;
  1.1750 +  _ForwardIter __result = __first;
  1.1751 +  while (++__first != __last) 
  1.1752 +    if (*__result < *__first)
  1.1753 +      __result = __first;
  1.1754 +  return __result;
  1.1755 +}
  1.1756 +
  1.1757 +template <class _ForwardIter>
  1.1758 +_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
  1.1759 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1760 +  if (__first == __last) return __first;
  1.1761 +  _ForwardIter __result = __first;
  1.1762 +  while (++__first != __last) 
  1.1763 +    if (*__first < *__result)
  1.1764 +      __result = __first;
  1.1765 +  return __result;
  1.1766 +}
  1.1767 +
  1.1768 +template <class _ForwardIter, class _Compare>
  1.1769 +_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
  1.1770 +                            _Compare __comp) {
  1.1771 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1772 +  if (__first == __last) return __first;
  1.1773 +  _ForwardIter __result = __first;
  1.1774 +  while (++__first != __last) 
  1.1775 +    if (__comp(*__first, *__result)) __result = __first;
  1.1776 +  return __result;
  1.1777 +}
  1.1778 +
  1.1779 +// next_permutation and prev_permutation, with and without an explicitly 
  1.1780 +// supplied comparison function.
  1.1781 +template <class _BidirectionalIter, class _Compare>
  1.1782 +bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1.1783 +                        _Compare __comp) {
  1.1784 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1785 +  if (__first == __last)
  1.1786 +    return false;
  1.1787 +  _BidirectionalIter __i = __first;
  1.1788 +  ++__i;
  1.1789 +  if (__i == __last)
  1.1790 +    return false;
  1.1791 +  __i = __last;
  1.1792 +  --__i;
  1.1793 +
  1.1794 +  for(;;) {
  1.1795 +    _BidirectionalIter __ii = __i;
  1.1796 +    --__i;
  1.1797 +    if (__comp(*__i, *__ii)) {
  1.1798 +      _BidirectionalIter __j = __last;
  1.1799 +      while (!__comp(*__i, *--__j))
  1.1800 +        {}
  1.1801 +      iter_swap(__i, __j);
  1.1802 +      reverse(__ii, __last);
  1.1803 +      return true;
  1.1804 +    }
  1.1805 +    if (__i == __first) {
  1.1806 +      reverse(__first, __last);
  1.1807 +      return false;
  1.1808 +    }
  1.1809 +  }
  1.1810 +#if defined(_STLP_NEED_UNREACHABLE_RETURN)
  1.1811 +    return 0;
  1.1812 +#endif
  1.1813 +}
  1.1814 +
  1.1815 +template <class _BidirectionalIter>
  1.1816 +bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  1.1817 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1818 +  return __next_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1.1819 +}
  1.1820 +
  1.1821 +template <class _BidirectionalIter, class _Compare>
  1.1822 +bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1.1823 +                      _Compare __comp) {
  1.1824 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1825 +  return __next_permutation(__first, __last, __comp);
  1.1826 +}
  1.1827 +
  1.1828 +template <class _BidirectionalIter, class _Compare>
  1.1829 +bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1.1830 +                      _Compare __comp) {
  1.1831 +  if (__first == __last)
  1.1832 +    return false;
  1.1833 +  _BidirectionalIter __i = __first;
  1.1834 +  ++__i;
  1.1835 +  if (__i == __last)
  1.1836 +    return false;
  1.1837 +  __i = __last;
  1.1838 +  --__i;
  1.1839 +
  1.1840 +  for(;;) {
  1.1841 +    _BidirectionalIter __ii = __i;
  1.1842 +    --__i;
  1.1843 +    if (__comp(*__ii, *__i)) {
  1.1844 +      _BidirectionalIter __j = __last;
  1.1845 +      while (!__comp(*--__j, *__i))
  1.1846 +        {}
  1.1847 +      iter_swap(__i, __j);
  1.1848 +      reverse(__ii, __last);
  1.1849 +      return true;
  1.1850 +    }
  1.1851 +    if (__i == __first) {
  1.1852 +      reverse(__first, __last);
  1.1853 +      return false;
  1.1854 +    }
  1.1855 +  }
  1.1856 +#if defined(_STLP_NEED_UNREACHABLE_RETURN)
  1.1857 +    return 0;
  1.1858 +#endif
  1.1859 +}
  1.1860 +
  1.1861 +template <class _BidirectionalIter>
  1.1862 +bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  1.1863 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1864 +  return __prev_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1.1865 +}
  1.1866 +
  1.1867 +template <class _BidirectionalIter, class _Compare>
  1.1868 +bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1.1869 +                      _Compare __comp) {
  1.1870 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1871 +  return __prev_permutation(__first, __last, __comp);
  1.1872 +}
  1.1873 +
  1.1874 +# ifndef _STLP_NO_EXTENSIONS
  1.1875 +
  1.1876 +// is_heap, a predicate testing whether or not a range is
  1.1877 +// a heap.  This function is an extension, not part of the C++
  1.1878 +// standard.
  1.1879 +
  1.1880 +
  1.1881 +template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
  1.1882 +bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
  1.1883 +               _Distance __n)
  1.1884 +{
  1.1885 +  _Distance __parent = 0;
  1.1886 +  for (_Distance __child = 1; __child < __n; ++__child) {
  1.1887 +    if (__comp(__first[__parent], __first[__child]))
  1.1888 +      return false;
  1.1889 +    if ((__child & 1) == 0)
  1.1890 +      ++__parent;
  1.1891 +  }
  1.1892 +  return true;
  1.1893 +}
  1.1894 +
  1.1895 +template <class _RandomAccessIter>
  1.1896 +bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
  1.1897 +{
  1.1898 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1899 +  return __is_heap(__first, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
  1.1900 +}
  1.1901 +
  1.1902 +template <class _RandomAccessIter, class _StrictWeakOrdering>
  1.1903 +bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
  1.1904 +	     _StrictWeakOrdering __comp)
  1.1905 +{
  1.1906 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1907 +  return __is_heap(__first, __comp, __last - __first);
  1.1908 +}
  1.1909 +
  1.1910 +
  1.1911 +template <class _ForwardIter, class _StrictWeakOrdering>
  1.1912 +bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
  1.1913 +                 _StrictWeakOrdering __comp)
  1.1914 +{
  1.1915 +  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1.1916 +  if (__first == __last)
  1.1917 +    return true;
  1.1918 +
  1.1919 +  _ForwardIter __next = __first;
  1.1920 +  for (++__next; __next != __last; __first = __next, ++__next) {
  1.1921 +    if (__comp(*__next, *__first))
  1.1922 +      return false;
  1.1923 +  }
  1.1924 +
  1.1925 +  return true;
  1.1926 +}
  1.1927 +
  1.1928 +# endif /* _STLP_NO_EXTENSIONS */
  1.1929 +
  1.1930 +_STLP_END_NAMESPACE
  1.1931 +
  1.1932 +# undef __stl_threshold
  1.1933 +
  1.1934 +#endif /* _STLP_ALGO_C */
  1.1935 +// Local Variables:
  1.1936 +// mode:C++
  1.1937 +// End: