1.1 --- a/epoc32/include/stdapis/stlport/stl/_algo.h Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,740 +0,0 @@
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 -