Mercurialtest / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
epoc32/include/tools/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 #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       _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

    43       return true;

    44     }

    45     if (*__first2 < *__first1)

    46       return false;

    47   }

    48   return __first1 == __last1 && __first2 != __last2;

    49 }

    50 

    51 template <class _InputIter1, class _InputIter2, class _Compare>

    52 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,

    53                              _InputIter2 __first2, _InputIter2 __last2,

    54                              _Compare __comp) {

    55   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

    56   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

    57   for ( ; __first1 != __last1 && __first2 != __last2

    58         ; ++__first1, ++__first2) {

    59     if (__comp(*__first1, *__first2)) {

    60       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

    61       return true;

    62     }

    63     if (__comp(*__first2, *__first1))

    64       return false;

    65   }

    66   return __first1 == __last1 && __first2 != __last2;

    67 }

    68 

    69 #if !defined (_STLP_NO_EXTENSIONS)

    70 _STLP_MOVE_TO_PRIV_NAMESPACE

    71 

    72 template <class _InputIter1, class _InputIter2>

    73 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,

    74                                    _InputIter2 __first2, _InputIter2 __last2) {

    75   while (__first1 != __last1 && __first2 != __last2) {

    76     if (*__first1 < *__first2) {

    77       _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

    78       return -1;

    79     }

    80     if (*__first2 < *__first1)

    81       return 1;

    82     ++__first1;

    83     ++__first2;

    84   }

    85   if (__first2 == __last2) {

    86     return !(__first1 == __last1);

    87   }

    88   else {

    89     return -1;

    90   }

    91 }

    92 

    93 _STLP_MOVE_TO_STD_NAMESPACE

    94 

    95 template <class _InputIter1, class _InputIter2>

    96 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,

    97                                  _InputIter2 __first2, _InputIter2 __last2) {

    98   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

    99   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

   100   return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);

   101 }

   102 #endif

   103 

   104 _STLP_MOVE_TO_PRIV_NAMESPACE

   105 

   106 template <class _RandomAccessIter, class _Tp>

   107 _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,

   108                                            const _Tp& __val,

   109                                            const random_access_iterator_tag &) {

   110   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;

   111 

   112   for ( ; __trip_count > 0 ; --__trip_count) {

   113     if (*__first == __val) return __first;

   114     ++__first;

   115 

   116     if (*__first == __val) return __first;

   117     ++__first;

   118 

   119     if (*__first == __val) return __first;

   120     ++__first;

   121 

   122     if (*__first == __val) return __first;

   123     ++__first;

   124   }

   125 

   126   switch (__last - __first) {

   127   case 3:

   128     if (*__first == __val) return __first;

   129     ++__first;

   130   case 2:

   131     if (*__first == __val) return __first;

   132     ++__first;

   133   case 1:

   134     if (*__first == __val) return __first;

   135     //++__first;

   136   case 0:

   137   default:

   138     return __last;

   139   }

   140 }

   141 

   142 inline char*

   143 __find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {

   144   void *res =  memchr(__first, __val, __last - __first);

   145   return res != 0 ? __STATIC_CAST(char*, res) : __last;

   146 }

   147 inline const char*

   148 __find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {

   149   const void *res =  memchr(__first, __val, __last - __first);

   150   return res != 0 ? __STATIC_CAST(const char*, res) : __last;

   151 }

   152 

   153 template <class _RandomAccessIter, class _Predicate>

   154 _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,

   155                                               _Predicate __pred,

   156                                               const random_access_iterator_tag &) {

   157   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;

   158 

   159   for ( ; __trip_count > 0 ; --__trip_count) {

   160     if (__pred(*__first)) return __first;

   161     ++__first;

   162 

   163     if (__pred(*__first)) return __first;

   164     ++__first;

   165 

   166     if (__pred(*__first)) return __first;

   167     ++__first;

   168 

   169     if (__pred(*__first)) return __first;

   170     ++__first;

   171   }

   172 

   173   switch(__last - __first) {

   174   case 3:

   175     if (__pred(*__first)) return __first;

   176     ++__first;

   177   case 2:

   178     if (__pred(*__first)) return __first;

   179     ++__first;

   180   case 1:

   181     if (__pred(*__first)) return __first;

   182       //++__first;

   183   case 0:

   184   default:

   185     return __last;

   186   }

   187 }

   188 

   189 template <class _InputIter, class _Tp>

   190 _STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,

   191                                     const _Tp& __val,

   192                                     const input_iterator_tag &) {

   193   while (__first != __last && !(*__first == __val)) ++__first;

   194   return __first;

   195 }

   196 

   197 template <class _InputIter, class _Predicate>

   198 _STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,

   199                                        _Predicate __pred,

   200                                        const input_iterator_tag &) {

   201   while (__first != __last && !__pred(*__first))

   202     ++__first;

   203   return __first;

   204 }

   205 

   206 _STLP_MOVE_TO_STD_NAMESPACE

   207 

   208 template <class _InputIter, class _Predicate>

   209 _InputIter find_if(_InputIter __first, _InputIter __last,

   210                    _Predicate __pred) {

   211   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   212   return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));

   213 }

   214 

   215 template <class _InputIter, class _Tp>

   216 _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {

   217   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   218   return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));

   219 }

   220 

   221 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>

   222 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,

   223                      _ForwardIter2 __first2, _ForwardIter2 __last2,

   224                      _BinaryPred  __pred) {

   225   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

   226   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

   227   // Test for empty ranges

   228   if (__first1 == __last1 || __first2 == __last2)

   229     return __first1;

   230 

   231   // Test for a pattern of length 1.

   232   _ForwardIter2 __tmp(__first2);

   233   ++__tmp;

   234   if (__tmp == __last2) {

   235     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {

   236       _STLP_VERBOSE_ASSERT(!__pred(*__first2, *__first1), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   237       ++__first1;

   238     }

   239     _STLP_VERBOSE_ASSERT((__first1 == __last1) || __pred(*__first2, *__first1),

   240                          _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   241     return __first1;

   242   }

   243 

   244   // General case.

   245 

   246   _ForwardIter2 __p1, __p;

   247 

   248   __p1 = __first2; ++__p1;

   249 

   250   //  _ForwardIter1 __current = __first1;

   251 

   252   while (__first1 != __last1) {

   253     while (__first1 != __last1) {

   254       if (__pred(*__first1, *__first2)) {

   255         _STLP_VERBOSE_ASSERT(__pred(*__first2, *__first1), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   256         break;

   257       }

   258       _STLP_VERBOSE_ASSERT(!__pred(*__first2, *__first1), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   259       ++__first1;

   260     }

   261     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {

   262       _STLP_VERBOSE_ASSERT(!__pred(*__first2, *__first1), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   263       ++__first1;

   264     }

   265     if (__first1 == __last1)

   266       return __last1;

   267     _STLP_VERBOSE_ASSERT(__pred(*__first2, *__first1), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   268 

   269     __p = __p1;

   270     _ForwardIter1 __current = __first1;

   271     if (++__current == __last1) return __last1;

   272 

   273     while (__pred(*__current, *__p)) {

   274       _STLP_VERBOSE_ASSERT(__pred(*__p, *__current), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   275       if (++__p == __last2)

   276         return __first1;

   277       if (++__current == __last1)

   278         return __last1;

   279     }

   280 

   281     _STLP_VERBOSE_ASSERT(!__pred(*__p, *__current), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   282     ++__first1;

   283   }

   284   return __first1;

   285 }

   286 

   287 _STLP_MOVE_TO_PRIV_NAMESPACE

   288 

   289 // find_first_of, with and without an explicitly supplied comparison function.

   290 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>

   291 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,

   292                            _ForwardIter __first2, _ForwardIter __last2,

   293                            _BinaryPredicate __comp) {

   294   for ( ; __first1 != __last1; ++__first1) {

   295     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {

   296       if (__comp(*__first1, *__iter)) {

   297         _STLP_VERBOSE_ASSERT(__comp(*__iter, *__first1), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   298         return __first1;

   299       }

   300       _STLP_VERBOSE_ASSERT(!__comp(*__iter, *__first1), _StlMsg_INVALID_EQUIVALENT_PREDICATE)

   301     }

   302   }

   303   return __last1;

   304 }

   305 

   306 // find_end, with and without an explicitly supplied comparison function.

   307 // Search [first2, last2) as a subsequence in [first1, last1), and return

   308 // the *last* possible match.  Note that find_end for bidirectional iterators

   309 // is much faster than for forward iterators.

   310 

   311 // find_end for forward iterators.

   312 template <class _ForwardIter1, class _ForwardIter2,

   313   class _BinaryPredicate>

   314 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,

   315                          _ForwardIter2 __first2, _ForwardIter2 __last2,

   316                          const forward_iterator_tag &, const forward_iterator_tag &,

   317                          _BinaryPredicate __comp) {

   318   if (__first2 == __last2)

   319     return __last1;

   320   else {

   321     _ForwardIter1 __result = __last1;

   322     for (;;) {

   323       _ForwardIter1 __new_result = search(__first1, __last1, __first2, __last2, __comp);

   324       if (__new_result == __last1)

   325         return __result;

   326       else {

   327         __result = __new_result;

   328         __first1 = __new_result;

   329         ++__first1;

   330       }

   331     }

   332   }

   333 }

   334 

   335 _STLP_MOVE_TO_STD_NAMESPACE

   336 

   337 // find_end for bidirectional iterators.  Requires partial specialization.

   338 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

   339 

   340 #  ifndef _STLP_INTERNAL_ITERATOR_H

   341 _STLP_END_NAMESPACE

   342 #    include <stl/_iterator.h>

   343 _STLP_BEGIN_NAMESPACE

   344 #  endif /*_STLP_INTERNAL_ITERATOR_H*/

   345 

   346 _STLP_MOVE_TO_PRIV_NAMESPACE

   347 

   348 template <class _BidirectionalIter1, class _BidirectionalIter2,

   349           class _BinaryPredicate>

   350 _BidirectionalIter1

   351 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,

   352            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,

   353            const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,

   354            _BinaryPredicate __comp) {

   355   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;

   356   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;

   357 

   358   _RevIter1 __rlast1(__first1);

   359   _RevIter2 __rlast2(__first2);

   360   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,

   361                                _RevIter2(__last2), __rlast2,

   362                                __comp);

   363 

   364   if (__rresult == __rlast1)

   365     return __last1;

   366   else {

   367     _BidirectionalIter1 __result = __rresult.base();

   368     advance(__result, -distance(__first2, __last2));

   369     return __result;

   370   }

   371 }

   372 

   373 _STLP_MOVE_TO_STD_NAMESPACE

   374 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */

   375 

   376 template <class _ForwardIter1, class _ForwardIter2,

   377           class _BinaryPredicate>

   378 _ForwardIter1

   379 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,

   380          _ForwardIter2 __first2, _ForwardIter2 __last2,

   381          _BinaryPredicate __comp) {

   382   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

   383   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

   384   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,

   385 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

   386                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),

   387                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),

   388 #else

   389                                forward_iterator_tag(),

   390                                forward_iterator_tag(),

   391 #endif

   392                                __comp);

   393 }

   394 

   395 _STLP_MOVE_TO_PRIV_NAMESPACE

   396 

   397 template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>

   398 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,

   399                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {

   400   _Distance __len = distance(__first, __last);

   401   _Distance __half;

   402   _ForwardIter __middle;

   403 

   404   while (__len > 0) {

   405     __half = __len >> 1;

   406     __middle = __first;

   407     advance(__middle, __half);

   408     if (__comp1(*__middle, __val)) {

   409       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

   410       __first = __middle;

   411       ++__first;

   412       __len = __len - __half - 1;

   413     }

   414     else

   415       __len = __half;

   416   }

   417   return __first;

   418 }

   419 

   420 _STLP_MOVE_TO_STD_NAMESPACE

   421 

   422 _STLP_END_NAMESPACE

   423 

   424 #endif /* _STLP_ALGOBASE_C */

   425 

   426 // Local Variables:

   427 // mode:C++

   428 // End:
test