Mercurialtest / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
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:
test