1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 18 * Permission to use or copy this software for any purpose is hereby granted 19 * without fee, provided the above notices are retained on all copies. 20 * Permission to modify the code and to distribute modified code is granted, 21 * provided the above notices are retained, and a notice that the code was 22 * modified is included with the above copyright notice. 23 * 24 */ 25 #ifndef _STLP_ALGOBASE_C 26 #define _STLP_ALGOBASE_C 27 28 #ifndef _STLP_INTERNAL_ALGOBASE_H 29 # include <stl/_algobase.h> 30 #endif 31 32 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H 33 # include <stl/_function_base.h> 34 #endif 35 36 _STLP_BEGIN_NAMESPACE 37 38 template <class _InputIter1, class _InputIter2> 39 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, 40 _InputIter2 __first2, _InputIter2 __last2) { 41 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 42 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 43 for ( ; __first1 != __last1 && __first2 != __last2 44 ; ++__first1, ++__first2) { 45 if (*__first1 < *__first2) { 46 _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 47 return true; 48 } 49 if (*__first2 < *__first1) 50 return false; 51 } 52 return __first1 == __last1 && __first2 != __last2; 53 } 54 55 template <class _InputIter1, class _InputIter2, class _Compare> 56 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, 57 _InputIter2 __first2, _InputIter2 __last2, 58 _Compare __comp) { 59 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 60 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 61 for ( ; __first1 != __last1 && __first2 != __last2 62 ; ++__first1, ++__first2) { 63 if (__comp(*__first1, *__first2)) { 64 _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), 65 _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 66 return true; 67 } 68 if (__comp(*__first2, *__first1)) 69 return false; 70 } 71 return __first1 == __last1 && __first2 != __last2; 72 } 73 74 #if !defined (_STLP_NO_EXTENSIONS) 75 _STLP_MOVE_TO_PRIV_NAMESPACE 76 77 template <class _InputIter1, class _InputIter2> 78 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, 79 _InputIter2 __first2, _InputIter2 __last2) { 80 while (__first1 != __last1 && __first2 != __last2) { 81 if (*__first1 < *__first2) { 82 _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 83 return -1; 84 } 85 if (*__first2 < *__first1) 86 return 1; 87 ++__first1; 88 ++__first2; 89 } 90 if (__first2 == __last2) { 91 return !(__first1 == __last1); 92 } 93 else { 94 return -1; 95 } 96 } 97 98 _STLP_MOVE_TO_STD_NAMESPACE 99 100 template <class _InputIter1, class _InputIter2> 101 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, 102 _InputIter2 __first2, _InputIter2 __last2) { 103 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 104 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 105 return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2); 106 } 107 #endif 108 109 _STLP_MOVE_TO_PRIV_NAMESPACE 110 111 template <class _RandomAccessIter, class _Tp> 112 _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last, 113 const _Tp& __val, 114 const random_access_iterator_tag &) { 115 _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2; 116 117 for ( ; __trip_count > 0 ; --__trip_count) { 118 if (*__first == __val) return __first; 119 ++__first; 120 121 if (*__first == __val) return __first; 122 ++__first; 123 124 if (*__first == __val) return __first; 125 ++__first; 126 127 if (*__first == __val) return __first; 128 ++__first; 129 } 130 131 switch (__last - __first) { 132 case 3: 133 if (*__first == __val) return __first; 134 ++__first; 135 case 2: 136 if (*__first == __val) return __first; 137 ++__first; 138 case 1: 139 if (*__first == __val) return __first; 140 //++__first; 141 case 0: 142 default: 143 return __last; 144 } 145 } 146 147 inline char* 148 __find(char* __first, char* __last, char __val, const random_access_iterator_tag &) { 149 void *res = memchr(__first, __val, __last - __first); 150 return res != 0 ? __STATIC_CAST(char*, res) : __last; 151 } 152 inline const char* 153 __find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) { 154 const void *res = memchr(__first, __val, __last - __first); 155 return res != 0 ? __STATIC_CAST(const char*, res) : __last; 156 } 157 158 template <class _RandomAccessIter, class _Predicate> 159 _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last, 160 _Predicate __pred, 161 const random_access_iterator_tag &) { 162 _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2; 163 164 for ( ; __trip_count > 0 ; --__trip_count) { 165 if (__pred(*__first)) return __first; 166 ++__first; 167 168 if (__pred(*__first)) return __first; 169 ++__first; 170 171 if (__pred(*__first)) return __first; 172 ++__first; 173 174 if (__pred(*__first)) return __first; 175 ++__first; 176 } 177 178 switch(__last - __first) { 179 case 3: 180 if (__pred(*__first)) return __first; 181 ++__first; 182 case 2: 183 if (__pred(*__first)) return __first; 184 ++__first; 185 case 1: 186 if (__pred(*__first)) return __first; 187 //++__first; 188 case 0: 189 default: 190 return __last; 191 } 192 } 193 194 template <class _InputIter, class _Tp> 195 _STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last, 196 const _Tp& __val, 197 const input_iterator_tag &) { 198 while (__first != __last && !(*__first == __val)) ++__first; 199 return __first; 200 } 201 202 template <class _InputIter, class _Predicate> 203 _STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _InputIter __last, 204 _Predicate __pred, 205 const input_iterator_tag &) { 206 while (__first != __last && !__pred(*__first)) 207 ++__first; 208 return __first; 209 } 210 211 _STLP_MOVE_TO_STD_NAMESPACE 212 213 template <class _InputIter, class _Predicate> 214 _InputIter find_if(_InputIter __first, _InputIter __last, 215 _Predicate __pred) { 216 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 217 return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); 218 } 219 220 template <class _InputIter, class _Tp> 221 _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) { 222 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 223 return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); 224 } 225 226 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred> 227 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 228 _ForwardIter2 __first2, _ForwardIter2 __last2, 229 _BinaryPred __pred) { 230 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 231 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 232 // Test for empty ranges 233 if (__first1 == __last1 || __first2 == __last2) 234 return __first1; 235 236 // Test for a pattern of length 1. 237 _ForwardIter2 __p1(__first2); 238 239 if ( ++__p1 == __last2 ) { 240 while (__first1 != __last1 && !__pred(*__first1, *__first2)) { 241 ++__first1; 242 } 243 return __first1; 244 } 245 246 // General case. 247 248 for ( ; ; ) { // __first1 != __last1 will be checked below 249 while (__first1 != __last1 && !__pred(*__first1, *__first2)) { 250 ++__first1; 251 } 252 if (__first1 == __last1) { 253 return __last1; 254 } 255 _ForwardIter2 __p = __p1; 256 _ForwardIter1 __current = __first1; 257 if (++__current == __last1) return __last1; 258 259 while (__pred(*__current, *__p)) { 260 if (++__p == __last2) 261 return __first1; 262 if (++__current == __last1) 263 return __last1; 264 } 265 ++__first1; 266 } 267 return __first1; 268 } 269 270 _STLP_MOVE_TO_PRIV_NAMESPACE 271 template <class _Tp> 272 struct _IsCharLikeType 273 { typedef __false_type _Ret; }; 274 275 _STLP_TEMPLATE_NULL struct _IsCharLikeType<char> 276 { typedef __true_type _Ret; }; 277 278 _STLP_TEMPLATE_NULL struct _IsCharLikeType<unsigned char> 279 { typedef __true_type _Ret; }; 280 281 # ifndef _STLP_NO_SIGNED_BUILTINS 282 _STLP_TEMPLATE_NULL struct _IsCharLikeType<signed char> 283 { typedef __true_type _Ret; }; 284 # endif 285 286 template <class _Tp1, class _Tp2> 287 inline bool __stlp_eq(_Tp1 __val1, _Tp2 __val2) 288 { return __val1 == __val2; } 289 290 #if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 291 template <class _Tp> 292 inline bool __stlp_eq(_Tp, _Tp) 293 { return true; } 294 #endif 295 296 template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate> 297 inline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1, 298 _ForwardIter __first2, _ForwardIter __last2, 299 _Tp2*, _Predicate __pred, 300 const __true_type& /* _UseStrcspnLikeAlgo */) { 301 unsigned char __hints[(UCHAR_MAX + 1) / CHAR_BIT]; 302 memset(__hints, 0, sizeof(__hints) / sizeof(unsigned char)); 303 for (; __first2 != __last2; ++__first2) { 304 unsigned char __tmp = (unsigned char)*__first2; 305 __hints[__tmp / CHAR_BIT] |= (1 << (__tmp % CHAR_BIT)); 306 } 307 308 for (; __first1 != __last1; ++__first1) { 309 _Tp2 __tmp = (_Tp2)*__first1; 310 if (__stlp_eq(*__first1, __tmp) && 311 __pred((__hints[(unsigned char)__tmp / CHAR_BIT] & (1 << ((unsigned char)__tmp % CHAR_BIT))) != 0)) 312 break; 313 } 314 return __first1; 315 } 316 317 template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate> 318 inline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1, 319 _ForwardIter __first2, _ForwardIter __last2, 320 _Tp2* /* __dummy */, _Predicate /* __pred */, 321 const __false_type& /* _UseStrcspnLikeAlgo */) { 322 return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2, 323 _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _InputIter))); 324 } 325 326 template <class _InputIter, class _ForwardIter, class _Tp1, class _Tp2> 327 inline _InputIter __find_first_of_aux1(_InputIter __first1, _InputIter __last1, 328 _ForwardIter __first2, _ForwardIter __last2, 329 _Tp1* __pt1, _Tp2* __pt2) { 330 typedef _STLP_TYPENAME _STLP_STD::_IsIntegral<_Tp1>::_Ret _IsIntegral; 331 typedef _STLP_TYPENAME _STLP_PRIV _IsCharLikeType<_Tp2>::_Ret _IsCharLike; 332 typedef _STLP_TYPENAME _STLP_STD::_Land2<_IsIntegral, _IsCharLike>::_Ret _UseStrcspnLikeAlgo; 333 return _STLP_PRIV __find_first_of_aux2(__first1, __last1, 334 __first2, __last2, 335 __pt2, _Identity<bool>(), _UseStrcspnLikeAlgo()); 336 } 337 338 template <class _InputIter, class _ForwardIter> 339 inline _InputIter __find_first_of(_InputIter __first1, _InputIter __last1, 340 _ForwardIter __first2, _ForwardIter __last2) { 341 return _STLP_PRIV __find_first_of_aux1(__first1, __last1, __first2, __last2, 342 _STLP_VALUE_TYPE(__first1, _InputIter), 343 _STLP_VALUE_TYPE(__first2, _ForwardIter)); 344 } 345 346 // find_first_of, with and without an explicitly supplied comparison function. 347 template <class _InputIter, class _ForwardIter, class _BinaryPredicate> 348 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1, 349 _ForwardIter __first2, _ForwardIter __last2, 350 _BinaryPredicate __comp) { 351 for ( ; __first1 != __last1; ++__first1) { 352 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) { 353 if (__comp(*__first1, *__iter)) { 354 return __first1; 355 } 356 } 357 } 358 return __last1; 359 } 360 361 // find_end, with and without an explicitly supplied comparison function. 362 // Search [first2, last2) as a subsequence in [first1, last1), and return 363 // the *last* possible match. Note that find_end for bidirectional iterators 364 // is much faster than for forward iterators. 365 366 // find_end for forward iterators. 367 template <class _ForwardIter1, class _ForwardIter2, 368 class _BinaryPredicate> 369 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 370 _ForwardIter2 __first2, _ForwardIter2 __last2, 371 const forward_iterator_tag &, const forward_iterator_tag &, 372 _BinaryPredicate __comp) { 373 if (__first2 == __last2) 374 return __last1; 375 else { 376 _ForwardIter1 __result = __last1; 377 for (;;) { 378 _ForwardIter1 __new_result = _STLP_STD::search(__first1, __last1, __first2, __last2, __comp); 379 if (__new_result == __last1) 380 return __result; 381 else { 382 __result = __new_result; 383 __first1 = __new_result; 384 ++__first1; 385 } 386 } 387 } 388 } 389 390 _STLP_MOVE_TO_STD_NAMESPACE 391 392 // find_end for bidirectional iterators. Requires partial specialization. 393 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 394 395 # ifndef _STLP_INTERNAL_ITERATOR_H 396 _STLP_END_NAMESPACE 397 # include <stl/_iterator.h> 398 _STLP_BEGIN_NAMESPACE 399 # endif /*_STLP_INTERNAL_ITERATOR_H*/ 400 401 _STLP_MOVE_TO_PRIV_NAMESPACE 402 403 template <class _BidirectionalIter1, class _BidirectionalIter2, 404 class _BinaryPredicate> 405 _BidirectionalIter1 406 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 407 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 408 const bidirectional_iterator_tag &, const bidirectional_iterator_tag &, 409 _BinaryPredicate __comp) { 410 typedef _STLP_STD::reverse_iterator<_BidirectionalIter1> _RevIter1; 411 typedef _STLP_STD::reverse_iterator<_BidirectionalIter2> _RevIter2; 412 413 _RevIter1 __rlast1(__first1); 414 _RevIter2 __rlast2(__first2); 415 _RevIter1 __rresult = _STLP_STD::search(_RevIter1(__last1), __rlast1, 416 _RevIter2(__last2), __rlast2, 417 __comp); 418 419 if (__rresult == __rlast1) 420 return __last1; 421 else { 422 _BidirectionalIter1 __result = __rresult.base(); 423 _STLP_STD::advance(__result, -_STLP_STD::distance(__first2, __last2)); 424 return __result; 425 } 426 } 427 428 _STLP_MOVE_TO_STD_NAMESPACE 429 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 430 431 template <class _ForwardIter1, class _ForwardIter2, 432 class _BinaryPredicate> 433 _ForwardIter1 434 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 435 _ForwardIter2 __first2, _ForwardIter2 __last2, 436 _BinaryPredicate __comp) { 437 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 438 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 439 return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2, 440 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 441 _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1), 442 _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2), 443 #else 444 forward_iterator_tag(), 445 forward_iterator_tag(), 446 #endif 447 __comp); 448 } 449 450 _STLP_MOVE_TO_PRIV_NAMESPACE 451 452 template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance> 453 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 454 _Compare1 __comp1, _Compare2 __comp2, _Distance*) { 455 _Distance __len = _STLP_STD::distance(__first, __last); 456 _Distance __half; 457 _ForwardIter __middle; 458 459 while (__len > 0) { 460 __half = __len >> 1; 461 __middle = __first; 462 _STLP_STD::advance(__middle, __half); 463 if (__comp1(*__middle, __val)) { 464 _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 465 __first = __middle; 466 ++__first; 467 __len = __len - __half - 1; 468 } 469 else 470 __len = __half; 471 } 472 return __first; 473 } 474 475 _STLP_MOVE_TO_STD_NAMESPACE 476 477 _STLP_END_NAMESPACE 478 479 #endif /* _STLP_ALGOBASE_C */ 480 481 // Local Variables: 482 // mode:C++ 483 // End: 484
