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