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