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