include/c++/stl/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 _STLP_BEGIN_NAMESPACE
  33
  34 template <class _InputIter1, class _InputIter2>
  35 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  36                              _InputIter2 __first2, _InputIter2 __last2) {
  37   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  38   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  39   for ( ; __first1 != __last1 && __first2 != __last2
  40         ; ++__first1, ++__first2) {
  41     if (*__first1 < *__first2) {
  42       return true;
  43     }
  44     if (*__first2 < *__first1)
  45       return false;
  46   }
  47   return __first1 == __last1 && __first2 != __last2;
  48 }
  49
  50 template <class _InputIter1, class _InputIter2, class _Compare>
  51 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  52                              _InputIter2 __first2, _InputIter2 __last2,
  53                              _Compare __comp) {
  54   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  55   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  56   for ( ; __first1 != __last1 && __first2 != __last2
  57         ; ++__first1, ++__first2) {
  58     if (__comp(*__first1, *__first2)) {
  59       return true;
  60     }
  61     if (__comp(*__first2, *__first1))
  62       return false;
  63   }
  64   return __first1 == __last1 && __first2 != __last2;
  65 }
  66
  67 #if !defined (_STLP_NO_EXTENSIONS)
  68 _STLP_MOVE_TO_PRIV_NAMESPACE
  69
  70 template <class _InputIter1, class _InputIter2>
  71 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  72                                    _InputIter2 __first2, _InputIter2 __last2) {
  73   while (__first1 != __last1 && __first2 != __last2) {
  74     if (*__first1 < *__first2) {
  75       _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  76       return -1;
  77     }
  78     if (*__first2 < *__first1)
  79       return 1;
  80     ++__first1;
  81     ++__first2;
  82   }
  83   if (__first2 == __last2) {
  84     return !(__first1 == __last1);
  85   }
  86   else {
  87     return -1;
  88   }
  89 }
  90
  91 _STLP_MOVE_TO_STD_NAMESPACE
  92
  93 template <class _InputIter1, class _InputIter2>
  94 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  95                                  _InputIter2 __first2, _InputIter2 __last2) {
  96   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  97   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  98   return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
  99 }
 100 #endif
 101
 102 _STLP_MOVE_TO_PRIV_NAMESPACE
 103
 104 template <class _RandomAccessIter, class _Tp>
 105 _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
 106                                            const _Tp& __val,
 107                                            const random_access_iterator_tag &) {
 108   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
 109
 110   for ( ; __trip_count > 0 ; --__trip_count) {
 111     if (*__first == __val) return __first;
 112     ++__first;
 113
 114     if (*__first == __val) return __first;
 115     ++__first;
 116
 117     if (*__first == __val) return __first;
 118     ++__first;
 119
 120     if (*__first == __val) return __first;
 121     ++__first;
 122   }
 123
 124   switch (__last - __first) {
 125   case 3:
 126     if (*__first == __val) return __first;
 127     ++__first;
 128   case 2:
 129     if (*__first == __val) return __first;
 130     ++__first;
 131   case 1:
 132     if (*__first == __val) return __first;
 133     //++__first;
 134   case 0:
 135   default:
 136     return __last;
 137   }
 138 }
 139
 140 inline char*
 141 __find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
 142   void *res =  memchr(__first, __val, __last - __first);
 143   return res != 0 ? __STATIC_CAST(char*, res) : __last;
 144 }
 145 inline const char*
 146 __find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
 147   const void *res =  memchr(__first, __val, __last - __first);
 148   return res != 0 ? __STATIC_CAST(const char*, res) : __last;
 149 }
 150
 151 template <class _RandomAccessIter, class _Predicate>
 152 _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
 153                                               _Predicate __pred,
 154                                               const random_access_iterator_tag &) {
 155   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
 156
 157   for ( ; __trip_count > 0 ; --__trip_count) {
 158     if (__pred(*__first)) return __first;
 159     ++__first;
 160
 161     if (__pred(*__first)) return __first;
 162     ++__first;
 163
 164     if (__pred(*__first)) return __first;
 165     ++__first;
 166
 167     if (__pred(*__first)) return __first;
 168     ++__first;
 169   }
 170
 171   switch(__last - __first) {
 172   case 3:
 173     if (__pred(*__first)) return __first;
 174     ++__first;
 175   case 2:
 176     if (__pred(*__first)) return __first;
 177     ++__first;
 178   case 1:
 179     if (__pred(*__first)) return __first;
 180       //++__first;
 181   case 0:
 182   default:
 183     return __last;
 184   }
 185 }
 186
 187 template <class _InputIter, class _Tp>
 188 _STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
 189                                     const _Tp& __val,
 190                                     const input_iterator_tag &) {
 191   while (__first != __last && !(*__first == __val)) ++__first;
 192   return __first;
 193 }
 194
 195 template <class _InputIter, class _Predicate>
 196 _STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
 197                                        _Predicate __pred,
 198                                        const input_iterator_tag &) {
 199   while (__first != __last && !__pred(*__first))
 200     ++__first;
 201   return __first;
 202 }
 203
 204 _STLP_MOVE_TO_STD_NAMESPACE
 205
 206 template <class _InputIter, class _Predicate>
 207 _InputIter find_if(_InputIter __first, _InputIter __last,
 208                    _Predicate __pred) {
 209   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 210   return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
 211 }
 212
 213 template <class _InputIter, class _Tp>
 214 _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
 215   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 216   return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
 217 }
 218
 219 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
 220 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
 221                      _ForwardIter2 __first2, _ForwardIter2 __last2,
 222                      _BinaryPred  __pred) {
 223   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
 224   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
 225   // Test for empty ranges
 226   if (__first1 == __last1 || __first2 == __last2)
 227     return __first1;
 228
 229   // Test for a pattern of length 1.
 230   _ForwardIter2 __p1(__first2);
 231
 232   if ( ++__p1 == __last2 ) {
 233     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
 234       ++__first1;
 235     }
 236     return __first1;
 237   }
 238
 239   // General case.
 240
 241   for ( ; ; ) { // __first1 != __last1 will be checked below
 242     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
 243       ++__first1;
 244     }
 245     if (__first1 == __last1) {
 246       return __last1;
 247     }
 248     _ForwardIter2 __p = __p1;
 249     _ForwardIter1 __current = __first1;
 250     if (++__current == __last1) return __last1;
 251
 252     while (__pred(*__current, *__p)) {
 253       if (++__p == __last2)
 254         return __first1;
 255       if (++__current == __last1)
 256         return __last1;
 257     }
 258
 259     ++__first1;
 260   }
 261   return __first1;
 262 }
 263
 264 _STLP_MOVE_TO_PRIV_NAMESPACE
 265
 266 // find_first_of, with and without an explicitly supplied comparison function.
 267 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
 268 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
 269                            _ForwardIter __first2, _ForwardIter __last2,
 270                            _BinaryPredicate __comp) {
 271   for ( ; __first1 != __last1; ++__first1) {
 272     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
 273       if (__comp(*__first1, *__iter)) {
 274         return __first1;
 275       }
 276     }
 277   }
 278   return __last1;
 279 }
 280
 281 // find_end, with and without an explicitly supplied comparison function.
 282 // Search [first2, last2) as a subsequence in [first1, last1), and return
 283 // the *last* possible match.  Note that find_end for bidirectional iterators
 284 // is much faster than for forward iterators.
 285
 286 // find_end for forward iterators.
 287 template <class _ForwardIter1, class _ForwardIter2,
 288   class _BinaryPredicate>
 289 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
 290                          _ForwardIter2 __first2, _ForwardIter2 __last2,
 291                          const forward_iterator_tag &, const forward_iterator_tag &,
 292                          _BinaryPredicate __comp) {
 293   if (__first2 == __last2)
 294     return __last1;
 295   else {
 296     _ForwardIter1 __result = __last1;
 297     for (;;) {
 298       _ForwardIter1 __new_result = search(__first1, __last1, __first2, __last2, __comp);
 299       if (__new_result == __last1)
 300         return __result;
 301       else {
 302         __result = __new_result;
 303         __first1 = __new_result;
 304         ++__first1;
 305       }
 306     }
 307   }
 308 }
 309
 310 _STLP_MOVE_TO_STD_NAMESPACE
 311
 312 // find_end for bidirectional iterators.  Requires partial specialization.
 313 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 314
 315 #  ifndef _STLP_INTERNAL_ITERATOR_H
 316 _STLP_END_NAMESPACE
 317 #    include <stl/_iterator.h>
 318 _STLP_BEGIN_NAMESPACE
 319 #  endif /*_STLP_INTERNAL_ITERATOR_H*/
 320
 321 _STLP_MOVE_TO_PRIV_NAMESPACE
 322
 323 template <class _BidirectionalIter1, class _BidirectionalIter2,
 324           class _BinaryPredicate>
 325 _BidirectionalIter1
 326 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
 327            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
 328            const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
 329            _BinaryPredicate __comp) {
 330   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
 331   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
 332
 333   _RevIter1 __rlast1(__first1);
 334   _RevIter2 __rlast2(__first2);
 335   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
 336                                _RevIter2(__last2), __rlast2,
 337                                __comp);
 338
 339   if (__rresult == __rlast1)
 340     return __last1;
 341   else {
 342     _BidirectionalIter1 __result = __rresult.base();
 343     advance(__result, -distance(__first2, __last2));
 344     return __result;
 345   }
 346 }
 347
 348 _STLP_MOVE_TO_STD_NAMESPACE
 349 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 350
 351 template <class _ForwardIter1, class _ForwardIter2,
 352           class _BinaryPredicate>
 353 _ForwardIter1
 354 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
 355          _ForwardIter2 __first2, _ForwardIter2 __last2,
 356          _BinaryPredicate __comp) {
 357   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
 358   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
 359   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
 360 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 361                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
 362                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
 363 #else
 364                                forward_iterator_tag(),
 365                                forward_iterator_tag(),
 366 #endif
 367                                __comp);
 368 }
 369
 370 _STLP_MOVE_TO_PRIV_NAMESPACE
 371
 372 template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
 373 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
 374                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
 375   _Distance __len = distance(__first, __last);
 376   _Distance __half;
 377   _ForwardIter __middle;
 378
 379   while (__len > 0) {
 380     __half = __len >> 1;
 381     __middle = __first;
 382     advance(__middle, __half);
 383     if (__comp1(*__middle, __val)) {
 384       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
 385       __first = __middle;
 386       ++__first;
 387       __len = __len - __half - 1;
 388     }
 389     else
 390       __len = __half;
 391   }
 392   return __first;
 393 }
 394
 395 _STLP_MOVE_TO_STD_NAMESPACE
 396
 397 _STLP_END_NAMESPACE
 398
 399 #endif /* _STLP_ALGOBASE_C */
 400
 401 // Local Variables:
 402 // mode:C++
 403 // End: