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.
williamr@2
     1
/*
williamr@2
     2
 *
williamr@2
     3
 * Copyright (c) 1994
williamr@2
     4
 * Hewlett-Packard Company
williamr@2
     5
 *
williamr@2
     6
 * Copyright (c) 1996,1997
williamr@2
     7
 * Silicon Graphics Computer Systems, Inc.
williamr@2
     8
 *
williamr@2
     9
 * Copyright (c) 1997
williamr@2
    10
 * Moscow Center for SPARC Technology
williamr@2
    11
 *
williamr@4
    12
 * Copyright (c) 1999
williamr@2
    13
 * Boris Fomitchev
williamr@2
    14
 *
williamr@2
    15
 * This material is provided "as is", with absolutely no warranty expressed
williamr@2
    16
 * or implied. Any use is at your own risk.
williamr@2
    17
 *
williamr@4
    18
 * Permission to use or copy this software for any purpose is hereby granted
williamr@2
    19
 * without fee, provided the above notices are retained on all copies.
williamr@2
    20
 * Permission to modify the code and to distribute modified code is granted,
williamr@2
    21
 * provided the above notices are retained, and a notice that the code was
williamr@2
    22
 * modified is included with the above copyright notice.
williamr@2
    23
 *
williamr@2
    24
 */
williamr@2
    25
williamr@2
    26
/* NOTE: This is an internal header file, included by other STL headers.
williamr@2
    27
 *   You should not attempt to use it directly.
williamr@2
    28
 */
williamr@2
    29
williamr@2
    30
#ifndef _STLP_INTERNAL_ALGO_H
williamr@2
    31
#define _STLP_INTERNAL_ALGO_H
williamr@2
    32
williamr@4
    33
#ifndef _STLP_INTERNAL_ALGOBASE_H
williamr@2
    34
#  include <stl/_algobase.h>
williamr@4
    35
#endif
williamr@2
    36
williamr@4
    37
#ifndef _STLP_INTERNAL_HEAP_H
williamr@4
    38
#  include <stl/_heap.h>
williamr@4
    39
#endif
williamr@2
    40
williamr@4
    41
#ifndef _STLP_INTERNAL_ITERATOR_H
williamr@4
    42
#  include <stl/_iterator.h>
williamr@4
    43
#endif
williamr@2
    44
williamr@4
    45
#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
williamr@4
    46
#  include <stl/_function_base.h>
williamr@4
    47
#endif
williamr@2
    48
williamr@4
    49
#if defined (__SUNPRO_CC) && !defined (_STLP_INTERNAL_CSTDIO)
williamr@2
    50
// remove() conflict
williamr@4
    51
#  include <stl/_cstdio.h>
williamr@4
    52
#endif
williamr@2
    53
williamr@2
    54
_STLP_BEGIN_NAMESPACE
williamr@2
    55
williamr@2
    56
// for_each.  Apply a function to every element of a range.
williamr@2
    57
template <class _InputIter, class _Function>
williamr@4
    58
_STLP_INLINE_LOOP _Function
williamr@2
    59
for_each(_InputIter __first, _InputIter __last, _Function __f) {
williamr@2
    60
  for ( ; __first != __last; ++__first)
williamr@2
    61
    __f(*__first);
williamr@2
    62
  return __f;
williamr@2
    63
}
williamr@2
    64
williamr@2
    65
// count_if
williamr@2
    66
template <class _InputIter, class _Predicate>
williamr@2
    67
_STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter)
williamr@2
    68
count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
williamr@4
    69
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
    70
  _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;
williamr@4
    71
  for ( ; __first != __last; ++__first) {
williamr@2
    72
    if (__pred(*__first))
williamr@2
    73
      ++__n;
williamr@4
    74
  }
williamr@2
    75
  return __n;
williamr@2
    76
}
williamr@2
    77
williamr@2
    78
// adjacent_find.
williamr@2
    79
williamr@2
    80
template <class _ForwardIter, class _BinaryPredicate>
williamr@4
    81
_STLP_INLINE_LOOP _ForwardIter
williamr@2
    82
adjacent_find(_ForwardIter __first, _ForwardIter __last,
williamr@2
    83
              _BinaryPredicate __binary_pred) {
williamr@4
    84
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
    85
  if (__first == __last)
williamr@2
    86
    return __last;
williamr@2
    87
  _ForwardIter __next = __first;
williamr@2
    88
  while(++__next != __last) {
williamr@2
    89
    if (__binary_pred(*__first, *__next))
williamr@2
    90
      return __first;
williamr@2
    91
    __first = __next;
williamr@2
    92
  }
williamr@2
    93
  return __last;
williamr@2
    94
}
williamr@2
    95
williamr@2
    96
template <class _ForwardIter>
williamr@4
    97
_STLP_INLINE_LOOP _ForwardIter
williamr@2
    98
adjacent_find(_ForwardIter __first, _ForwardIter __last) {
williamr@2
    99
  return adjacent_find(__first, __last,
williamr@4
   100
                       _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _ForwardIter)));
williamr@2
   101
}
williamr@2
   102
williamr@4
   103
#if !defined (_STLP_NO_ANACHRONISMS)
williamr@2
   104
template <class _InputIter, class _Tp, class _Size>
williamr@4
   105
_STLP_INLINE_LOOP void
williamr@2
   106
count(_InputIter __first, _InputIter __last, const _Tp& __val, _Size& __n) {
williamr@4
   107
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   108
    for ( ; __first != __last; ++__first)
williamr@2
   109
      if (*__first == __val)
williamr@2
   110
        ++__n;
williamr@2
   111
}
williamr@2
   112
williamr@2
   113
template <class _InputIter, class _Predicate, class _Size>
williamr@4
   114
_STLP_INLINE_LOOP void
williamr@2
   115
count_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) {
williamr@4
   116
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   117
  for ( ; __first != __last; ++__first)
williamr@2
   118
    if (__pred(*__first))
williamr@2
   119
      ++__n;
williamr@2
   120
}
williamr@4
   121
#endif
williamr@2
   122
williamr@2
   123
template <class _ForwardIter1, class _ForwardIter2>
williamr@2
   124
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
williamr@2
   125
                     _ForwardIter2 __first2, _ForwardIter2 __last2);
williamr@2
   126
williamr@2
   127
// search_n.  Search for __count consecutive copies of __val.
williamr@2
   128
template <class _ForwardIter, class _Integer, class _Tp>
williamr@2
   129
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
williamr@2
   130
                      _Integer __count, const _Tp& __val);
williamr@2
   131
template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
williamr@2
   132
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
williamr@2
   133
                      _Integer __count, const _Tp& __val, _BinaryPred __binary_pred);
williamr@2
   134
williamr@2
   135
template <class _InputIter, class _ForwardIter>
williamr@2
   136
inline _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
williamr@2
   137
                                _ForwardIter __first2, _ForwardIter __last2) {
williamr@4
   138
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@4
   139
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
williamr@4
   140
  return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2,
williamr@4
   141
                                    _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _InputIter)));
williamr@2
   142
}
williamr@2
   143
williamr@2
   144
template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
williamr@4
   145
inline _InputIter
williamr@2
   146
find_first_of(_InputIter __first1, _InputIter __last1,
williamr@4
   147
              _ForwardIter __first2, _ForwardIter __last2, _BinaryPredicate __comp) {
williamr@4
   148
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@4
   149
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
williamr@4
   150
  return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2, __comp);
williamr@2
   151
}
williamr@2
   152
williamr@2
   153
template <class _ForwardIter1, class _ForwardIter2>
williamr@4
   154
_ForwardIter1
williamr@4
   155
find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
williamr@2
   156
         _ForwardIter2 __first2, _ForwardIter2 __last2);
williamr@2
   157
williamr@2
   158
// swap_ranges
williamr@2
   159
template <class _ForwardIter1, class _ForwardIter2>
williamr@4
   160
_STLP_INLINE_LOOP _ForwardIter2
williamr@2
   161
swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2) {
williamr@4
   162
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@2
   163
  for ( ; __first1 != __last1; ++__first1, ++__first2)
williamr@2
   164
    iter_swap(__first1, __first2);
williamr@2
   165
  return __first2;
williamr@2
   166
}
williamr@2
   167
williamr@2
   168
// transform
williamr@2
   169
template <class _InputIter, class _OutputIter, class _UnaryOperation>
williamr@4
   170
_STLP_INLINE_LOOP _OutputIter
williamr@2
   171
transform(_InputIter __first, _InputIter __last, _OutputIter __result, _UnaryOperation __opr) {
williamr@4
   172
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   173
  for ( ; __first != __last; ++__first, ++__result)
williamr@2
   174
    *__result = __opr(*__first);
williamr@2
   175
  return __result;
williamr@2
   176
}
williamr@2
   177
template <class _InputIter1, class _InputIter2, class _OutputIter, class _BinaryOperation>
williamr@4
   178
_STLP_INLINE_LOOP _OutputIter
williamr@4
   179
transform(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   180
          _InputIter2 __first2, _OutputIter __result,_BinaryOperation __binary_op) {
williamr@4
   181
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@2
   182
  for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
williamr@2
   183
    *__result = __binary_op(*__first1, *__first2);
williamr@2
   184
  return __result;
williamr@2
   185
}
williamr@2
   186
williamr@2
   187
// replace_if, replace_copy, replace_copy_if
williamr@2
   188
williamr@2
   189
template <class _ForwardIter, class _Predicate, class _Tp>
williamr@4
   190
_STLP_INLINE_LOOP void
williamr@2
   191
replace_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const _Tp& __new_value) {
williamr@4
   192
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   193
  for ( ; __first != __last; ++__first)
williamr@2
   194
    if (__pred(*__first))
williamr@2
   195
      *__first = __new_value;
williamr@2
   196
}
williamr@2
   197
williamr@2
   198
template <class _InputIter, class _OutputIter, class _Tp>
williamr@4
   199
_STLP_INLINE_LOOP  _OutputIter
williamr@2
   200
replace_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
williamr@2
   201
             const _Tp& __old_value, const _Tp& __new_value) {
williamr@4
   202
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   203
  for ( ; __first != __last; ++__first, ++__result)
williamr@2
   204
    *__result = *__first == __old_value ? __new_value : *__first;
williamr@2
   205
  return __result;
williamr@2
   206
}
williamr@2
   207
williamr@2
   208
template <class _Iterator, class _OutputIter, class _Predicate, class _Tp>
williamr@4
   209
_STLP_INLINE_LOOP _OutputIter
williamr@2
   210
replace_copy_if(_Iterator __first, _Iterator __last,
williamr@2
   211
                _OutputIter __result,
williamr@2
   212
                _Predicate __pred, const _Tp& __new_value) {
williamr@4
   213
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   214
  for ( ; __first != __last; ++__first, ++__result)
williamr@2
   215
    *__result = __pred(*__first) ? __new_value : *__first;
williamr@2
   216
  return __result;
williamr@2
   217
}
williamr@2
   218
williamr@2
   219
// generate and generate_n
williamr@2
   220
williamr@2
   221
template <class _ForwardIter, class _Generator>
williamr@4
   222
_STLP_INLINE_LOOP void
williamr@2
   223
generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
williamr@4
   224
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   225
  for ( ; __first != __last; ++__first)
williamr@2
   226
    *__first = __gen();
williamr@2
   227
}
williamr@2
   228
williamr@2
   229
template <class _OutputIter, class _Size, class _Generator>
williamr@4
   230
_STLP_INLINE_LOOP void
williamr@2
   231
generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
williamr@2
   232
  for ( ; __n > 0; --__n, ++__first)
williamr@2
   233
    *__first = __gen();
williamr@2
   234
}
williamr@2
   235
williamr@2
   236
// remove, remove_if, remove_copy, remove_copy_if
williamr@2
   237
williamr@2
   238
template <class _InputIter, class _OutputIter, class _Tp>
williamr@4
   239
_STLP_INLINE_LOOP _OutputIter
williamr@2
   240
remove_copy(_InputIter __first, _InputIter __last,_OutputIter __result, const _Tp& __val) {
williamr@4
   241
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   242
  for ( ; __first != __last; ++__first) {
williamr@2
   243
    if (!(*__first == __val)) {
williamr@2
   244
      *__result = *__first;
williamr@2
   245
      ++__result;
williamr@2
   246
    }
williamr@4
   247
  }
williamr@2
   248
  return __result;
williamr@2
   249
}
williamr@2
   250
williamr@2
   251
template <class _InputIter, class _OutputIter, class _Predicate>
williamr@4
   252
_STLP_INLINE_LOOP _OutputIter
williamr@2
   253
remove_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred) {
williamr@4
   254
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   255
  for ( ; __first != __last; ++__first) {
williamr@2
   256
    if (!__pred(*__first)) {
williamr@2
   257
      *__result = *__first;
williamr@2
   258
      ++__result;
williamr@2
   259
    }
williamr@4
   260
  }
williamr@2
   261
  return __result;
williamr@2
   262
}
williamr@2
   263
williamr@2
   264
template <class _ForwardIter, class _Tp>
williamr@4
   265
_STLP_INLINE_LOOP _ForwardIter
williamr@2
   266
remove(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
williamr@4
   267
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   268
  __first = find(__first, __last, __val);
williamr@2
   269
  if (__first == __last)
williamr@2
   270
    return __first;
williamr@4
   271
  else {
williamr@2
   272
    _ForwardIter __next = __first;
williamr@2
   273
    return remove_copy(++__next, __last, __first, __val);
williamr@2
   274
  }
williamr@2
   275
}
williamr@2
   276
williamr@2
   277
template <class _ForwardIter, class _Predicate>
williamr@4
   278
_STLP_INLINE_LOOP _ForwardIter
williamr@2
   279
remove_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
williamr@4
   280
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   281
  __first = find_if(__first, __last, __pred);
williamr@2
   282
  if ( __first == __last )
williamr@2
   283
    return __first;
williamr@2
   284
  else {
williamr@2
   285
    _ForwardIter __next = __first;
williamr@2
   286
    return remove_copy_if(++__next, __last, __first, __pred);
williamr@2
   287
  }
williamr@2
   288
}
williamr@2
   289
williamr@2
   290
// unique and unique_copy
williamr@2
   291
template <class _InputIter, class _OutputIter>
williamr@2
   292
_OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result);
williamr@2
   293
williamr@2
   294
template <class _InputIter, class _OutputIter, class _BinaryPredicate>
williamr@2
   295
_OutputIter unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
williamr@2
   296
                        _BinaryPredicate __binary_pred);
williamr@2
   297
williamr@2
   298
template <class _ForwardIter>
williamr@2
   299
inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
williamr@2
   300
  __first = adjacent_find(__first, __last);
williamr@2
   301
  return unique_copy(__first, __last, __first);
williamr@2
   302
}
williamr@2
   303
williamr@2
   304
template <class _ForwardIter, class _BinaryPredicate>
williamr@2
   305
inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
williamr@4
   306
                           _BinaryPredicate __binary_pred) {
williamr@2
   307
  __first = adjacent_find(__first, __last, __binary_pred);
williamr@2
   308
  return unique_copy(__first, __last, __first, __binary_pred);
williamr@2
   309
}
williamr@2
   310
williamr@2
   311
// reverse and reverse_copy, and their auxiliary functions
williamr@2
   312
williamr@2
   313
template <class _BidirectionalIter>
williamr@4
   314
_STLP_INLINE_LOOP void
williamr@2
   315
__reverse(_BidirectionalIter __first, _BidirectionalIter __last, const bidirectional_iterator_tag &) {
williamr@4
   316
  for (; __first != __last && __first != --__last; ++__first)
williamr@2
   317
    iter_swap(__first,__last);
williamr@2
   318
}
williamr@2
   319
williamr@2
   320
williamr@2
   321
template <class _RandomAccessIter>
williamr@4
   322
_STLP_INLINE_LOOP void
williamr@2
   323
__reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) {
williamr@4
   324
  for (; __first < __last; ++__first)
williamr@4
   325
    iter_swap(__first, --__last);
williamr@2
   326
}
williamr@2
   327
williamr@2
   328
template <class _BidirectionalIter>
williamr@4
   329
inline void
williamr@2
   330
reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
williamr@4
   331
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   332
  __reverse(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _BidirectionalIter));
williamr@2
   333
}
williamr@2
   334
williamr@2
   335
template <class _BidirectionalIter, class _OutputIter>
williamr@2
   336
_STLP_INLINE_LOOP
williamr@2
   337
_OutputIter reverse_copy(_BidirectionalIter __first,
williamr@4
   338
                         _BidirectionalIter __last,
williamr@4
   339
                         _OutputIter __result) {
williamr@4
   340
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2
   341
  while (__first != __last) {
williamr@2
   342
    --__last;
williamr@2
   343
    *__result = *__last;
williamr@2
   344
    ++__result;
williamr@2
   345
  }
williamr@2
   346
  return __result;
williamr@2
   347
}
williamr@2
   348
williamr@4
   349
_STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4
   350
williamr@2
   351
// rotate and rotate_copy, and their auxiliary functions
williamr@2
   352
template <class _EuclideanRingElement>
williamr@2
   353
_STLP_INLINE_LOOP
williamr@2
   354
_EuclideanRingElement __gcd(_EuclideanRingElement __m,
williamr@4
   355
                            _EuclideanRingElement __n) {
williamr@2
   356
  while (__n != 0) {
williamr@2
   357
    _EuclideanRingElement __t = __m % __n;
williamr@2
   358
    __m = __n;
williamr@2
   359
    __n = __t;
williamr@2
   360
  }
williamr@2
   361
  return __m;
williamr@2
   362
}
williamr@2
   363
williamr@4
   364
_STLP_MOVE_TO_STD_NAMESPACE
williamr@4
   365
williamr@2
   366
template <class _ForwardIter>
williamr@4
   367
void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last);
williamr@2
   368
williamr@2
   369
template <class _ForwardIter, class _OutputIter>
williamr@2
   370
inline _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
williamr@2
   371
                               _ForwardIter __last, _OutputIter __result) {
williamr@2
   372
  return copy(__first, __middle, copy(__middle, __last, __result));
williamr@2
   373
}
williamr@2
   374
williamr@2
   375
// random_shuffle
williamr@2
   376
williamr@2
   377
template <class _RandomAccessIter>
williamr@2
   378
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last);
williamr@2
   379
williamr@2
   380
template <class _RandomAccessIter, class _RandomNumberGenerator>
williamr@2
   381
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
williamr@2
   382
                    _RandomNumberGenerator& __rand);
williamr@2
   383
williamr@4
   384
#if !defined (_STLP_NO_EXTENSIONS)
williamr@2
   385
// random_sample and random_sample_n (extensions, not part of the standard).
williamr@2
   386
williamr@2
   387
template <class _ForwardIter, class _OutputIter, class _Distance>
williamr@2
   388
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
williamr@4
   389
                            _OutputIter __out_ite, const _Distance __n);
williamr@2
   390
williamr@2
   391
template <class _ForwardIter, class _OutputIter, class _Distance,
williamr@2
   392
          class _RandomNumberGenerator>
williamr@2
   393
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
williamr@4
   394
                            _OutputIter __out_ite, const _Distance __n,
williamr@2
   395
                            _RandomNumberGenerator& __rand);
williamr@2
   396
williamr@2
   397
template <class _InputIter, class _RandomAccessIter>
williamr@2
   398
_RandomAccessIter
williamr@2
   399
random_sample(_InputIter __first, _InputIter __last,
williamr@2
   400
              _RandomAccessIter __out_first, _RandomAccessIter __out_last);
williamr@2
   401
williamr@4
   402
template <class _InputIter, class _RandomAccessIter,
williamr@2
   403
          class _RandomNumberGenerator>
williamr@2
   404
_RandomAccessIter
williamr@2
   405
random_sample(_InputIter __first, _InputIter __last,
williamr@2
   406
              _RandomAccessIter __out_first, _RandomAccessIter __out_last,
williamr@2
   407
              _RandomNumberGenerator& __rand);
williamr@2
   408
williamr@4
   409
#endif /* _STLP_NO_EXTENSIONS */
williamr@2
   410
williamr@2
   411
// partition, stable_partition, and their auxiliary functions
williamr@2
   412
williamr@2
   413
template <class _ForwardIter, class _Predicate>
williamr@2
   414
_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred);
williamr@2
   415
williamr@2
   416
template <class _ForwardIter, class _Predicate>
williamr@4
   417
_ForwardIter
williamr@2
   418
stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred);
williamr@2
   419
williamr@4
   420
// sort() and its auxiliary functions.
williamr@4
   421
_STLP_MOVE_TO_PRIV_NAMESPACE
williamr@2
   422
williamr@2
   423
template <class _Size>
williamr@2
   424
inline _Size __lg(_Size __n) {
williamr@2
   425
  _Size __k;
williamr@2
   426
  for (__k = 0; __n != 1; __n >>= 1) ++__k;
williamr@2
   427
  return __k;
williamr@2
   428
}
williamr@2
   429
williamr@4
   430
_STLP_MOVE_TO_STD_NAMESPACE
williamr@4
   431
williamr@2
   432
template <class _RandomAccessIter>
williamr@2
   433
void sort(_RandomAccessIter __first, _RandomAccessIter __last);
williamr@2
   434
template <class _RandomAccessIter, class _Compare>
williamr@2
   435
void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp);
williamr@2
   436
williamr@2
   437
// stable_sort() and its auxiliary functions.
williamr@2
   438
template <class _RandomAccessIter>
williamr@2
   439
void stable_sort(_RandomAccessIter __first,
williamr@4
   440
                 _RandomAccessIter __last);
williamr@2
   441
williamr@2
   442
template <class _RandomAccessIter, class _Compare>
williamr@2
   443
void stable_sort(_RandomAccessIter __first,
williamr@4
   444
                 _RandomAccessIter __last, _Compare __comp);
williamr@2
   445
williamr@2
   446
// partial_sort, partial_sort_copy, and auxiliary functions.
williamr@2
   447
williamr@2
   448
template <class _RandomAccessIter>
williamr@4
   449
void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
williamr@4
   450
                  _RandomAccessIter __last);
williamr@2
   451
williamr@2
   452
template <class _RandomAccessIter, class _Compare>
williamr@4
   453
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
williamr@4
   454
                  _RandomAccessIter __last, _Compare __comp);
williamr@2
   455
williamr@2
   456
template <class _InputIter, class _RandomAccessIter>
williamr@2
   457
_RandomAccessIter
williamr@2
   458
partial_sort_copy(_InputIter __first, _InputIter __last,
williamr@2
   459
                  _RandomAccessIter __result_first, _RandomAccessIter __result_last);
williamr@2
   460
williamr@2
   461
template <class _InputIter, class _RandomAccessIter, class _Compare>
williamr@2
   462
_RandomAccessIter
williamr@2
   463
partial_sort_copy(_InputIter __first, _InputIter __last,
williamr@2
   464
                  _RandomAccessIter __result_first,
williamr@2
   465
                  _RandomAccessIter __result_last, _Compare __comp);
williamr@2
   466
williamr@4
   467
// nth_element() and its auxiliary functions.
williamr@2
   468
template <class _RandomAccessIter>
williamr@2
   469
void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
williamr@2
   470
                 _RandomAccessIter __last);
williamr@2
   471
williamr@2
   472
template <class _RandomAccessIter, class _Compare>
williamr@2
   473
void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
williamr@2
   474
                 _RandomAccessIter __last, _Compare __comp);
williamr@2
   475
williamr@2
   476
// auxiliary class for lower_bound, etc.
williamr@4
   477
_STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4
   478
williamr@2
   479
template <class _T1, class _T2>
williamr@2
   480
struct __less_2 {
williamr@4
   481
  bool operator() (const _T1& __x, const _T2& __y) const { return __x < __y ; }
williamr@2
   482
};
williamr@2
   483
williamr@2
   484
template <class _T1, class _T2>
williamr@2
   485
__less_2<_T1,_T2> __less2(_T1*, _T2* ) { return __less_2<_T1, _T2>(); }
williamr@2
   486
williamr@4
   487
#if defined (_STLP_FUNCTION_PARTIAL_ORDER)
williamr@2
   488
template <class _Tp>
williamr@2
   489
less<_Tp> __less2(_Tp*, _Tp* ) { return less<_Tp>(); }
williamr@2
   490
#endif
williamr@2
   491
williamr@4
   492
_STLP_MOVE_TO_STD_NAMESPACE
williamr@4
   493
williamr@2
   494
// Binary search (lower_bound, upper_bound, equal_range, binary_search).
williamr@2
   495
template <class _ForwardIter, class _Tp>
williamr@2
   496
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
williamr@2
   497
                                   const _Tp& __val) {
williamr@4
   498
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   499
  return _STLP_PRIV __lower_bound(__first, __last, __val,
williamr@4
   500
                                  _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),
williamr@4
   501
                                  _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)),
williamr@4
   502
                                  _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2
   503
}
williamr@2
   504
williamr@2
   505
template <class _ForwardIter, class _Tp, class _Compare>
williamr@2
   506
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
williamr@2
   507
                                const _Tp& __val, _Compare __comp) {
williamr@4
   508
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   509
  return _STLP_PRIV __lower_bound(__first, __last, __val, __comp, __comp,
williamr@4
   510
                                  _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2
   511
}
williamr@2
   512
williamr@4
   513
_STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4
   514
williamr@4
   515
template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
williamr@4
   516
_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
williamr@4
   517
                           _Compare1 __comp1, _Compare2 __comp2, _Distance*);
williamr@4
   518
williamr@4
   519
_STLP_MOVE_TO_STD_NAMESPACE
williamr@2
   520
williamr@2
   521
template <class _ForwardIter, class _Tp>
williamr@2
   522
inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
williamr@2
   523
                                const _Tp& __val) {
williamr@4
   524
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   525
  return _STLP_PRIV __upper_bound(__first, __last, __val,
williamr@4
   526
                                  _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),
williamr@4
   527
                                  _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)),
williamr@4
   528
                                  _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2
   529
}
williamr@2
   530
williamr@2
   531
template <class _ForwardIter, class _Tp, class _Compare>
williamr@2
   532
inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
williamr@2
   533
                                const _Tp& __val, _Compare __comp) {
williamr@4
   534
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   535
  return _STLP_PRIV __upper_bound(__first, __last, __val, __comp, __comp,
williamr@4
   536
                                  _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2
   537
}
williamr@2
   538
williamr@4
   539
_STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4
   540
williamr@4
   541
template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
williamr@2
   542
pair<_ForwardIter, _ForwardIter>
williamr@2
   543
__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
williamr@4
   544
              _Compare1 __comp1, _Compare2 __comp2, _Distance*);
williamr@4
   545
williamr@4
   546
_STLP_MOVE_TO_STD_NAMESPACE
williamr@2
   547
williamr@2
   548
template <class _ForwardIter, class _Tp>
williamr@2
   549
inline pair<_ForwardIter, _ForwardIter>
williamr@2
   550
equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
williamr@4
   551
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   552
  return _STLP_PRIV __equal_range(__first, __last, __val,
williamr@4
   553
                                  _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),
williamr@4
   554
                                  _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)),
williamr@4
   555
                                  _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2
   556
}
williamr@2
   557
williamr@2
   558
template <class _ForwardIter, class _Tp, class _Compare>
williamr@2
   559
inline pair<_ForwardIter, _ForwardIter>
williamr@2
   560
equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
williamr@2
   561
            _Compare __comp) {
williamr@4
   562
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   563
  return _STLP_PRIV __equal_range(__first, __last, __val, __comp, __comp,
williamr@4
   564
                                  _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@4
   565
}
williamr@2
   566
williamr@2
   567
template <class _ForwardIter, class _Tp>
williamr@2
   568
inline bool binary_search(_ForwardIter __first, _ForwardIter __last,
williamr@2
   569
                   const _Tp& __val) {
williamr@4
   570
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   571
  _ForwardIter __i = _STLP_PRIV __lower_bound(__first, __last, __val,
williamr@4
   572
                                              _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0),
williamr@4
   573
                                              _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)),
williamr@4
   574
                                              _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2
   575
  return __i != __last && !(__val < *__i);
williamr@2
   576
}
williamr@2
   577
williamr@2
   578
template <class _ForwardIter, class _Tp, class _Compare>
williamr@2
   579
inline bool binary_search(_ForwardIter __first, _ForwardIter __last,
williamr@4
   580
                          const _Tp& __val,
williamr@4
   581
                          _Compare __comp) {
williamr@4
   582
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4
   583
  _ForwardIter __i = _STLP_PRIV __lower_bound(__first, __last, __val, __comp, __comp,
williamr@4
   584
                                              _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2
   585
  return __i != __last && !__comp(__val, *__i);
williamr@2
   586
}
williamr@2
   587
williamr@2
   588
// merge, with and without an explicitly supplied comparison function.
williamr@2
   589
williamr@2
   590
template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2
   591
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   592
                  _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   593
                  _OutputIter __result);
williamr@4
   594
williamr@2
   595
template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2
   596
          class _Compare>
williamr@2
   597
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   598
                  _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   599
                  _OutputIter __result, _Compare __comp);
williamr@2
   600
williamr@2
   601
williamr@4
   602
// inplace_merge and its auxiliary functions.
williamr@2
   603
williamr@2
   604
williamr@2
   605
template <class _BidirectionalIter>
williamr@2
   606
void inplace_merge(_BidirectionalIter __first,
williamr@4
   607
                   _BidirectionalIter __middle,
williamr@4
   608
                   _BidirectionalIter __last) ;
williamr@2
   609
williamr@2
   610
template <class _BidirectionalIter, class _Compare>
williamr@2
   611
void inplace_merge(_BidirectionalIter __first,
williamr@4
   612
                   _BidirectionalIter __middle,
williamr@4
   613
                   _BidirectionalIter __last, _Compare __comp);
williamr@2
   614
williamr@2
   615
// Set algorithms: includes, set_union, set_intersection, set_difference,
williamr@2
   616
// set_symmetric_difference.  All of these algorithms have the precondition
williamr@2
   617
// that their input ranges are sorted and the postcondition that their output
williamr@2
   618
// ranges are sorted.
williamr@2
   619
williamr@2
   620
template <class _InputIter1, class _InputIter2>
williamr@2
   621
bool includes(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   622
              _InputIter2 __first2, _InputIter2 __last2);
williamr@2
   623
williamr@2
   624
template <class _InputIter1, class _InputIter2, class _Compare>
williamr@2
   625
bool includes(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   626
              _InputIter2 __first2, _InputIter2 __last2, _Compare __comp);
williamr@4
   627
williamr@2
   628
template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2
   629
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   630
                      _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   631
                      _OutputIter __result);
williamr@2
   632
williamr@2
   633
template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2
   634
          class _Compare>
williamr@2
   635
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   636
                      _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   637
                      _OutputIter __result, _Compare __comp);
williamr@2
   638
williamr@2
   639
template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2
   640
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   641
                             _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   642
                             _OutputIter __result);
williamr@2
   643
williamr@2
   644
template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2
   645
          class _Compare>
williamr@2
   646
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   647
                             _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   648
                             _OutputIter __result, _Compare __comp);
williamr@2
   649
williamr@2
   650
williamr@2
   651
williamr@2
   652
template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2
   653
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   654
                           _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   655
                           _OutputIter __result);
williamr@2
   656
williamr@4
   657
template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2
   658
          class _Compare>
williamr@2
   659
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@4
   660
                           _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   661
                           _OutputIter __result, _Compare __comp);
williamr@2
   662
williamr@2
   663
template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@4
   664
_OutputIter
williamr@2
   665
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   666
                         _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   667
                         _OutputIter __result);
williamr@2
   668
williamr@2
   669
williamr@2
   670
template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2
   671
          class _Compare>
williamr@4
   672
_OutputIter
williamr@2
   673
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2
   674
                         _InputIter2 __first2, _InputIter2 __last2,
williamr@2
   675
                         _OutputIter __result,
williamr@2
   676
                         _Compare __comp);
williamr@2
   677
williamr@2
   678
williamr@2
   679
// min_element and max_element, with and without an explicitly supplied
williamr@2
   680
// comparison function.
williamr@2
   681
williamr@2
   682
template <class _ForwardIter>
williamr@2
   683
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last);
williamr@2
   684
template <class _ForwardIter, class _Compare>
williamr@2
   685
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
williamr@2
   686
                            _Compare __comp);
williamr@2
   687
williamr@2
   688
template <class _ForwardIter>
williamr@2
   689
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last);
williamr@2
   690
williamr@2
   691
template <class _ForwardIter, class _Compare>
williamr@2
   692
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
williamr@2
   693
                            _Compare __comp);
williamr@2
   694
williamr@4
   695
// next_permutation and prev_permutation, with and without an explicitly
williamr@2
   696
// supplied comparison function.
williamr@2
   697
williamr@2
   698
template <class _BidirectionalIter>
williamr@2
   699
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last);
williamr@2
   700
williamr@2
   701
template <class _BidirectionalIter, class _Compare>
williamr@2
   702
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
williamr@2
   703
                      _Compare __comp);
williamr@2
   704
williamr@2
   705
williamr@2
   706
template <class _BidirectionalIter>
williamr@2
   707
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last);
williamr@2
   708
williamr@2
   709
williamr@2
   710
template <class _BidirectionalIter, class _Compare>
williamr@2
   711
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
williamr@2
   712
                      _Compare __comp);
williamr@2
   713
williamr@4
   714
#if !defined (_STLP_NO_EXTENSIONS)
williamr@2
   715
// is_heap, a predicate testing whether or not a range is
williamr@2
   716
// a heap.  This function is an extension, not part of the C++
williamr@2
   717
// standard.
williamr@2
   718
williamr@2
   719
template <class _RandomAccessIter>
williamr@2
   720
bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last);
williamr@2
   721
williamr@2
   722
template <class _RandomAccessIter, class _StrictWeakOrdering>
williamr@2
   723
bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
williamr@4
   724
             _StrictWeakOrdering __comp);
williamr@2
   725
williamr@2
   726
// is_sorted, a predicated testing whether a range is sorted in
williamr@2
   727
// nondescending order.  This is an extension, not part of the C++
williamr@2
   728
// standard.
williamr@4
   729
_STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4
   730
williamr@2
   731
template <class _ForwardIter, class _StrictWeakOrdering>
williamr@2
   732
bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
williamr@2
   733
                 _StrictWeakOrdering __comp);
williamr@2
   734
williamr@4
   735
_STLP_MOVE_TO_STD_NAMESPACE
williamr@2
   736
template <class _ForwardIter>
williamr@2
   737
inline bool is_sorted(_ForwardIter __first, _ForwardIter __last) {
williamr@4
   738
  return _STLP_PRIV __is_sorted(__first, __last,
williamr@4
   739
                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _ForwardIter)));
williamr@2
   740
}
williamr@2
   741
williamr@2
   742
template <class _ForwardIter, class _StrictWeakOrdering>
williamr@2
   743
inline bool is_sorted(_ForwardIter __first, _ForwardIter __last,
williamr@2
   744
                      _StrictWeakOrdering __comp) {
williamr@4
   745
  return _STLP_PRIV __is_sorted(__first, __last, __comp);
williamr@2
   746
}
williamr@4
   747
#endif
williamr@2
   748
williamr@2
   749
_STLP_END_NAMESPACE
williamr@2
   750
williamr@4
   751
#if !defined (_STLP_LINK_TIME_INSTANTIATION)
williamr@2
   752
#  include <stl/_algo.c>
williamr@4
   753
#endif
williamr@2
   754
williamr@2
   755
#endif /* _STLP_INTERNAL_ALGO_H */
williamr@2
   756
williamr@2
   757
// Local Variables:
williamr@2
   758
// mode:C++
williamr@2
   759
// End:
williamr@2
   760