1.1 --- a/epoc32/include/stdapis/stlport/stl/_algobase.c Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,392 +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 -#ifndef _STLP_ALGOBASE_C
1.29 -#define _STLP_ALGOBASE_C
1.30 -
1.31 -# if !defined (_STLP_INTERNAL_ALGOBASE_H)
1.32 -# include <stl/_algobase.h>
1.33 -# endif
1.34 -
1.35 -_STLP_BEGIN_NAMESPACE
1.36 -
1.37 -template <class _InputIter1, class _InputIter2>
1.38 -bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
1.39 - _InputIter2 __first2, _InputIter2 __last2) {
1.40 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.41 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.42 - for ( ; __first1 != __last1 && __first2 != __last2
1.43 - ; ++__first1, ++__first2) {
1.44 - if (*__first1 < *__first2)
1.45 - return true;
1.46 - if (*__first2 < *__first1)
1.47 - return false;
1.48 - }
1.49 - return __first1 == __last1 && __first2 != __last2;
1.50 -}
1.51 -
1.52 -template <class _InputIter1, class _InputIter2, class _Compare>
1.53 -bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
1.54 - _InputIter2 __first2, _InputIter2 __last2,
1.55 - _Compare __comp) {
1.56 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.57 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.58 - for ( ; __first1 != __last1 && __first2 != __last2
1.59 - ; ++__first1, ++__first2) {
1.60 - if (__comp(*__first1, *__first2))
1.61 - return true;
1.62 - if (__comp(*__first2, *__first1))
1.63 - return false;
1.64 - }
1.65 - return __first1 == __last1 && __first2 != __last2;
1.66 -}
1.67 -
1.68 -# ifndef _STLP_NO_EXTENSIONS
1.69 -
1.70 -template <class _InputIter1, class _InputIter2>
1.71 -int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
1.72 - _InputIter2 __first2, _InputIter2 __last2)
1.73 -{
1.74 - while (__first1 != __last1 && __first2 != __last2) {
1.75 - if (*__first1 < *__first2)
1.76 - return -1;
1.77 - if (*__first2 < *__first1)
1.78 - return 1;
1.79 - ++__first1;
1.80 - ++__first2;
1.81 - }
1.82 - if (__first2 == __last2) {
1.83 - return !(__first1 == __last1);
1.84 - }
1.85 - else {
1.86 - return -1;
1.87 - }
1.88 -}
1.89 -
1.90 -
1.91 -template <class _InputIter1, class _InputIter2>
1.92 -int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
1.93 - _InputIter2 __first2, _InputIter2 __last2)
1.94 -{
1.95 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.96 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.97 - return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
1.98 -}
1.99 -# endif
1.100 -
1.101 -template <class _RandomAccessIter, class _Tp>
1.102 -_STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
1.103 - const _Tp& __val,
1.104 - const random_access_iterator_tag &)
1.105 -{
1.106 - _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
1.107 -
1.108 - for ( ; __trip_count > 0 ; --__trip_count) {
1.109 - if (*__first == __val) return __first;
1.110 - ++__first;
1.111 -
1.112 - if (*__first == __val) return __first;
1.113 - ++__first;
1.114 -
1.115 - if (*__first == __val) return __first;
1.116 - ++__first;
1.117 -
1.118 - if (*__first == __val) return __first;
1.119 - ++__first;
1.120 - }
1.121 -
1.122 - switch(__last - __first) {
1.123 - case 3:
1.124 - if (*__first == __val) return __first;
1.125 - ++__first;
1.126 - case 2:
1.127 - if (*__first == __val) return __first;
1.128 - ++__first;
1.129 - case 1:
1.130 - if (*__first == __val) return __first;
1.131 - ++__first;
1.132 - case 0:
1.133 - default:
1.134 - return __last;
1.135 - }
1.136 -}
1.137 -
1.138 -template <class _RandomAccessIter, class _Predicate>
1.139 -_STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
1.140 - _Predicate __pred,
1.141 - const random_access_iterator_tag &)
1.142 -{
1.143 - _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
1.144 -
1.145 - for ( ; __trip_count > 0 ; --__trip_count) {
1.146 - if (__pred(*__first)) return __first;
1.147 - ++__first;
1.148 -
1.149 - if (__pred(*__first)) return __first;
1.150 - ++__first;
1.151 -
1.152 - if (__pred(*__first)) return __first;
1.153 - ++__first;
1.154 -
1.155 - if (__pred(*__first)) return __first;
1.156 - ++__first;
1.157 - }
1.158 -
1.159 - switch(__last - __first) {
1.160 - case 3:
1.161 - if (__pred(*__first)) return __first;
1.162 - ++__first;
1.163 - case 2:
1.164 - if (__pred(*__first)) return __first;
1.165 - ++__first;
1.166 - case 1:
1.167 - if (__pred(*__first)) return __first;
1.168 - // ++__first;
1.169 - case 0:
1.170 - default:
1.171 - return __last;
1.172 - }
1.173 -}
1.174 -
1.175 -template <class _InputIter, class _Tp>
1.176 -inline _InputIter __find(_InputIter __first, _InputIter __last,
1.177 - const _Tp& __val,
1.178 - const input_iterator_tag &)
1.179 -{
1.180 - while (__first != __last && !(*__first == __val))
1.181 - ++__first;
1.182 - return __first;
1.183 -}
1.184 -
1.185 -template <class _InputIter, class _Predicate>
1.186 -inline _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
1.187 - _Predicate __pred,
1.188 - const input_iterator_tag &)
1.189 -{
1.190 - while (__first != __last && !__pred(*__first))
1.191 - ++__first;
1.192 - return __first;
1.193 -}
1.194 -
1.195 -template <class _InputIter, class _Predicate>
1.196 -_InputIter find_if(_InputIter __first, _InputIter __last,
1.197 - _Predicate __pred) {
1.198 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.199 - return __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
1.200 -}
1.201 -
1.202 -template <class _InputIter, class _Tp>
1.203 -_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val)
1.204 -{
1.205 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.206 - return __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
1.207 -}
1.208 -
1.209 -template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
1.210 -_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.211 - _ForwardIter2 __first2, _ForwardIter2 __last2,
1.212 - _BinaryPred __predicate)
1.213 -{
1.214 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.215 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.216 - // Test for empty ranges
1.217 - if (__first1 == __last1 || __first2 == __last2)
1.218 - return __first1;
1.219 -
1.220 - // Test for a pattern of length 1.
1.221 - _ForwardIter2 __tmp(__first2);
1.222 - ++__tmp;
1.223 - if (__tmp == __last2) {
1.224 - while (__first1 != __last1 && !__predicate(*__first1, *__first2))
1.225 - ++__first1;
1.226 - return __first1;
1.227 - }
1.228 -
1.229 - // General case.
1.230 -
1.231 - _ForwardIter2 __p1, __p;
1.232 -
1.233 - __p1 = __first2; ++__p1;
1.234 -
1.235 - // _ForwardIter1 __current = __first1;
1.236 -
1.237 - while (__first1 != __last1) {
1.238 - while (__first1 != __last1) {
1.239 - if (__predicate(*__first1, *__first2))
1.240 - break;
1.241 - ++__first1;
1.242 - }
1.243 - while (__first1 != __last1 && !__predicate(*__first1, *__first2))
1.244 - ++__first1;
1.245 - if (__first1 == __last1)
1.246 - return __last1;
1.247 -
1.248 - __p = __p1;
1.249 - _ForwardIter1 __current = __first1;
1.250 - if (++__current == __last1) return __last1;
1.251 -
1.252 - while (__predicate(*__current, *__p)) {
1.253 - if (++__p == __last2)
1.254 - return __first1;
1.255 - if (++__current == __last1)
1.256 - return __last1;
1.257 - }
1.258 -
1.259 - ++__first1;
1.260 - }
1.261 - return __first1;
1.262 -}
1.263 -
1.264 -// find_first_of, with and without an explicitly supplied comparison function.
1.265 -
1.266 -template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
1.267 -_InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
1.268 - _ForwardIter __first2, _ForwardIter __last2,
1.269 - _BinaryPredicate __comp) {
1.270 - for ( ; __first1 != __last1; ++__first1)
1.271 - for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
1.272 - if (__comp(*__first1, *__iter))
1.273 - return __first1;
1.274 - return __last1;
1.275 -}
1.276 -
1.277 -
1.278 -// find_end, with and without an explicitly supplied comparison function.
1.279 -// Search [first2, last2) as a subsequence in [first1, last1), and return
1.280 -// the *last* possible match. Note that find_end for bidirectional iterators
1.281 -// is much faster than for forward iterators.
1.282 -
1.283 -// find_end for forward iterators.
1.284 -
1.285 -template <class _ForwardIter1, class _ForwardIter2,
1.286 - class _BinaryPredicate>
1.287 -_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.288 - _ForwardIter2 __first2, _ForwardIter2 __last2,
1.289 - const forward_iterator_tag &, const forward_iterator_tag &,
1.290 - _BinaryPredicate __comp)
1.291 -{
1.292 - if (__first2 == __last2)
1.293 - return __last1;
1.294 - else {
1.295 - _ForwardIter1 __result = __last1;
1.296 - while (1) {
1.297 - _ForwardIter1 __new_result
1.298 - = search(__first1, __last1, __first2, __last2, __comp);
1.299 - if (__new_result == __last1)
1.300 - return __result;
1.301 - else {
1.302 - __result = __new_result;
1.303 - __first1 = __new_result;
1.304 - ++__first1;
1.305 - }
1.306 - }
1.307 - }
1.308 -}
1.309 -
1.310 -// find_end for bidirectional iterators. Requires partial specialization.
1.311 -#if defined ( _STLP_CLASS_PARTIAL_SPECIALIZATION )
1.312 -
1.313 -#if ! defined (_STLP_INTERNAL_ITERATOR_H)
1.314 -_STLP_END_NAMESPACE
1.315 -# include <stl/_iterator.h>
1.316 -_STLP_BEGIN_NAMESPACE
1.317 -#endif
1.318 -
1.319 -template <class _BidirectionalIter1, class _BidirectionalIter2,
1.320 - class _BinaryPredicate>
1.321 -_BidirectionalIter1
1.322 -__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
1.323 - _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
1.324 - const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
1.325 - _BinaryPredicate __comp)
1.326 -{
1.327 - typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
1.328 - typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
1.329 -
1.330 - _RevIter1 __rlast1(__first1);
1.331 - _RevIter2 __rlast2(__first2);
1.332 - _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
1.333 - _RevIter2(__last2), __rlast2,
1.334 - __comp);
1.335 -
1.336 - if (__rresult == __rlast1)
1.337 - return __last1;
1.338 - else {
1.339 - _BidirectionalIter1 __result = __rresult.base();
1.340 - advance(__result, -distance(__first2, __last2));
1.341 - return __result;
1.342 - }
1.343 -}
1.344 -#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.345 -
1.346 -template <class _ForwardIter1, class _ForwardIter2,
1.347 - class _BinaryPredicate>
1.348 -_ForwardIter1
1.349 -find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.350 - _ForwardIter2 __first2, _ForwardIter2 __last2,
1.351 - _BinaryPredicate __comp)
1.352 -{
1.353 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.354 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.355 - return __find_end(__first1, __last1, __first2, __last2,
1.356 -# if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.357 - _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
1.358 - _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
1.359 -# else
1.360 - forward_iterator_tag(),
1.361 - forward_iterator_tag(),
1.362 -# endif
1.363 - __comp);
1.364 -}
1.365 -
1.366 -template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1.367 -_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
1.368 - const _Tp& __val, _Compare __comp, _Distance*)
1.369 -{
1.370 - _Distance __len = distance(__first, __last);
1.371 - _Distance __half;
1.372 - _ForwardIter __middle;
1.373 -
1.374 - while (__len > 0) {
1.375 - __half = __len >> 1;
1.376 - __middle = __first;
1.377 - advance(__middle, __half);
1.378 - if (__comp(*__middle, __val)) {
1.379 - __first = __middle;
1.380 - ++__first;
1.381 - __len = __len - __half - 1;
1.382 - }
1.383 - else
1.384 - __len = __half;
1.385 - }
1.386 - return __first;
1.387 -}
1.388 -
1.389 -_STLP_END_NAMESPACE
1.390 -
1.391 -#endif /* _STLP_ALGOBASE_C */
1.392 -
1.393 -// Local Variables:
1.394 -// mode:C++
1.395 -// End: