Mercurialtest / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
epoc32/include/stdapis/stlportv5/stl/_algo.h
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  * 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 

    26 /* NOTE: This is an internal header file, included by other STL headers.

    27  *   You should not attempt to use it directly.

    28  */

    29 

    30 #ifndef _STLP_INTERNAL_ALGO_H

    31 #define _STLP_INTERNAL_ALGO_H

    32 

    33 #ifndef _STLP_INTERNAL_ALGOBASE_H

    34 #  include <stl/_algobase.h>

    35 #endif

    36 

    37 #ifndef _STLP_INTERNAL_HEAP_H

    38 #  include <stl/_heap.h>

    39 #endif

    40 

    41 #ifndef _STLP_INTERNAL_ITERATOR_H

    42 #  include <stl/_iterator.h>

    43 #endif

    44 

    45 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H

    46 #  include <stl/_function_base.h>

    47 #endif

    48 

    49 #if defined (__SUNPRO_CC) && !defined (_STLP_INTERNAL_CSTDIO)

    50 // remove() conflict

    51 #  include <stl/_cstdio.h>

    52 #endif

    53 

    54 _STLP_BEGIN_NAMESPACE

    55 

    56 // for_each.  Apply a function to every element of a range.

    57 template <class _InputIter, class _Function>

    58 _STLP_INLINE_LOOP _Function

    59 for_each(_InputIter __first, _InputIter __last, _Function __f) {

    60   for ( ; __first != __last; ++__first)

    61     __f(*__first);

    62   return __f;

    63 }

    64 

    65 // count_if

    66 template <class _InputIter, class _Predicate>

    67 _STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter)

    68 count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {

    69   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

    70   _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;

    71   for ( ; __first != __last; ++__first) {

    72     if (__pred(*__first))

    73       ++__n;

    74   }

    75   return __n;

    76 }

    77 

    78 // adjacent_find.

    79 

    80 template <class _ForwardIter, class _BinaryPredicate>

    81 _STLP_INLINE_LOOP _ForwardIter

    82 adjacent_find(_ForwardIter __first, _ForwardIter __last,

    83               _BinaryPredicate __binary_pred) {

    84   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

    85   if (__first == __last)

    86     return __last;

    87   _ForwardIter __next = __first;

    88   while(++__next != __last) {

    89     if (__binary_pred(*__first, *__next))

    90       return __first;

    91     __first = __next;

    92   }

    93   return __last;

    94 }

    95 

    96 template <class _ForwardIter>

    97 _STLP_INLINE_LOOP _ForwardIter

    98 adjacent_find(_ForwardIter __first, _ForwardIter __last) {

    99   return adjacent_find(__first, __last,

   100                        _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _ForwardIter)));

   101 }

   102 

   103 #if !defined (_STLP_NO_ANACHRONISMS)

   104 template <class _InputIter, class _Tp, class _Size>

   105 _STLP_INLINE_LOOP void

   106 count(_InputIter __first, _InputIter __last, const _Tp& __val, _Size& __n) {

   107   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   108     for ( ; __first != __last; ++__first)

   109       if (*__first == __val)

   110         ++__n;

   111 }

   112 

   113 template <class _InputIter, class _Predicate, class _Size>

   114 _STLP_INLINE_LOOP void

   115 count_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) {

   116   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   117   for ( ; __first != __last; ++__first)

   118     if (__pred(*__first))

   119       ++__n;

   120 }

   121 #endif

   122 

   123 template <class _ForwardIter1, class _ForwardIter2>

   124 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,

   125                      _ForwardIter2 __first2, _ForwardIter2 __last2);

   126 

   127 // search_n.  Search for __count consecutive copies of __val.

   128 template <class _ForwardIter, class _Integer, class _Tp>

   129 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

   130                       _Integer __count, const _Tp& __val);

   131 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>

   132 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

   133                       _Integer __count, const _Tp& __val, _BinaryPred __binary_pred);

   134 

   135 template <class _InputIter, class _ForwardIter>

   136 inline _InputIter find_first_of(_InputIter __first1, _InputIter __last1,

   137                                 _ForwardIter __first2, _ForwardIter __last2) {

   138   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

   139   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

   140   return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2,

   141                                     _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _InputIter)));

   142 }

   143 

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

   145 inline _InputIter

   146 find_first_of(_InputIter __first1, _InputIter __last1,

   147               _ForwardIter __first2, _ForwardIter __last2, _BinaryPredicate __comp) {

   148   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

   149   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

   150   return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2, __comp);

   151 }

   152 

   153 template <class _ForwardIter1, class _ForwardIter2>

   154 _ForwardIter1

   155 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,

   156          _ForwardIter2 __first2, _ForwardIter2 __last2);

   157 

   158 // swap_ranges

   159 template <class _ForwardIter1, class _ForwardIter2>

   160 _STLP_INLINE_LOOP _ForwardIter2

   161 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2) {

   162   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

   163   for ( ; __first1 != __last1; ++__first1, ++__first2)

   164     iter_swap(__first1, __first2);

   165   return __first2;

   166 }

   167 

   168 // transform

   169 template <class _InputIter, class _OutputIter, class _UnaryOperation>

   170 _STLP_INLINE_LOOP _OutputIter

   171 transform(_InputIter __first, _InputIter __last, _OutputIter __result, _UnaryOperation __opr) {

   172   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   173   for ( ; __first != __last; ++__first, ++__result)

   174     *__result = __opr(*__first);

   175   return __result;

   176 }

   177 template <class _InputIter1, class _InputIter2, class _OutputIter, class _BinaryOperation>

   178 _STLP_INLINE_LOOP _OutputIter

   179 transform(_InputIter1 __first1, _InputIter1 __last1,

   180           _InputIter2 __first2, _OutputIter __result,_BinaryOperation __binary_op) {

   181   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

   182   for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)

   183     *__result = __binary_op(*__first1, *__first2);

   184   return __result;

   185 }

   186 

   187 // replace_if, replace_copy, replace_copy_if

   188 

   189 template <class _ForwardIter, class _Predicate, class _Tp>

   190 _STLP_INLINE_LOOP void

   191 replace_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const _Tp& __new_value) {

   192   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   193   for ( ; __first != __last; ++__first)

   194     if (__pred(*__first))

   195       *__first = __new_value;

   196 }

   197 

   198 template <class _InputIter, class _OutputIter, class _Tp>

   199 _STLP_INLINE_LOOP  _OutputIter

   200 replace_copy(_InputIter __first, _InputIter __last,_OutputIter __result,

   201              const _Tp& __old_value, const _Tp& __new_value) {

   202   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   203   for ( ; __first != __last; ++__first, ++__result)

   204     *__result = *__first == __old_value ? __new_value : *__first;

   205   return __result;

   206 }

   207 

   208 template <class _Iterator, class _OutputIter, class _Predicate, class _Tp>

   209 _STLP_INLINE_LOOP _OutputIter

   210 replace_copy_if(_Iterator __first, _Iterator __last,

   211                 _OutputIter __result,

   212                 _Predicate __pred, const _Tp& __new_value) {

   213   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   214   for ( ; __first != __last; ++__first, ++__result)

   215     *__result = __pred(*__first) ? __new_value : *__first;

   216   return __result;

   217 }

   218 

   219 // generate and generate_n

   220 

   221 template <class _ForwardIter, class _Generator>

   222 _STLP_INLINE_LOOP void

   223 generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {

   224   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   225   for ( ; __first != __last; ++__first)

   226     *__first = __gen();

   227 }

   228 

   229 template <class _OutputIter, class _Size, class _Generator>

   230 _STLP_INLINE_LOOP void

   231 generate_n(_OutputIter __first, _Size __n, _Generator __gen) {

   232   for ( ; __n > 0; --__n, ++__first)

   233     *__first = __gen();

   234 }

   235 

   236 // remove, remove_if, remove_copy, remove_copy_if

   237 

   238 template <class _InputIter, class _OutputIter, class _Tp>

   239 _STLP_INLINE_LOOP _OutputIter

   240 remove_copy(_InputIter __first, _InputIter __last,_OutputIter __result, const _Tp& __val) {

   241   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   242   for ( ; __first != __last; ++__first) {

   243     if (!(*__first == __val)) {

   244       *__result = *__first;

   245       ++__result;

   246     }

   247   }

   248   return __result;

   249 }

   250 

   251 template <class _InputIter, class _OutputIter, class _Predicate>

   252 _STLP_INLINE_LOOP _OutputIter

   253 remove_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred) {

   254   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   255   for ( ; __first != __last; ++__first) {

   256     if (!__pred(*__first)) {

   257       *__result = *__first;

   258       ++__result;

   259     }

   260   }

   261   return __result;

   262 }

   263 

   264 template <class _ForwardIter, class _Tp>

   265 _STLP_INLINE_LOOP _ForwardIter

   266 remove(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {

   267   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   268   __first = find(__first, __last, __val);

   269   if (__first == __last)

   270     return __first;

   271   else {

   272     _ForwardIter __next = __first;

   273     return remove_copy(++__next, __last, __first, __val);

   274   }

   275 }

   276 

   277 template <class _ForwardIter, class _Predicate>

   278 _STLP_INLINE_LOOP _ForwardIter

   279 remove_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {

   280   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   281   __first = find_if(__first, __last, __pred);

   282   if ( __first == __last )

   283     return __first;

   284   else {

   285     _ForwardIter __next = __first;

   286     return remove_copy_if(++__next, __last, __first, __pred);

   287   }

   288 }

   289 

   290 // unique and unique_copy

   291 template <class _InputIter, class _OutputIter>

   292 _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result);

   293 

   294 template <class _InputIter, class _OutputIter, class _BinaryPredicate>

   295 _OutputIter unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,

   296                         _BinaryPredicate __binary_pred);

   297 

   298 template <class _ForwardIter>

   299 inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {

   300   __first = adjacent_find(__first, __last);

   301   return unique_copy(__first, __last, __first);

   302 }

   303 

   304 template <class _ForwardIter, class _BinaryPredicate>

   305 inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,

   306                            _BinaryPredicate __binary_pred) {

   307   __first = adjacent_find(__first, __last, __binary_pred);

   308   return unique_copy(__first, __last, __first, __binary_pred);

   309 }

   310 

   311 // reverse and reverse_copy, and their auxiliary functions

   312 

   313 template <class _BidirectionalIter>

   314 _STLP_INLINE_LOOP void

   315 __reverse(_BidirectionalIter __first, _BidirectionalIter __last, const bidirectional_iterator_tag &) {

   316   for (; __first != __last && __first != --__last; ++__first)

   317     iter_swap(__first,__last);

   318 }

   319 

   320 

   321 template <class _RandomAccessIter>

   322 _STLP_INLINE_LOOP void

   323 __reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) {

   324   for (; __first < __last; ++__first)

   325     iter_swap(__first, --__last);

   326 }

   327 

   328 template <class _BidirectionalIter>

   329 inline void

   330 reverse(_BidirectionalIter __first, _BidirectionalIter __last) {

   331   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   332   __reverse(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _BidirectionalIter));

   333 }

   334 

   335 template <class _BidirectionalIter, class _OutputIter>

   336 _STLP_INLINE_LOOP

   337 _OutputIter reverse_copy(_BidirectionalIter __first,

   338                          _BidirectionalIter __last,

   339                          _OutputIter __result) {

   340   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   341   while (__first != __last) {

   342     --__last;

   343     *__result = *__last;

   344     ++__result;

   345   }

   346   return __result;

   347 }

   348 

   349 _STLP_MOVE_TO_PRIV_NAMESPACE

   350 

   351 // rotate and rotate_copy, and their auxiliary functions

   352 template <class _EuclideanRingElement>

   353 _STLP_INLINE_LOOP

   354 _EuclideanRingElement __gcd(_EuclideanRingElement __m,

   355                             _EuclideanRingElement __n) {

   356   while (__n != 0) {

   357     _EuclideanRingElement __t = __m % __n;

   358     __m = __n;

   359     __n = __t;

   360   }

   361   return __m;

   362 }

   363 

   364 _STLP_MOVE_TO_STD_NAMESPACE

   365 

   366 template <class _ForwardIter>

   367 void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last);

   368 

   369 template <class _ForwardIter, class _OutputIter>

   370 inline _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,

   371                                _ForwardIter __last, _OutputIter __result) {

   372   return copy(__first, __middle, copy(__middle, __last, __result));

   373 }

   374 

   375 // random_shuffle

   376 

   377 template <class _RandomAccessIter>

   378 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last);

   379 

   380 template <class _RandomAccessIter, class _RandomNumberGenerator>

   381 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,

   382                     _RandomNumberGenerator& __rand);

   383 

   384 #if !defined (_STLP_NO_EXTENSIONS)

   385 // random_sample and random_sample_n (extensions, not part of the standard).

   386 

   387 template <class _ForwardIter, class _OutputIter, class _Distance>

   388 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

   389                             _OutputIter __out_ite, const _Distance __n);

   390 

   391 template <class _ForwardIter, class _OutputIter, class _Distance,

   392           class _RandomNumberGenerator>

   393 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

   394                             _OutputIter __out_ite, const _Distance __n,

   395                             _RandomNumberGenerator& __rand);

   396 

   397 template <class _InputIter, class _RandomAccessIter>

   398 _RandomAccessIter

   399 random_sample(_InputIter __first, _InputIter __last,

   400               _RandomAccessIter __out_first, _RandomAccessIter __out_last);

   401 

   402 template <class _InputIter, class _RandomAccessIter,

   403           class _RandomNumberGenerator>

   404 _RandomAccessIter

   405 random_sample(_InputIter __first, _InputIter __last,

   406               _RandomAccessIter __out_first, _RandomAccessIter __out_last,

   407               _RandomNumberGenerator& __rand);

   408 

   409 #endif /* _STLP_NO_EXTENSIONS */

   410 

   411 // partition, stable_partition, and their auxiliary functions

   412 

   413 template <class _ForwardIter, class _Predicate>

   414 _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred);

   415 

   416 template <class _ForwardIter, class _Predicate>

   417 _ForwardIter

   418 stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred);

   419 

   420 // sort() and its auxiliary functions.

   421 _STLP_MOVE_TO_PRIV_NAMESPACE

   422 

   423 template <class _Size>

   424 inline _Size __lg(_Size __n) {

   425   _Size __k;

   426   for (__k = 0; __n != 1; __n >>= 1) ++__k;

   427   return __k;

   428 }

   429 

   430 _STLP_MOVE_TO_STD_NAMESPACE

   431 

   432 template <class _RandomAccessIter>

   433 void sort(_RandomAccessIter __first, _RandomAccessIter __last);

   434 template <class _RandomAccessIter, class _Compare>

   435 void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp);

   436 

   437 // stable_sort() and its auxiliary functions.

   438 template <class _RandomAccessIter>

   439 void stable_sort(_RandomAccessIter __first,

   440                  _RandomAccessIter __last);

   441 

   442 template <class _RandomAccessIter, class _Compare>

   443 void stable_sort(_RandomAccessIter __first,

   444                  _RandomAccessIter __last, _Compare __comp);

   445 

   446 // partial_sort, partial_sort_copy, and auxiliary functions.

   447 

   448 template <class _RandomAccessIter>

   449 void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,

   450                   _RandomAccessIter __last);

   451 

   452 template <class _RandomAccessIter, class _Compare>

   453 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,

   454                   _RandomAccessIter __last, _Compare __comp);

   455 

   456 template <class _InputIter, class _RandomAccessIter>

   457 _RandomAccessIter

   458 partial_sort_copy(_InputIter __first, _InputIter __last,

   459                   _RandomAccessIter __result_first, _RandomAccessIter __result_last);

   460 

   461 template <class _InputIter, class _RandomAccessIter, class _Compare>

   462 _RandomAccessIter

   463 partial_sort_copy(_InputIter __first, _InputIter __last,

   464                   _RandomAccessIter __result_first,

   465                   _RandomAccessIter __result_last, _Compare __comp);

   466 

   467 // nth_element() and its auxiliary functions.

   468 template <class _RandomAccessIter>

   469 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

   470                  _RandomAccessIter __last);

   471 

   472 template <class _RandomAccessIter, class _Compare>

   473 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

   474                  _RandomAccessIter __last, _Compare __comp);

   475 

   476 // auxiliary class for lower_bound, etc.

   477 _STLP_MOVE_TO_PRIV_NAMESPACE

   478 

   479 template <class _T1, class _T2>

   480 struct __less_2 {

   481   bool operator() (const _T1& __x, const _T2& __y) const { return __x < __y ; }

   482 };

   483 

   484 template <class _T1, class _T2>

   485 __less_2<_T1,_T2> __less2(_T1*, _T2* ) { return __less_2<_T1, _T2>(); }

   486 

   487 #if defined (_STLP_FUNCTION_PARTIAL_ORDER)

   488 template <class _Tp>

   489 less<_Tp> __less2(_Tp*, _Tp* ) { return less<_Tp>(); }

   490 #endif

   491 

   492 _STLP_MOVE_TO_STD_NAMESPACE

   493 

   494 // Binary search (lower_bound, upper_bound, equal_range, binary_search).

   495 template <class _ForwardIter, class _Tp>

   496 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,

   497                                    const _Tp& __val) {

   498   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   499   return _STLP_PRIV __lower_bound(__first, __last, __val,

   500                                   _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),

   501                                   _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)),

   502                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   503 }

   504 

   505 template <class _ForwardIter, class _Tp, class _Compare>

   506 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,

   507                                 const _Tp& __val, _Compare __comp) {

   508   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   509   return _STLP_PRIV __lower_bound(__first, __last, __val, __comp, __comp,

   510                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   511 }

   512 

   513 _STLP_MOVE_TO_PRIV_NAMESPACE

   514 

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

   516 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,

   517                            _Compare1 __comp1, _Compare2 __comp2, _Distance*);

   518 

   519 _STLP_MOVE_TO_STD_NAMESPACE

   520 

   521 template <class _ForwardIter, class _Tp>

   522 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,

   523                                 const _Tp& __val) {

   524   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   525   return _STLP_PRIV __upper_bound(__first, __last, __val,

   526                                   _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),

   527                                   _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)),

   528                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   529 }

   530 

   531 template <class _ForwardIter, class _Tp, class _Compare>

   532 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,

   533                                 const _Tp& __val, _Compare __comp) {

   534   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   535   return _STLP_PRIV __upper_bound(__first, __last, __val, __comp, __comp,

   536                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   537 }

   538 

   539 _STLP_MOVE_TO_PRIV_NAMESPACE

   540 

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

   542 pair<_ForwardIter, _ForwardIter>

   543 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,

   544               _Compare1 __comp1, _Compare2 __comp2, _Distance*);

   545 

   546 _STLP_MOVE_TO_STD_NAMESPACE

   547 

   548 template <class _ForwardIter, class _Tp>

   549 inline pair<_ForwardIter, _ForwardIter>

   550 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {

   551   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   552   return _STLP_PRIV __equal_range(__first, __last, __val,

   553                                   _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),

   554                                   _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)),

   555                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   556 }

   557 

   558 template <class _ForwardIter, class _Tp, class _Compare>

   559 inline pair<_ForwardIter, _ForwardIter>

   560 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,

   561             _Compare __comp) {

   562   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   563   return _STLP_PRIV __equal_range(__first, __last, __val, __comp, __comp,

   564                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   565 }

   566 

   567 template <class _ForwardIter, class _Tp>

   568 inline bool binary_search(_ForwardIter __first, _ForwardIter __last,

   569                    const _Tp& __val) {

   570   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   571   _ForwardIter __i = _STLP_PRIV __lower_bound(__first, __last, __val,

   572                                               _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),

   573                                               _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)),

   574                                               _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   575   return __i != __last && !(__val < *__i);

   576 }

   577 

   578 template <class _ForwardIter, class _Tp, class _Compare>

   579 inline bool binary_search(_ForwardIter __first, _ForwardIter __last,

   580                           const _Tp& __val,

   581                           _Compare __comp) {

   582   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

   583   _ForwardIter __i = _STLP_PRIV __lower_bound(__first, __last, __val, __comp, __comp,

   584                                               _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   585   return __i != __last && !__comp(__val, *__i);

   586 }

   587 

   588 // merge, with and without an explicitly supplied comparison function.

   589 

   590 template <class _InputIter1, class _InputIter2, class _OutputIter>

   591 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,

   592                   _InputIter2 __first2, _InputIter2 __last2,

   593                   _OutputIter __result);

   594 

   595 template <class _InputIter1, class _InputIter2, class _OutputIter,

   596           class _Compare>

   597 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,

   598                   _InputIter2 __first2, _InputIter2 __last2,

   599                   _OutputIter __result, _Compare __comp);

   600 

   601 

   602 // inplace_merge and its auxiliary functions.

   603 

   604 

   605 template <class _BidirectionalIter>

   606 void inplace_merge(_BidirectionalIter __first,

   607                    _BidirectionalIter __middle,

   608                    _BidirectionalIter __last) ;

   609 

   610 template <class _BidirectionalIter, class _Compare>

   611 void inplace_merge(_BidirectionalIter __first,

   612                    _BidirectionalIter __middle,

   613                    _BidirectionalIter __last, _Compare __comp);

   614 

   615 // Set algorithms: includes, set_union, set_intersection, set_difference,

   616 // set_symmetric_difference.  All of these algorithms have the precondition

   617 // that their input ranges are sorted and the postcondition that their output

   618 // ranges are sorted.

   619 

   620 template <class _InputIter1, class _InputIter2>

   621 bool includes(_InputIter1 __first1, _InputIter1 __last1,

   622               _InputIter2 __first2, _InputIter2 __last2);

   623 

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

   625 bool includes(_InputIter1 __first1, _InputIter1 __last1,

   626               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp);

   627 

   628 template <class _InputIter1, class _InputIter2, class _OutputIter>

   629 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,

   630                       _InputIter2 __first2, _InputIter2 __last2,

   631                       _OutputIter __result);

   632 

   633 template <class _InputIter1, class _InputIter2, class _OutputIter,

   634           class _Compare>

   635 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,

   636                       _InputIter2 __first2, _InputIter2 __last2,

   637                       _OutputIter __result, _Compare __comp);

   638 

   639 template <class _InputIter1, class _InputIter2, class _OutputIter>

   640 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,

   641                              _InputIter2 __first2, _InputIter2 __last2,

   642                              _OutputIter __result);

   643 

   644 template <class _InputIter1, class _InputIter2, class _OutputIter,

   645           class _Compare>

   646 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,

   647                              _InputIter2 __first2, _InputIter2 __last2,

   648                              _OutputIter __result, _Compare __comp);

   649 

   650 

   651 

   652 template <class _InputIter1, class _InputIter2, class _OutputIter>

   653 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,

   654                            _InputIter2 __first2, _InputIter2 __last2,

   655                            _OutputIter __result);

   656 

   657 template <class _InputIter1, class _InputIter2, class _OutputIter,

   658           class _Compare>

   659 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,

   660                            _InputIter2 __first2, _InputIter2 __last2,

   661                            _OutputIter __result, _Compare __comp);

   662 

   663 template <class _InputIter1, class _InputIter2, class _OutputIter>

   664 _OutputIter

   665 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

   666                          _InputIter2 __first2, _InputIter2 __last2,

   667                          _OutputIter __result);

   668 

   669 

   670 template <class _InputIter1, class _InputIter2, class _OutputIter,

   671           class _Compare>

   672 _OutputIter

   673 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

   674                          _InputIter2 __first2, _InputIter2 __last2,

   675                          _OutputIter __result,

   676                          _Compare __comp);

   677 

   678 

   679 // min_element and max_element, with and without an explicitly supplied

   680 // comparison function.

   681 

   682 template <class _ForwardIter>

   683 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last);

   684 template <class _ForwardIter, class _Compare>

   685 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,

   686                             _Compare __comp);

   687 

   688 template <class _ForwardIter>

   689 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last);

   690 

   691 template <class _ForwardIter, class _Compare>

   692 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,

   693                             _Compare __comp);

   694 

   695 // next_permutation and prev_permutation, with and without an explicitly

   696 // supplied comparison function.

   697 

   698 template <class _BidirectionalIter>

   699 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last);

   700 

   701 template <class _BidirectionalIter, class _Compare>

   702 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

   703                       _Compare __comp);

   704 

   705 

   706 template <class _BidirectionalIter>

   707 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last);

   708 

   709 

   710 template <class _BidirectionalIter, class _Compare>

   711 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

   712                       _Compare __comp);

   713 

   714 #if !defined (_STLP_NO_EXTENSIONS)

   715 // is_heap, a predicate testing whether or not a range is

   716 // a heap.  This function is an extension, not part of the C++

   717 // standard.

   718 

   719 template <class _RandomAccessIter>

   720 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last);

   721 

   722 template <class _RandomAccessIter, class _StrictWeakOrdering>

   723 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,

   724              _StrictWeakOrdering __comp);

   725 

   726 // is_sorted, a predicated testing whether a range is sorted in

   727 // nondescending order.  This is an extension, not part of the C++

   728 // standard.

   729 _STLP_MOVE_TO_PRIV_NAMESPACE

   730 

   731 template <class _ForwardIter, class _StrictWeakOrdering>

   732 bool __is_sorted(_ForwardIter __first, _ForwardIter __last,

   733                  _StrictWeakOrdering __comp);

   734 

   735 _STLP_MOVE_TO_STD_NAMESPACE

   736 template <class _ForwardIter>

   737 inline bool is_sorted(_ForwardIter __first, _ForwardIter __last) {

   738   return _STLP_PRIV __is_sorted(__first, __last,

   739                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _ForwardIter)));

   740 }

   741 

   742 template <class _ForwardIter, class _StrictWeakOrdering>

   743 inline bool is_sorted(_ForwardIter __first, _ForwardIter __last,

   744                       _StrictWeakOrdering __comp) {

   745   return _STLP_PRIV __is_sorted(__first, __last, __comp);

   746 }

   747 #endif

   748 

   749 _STLP_END_NAMESPACE

   750 

   751 #if !defined (_STLP_LINK_TIME_INSTANTIATION)

   752 #  include <stl/_algo.c>

   753 #endif

   754 

   755 #endif /* _STLP_INTERNAL_ALGO_H */

   756 

   757 // Local Variables:

   758 // mode:C++

   759 // End:

   760
test