ndk/sources/cxx-stl/stlport/stlport/stl/_algobase.c

   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: