/home/ntakagi/work/STLport-5.1.5/stlport/stl/_algobase.c Source File

00001 /*
00002  *
00003  * Copyright (c) 1994
00004  * Hewlett-Packard Company
00005  *
00006  * Copyright (c) 1996,1997
00007  * Silicon Graphics Computer Systems, Inc.
00008  *
00009  * Copyright (c) 1997
00010  * Moscow Center for SPARC Technology
00011  *
00012  * Copyright (c) 1999
00013  * Boris Fomitchev
00014  *
00015  * This material is provided "as is", with absolutely no warranty expressed
00016  * or implied. Any use is at your own risk.
00017  *
00018  * Permission to use or copy this software for any purpose is hereby granted
00019  * without fee, provided the above notices are retained on all copies.
00020  * Permission to modify the code and to distribute modified code is granted,
00021  * provided the above notices are retained, and a notice that the code was
00022  * modified is included with the above copyright notice.
00023  *
00024  */
00025 #ifndef _STLP_ALGOBASE_C
00026 #define _STLP_ALGOBASE_C
00027 
00028 #ifndef _STLP_INTERNAL_ALGOBASE_H
00029 #  include <stl/_algobase.h>
00030 #endif
00031 
00032 _STLP_BEGIN_NAMESPACE
00033 
00034 template <class _InputIter1, class _InputIter2>
00035 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
00036                              _InputIter2 __first2, _InputIter2 __last2) {
00037   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
00038   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
00039   for ( ; __first1 != __last1 && __first2 != __last2
00040         ; ++__first1, ++__first2) {
00041     if (*__first1 < *__first2) {
00042       return true;
00043     }
00044     if (*__first2 < *__first1)
00045       return false;
00046   }
00047   return __first1 == __last1 && __first2 != __last2;
00048 }
00049 
00050 template <class _InputIter1, class _InputIter2, class _Compare>
00051 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
00052                              _InputIter2 __first2, _InputIter2 __last2,
00053                              _Compare __comp) {
00054   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
00055   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
00056   for ( ; __first1 != __last1 && __first2 != __last2
00057         ; ++__first1, ++__first2) {
00058     if (__comp(*__first1, *__first2)) {
00059       return true;
00060     }
00061     if (__comp(*__first2, *__first1))
00062       return false;
00063   }
00064   return __first1 == __last1 && __first2 != __last2;
00065 }
00066 
00067 #if !defined (_STLP_NO_EXTENSIONS)
00068 _STLP_MOVE_TO_PRIV_NAMESPACE
00069 
00070 template <class _InputIter1, class _InputIter2>
00071 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
00072                                    _InputIter2 __first2, _InputIter2 __last2) {
00073   while (__first1 != __last1 && __first2 != __last2) {
00074     if (*__first1 < *__first2) {
00075       _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00076       return -1;
00077     }
00078     if (*__first2 < *__first1)
00079       return 1;
00080     ++__first1;
00081     ++__first2;
00082   }
00083   if (__first2 == __last2) {
00084     return !(__first1 == __last1);
00085   }
00086   else {
00087     return -1;
00088   }
00089 }
00090 
00091 _STLP_MOVE_TO_STD_NAMESPACE
00092 
00093 template <class _InputIter1, class _InputIter2>
00094 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
00095                                  _InputIter2 __first2, _InputIter2 __last2) {
00096   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
00097   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
00098   return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
00099 }
00100 #endif
00101 
00102 _STLP_MOVE_TO_PRIV_NAMESPACE
00103 
00104 template <class _RandomAccessIter, class _Tp>
00105 _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
00106                                            const _Tp& __val,
00107                                            const random_access_iterator_tag &) {
00108   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
00109 
00110   for ( ; __trip_count > 0 ; --__trip_count) {
00111     if (*__first == __val) return __first;
00112     ++__first;
00113 
00114     if (*__first == __val) return __first;
00115     ++__first;
00116 
00117     if (*__first == __val) return __first;
00118     ++__first;
00119 
00120     if (*__first == __val) return __first;
00121     ++__first;
00122   }
00123 
00124   switch (__last - __first) {
00125   case 3:
00126     if (*__first == __val) return __first;
00127     ++__first;
00128   case 2:
00129     if (*__first == __val) return __first;
00130     ++__first;
00131   case 1:
00132     if (*__first == __val) return __first;
00133     //++__first;
00134   case 0:
00135   default:
00136     return __last;
00137   }
00138 }
00139 
00140 inline char*
00141 __find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
00142   void *res =  memchr(__first, __val, __last - __first);
00143   return res != 0 ? __STATIC_CAST(char*, res) : __last;
00144 }
00145 inline const char*
00146 __find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
00147   const void *res =  memchr(__first, __val, __last - __first);
00148   return res != 0 ? __STATIC_CAST(const char*, res) : __last;
00149 }
00150 
00151 template <class _RandomAccessIter, class _Predicate>
00152 _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
00153                                               _Predicate __pred,
00154                                               const random_access_iterator_tag &) {
00155   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
00156 
00157   for ( ; __trip_count > 0 ; --__trip_count) {
00158     if (__pred(*__first)) return __first;
00159     ++__first;
00160 
00161     if (__pred(*__first)) return __first;
00162     ++__first;
00163 
00164     if (__pred(*__first)) return __first;
00165     ++__first;
00166 
00167     if (__pred(*__first)) return __first;
00168     ++__first;
00169   }
00170 
00171   switch(__last - __first) {
00172   case 3:
00173     if (__pred(*__first)) return __first;
00174     ++__first;
00175   case 2:
00176     if (__pred(*__first)) return __first;
00177     ++__first;
00178   case 1:
00179     if (__pred(*__first)) return __first;
00180       //++__first;
00181   case 0:
00182   default:
00183     return __last;
00184   }
00185 }
00186 
00187 template <class _InputIter, class _Tp>
00188 _STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
00189                                     const _Tp& __val,
00190                                     const input_iterator_tag &) {
00191   while (__first != __last && !(*__first == __val)) ++__first;
00192   return __first;
00193 }
00194 
00195 template <class _InputIter, class _Predicate>
00196 _STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
00197                                        _Predicate __pred,
00198                                        const input_iterator_tag &) {
00199   while (__first != __last && !__pred(*__first))
00200     ++__first;
00201   return __first;
00202 }
00203 
00204 _STLP_MOVE_TO_STD_NAMESPACE
00205 
00206 template <class _InputIter, class _Predicate>
00207 _InputIter find_if(_InputIter __first, _InputIter __last,
00208                    _Predicate __pred) {
00209   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00210   return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
00211 }
00212 
00213 template <class _InputIter, class _Tp>
00214 _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
00215   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00216   return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
00217 }
00218 
00219 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
00220 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
00221                      _ForwardIter2 __first2, _ForwardIter2 __last2,
00222                      _BinaryPred  __pred) {
00223   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
00224   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
00225   // Test for empty ranges
00226   if (__first1 == __last1 || __first2 == __last2)
00227     return __first1;
00228 
00229   // Test for a pattern of length 1.
00230   _ForwardIter2 __p1(__first2);
00231 
00232   if ( ++__p1 == __last2 ) {
00233     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
00234       ++__first1;
00235     }
00236     return __first1;
00237   }
00238 
00239   // General case.
00240 
00241   for ( ; ; ) { // __first1 != __last1 will be checked below
00242     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
00243       ++__first1;
00244     }
00245     if (__first1 == __last1) {
00246       return __last1;
00247     }
00248     _ForwardIter2 __p = __p1;
00249     _ForwardIter1 __current = __first1;
00250     if (++__current == __last1) return __last1;
00251 
00252     while (__pred(*__current, *__p)) {
00253       if (++__p == __last2)
00254         return __first1;
00255       if (++__current == __last1)
00256         return __last1;
00257     }
00258 
00259     ++__first1;
00260   }
00261   return __first1;
00262 }
00263 
00264 _STLP_MOVE_TO_PRIV_NAMESPACE
00265 
00266 // find_first_of, with and without an explicitly supplied comparison function.
00267 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
00268 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
00269                            _ForwardIter __first2, _ForwardIter __last2,
00270                            _BinaryPredicate __comp) {
00271   for ( ; __first1 != __last1; ++__first1) {
00272     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
00273       if (__comp(*__first1, *__iter)) {
00274         return __first1;
00275       }
00276     }
00277   }
00278   return __last1;
00279 }
00280 
00281 // find_end, with and without an explicitly supplied comparison function.
00282 // Search [first2, last2) as a subsequence in [first1, last1), and return
00283 // the *last* possible match.  Note that find_end for bidirectional iterators
00284 // is much faster than for forward iterators.
00285 
00286 // find_end for forward iterators.
00287 template <class _ForwardIter1, class _ForwardIter2,
00288   class _BinaryPredicate>
00289 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
00290                          _ForwardIter2 __first2, _ForwardIter2 __last2,
00291                          const forward_iterator_tag &, const forward_iterator_tag &,
00292                          _BinaryPredicate __comp) {
00293   if (__first2 == __last2)
00294     return __last1;
00295   else {
00296     _ForwardIter1 __result = __last1;
00297     for (;;) {
00298       _ForwardIter1 __new_result = search(__first1, __last1, __first2, __last2, __comp);
00299       if (__new_result == __last1)
00300         return __result;
00301       else {
00302         __result = __new_result;
00303         __first1 = __new_result;
00304         ++__first1;
00305       }
00306     }
00307   }
00308 }
00309 
00310 _STLP_MOVE_TO_STD_NAMESPACE
00311 
00312 // find_end for bidirectional iterators.  Requires partial specialization.
00313 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
00314 
00315 #  ifndef _STLP_INTERNAL_ITERATOR_H
00316 _STLP_END_NAMESPACE
00317 #    include <stl/_iterator.h>
00318 _STLP_BEGIN_NAMESPACE
00319 #  endif /*_STLP_INTERNAL_ITERATOR_H*/
00320 
00321 _STLP_MOVE_TO_PRIV_NAMESPACE
00322 
00323 template <class _BidirectionalIter1, class _BidirectionalIter2,
00324           class _BinaryPredicate>
00325 _BidirectionalIter1
00326 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
00327            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
00328            const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
00329            _BinaryPredicate __comp) {
00330   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
00331   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
00332 
00333   _RevIter1 __rlast1(__first1);
00334   _RevIter2 __rlast2(__first2);
00335   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
00336                                _RevIter2(__last2), __rlast2,
00337                                __comp);
00338 
00339   if (__rresult == __rlast1)
00340     return __last1;
00341   else {
00342     _BidirectionalIter1 __result = __rresult.base();
00343     advance(__result, -distance(__first2, __last2));
00344     return __result;
00345   }
00346 }
00347 
00348 _STLP_MOVE_TO_STD_NAMESPACE
00349 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
00350 
00351 template <class _ForwardIter1, class _ForwardIter2,
00352           class _BinaryPredicate>
00353 _ForwardIter1
00354 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
00355          _ForwardIter2 __first2, _ForwardIter2 __last2,
00356          _BinaryPredicate __comp) {
00357   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
00358   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
00359   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
00360 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
00361                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
00362                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
00363 #else
00364                                forward_iterator_tag(),
00365                                forward_iterator_tag(),
00366 #endif
00367                                __comp);
00368 }
00369 
00370 _STLP_MOVE_TO_PRIV_NAMESPACE
00371 
00372 template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
00373 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
00374                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
00375   _Distance __len = distance(__first, __last);
00376   _Distance __half;
00377   _ForwardIter __middle;
00378 
00379   while (__len > 0) {
00380     __half = __len >> 1;
00381     __middle = __first;
00382     advance(__middle, __half);
00383     if (__comp1(*__middle, __val)) {
00384       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00385       __first = __middle;
00386       ++__first;
00387       __len = __len - __half - 1;
00388     }
00389     else
00390       __len = __half;
00391   }
00392   return __first;
00393 }
00394 
00395 _STLP_MOVE_TO_STD_NAMESPACE
00396 
00397 _STLP_END_NAMESPACE
00398 
00399 #endif /* _STLP_ALGOBASE_C */
00400 
00401 // Local Variables:
00402 // mode:C++
00403 // End: