Mercurialtest / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
epoc32/include/stdapis/stlportv5/stl/_algobase.c
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
parent 3 e1b950c65cb4
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  * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.

     4  *

     5  * Copyright (c) 1994

     6  * Hewlett-Packard Company

     7  *

     8  * Copyright (c) 1996,1997

     9  * Silicon Graphics Computer Systems, Inc.

    10  *

    11  * Copyright (c) 1997

    12  * Moscow Center for SPARC Technology

    13  *

    14  * Copyright (c) 1999

    15  * Boris Fomitchev

    16  *

    17  * This material is provided "as is", with absolutely no warranty expressed

    18  * or implied. Any use is at your own risk.

    19  *

    20  * Permission to use or copy this software for any purpose is hereby granted

    21  * without fee, provided the above notices are retained on all copies.

    22  * Permission to modify the code and to distribute modified code is granted,

    23  * provided the above notices are retained, and a notice that the code was

    24  * modified is included with the above copyright notice.

    25  *

    26  */

    27 #ifndef _STLP_ALGOBASE_C

    28 #define _STLP_ALGOBASE_C

    29 

    30 #ifndef _STLP_INTERNAL_ALGOBASE_H

    31 #  include <stl/_algobase.h>

    32 #endif

    33 

    34 _STLP_BEGIN_NAMESPACE

    35 

    36 template <class _InputIter1, class _InputIter2>

    37 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,

    38                              _InputIter2 __first2, _InputIter2 __last2) {

    39   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

    40   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

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

    42         ; ++__first1, ++__first2) {

    43     if (*__first1 < *__first2) {

    44       return true;

    45     }

    46     if (*__first2 < *__first1)

    47       return false;

    48   }

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

    50 }

    51 

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

    53 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,

    54                              _InputIter2 __first2, _InputIter2 __last2,

    55                              _Compare __comp) {

    56   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

    57   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

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

    59         ; ++__first1, ++__first2) {

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

    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 __p1(__first2);

   233 

   234   if ( ++__p1 == __last2 ) {

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

   236       ++__first1;

   237     }

   238     return __first1;

   239   }

   240 

   241   // General case.

   242 

   243   for ( ; ; ) { // __first1 != __last1 will be checked below

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

   245       ++__first1;

   246     }

   247     if (__first1 == __last1) {

   248       return __last1;

   249     }

   250     _ForwardIter2 __p = __p1;

   251     _ForwardIter1 __current = __first1;

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

   253 

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

   255       if (++__p == __last2)

   256         return __first1;

   257       if (++__current == __last1)

   258         return __last1;

   259     }

   260 

   261     ++__first1;

   262   }

   263   return __first1;

   264 }

   265 

   266 _STLP_MOVE_TO_PRIV_NAMESPACE

   267 

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

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

   270 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,

   271                            _ForwardIter __first2, _ForwardIter __last2,

   272                            _BinaryPredicate __comp) {

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

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

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

   276         return __first1;

   277       }

   278     }

   279   }

   280   return __last1;

   281 }

   282 

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

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

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

   286 // is much faster than for forward iterators.

   287 

   288 // find_end for forward iterators.

   289 template <class _ForwardIter1, class _ForwardIter2,

   290   class _BinaryPredicate>

   291 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,

   292                          _ForwardIter2 __first2, _ForwardIter2 __last2,

   293                          const forward_iterator_tag &, const forward_iterator_tag &,

   294                          _BinaryPredicate __comp) {

   295   if (__first2 == __last2)

   296     return __last1;

   297   else {

   298     _ForwardIter1 __result = __last1;

   299     for (;;) {

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

   301       if (__new_result == __last1)

   302         return __result;

   303       else {

   304         __result = __new_result;

   305         __first1 = __new_result;

   306         ++__first1;

   307       }

   308     }

   309   }

   310 }

   311 

   312 _STLP_MOVE_TO_STD_NAMESPACE

   313 

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

   315 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

   316 

   317 #  ifndef _STLP_INTERNAL_ITERATOR_H

   318 _STLP_END_NAMESPACE

   319 #    include <stl/_iterator.h>

   320 _STLP_BEGIN_NAMESPACE

   321 #  endif /*_STLP_INTERNAL_ITERATOR_H*/

   322 

   323 _STLP_MOVE_TO_PRIV_NAMESPACE

   324 

   325 template <class _BidirectionalIter1, class _BidirectionalIter2,

   326           class _BinaryPredicate>

   327 _BidirectionalIter1

   328 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,

   329            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,

   330            const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,

   331            _BinaryPredicate __comp) {

   332   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;

   333   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;

   334 

   335   _RevIter1 __rlast1(__first1);

   336   _RevIter2 __rlast2(__first2);

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

   338                                _RevIter2(__last2), __rlast2,

   339                                __comp);

   340 

   341   if (__rresult == __rlast1)

   342     return __last1;

   343   else {

   344     _BidirectionalIter1 __result = __rresult.base();

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

   346     return __result;

   347   }

   348 }

   349 

   350 _STLP_MOVE_TO_STD_NAMESPACE

   351 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */

   352 

   353 template <class _ForwardIter1, class _ForwardIter2,

   354           class _BinaryPredicate>

   355 _ForwardIter1

   356 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,

   357          _ForwardIter2 __first2, _ForwardIter2 __last2,

   358          _BinaryPredicate __comp) {

   359   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

   360   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

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

   362 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

   363                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),

   364                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),

   365 #else

   366                                forward_iterator_tag(),

   367                                forward_iterator_tag(),

   368 #endif

   369                                __comp);

   370 }

   371 

   372 _STLP_MOVE_TO_PRIV_NAMESPACE

   373 

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

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

   376                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {

   377   _Distance __len = distance(__first, __last);

   378   _Distance __half;

   379   _ForwardIter __middle;

   380 

   381   while (__len > 0) {

   382     __half = __len >> 1;

   383     __middle = __first;

   384     advance(__middle, __half);

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

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

   387       __first = __middle;

   388       ++__first;

   389       __len = __len - __half - 1;

   390     }

   391     else

   392       __len = __half;

   393   }

   394   if (&__comp2) {/* do nothing. to avoid warnings */} 

   395   return __first;

   396 }

   397 

   398 _STLP_MOVE_TO_STD_NAMESPACE

   399 

   400 _STLP_END_NAMESPACE

   401 

   402 #endif /* _STLP_ALGOBASE_C */

   403 

   404 // Local Variables:

   405 // mode:C++

   406 // End:
test