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:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
parent 2 epoc32/include/stdapis/stlport/stl/_algo.h@2fe1408b6811
child 4 837f303aceeb
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations 
     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_TEMPBUF_H

    38 #  include <stl/_tempbuf.h>

    39 # endif

    40 

    41 # ifndef _STLP_INTERNAL_HEAP_H

    42 #  include <stl/_heap.h>

    43 # endif

    44 

    45 # ifndef _STLP_INTERNAL_ITERATOR_H

    46 #  include <stl/_iterator.h>

    47 # endif

    48 

    49 # ifndef _STLP_INTERNAL_FUNCTION_BASE_H

    50 #  include <stl/_function_base.h>

    51 # endif

    52 

    53 # ifdef __SUNPRO_CC

    54 // remove() conflict

    55 #  include <cstdio>

    56 # endif

    57 

    58 _STLP_BEGIN_NAMESPACE

    59 

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

    61 template <class _InputIter, class _Function>

    62 _STLP_INLINE_LOOP _Function 

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

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

    65     __f(*__first);

    66   return __f;

    67 }

    68 

    69 // count_if

    70 template <class _InputIter, class _Predicate>

    71 _STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter)

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

    73   _STLP_DEBUG_CHECK(__check_range(__first, __last))

    74 _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;

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

    76     if (__pred(*__first))

    77       ++__n;

    78   return __n;

    79 }

    80 

    81 // adjacent_find.

    82 

    83 template <class _ForwardIter, class _BinaryPredicate>

    84 _STLP_INLINE_LOOP _ForwardIter 

    85 adjacent_find(_ForwardIter __first, _ForwardIter __last,

    86               _BinaryPredicate __binary_pred) {

    87   _STLP_DEBUG_CHECK(__check_range(__first, __last))

    88   if (__first == __last)

    89     return __last;

    90   _ForwardIter __next = __first;

    91   while(++__next != __last) {

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

    93       return __first;

    94     __first = __next;

    95   }

    96   return __last;

    97 }

    98 

    99 template <class _ForwardIter>

   100 _STLP_INLINE_LOOP _ForwardIter 

   101 adjacent_find(_ForwardIter __first, _ForwardIter __last) {

   102   return adjacent_find(__first, __last,

   103 		       __equal_to(_STLP_VALUE_TYPE(__first, _ForwardIter)));

   104 }

   105 

   106 # ifndef _STLP_NO_ANACHRONISMS

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

   108 _STLP_INLINE_LOOP void 

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

   110   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

   112       if (*__first == __val)

   113         ++__n;

   114 }

   115 

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

   117 _STLP_INLINE_LOOP void 

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

   119   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

   121     if (__pred(*__first))

   122       ++__n;

   123 }

   124 # endif

   125 

   126 template <class _ForwardIter1, class _ForwardIter2>

   127 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,

   128                      _ForwardIter2 __first2, _ForwardIter2 __last2);

   129 

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

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

   132 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

   133                       _Integer __count, const _Tp& __val);

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

   135 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

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

   137 

   138 template <class _InputIter, class _ForwardIter>

   139 inline _InputIter find_first_of(_InputIter __first1, _InputIter __last1,

   140                                 _ForwardIter __first2, _ForwardIter __last2) {

   141   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

   142   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

   143   return __find_first_of(__first1, __last1, __first2, __last2,__equal_to(_STLP_VALUE_TYPE(__first1, _InputIter)));

   144 }

   145 

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

   147 inline _InputIter 

   148 find_first_of(_InputIter __first1, _InputIter __last1,

   149               _ForwardIter __first2, _ForwardIter __last2,_BinaryPredicate __comp) {

   150   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

   151   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

   152   return __find_first_of(__first1, __last1, __first2, __last2,__comp);

   153 }

   154 

   155 template <class _ForwardIter1, class _ForwardIter2>

   156 _ForwardIter1 

   157 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 

   158          _ForwardIter2 __first2, _ForwardIter2 __last2);

   159 

   160 // swap_ranges

   161 template <class _ForwardIter1, class _ForwardIter2>

   162 _STLP_INLINE_LOOP _ForwardIter2 

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

   164   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

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

   166     iter_swap(__first1, __first2);

   167   return __first2;

   168 }

   169 

   170 // transform

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

   172 _STLP_INLINE_LOOP _OutputIter 

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

   174   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

   176     *__result = __opr(*__first);

   177   return __result;

   178 }

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

   180 _STLP_INLINE_LOOP _OutputIter 

   181 transform(_InputIter1 __first1, _InputIter1 __last1, 

   182           _InputIter2 __first2, _OutputIter __result,_BinaryOperation __binary_op) {

   183   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

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

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

   186   return __result;

   187 }

   188 

   189 // replace_if, replace_copy, replace_copy_if

   190 

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

   192 _STLP_INLINE_LOOP void 

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

   194   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

   196     if (__pred(*__first))

   197       *__first = __new_value;

   198 }

   199 

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

   201 _STLP_INLINE_LOOP  _OutputIter 

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

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

   204   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

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

   207   return __result;

   208 }

   209 

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

   211 _STLP_INLINE_LOOP _OutputIter 

   212 replace_copy_if(_Iterator __first, _Iterator __last,

   213                 _OutputIter __result,

   214                 _Predicate __pred, const _Tp& __new_value) {

   215   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

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

   218   return __result;

   219 }

   220 

   221 // generate and generate_n

   222 

   223 template <class _ForwardIter, class _Generator>

   224 _STLP_INLINE_LOOP void 

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

   226   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

   228     *__first = __gen();

   229 }

   230 

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

   232 _STLP_INLINE_LOOP _OutputIter 

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

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

   235     *__first = __gen();

   236   return __first;

   237 }

   238 

   239 // remove, remove_if, remove_copy, remove_copy_if

   240 

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

   242 _STLP_INLINE_LOOP _OutputIter 

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

   244   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

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

   247       *__result = *__first;

   248       ++__result;

   249     }

   250   return __result;

   251 }

   252 

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

   254 _STLP_INLINE_LOOP _OutputIter 

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

   256   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

   258     if (!__pred(*__first)) {

   259       *__result = *__first;

   260       ++__result;

   261     }

   262   return __result;

   263 }

   264 

   265 template <class _ForwardIter, class _Tp>

   266 _STLP_INLINE_LOOP _ForwardIter 

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

   268   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

   270   if (__first == __last)

   271     return __first;

   272   else { 

   273     _ForwardIter __next = __first;

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

   275   }

   276 }

   277 

   278 template <class _ForwardIter, class _Predicate>

   279 _STLP_INLINE_LOOP _ForwardIter 

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

   281   _STLP_DEBUG_CHECK(__check_range(__first, __last))

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

   283   if ( __first == __last )

   284     return __first;

   285   else {

   286     _ForwardIter __next = __first;

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

   288   }

   289 }

   290 

   291 // unique and unique_copy

   292 template <class _InputIter, class _OutputIter>

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

   294 

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

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

   297                         _BinaryPredicate __binary_pred);

   298 

   299 template <class _ForwardIter>

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

   301   __first = adjacent_find(__first, __last);

   302   return unique_copy(__first, __last, __first);

   303 }

   304 

   305 template <class _ForwardIter, class _BinaryPredicate>

   306 inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,

   307                     _BinaryPredicate __binary_pred) {

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

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

   310 }

   311 

   312 // reverse and reverse_copy, and their auxiliary functions

   313 

   314 template <class _BidirectionalIter>

   315 _STLP_INLINE_LOOP void 

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

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

   318     iter_swap(__first,__last);

   319 }

   320 

   321 

   322 template <class _RandomAccessIter>

   323 _STLP_INLINE_LOOP void 

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

   325   for (; __first < __last; ++__first) iter_swap(__first, --__last);

   326 }

   327 

   328 template <class _BidirectionalIter>

   329 inline void 

   330 reverse(_BidirectionalIter __first, _BidirectionalIter __last) {

   331   _STLP_DEBUG_CHECK(__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(__check_range(__first, __last))

   341   while (__first != __last) {

   342     --__last;

   343     *__result = *__last;

   344     ++__result;

   345   }

   346   return __result;

   347 }

   348 

   349 // rotate and rotate_copy, and their auxiliary functions

   350 

   351 template <class _EuclideanRingElement>

   352 _STLP_INLINE_LOOP

   353 _EuclideanRingElement __gcd(_EuclideanRingElement __m,

   354                             _EuclideanRingElement __n)

   355 {

   356   while (__n != 0) {

   357     _EuclideanRingElement __t = __m % __n;

   358     __m = __n;

   359     __n = __t;

   360   }

   361   return __m;

   362 }

   363 

   364 template <class _ForwardIter>

   365 _ForwardIter 

   366 rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last);

   367 

   368 template <class _ForwardIter, class _OutputIter>

   369 inline _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,

   370                                _ForwardIter __last, _OutputIter __result) {

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

   372 }

   373 

   374 // random_shuffle

   375 

   376 template <class _RandomAccessIter>

   377 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last);

   378 

   379 template <class _RandomAccessIter, class _RandomNumberGenerator>

   380 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,

   381                     _RandomNumberGenerator& __rand);

   382 

   383 # ifndef _STLP_NO_EXTENSIONS

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

   385 

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

   387 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

   388                             _OutputIter __stl_out, const _Distance __n);

   389 

   390 template <class _ForwardIter, class _OutputIter, class _Distance,

   391           class _RandomNumberGenerator>

   392 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

   393                             _OutputIter __stl_out, const _Distance __n,

   394                             _RandomNumberGenerator& __rand);

   395 

   396 template <class _InputIter, class _RandomAccessIter>

   397 _RandomAccessIter

   398 random_sample(_InputIter __first, _InputIter __last,

   399               _RandomAccessIter __out_first, _RandomAccessIter __out_last);

   400 

   401 template <class _InputIter, class _RandomAccessIter, 

   402           class _RandomNumberGenerator>

   403 _RandomAccessIter

   404 random_sample(_InputIter __first, _InputIter __last,

   405               _RandomAccessIter __out_first, _RandomAccessIter __out_last,

   406               _RandomNumberGenerator& __rand);

   407 

   408 # endif /* _STLP_NO_EXTENSIONS */

   409 

   410 // partition, stable_partition, and their auxiliary functions

   411 

   412 template <class _ForwardIter, class _Predicate>

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

   414 

   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 

   422 template <class _Size>

   423 inline _Size __lg(_Size __n) {

   424   _Size __k;

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

   426   return __k;

   427 }

   428 

   429 template <class _RandomAccessIter>

   430 void sort(_RandomAccessIter __first, _RandomAccessIter __last);

   431 template <class _RandomAccessIter, class _Compare>

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

   433 

   434 // stable_sort() and its auxiliary functions.

   435 template <class _RandomAccessIter>

   436 void stable_sort(_RandomAccessIter __first,

   437 		 _RandomAccessIter __last);

   438 

   439 template <class _RandomAccessIter, class _Compare>

   440 void stable_sort(_RandomAccessIter __first,

   441 		 _RandomAccessIter __last, _Compare __comp);

   442 

   443 // partial_sort, partial_sort_copy, and auxiliary functions.

   444 

   445 template <class _RandomAccessIter>

   446 void 

   447 partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last);

   448 

   449 template <class _RandomAccessIter, class _Compare>

   450 void 

   451 partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, 

   452              _RandomAccessIter __last, _Compare __comp);

   453 

   454 template <class _InputIter, class _RandomAccessIter>

   455 _RandomAccessIter

   456 partial_sort_copy(_InputIter __first, _InputIter __last,

   457                   _RandomAccessIter __result_first, _RandomAccessIter __result_last);

   458 

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

   460 _RandomAccessIter

   461 partial_sort_copy(_InputIter __first, _InputIter __last,

   462                   _RandomAccessIter __result_first,

   463                   _RandomAccessIter __result_last, _Compare __comp);

   464 

   465 // nth_element() and its auxiliary functions.  

   466 

   467 template <class _RandomAccessIter>

   468 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

   469                  _RandomAccessIter __last);

   470 

   471 template <class _RandomAccessIter, class _Compare>

   472 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,

   473                  _RandomAccessIter __last, _Compare __comp);

   474 

   475 // auxiliary class for lower_bound, etc.

   476 template <class _T1, class _T2>

   477 struct __less_2 {

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

   479 };

   480 

   481 template <class _T1, class _T2>

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

   483 

   484 #ifdef _STLP_FUNCTION_PARTIAL_ORDER

   485 template <class _Tp>

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

   487 #endif

   488 

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

   490 

   491 template <class _ForwardIter, class _Tp>

   492 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,

   493                                    const _Tp& __val) {

   494   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   495     return __lower_bound(__first, __last, __val, 

   496 			 __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),

   497 			 _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   498 }

   499 

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

   501 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,

   502                                 const _Tp& __val, _Compare __comp) {

   503   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   504   return __lower_bound(__first, __last, __val, __comp, _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   505 }

   506 

   507 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>

   508 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,

   509                            const _Tp& __val, _Compare __comp, _Distance*);

   510 

   511 template <class _ForwardIter, class _Tp>

   512 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,

   513                                 const _Tp& __val) {

   514   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   515   return __upper_bound(__first, __last, __val, 

   516 		       __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),

   517                        _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   518 }

   519 

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

   521 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,

   522                                 const _Tp& __val, _Compare __comp) {

   523   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   524   return __upper_bound(__first, __last, __val, __comp,

   525                        _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   526 }

   527 

   528 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>

   529 pair<_ForwardIter, _ForwardIter>

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

   531               _Compare __comp, _Distance*);

   532 

   533 template <class _ForwardIter, class _Tp>

   534 inline pair<_ForwardIter, _ForwardIter>

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

   536   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   537   return __equal_range(__first, __last, __val,  

   538 		       __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),

   539                        _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   540 }

   541 

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

   543 inline pair<_ForwardIter, _ForwardIter>

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

   545             _Compare __comp) {

   546   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   547   return __equal_range(__first, __last, __val, __comp,

   548                        _STLP_DISTANCE_TYPE(__first, _ForwardIter));

   549 } 

   550 

   551 template <class _ForwardIter, class _Tp>

   552 inline bool binary_search(_ForwardIter __first, _ForwardIter __last,

   553                    const _Tp& __val) {

   554   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   555   _ForwardIter __i = __lower_bound(__first, __last, __val, 

   556                                    __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),

   557                                    _STLP_DISTANCE_TYPE(__first, _ForwardIter));

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

   559 }

   560 

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

   562 inline bool binary_search(_ForwardIter __first, _ForwardIter __last,

   563                    const _Tp& __val,

   564                    _Compare __comp) {

   565   _STLP_DEBUG_CHECK(__check_range(__first, __last))

   566   _ForwardIter __i = __lower_bound(__first, __last, __val, __comp, _STLP_DISTANCE_TYPE(__first, _ForwardIter));

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

   568 }

   569 

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

   571 

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

   573 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,

   574                   _InputIter2 __first2, _InputIter2 __last2,

   575                   _OutputIter __result);

   576  

   577 template <class _InputIter1, class _InputIter2, class _OutputIter,

   578           class _Compare>

   579 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,

   580                   _InputIter2 __first2, _InputIter2 __last2,

   581                   _OutputIter __result, _Compare __comp);

   582 

   583 

   584 // inplace_merge and its auxiliary functions. 

   585 

   586 

   587 template <class _BidirectionalIter>

   588 void inplace_merge(_BidirectionalIter __first,

   589 		   _BidirectionalIter __middle,

   590 		   _BidirectionalIter __last) ;

   591 

   592 template <class _BidirectionalIter, class _Compare>

   593 void inplace_merge(_BidirectionalIter __first,

   594 		   _BidirectionalIter __middle,

   595 		   _BidirectionalIter __last, _Compare __comp);

   596 

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

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

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

   600 // ranges are sorted.

   601 

   602 template <class _InputIter1, class _InputIter2>

   603 bool includes(_InputIter1 __first1, _InputIter1 __last1,

   604               _InputIter2 __first2, _InputIter2 __last2);

   605 

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

   607 bool includes(_InputIter1 __first1, _InputIter1 __last1,

   608               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp);

   609  

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

   611 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,

   612                       _InputIter2 __first2, _InputIter2 __last2,

   613                       _OutputIter __result);

   614 

   615 template <class _InputIter1, class _InputIter2, class _OutputIter,

   616           class _Compare>

   617 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,

   618                       _InputIter2 __first2, _InputIter2 __last2,

   619                       _OutputIter __result, _Compare __comp);

   620 

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

   622 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,

   623                              _InputIter2 __first2, _InputIter2 __last2,

   624                              _OutputIter __result);

   625 

   626 template <class _InputIter1, class _InputIter2, class _OutputIter,

   627           class _Compare>

   628 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,

   629                              _InputIter2 __first2, _InputIter2 __last2,

   630                              _OutputIter __result, _Compare __comp);

   631 

   632 

   633 

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

   635 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,

   636                            _InputIter2 __first2, _InputIter2 __last2,

   637                            _OutputIter __result);

   638 

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

   640           class _Compare>

   641 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,

   642                            _InputIter2 __first2, _InputIter2 __last2, 

   643                            _OutputIter __result, _Compare __comp);

   644 

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

   646 _OutputIter 

   647 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

   648                          _InputIter2 __first2, _InputIter2 __last2,

   649                          _OutputIter __result);

   650 

   651 

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

   653           class _Compare>

   654 _OutputIter 

   655 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,

   656                          _InputIter2 __first2, _InputIter2 __last2,

   657                          _OutputIter __result,

   658                          _Compare __comp);

   659 

   660 

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

   662 // comparison function.

   663 

   664 template <class _ForwardIter>

   665 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last);

   666 template <class _ForwardIter, class _Compare>

   667 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,

   668                             _Compare __comp);

   669 

   670 template <class _ForwardIter>

   671 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last);

   672 

   673 template <class _ForwardIter, class _Compare>

   674 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,

   675                             _Compare __comp);

   676 

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

   678 // supplied comparison function.

   679 

   680 template <class _BidirectionalIter>

   681 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last);

   682 

   683 template <class _BidirectionalIter, class _Compare>

   684 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

   685                       _Compare __comp);

   686 

   687 

   688 template <class _BidirectionalIter>

   689 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last);

   690 

   691 

   692 template <class _BidirectionalIter, class _Compare>

   693 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,

   694                       _Compare __comp);

   695 

   696 # ifndef _STLP_NO_EXTENSIONS

   697 

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

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

   700 // standard.

   701 

   702 template <class _RandomAccessIter>

   703 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last);

   704 

   705 template <class _RandomAccessIter, class _StrictWeakOrdering>

   706 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,

   707 	     _StrictWeakOrdering __comp);

   708 

   709 

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

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

   712 // standard.

   713 template <class _ForwardIter, class _StrictWeakOrdering>

   714 bool __is_sorted(_ForwardIter __first, _ForwardIter __last,

   715                  _StrictWeakOrdering __comp);

   716 

   717 template <class _ForwardIter>

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

   719   return __is_sorted(__first, __last, __less(_STLP_VALUE_TYPE(__first, _ForwardIter)));

   720 }

   721 

   722 template <class _ForwardIter, class _StrictWeakOrdering>

   723 inline bool is_sorted(_ForwardIter __first, _ForwardIter __last,

   724                       _StrictWeakOrdering __comp) {

   725   return __is_sorted(__first, __last, __comp);

   726 }

   727 # endif

   728 

   729 _STLP_END_NAMESPACE

   730 

   731 # if !defined (_STLP_LINK_TIME_INSTANTIATION)

   732 #  include <stl/_algo.c>

   733 # endif

   734 

   735 #endif /* _STLP_INTERNAL_ALGO_H */

   736 

   737 // Local Variables:

   738 // mode:C++

   739 // End:

   740
test