1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/stlportv5/stl/_algo.h Wed Mar 31 12:27:01 2010 +0100
1.3 @@ -0,0 +1,740 @@
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 +/* NOTE: This is an internal header file, included by other STL headers.
1.30 + * You should not attempt to use it directly.
1.31 + */
1.32 +
1.33 +#ifndef _STLP_INTERNAL_ALGO_H
1.34 +#define _STLP_INTERNAL_ALGO_H
1.35 +
1.36 +# ifndef _STLP_INTERNAL_ALGOBASE_H
1.37 +# include <stl/_algobase.h>
1.38 +# endif
1.39 +
1.40 +# ifndef _STLP_INTERNAL_TEMPBUF_H
1.41 +# include <stl/_tempbuf.h>
1.42 +# endif
1.43 +
1.44 +# ifndef _STLP_INTERNAL_HEAP_H
1.45 +# include <stl/_heap.h>
1.46 +# endif
1.47 +
1.48 +# ifndef _STLP_INTERNAL_ITERATOR_H
1.49 +# include <stl/_iterator.h>
1.50 +# endif
1.51 +
1.52 +# ifndef _STLP_INTERNAL_FUNCTION_BASE_H
1.53 +# include <stl/_function_base.h>
1.54 +# endif
1.55 +
1.56 +# ifdef __SUNPRO_CC
1.57 +// remove() conflict
1.58 +# include <cstdio>
1.59 +# endif
1.60 +
1.61 +_STLP_BEGIN_NAMESPACE
1.62 +
1.63 +// for_each. Apply a function to every element of a range.
1.64 +template <class _InputIter, class _Function>
1.65 +_STLP_INLINE_LOOP _Function
1.66 +for_each(_InputIter __first, _InputIter __last, _Function __f) {
1.67 + for ( ; __first != __last; ++__first)
1.68 + __f(*__first);
1.69 + return __f;
1.70 +}
1.71 +
1.72 +// count_if
1.73 +template <class _InputIter, class _Predicate>
1.74 +_STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter)
1.75 +count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
1.76 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.77 +_STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;
1.78 + for ( ; __first != __last; ++__first)
1.79 + if (__pred(*__first))
1.80 + ++__n;
1.81 + return __n;
1.82 +}
1.83 +
1.84 +// adjacent_find.
1.85 +
1.86 +template <class _ForwardIter, class _BinaryPredicate>
1.87 +_STLP_INLINE_LOOP _ForwardIter
1.88 +adjacent_find(_ForwardIter __first, _ForwardIter __last,
1.89 + _BinaryPredicate __binary_pred) {
1.90 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.91 + if (__first == __last)
1.92 + return __last;
1.93 + _ForwardIter __next = __first;
1.94 + while(++__next != __last) {
1.95 + if (__binary_pred(*__first, *__next))
1.96 + return __first;
1.97 + __first = __next;
1.98 + }
1.99 + return __last;
1.100 +}
1.101 +
1.102 +template <class _ForwardIter>
1.103 +_STLP_INLINE_LOOP _ForwardIter
1.104 +adjacent_find(_ForwardIter __first, _ForwardIter __last) {
1.105 + return adjacent_find(__first, __last,
1.106 + __equal_to(_STLP_VALUE_TYPE(__first, _ForwardIter)));
1.107 +}
1.108 +
1.109 +# ifndef _STLP_NO_ANACHRONISMS
1.110 +template <class _InputIter, class _Tp, class _Size>
1.111 +_STLP_INLINE_LOOP void
1.112 +count(_InputIter __first, _InputIter __last, const _Tp& __val, _Size& __n) {
1.113 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.114 + for ( ; __first != __last; ++__first)
1.115 + if (*__first == __val)
1.116 + ++__n;
1.117 +}
1.118 +
1.119 +template <class _InputIter, class _Predicate, class _Size>
1.120 +_STLP_INLINE_LOOP void
1.121 +count_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) {
1.122 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.123 + for ( ; __first != __last; ++__first)
1.124 + if (__pred(*__first))
1.125 + ++__n;
1.126 +}
1.127 +# endif
1.128 +
1.129 +template <class _ForwardIter1, class _ForwardIter2>
1.130 +_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.131 + _ForwardIter2 __first2, _ForwardIter2 __last2);
1.132 +
1.133 +// search_n. Search for __count consecutive copies of __val.
1.134 +template <class _ForwardIter, class _Integer, class _Tp>
1.135 +_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
1.136 + _Integer __count, const _Tp& __val);
1.137 +template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
1.138 +_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
1.139 + _Integer __count, const _Tp& __val, _BinaryPred __binary_pred);
1.140 +
1.141 +template <class _InputIter, class _ForwardIter>
1.142 +inline _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
1.143 + _ForwardIter __first2, _ForwardIter __last2) {
1.144 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.145 + _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.146 + return __find_first_of(__first1, __last1, __first2, __last2,__equal_to(_STLP_VALUE_TYPE(__first1, _InputIter)));
1.147 +}
1.148 +
1.149 +template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
1.150 +inline _InputIter
1.151 +find_first_of(_InputIter __first1, _InputIter __last1,
1.152 + _ForwardIter __first2, _ForwardIter __last2,_BinaryPredicate __comp) {
1.153 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.154 + _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.155 + return __find_first_of(__first1, __last1, __first2, __last2,__comp);
1.156 +}
1.157 +
1.158 +template <class _ForwardIter1, class _ForwardIter2>
1.159 +_ForwardIter1
1.160 +find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.161 + _ForwardIter2 __first2, _ForwardIter2 __last2);
1.162 +
1.163 +// swap_ranges
1.164 +template <class _ForwardIter1, class _ForwardIter2>
1.165 +_STLP_INLINE_LOOP _ForwardIter2
1.166 +swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2) {
1.167 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.168 + for ( ; __first1 != __last1; ++__first1, ++__first2)
1.169 + iter_swap(__first1, __first2);
1.170 + return __first2;
1.171 +}
1.172 +
1.173 +// transform
1.174 +template <class _InputIter, class _OutputIter, class _UnaryOperation>
1.175 +_STLP_INLINE_LOOP _OutputIter
1.176 +transform(_InputIter __first, _InputIter __last, _OutputIter __result, _UnaryOperation __opr) {
1.177 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.178 + for ( ; __first != __last; ++__first, ++__result)
1.179 + *__result = __opr(*__first);
1.180 + return __result;
1.181 +}
1.182 +template <class _InputIter1, class _InputIter2, class _OutputIter, class _BinaryOperation>
1.183 +_STLP_INLINE_LOOP _OutputIter
1.184 +transform(_InputIter1 __first1, _InputIter1 __last1,
1.185 + _InputIter2 __first2, _OutputIter __result,_BinaryOperation __binary_op) {
1.186 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.187 + for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
1.188 + *__result = __binary_op(*__first1, *__first2);
1.189 + return __result;
1.190 +}
1.191 +
1.192 +// replace_if, replace_copy, replace_copy_if
1.193 +
1.194 +template <class _ForwardIter, class _Predicate, class _Tp>
1.195 +_STLP_INLINE_LOOP void
1.196 +replace_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const _Tp& __new_value) {
1.197 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.198 + for ( ; __first != __last; ++__first)
1.199 + if (__pred(*__first))
1.200 + *__first = __new_value;
1.201 +}
1.202 +
1.203 +template <class _InputIter, class _OutputIter, class _Tp>
1.204 +_STLP_INLINE_LOOP _OutputIter
1.205 +replace_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
1.206 + const _Tp& __old_value, const _Tp& __new_value) {
1.207 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.208 + for ( ; __first != __last; ++__first, ++__result)
1.209 + *__result = *__first == __old_value ? __new_value : *__first;
1.210 + return __result;
1.211 +}
1.212 +
1.213 +template <class _Iterator, class _OutputIter, class _Predicate, class _Tp>
1.214 +_STLP_INLINE_LOOP _OutputIter
1.215 +replace_copy_if(_Iterator __first, _Iterator __last,
1.216 + _OutputIter __result,
1.217 + _Predicate __pred, const _Tp& __new_value) {
1.218 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.219 + for ( ; __first != __last; ++__first, ++__result)
1.220 + *__result = __pred(*__first) ? __new_value : *__first;
1.221 + return __result;
1.222 +}
1.223 +
1.224 +// generate and generate_n
1.225 +
1.226 +template <class _ForwardIter, class _Generator>
1.227 +_STLP_INLINE_LOOP void
1.228 +generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
1.229 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.230 + for ( ; __first != __last; ++__first)
1.231 + *__first = __gen();
1.232 +}
1.233 +
1.234 +template <class _OutputIter, class _Size, class _Generator>
1.235 +_STLP_INLINE_LOOP _OutputIter
1.236 +generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
1.237 + for ( ; __n > 0; --__n, ++__first)
1.238 + *__first = __gen();
1.239 + return __first;
1.240 +}
1.241 +
1.242 +// remove, remove_if, remove_copy, remove_copy_if
1.243 +
1.244 +template <class _InputIter, class _OutputIter, class _Tp>
1.245 +_STLP_INLINE_LOOP _OutputIter
1.246 +remove_copy(_InputIter __first, _InputIter __last,_OutputIter __result, const _Tp& __val) {
1.247 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.248 + for ( ; __first != __last; ++__first)
1.249 + if (!(*__first == __val)) {
1.250 + *__result = *__first;
1.251 + ++__result;
1.252 + }
1.253 + return __result;
1.254 +}
1.255 +
1.256 +template <class _InputIter, class _OutputIter, class _Predicate>
1.257 +_STLP_INLINE_LOOP _OutputIter
1.258 +remove_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred) {
1.259 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.260 + for ( ; __first != __last; ++__first)
1.261 + if (!__pred(*__first)) {
1.262 + *__result = *__first;
1.263 + ++__result;
1.264 + }
1.265 + return __result;
1.266 +}
1.267 +
1.268 +template <class _ForwardIter, class _Tp>
1.269 +_STLP_INLINE_LOOP _ForwardIter
1.270 +remove(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
1.271 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.272 + __first = find(__first, __last, __val);
1.273 + if (__first == __last)
1.274 + return __first;
1.275 + else {
1.276 + _ForwardIter __next = __first;
1.277 + return remove_copy(++__next, __last, __first, __val);
1.278 + }
1.279 +}
1.280 +
1.281 +template <class _ForwardIter, class _Predicate>
1.282 +_STLP_INLINE_LOOP _ForwardIter
1.283 +remove_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
1.284 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.285 + __first = find_if(__first, __last, __pred);
1.286 + if ( __first == __last )
1.287 + return __first;
1.288 + else {
1.289 + _ForwardIter __next = __first;
1.290 + return remove_copy_if(++__next, __last, __first, __pred);
1.291 + }
1.292 +}
1.293 +
1.294 +// unique and unique_copy
1.295 +template <class _InputIter, class _OutputIter>
1.296 +_OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result);
1.297 +
1.298 +template <class _InputIter, class _OutputIter, class _BinaryPredicate>
1.299 +_OutputIter unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
1.300 + _BinaryPredicate __binary_pred);
1.301 +
1.302 +template <class _ForwardIter>
1.303 +inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
1.304 + __first = adjacent_find(__first, __last);
1.305 + return unique_copy(__first, __last, __first);
1.306 +}
1.307 +
1.308 +template <class _ForwardIter, class _BinaryPredicate>
1.309 +inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
1.310 + _BinaryPredicate __binary_pred) {
1.311 + __first = adjacent_find(__first, __last, __binary_pred);
1.312 + return unique_copy(__first, __last, __first, __binary_pred);
1.313 +}
1.314 +
1.315 +// reverse and reverse_copy, and their auxiliary functions
1.316 +
1.317 +template <class _BidirectionalIter>
1.318 +_STLP_INLINE_LOOP void
1.319 +__reverse(_BidirectionalIter __first, _BidirectionalIter __last, const bidirectional_iterator_tag &) {
1.320 + for(; __first != __last && __first != --__last; ++__first)
1.321 + iter_swap(__first,__last);
1.322 +}
1.323 +
1.324 +
1.325 +template <class _RandomAccessIter>
1.326 +_STLP_INLINE_LOOP void
1.327 +__reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) {
1.328 + for (; __first < __last; ++__first) iter_swap(__first, --__last);
1.329 +}
1.330 +
1.331 +template <class _BidirectionalIter>
1.332 +inline void
1.333 +reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
1.334 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.335 + __reverse(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _BidirectionalIter));
1.336 +}
1.337 +
1.338 +template <class _BidirectionalIter, class _OutputIter>
1.339 +_STLP_INLINE_LOOP
1.340 +_OutputIter reverse_copy(_BidirectionalIter __first,
1.341 + _BidirectionalIter __last,
1.342 + _OutputIter __result) {
1.343 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.344 + while (__first != __last) {
1.345 + --__last;
1.346 + *__result = *__last;
1.347 + ++__result;
1.348 + }
1.349 + return __result;
1.350 +}
1.351 +
1.352 +// rotate and rotate_copy, and their auxiliary functions
1.353 +
1.354 +template <class _EuclideanRingElement>
1.355 +_STLP_INLINE_LOOP
1.356 +_EuclideanRingElement __gcd(_EuclideanRingElement __m,
1.357 + _EuclideanRingElement __n)
1.358 +{
1.359 + while (__n != 0) {
1.360 + _EuclideanRingElement __t = __m % __n;
1.361 + __m = __n;
1.362 + __n = __t;
1.363 + }
1.364 + return __m;
1.365 +}
1.366 +
1.367 +template <class _ForwardIter>
1.368 +_ForwardIter
1.369 +rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last);
1.370 +
1.371 +template <class _ForwardIter, class _OutputIter>
1.372 +inline _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
1.373 + _ForwardIter __last, _OutputIter __result) {
1.374 + return copy(__first, __middle, copy(__middle, __last, __result));
1.375 +}
1.376 +
1.377 +// random_shuffle
1.378 +
1.379 +template <class _RandomAccessIter>
1.380 +void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last);
1.381 +
1.382 +template <class _RandomAccessIter, class _RandomNumberGenerator>
1.383 +void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
1.384 + _RandomNumberGenerator& __rand);
1.385 +
1.386 +# ifndef _STLP_NO_EXTENSIONS
1.387 +// random_sample and random_sample_n (extensions, not part of the standard).
1.388 +
1.389 +template <class _ForwardIter, class _OutputIter, class _Distance>
1.390 +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
1.391 + _OutputIter __stl_out, const _Distance __n);
1.392 +
1.393 +template <class _ForwardIter, class _OutputIter, class _Distance,
1.394 + class _RandomNumberGenerator>
1.395 +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
1.396 + _OutputIter __stl_out, const _Distance __n,
1.397 + _RandomNumberGenerator& __rand);
1.398 +
1.399 +template <class _InputIter, class _RandomAccessIter>
1.400 +_RandomAccessIter
1.401 +random_sample(_InputIter __first, _InputIter __last,
1.402 + _RandomAccessIter __out_first, _RandomAccessIter __out_last);
1.403 +
1.404 +template <class _InputIter, class _RandomAccessIter,
1.405 + class _RandomNumberGenerator>
1.406 +_RandomAccessIter
1.407 +random_sample(_InputIter __first, _InputIter __last,
1.408 + _RandomAccessIter __out_first, _RandomAccessIter __out_last,
1.409 + _RandomNumberGenerator& __rand);
1.410 +
1.411 +# endif /* _STLP_NO_EXTENSIONS */
1.412 +
1.413 +// partition, stable_partition, and their auxiliary functions
1.414 +
1.415 +template <class _ForwardIter, class _Predicate>
1.416 +_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred);
1.417 +
1.418 +
1.419 +template <class _ForwardIter, class _Predicate>
1.420 +_ForwardIter
1.421 +stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred);
1.422 +
1.423 +// sort() and its auxiliary functions.
1.424 +
1.425 +template <class _Size>
1.426 +inline _Size __lg(_Size __n) {
1.427 + _Size __k;
1.428 + for (__k = 0; __n != 1; __n >>= 1) ++__k;
1.429 + return __k;
1.430 +}
1.431 +
1.432 +template <class _RandomAccessIter>
1.433 +void sort(_RandomAccessIter __first, _RandomAccessIter __last);
1.434 +template <class _RandomAccessIter, class _Compare>
1.435 +void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp);
1.436 +
1.437 +// stable_sort() and its auxiliary functions.
1.438 +template <class _RandomAccessIter>
1.439 +void stable_sort(_RandomAccessIter __first,
1.440 + _RandomAccessIter __last);
1.441 +
1.442 +template <class _RandomAccessIter, class _Compare>
1.443 +void stable_sort(_RandomAccessIter __first,
1.444 + _RandomAccessIter __last, _Compare __comp);
1.445 +
1.446 +// partial_sort, partial_sort_copy, and auxiliary functions.
1.447 +
1.448 +template <class _RandomAccessIter>
1.449 +void
1.450 +partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last);
1.451 +
1.452 +template <class _RandomAccessIter, class _Compare>
1.453 +void
1.454 +partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
1.455 + _RandomAccessIter __last, _Compare __comp);
1.456 +
1.457 +template <class _InputIter, class _RandomAccessIter>
1.458 +_RandomAccessIter
1.459 +partial_sort_copy(_InputIter __first, _InputIter __last,
1.460 + _RandomAccessIter __result_first, _RandomAccessIter __result_last);
1.461 +
1.462 +template <class _InputIter, class _RandomAccessIter, class _Compare>
1.463 +_RandomAccessIter
1.464 +partial_sort_copy(_InputIter __first, _InputIter __last,
1.465 + _RandomAccessIter __result_first,
1.466 + _RandomAccessIter __result_last, _Compare __comp);
1.467 +
1.468 +// nth_element() and its auxiliary functions.
1.469 +
1.470 +template <class _RandomAccessIter>
1.471 +void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1.472 + _RandomAccessIter __last);
1.473 +
1.474 +template <class _RandomAccessIter, class _Compare>
1.475 +void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1.476 + _RandomAccessIter __last, _Compare __comp);
1.477 +
1.478 +// auxiliary class for lower_bound, etc.
1.479 +template <class _T1, class _T2>
1.480 +struct __less_2 {
1.481 + bool operator() (const _T1& __x, const _T2 __y) const { return __x < __y ; }
1.482 +};
1.483 +
1.484 +template <class _T1, class _T2>
1.485 +__less_2<_T1,_T2> __less2(_T1*, _T2* ) { return __less_2<_T1, _T2>(); }
1.486 +
1.487 +#ifdef _STLP_FUNCTION_PARTIAL_ORDER
1.488 +template <class _Tp>
1.489 +less<_Tp> __less2(_Tp*, _Tp* ) { return less<_Tp>(); }
1.490 +#endif
1.491 +
1.492 +// Binary search (lower_bound, upper_bound, equal_range, binary_search).
1.493 +
1.494 +template <class _ForwardIter, class _Tp>
1.495 +inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
1.496 + const _Tp& __val) {
1.497 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.498 + return __lower_bound(__first, __last, __val,
1.499 + __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),
1.500 + _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.501 +}
1.502 +
1.503 +template <class _ForwardIter, class _Tp, class _Compare>
1.504 +inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
1.505 + const _Tp& __val, _Compare __comp) {
1.506 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.507 + return __lower_bound(__first, __last, __val, __comp, _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.508 +}
1.509 +
1.510 +template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1.511 +_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
1.512 + const _Tp& __val, _Compare __comp, _Distance*);
1.513 +
1.514 +template <class _ForwardIter, class _Tp>
1.515 +inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
1.516 + const _Tp& __val) {
1.517 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.518 + return __upper_bound(__first, __last, __val,
1.519 + __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),
1.520 + _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.521 +}
1.522 +
1.523 +template <class _ForwardIter, class _Tp, class _Compare>
1.524 +inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
1.525 + const _Tp& __val, _Compare __comp) {
1.526 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.527 + return __upper_bound(__first, __last, __val, __comp,
1.528 + _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.529 +}
1.530 +
1.531 +template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1.532 +pair<_ForwardIter, _ForwardIter>
1.533 +__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1.534 + _Compare __comp, _Distance*);
1.535 +
1.536 +template <class _ForwardIter, class _Tp>
1.537 +inline pair<_ForwardIter, _ForwardIter>
1.538 +equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
1.539 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.540 + return __equal_range(__first, __last, __val,
1.541 + __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),
1.542 + _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.543 +}
1.544 +
1.545 +template <class _ForwardIter, class _Tp, class _Compare>
1.546 +inline pair<_ForwardIter, _ForwardIter>
1.547 +equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1.548 + _Compare __comp) {
1.549 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.550 + return __equal_range(__first, __last, __val, __comp,
1.551 + _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.552 +}
1.553 +
1.554 +template <class _ForwardIter, class _Tp>
1.555 +inline bool binary_search(_ForwardIter __first, _ForwardIter __last,
1.556 + const _Tp& __val) {
1.557 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.558 + _ForwardIter __i = __lower_bound(__first, __last, __val,
1.559 + __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),
1.560 + _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.561 + return __i != __last && !(__val < *__i);
1.562 +}
1.563 +
1.564 +template <class _ForwardIter, class _Tp, class _Compare>
1.565 +inline bool binary_search(_ForwardIter __first, _ForwardIter __last,
1.566 + const _Tp& __val,
1.567 + _Compare __comp) {
1.568 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.569 + _ForwardIter __i = __lower_bound(__first, __last, __val, __comp, _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.570 + return __i != __last && !__comp(__val, *__i);
1.571 +}
1.572 +
1.573 +// merge, with and without an explicitly supplied comparison function.
1.574 +
1.575 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.576 +_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1.577 + _InputIter2 __first2, _InputIter2 __last2,
1.578 + _OutputIter __result);
1.579 +
1.580 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.581 + class _Compare>
1.582 +_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1.583 + _InputIter2 __first2, _InputIter2 __last2,
1.584 + _OutputIter __result, _Compare __comp);
1.585 +
1.586 +
1.587 +// inplace_merge and its auxiliary functions.
1.588 +
1.589 +
1.590 +template <class _BidirectionalIter>
1.591 +void inplace_merge(_BidirectionalIter __first,
1.592 + _BidirectionalIter __middle,
1.593 + _BidirectionalIter __last) ;
1.594 +
1.595 +template <class _BidirectionalIter, class _Compare>
1.596 +void inplace_merge(_BidirectionalIter __first,
1.597 + _BidirectionalIter __middle,
1.598 + _BidirectionalIter __last, _Compare __comp);
1.599 +
1.600 +// Set algorithms: includes, set_union, set_intersection, set_difference,
1.601 +// set_symmetric_difference. All of these algorithms have the precondition
1.602 +// that their input ranges are sorted and the postcondition that their output
1.603 +// ranges are sorted.
1.604 +
1.605 +template <class _InputIter1, class _InputIter2>
1.606 +bool includes(_InputIter1 __first1, _InputIter1 __last1,
1.607 + _InputIter2 __first2, _InputIter2 __last2);
1.608 +
1.609 +template <class _InputIter1, class _InputIter2, class _Compare>
1.610 +bool includes(_InputIter1 __first1, _InputIter1 __last1,
1.611 + _InputIter2 __first2, _InputIter2 __last2, _Compare __comp);
1.612 +
1.613 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.614 +_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
1.615 + _InputIter2 __first2, _InputIter2 __last2,
1.616 + _OutputIter __result);
1.617 +
1.618 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.619 + class _Compare>
1.620 +_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
1.621 + _InputIter2 __first2, _InputIter2 __last2,
1.622 + _OutputIter __result, _Compare __comp);
1.623 +
1.624 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.625 +_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1.626 + _InputIter2 __first2, _InputIter2 __last2,
1.627 + _OutputIter __result);
1.628 +
1.629 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.630 + class _Compare>
1.631 +_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1.632 + _InputIter2 __first2, _InputIter2 __last2,
1.633 + _OutputIter __result, _Compare __comp);
1.634 +
1.635 +
1.636 +
1.637 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.638 +_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
1.639 + _InputIter2 __first2, _InputIter2 __last2,
1.640 + _OutputIter __result);
1.641 +
1.642 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.643 + class _Compare>
1.644 +_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
1.645 + _InputIter2 __first2, _InputIter2 __last2,
1.646 + _OutputIter __result, _Compare __comp);
1.647 +
1.648 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.649 +_OutputIter
1.650 +set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1.651 + _InputIter2 __first2, _InputIter2 __last2,
1.652 + _OutputIter __result);
1.653 +
1.654 +
1.655 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.656 + class _Compare>
1.657 +_OutputIter
1.658 +set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1.659 + _InputIter2 __first2, _InputIter2 __last2,
1.660 + _OutputIter __result,
1.661 + _Compare __comp);
1.662 +
1.663 +
1.664 +// min_element and max_element, with and without an explicitly supplied
1.665 +// comparison function.
1.666 +
1.667 +template <class _ForwardIter>
1.668 +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last);
1.669 +template <class _ForwardIter, class _Compare>
1.670 +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
1.671 + _Compare __comp);
1.672 +
1.673 +template <class _ForwardIter>
1.674 +_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last);
1.675 +
1.676 +template <class _ForwardIter, class _Compare>
1.677 +_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
1.678 + _Compare __comp);
1.679 +
1.680 +// next_permutation and prev_permutation, with and without an explicitly
1.681 +// supplied comparison function.
1.682 +
1.683 +template <class _BidirectionalIter>
1.684 +bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last);
1.685 +
1.686 +template <class _BidirectionalIter, class _Compare>
1.687 +bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.688 + _Compare __comp);
1.689 +
1.690 +
1.691 +template <class _BidirectionalIter>
1.692 +bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last);
1.693 +
1.694 +
1.695 +template <class _BidirectionalIter, class _Compare>
1.696 +bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.697 + _Compare __comp);
1.698 +
1.699 +# ifndef _STLP_NO_EXTENSIONS
1.700 +
1.701 +// is_heap, a predicate testing whether or not a range is
1.702 +// a heap. This function is an extension, not part of the C++
1.703 +// standard.
1.704 +
1.705 +template <class _RandomAccessIter>
1.706 +bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last);
1.707 +
1.708 +template <class _RandomAccessIter, class _StrictWeakOrdering>
1.709 +bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
1.710 + _StrictWeakOrdering __comp);
1.711 +
1.712 +
1.713 +// is_sorted, a predicated testing whether a range is sorted in
1.714 +// nondescending order. This is an extension, not part of the C++
1.715 +// standard.
1.716 +template <class _ForwardIter, class _StrictWeakOrdering>
1.717 +bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
1.718 + _StrictWeakOrdering __comp);
1.719 +
1.720 +template <class _ForwardIter>
1.721 +inline bool is_sorted(_ForwardIter __first, _ForwardIter __last) {
1.722 + return __is_sorted(__first, __last, __less(_STLP_VALUE_TYPE(__first, _ForwardIter)));
1.723 +}
1.724 +
1.725 +template <class _ForwardIter, class _StrictWeakOrdering>
1.726 +inline bool is_sorted(_ForwardIter __first, _ForwardIter __last,
1.727 + _StrictWeakOrdering __comp) {
1.728 + return __is_sorted(__first, __last, __comp);
1.729 +}
1.730 +# endif
1.731 +
1.732 +_STLP_END_NAMESPACE
1.733 +
1.734 +# if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.735 +# include <stl/_algo.c>
1.736 +# endif
1.737 +
1.738 +#endif /* _STLP_INTERNAL_ALGO_H */
1.739 +
1.740 +// Local Variables:
1.741 +// mode:C++
1.742 +// End:
1.743 +