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_ALGOBASE_H
31#define _STLP_INTERNAL_ALGOBASE_H
32
33#ifndef _STLP_INTERNAL_CSTDDEF
34#  include <stl/_cstddef.h>
35#endif
36
37#ifndef _STLP_INTERNAL_CSTRING
38#  include <stl/_cstring.h>
39#endif
40
41#ifndef _STLP_CLIMITS
42#  include <climits>
43#endif
44
45#ifndef _STLP_INTERNAL_CSTDLIB
46#  include <stl/_cstdlib.h>
47#endif
48
49#ifndef _STLP_INTERNAL_PAIR_H
50#  include <stl/_pair.h>
51#endif
52
53#ifndef _STLP_INTERNAL_ITERATOR_BASE_H
54#  include <stl/_iterator_base.h>
55#endif
56
57#ifndef _STLP_TYPE_TRAITS_H
58#  include <stl/type_traits.h>
59#endif
60
61_STLP_BEGIN_NAMESPACE
62
63#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
64_STLP_MOVE_TO_PRIV_NAMESPACE
65template <class _Tp>
66inline void __swap_aux(_Tp& __a, _Tp& __b, const __true_type& /*SwapImplemented*/) {
67  __a._M_swap_workaround(__b);
68}
69
70template <class _Tp>
71inline void __swap_aux(_Tp& __a, _Tp& __b, const __false_type& /*SwapImplemented*/) {
72  _Tp __tmp = __a;
73  __a = __b;
74  __b = __tmp;
75}
76_STLP_MOVE_TO_STD_NAMESPACE
77#endif
78
79// swap and iter_swap
80template <class _Tp>
81inline void swap(_Tp& __a, _Tp& __b) {
82#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
83#  if !defined(__BORLANDC__)
84  typedef typename _SwapImplemented<_Tp>::_Ret _Implemented;
85#  else
86  enum { _Is = _SwapImplemented<_Tp>::_Is };
87  typedef typename __bool2type<_Is>::_Ret _Implemented;
88#  endif
89  _STLP_PRIV __swap_aux(__a, __b, _Implemented());
90#else
91  _Tp __tmp = __a;
92  __a = __b;
93  __b = __tmp;
94#endif
95}
96
97_STLP_MOVE_TO_PRIV_NAMESPACE
98
99template <class _ForwardIter1, class _ForwardIter2, class _Value>
100inline void __iter_swap_aux_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, _Value *) {
101  _Value tmp = *__i1;
102  *__i1 = *__i2;
103  *__i2 = tmp;
104}
105
106template <class _ForwardIter1, class _ForwardIter2>
107inline void __iter_swap_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, const __true_type& /*OKToSwap*/) {
108  /* namespace specification breaks access to the right swap template overload (at least for gcc) */
109  /*_STLP_STD::*/ swap(*__i1, *__i2);
110}
111
112template <class _ForwardIter1, class _ForwardIter2>
113inline void __iter_swap_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, const __false_type& /*OKToSwap*/) {
114  _STLP_PRIV __iter_swap_aux_aux( __i1, __i2, _STLP_VALUE_TYPE(__i1,_ForwardIter1) );
115}
116
117_STLP_MOVE_TO_STD_NAMESPACE
118
119template <class _ForwardIter1, class _ForwardIter2>
120inline void iter_swap(_ForwardIter1 __i1, _ForwardIter2 __i2) {
121  _STLP_PRIV __iter_swap_aux( __i1, __i2, _IsOKToSwap(_STLP_VALUE_TYPE(__i1, _ForwardIter1), _STLP_VALUE_TYPE(__i2, _ForwardIter2),
122                                                      _STLP_IS_REF_TYPE_REAL_REF(__i1, _ForwardIter1),
123                                                      _STLP_IS_REF_TYPE_REAL_REF(__i2, _ForwardIter2))._Answer());
124}
125
126//--------------------------------------------------
127// min and max
128
129#if !defined (__BORLANDC__) || defined (_STLP_USE_OWN_NAMESPACE)
130#  if (defined (__BORLANDC__) && (__BORLANDC__ < 0x580)) && !defined (__STDC__)
131//In not ANSI mode Borland import min/max in global namespace which conflict
132//with STLport min/max when user does a 'using namespace std' in its code
133//(see test/unit/alg_test.cpp). To avoid this clash we simply import Borland min/max
134//in STLport namespace.
135using _STLP_VENDOR_STD::min;
136using _STLP_VENDOR_STD::max;
137#  else
138template <class _Tp>
139inline const _Tp& (min)(const _Tp& __a, const _Tp& __b) { return __b < __a ? __b : __a; }
140template <class _Tp>
141inline const _Tp& (max)(const _Tp& __a, const _Tp& __b) {  return  __a < __b ? __b : __a; }
142#  endif
143#endif
144
145# if defined (__BORLANDC__) && defined (_STLP_USE_OWN_NAMESPACE)
146inline unsigned long (min) (unsigned long __a, unsigned long __b) { return __b < __a ? __b : __a; }
147inline unsigned long (max) (unsigned long __a, unsigned long __b) {  return  __a < __b ? __b : __a; }
148# endif
149
150#  if !defined (__BORLANDC__) || (__BORLANDC__ < 0x590)
151template <class _Tp, class _Compare>
152inline const _Tp& (min)(const _Tp& __a, const _Tp& __b, _Compare __comp) {
153  return __comp(__b, __a) ? __b : __a;
154}
155
156template <class _Tp, class _Compare>
157inline const _Tp& (max)(const _Tp& __a, const _Tp& __b, _Compare __comp) {
158  return __comp(__a, __b) ? __b : __a;
159}
160#  else
161template <class _Tp, class _Compare>
162inline const _Tp (min)(const _Tp __a, const _Tp __b, _Compare __comp) {
163  return __comp(__b, __a) ? __b : __a;
164}
165
166template <class _Tp, class _Compare>
167inline const _Tp (max)(const _Tp __a, const _Tp __b, _Compare __comp) {
168  return __comp(__a, __b) ? __b : __a;
169}
170#  endif
171
172//--------------------------------------------------
173// copy
174
175// All of these auxiliary functions serve two purposes.  (1) Replace
176// calls to copy with memmove whenever possible.  (Memmove, not memcpy,
177// because the input and output ranges are permitted to overlap.)
178// (2) If we're using random access iterators, then write the loop as
179// a for loop with an explicit count.
180
181_STLP_MOVE_TO_PRIV_NAMESPACE
182
183template <class _InputIter, class _OutputIter, class _Distance>
184inline _OutputIter __copy(_InputIter __first, _InputIter __last,
185                          _OutputIter __result, const input_iterator_tag &, _Distance*) {
186  for ( ; __first != __last; ++__result, ++__first)
187    *__result = *__first;
188  return __result;
189}
190
191#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
192template <class _InputIter, class _OutputIter, class _Distance>
193inline _OutputIter __copy(_InputIter __first, _InputIter __last,
194                          _OutputIter __result, const forward_iterator_tag &, _Distance* ) {
195  for ( ; __first != __last; ++__result, ++__first)
196    *__result = *__first;
197  return __result;
198}
199
200template <class _InputIter, class _OutputIter, class _Distance>
201inline _OutputIter __copy(_InputIter __first, _InputIter __last,
202                          _OutputIter __result, const bidirectional_iterator_tag &, _Distance* ) {
203  for ( ; __first != __last; ++__result, ++__first)
204    *__result = *__first;
205  return __result;
206}
207#endif
208
209template <class _RandomAccessIter, class _OutputIter, class _Distance>
210inline _OutputIter
211__copy(_RandomAccessIter __first, _RandomAccessIter __last,
212       _OutputIter __result, const random_access_iterator_tag &, _Distance*) {
213  for (_Distance __n = __last - __first; __n > 0; --__n) {
214    *__result = *__first;
215    ++__first;
216    ++__result;
217  }
218  return __result;
219}
220
221inline void*
222__copy_trivial(const void* __first, const void* __last, void* __result) {
223  size_t __n = (const char*)__last - (const char*)__first;
224  return __n ? (void *)((char*)memmove(__result, __first, __n) + __n) : __result;
225}
226
227//--------------------------------------------------
228// copy_backward auxiliary functions
229
230template <class _BidirectionalIter1, class _BidirectionalIter2,
231          class _Distance>
232inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
233                                           _BidirectionalIter1 __last,
234                                           _BidirectionalIter2 __result,
235                                           const bidirectional_iterator_tag &,
236                                           _Distance*) {
237  while (__first != __last)
238    *--__result = *--__last;
239  return __result;
240}
241
242template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
243inline _BidirectionalIter __copy_backward(_RandomAccessIter __first,
244                                          _RandomAccessIter __last,
245                                          _BidirectionalIter __result,
246                                          const random_access_iterator_tag &,
247                                          _Distance*) {
248  for (_Distance __n = __last - __first; __n > 0; --__n)
249    *--__result = *--__last;
250  return __result;
251}
252
253inline void*
254__copy_trivial_backward(const void* __first, const void* __last, void* __result) {
255  const ptrdiff_t _Num = (const char*)__last - (const char*)__first;
256  return (_Num > 0) ? memmove((char*)__result - _Num, __first, _Num) : __result ;
257}
258
259template <class _InputIter, class _OutputIter>
260inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
261                               const __false_type& /*IsOKToMemCpy*/) {
262  return _STLP_PRIV __copy(__first, __last, __result, random_access_iterator_tag(), (ptrdiff_t*)0);
263}
264template <class _InputIter, class _OutputIter>
265inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
266                               const __true_type& /*IsOKToMemCpy*/) {
267  // we know they all pointers, so this cast is OK
268  //  return (_OutputIter)__copy_trivial(&(*__first), &(*__last), &(*__result));
269  return (_OutputIter)_STLP_PRIV __copy_trivial(__first, __last, __result);
270}
271
272template <class _InputIter, class _OutputIter>
273inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
274                              const __true_type& /*BothPtrType*/) {
275  return _STLP_PRIV __copy_ptrs(__first, __last, __result,
276                                _UseTrivialCopy(_STLP_VALUE_TYPE(__first, _InputIter),
277                                                _STLP_VALUE_TYPE(__result, _OutputIter))._Answer());
278}
279
280template <class _InputIter, class _OutputIter>
281inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
282                              const __false_type& /*BothPtrType*/) {
283  return _STLP_PRIV __copy(__first, __last, __result,
284                           _STLP_ITERATOR_CATEGORY(__first, _InputIter),
285                           _STLP_DISTANCE_TYPE(__first, _InputIter));
286}
287
288_STLP_MOVE_TO_STD_NAMESPACE
289
290template <class _InputIter, class _OutputIter>
291inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
292  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
293  return _STLP_PRIV __copy_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter>::_Answer());
294}
295
296_STLP_MOVE_TO_PRIV_NAMESPACE
297
298template <class _InputIter, class _OutputIter>
299inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last,
300                                        _OutputIter __result, const __false_type& /*TrivialAssignment*/) {
301  return _STLP_PRIV __copy_backward(__first, __last, __result,
302                                    _STLP_ITERATOR_CATEGORY(__first, _InputIter),
303                                    _STLP_DISTANCE_TYPE(__first, _InputIter));
304}
305template <class _InputIter, class _OutputIter>
306inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last,
307                                        _OutputIter __result, const __true_type& /*TrivialAssignment*/) {
308  return (_OutputIter)_STLP_PRIV __copy_trivial_backward(__first, __last, __result);
309}
310
311template <class _InputIter, class _OutputIter>
312inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
313  return _STLP_PRIV __copy_backward(__first, __last, __result,
314                                    _STLP_ITERATOR_CATEGORY(__first,_InputIter),
315                                    _STLP_DISTANCE_TYPE(__first, _InputIter));
316}
317
318template <class _InputIter, class _OutputIter>
319inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
320  return _STLP_PRIV __copy_backward_ptrs(__first, __last, __result,
321                                         _UseTrivialCopy(_STLP_VALUE_TYPE(__first, _InputIter),
322                                                         _STLP_VALUE_TYPE(__result, _OutputIter))._Answer());
323}
324
325_STLP_MOVE_TO_STD_NAMESPACE
326
327template <class _InputIter, class _OutputIter>
328inline _OutputIter copy_backward(_InputIter __first, _InputIter __last, _OutputIter __result) {
329  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
330  return _STLP_PRIV __copy_backward_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter>::_Answer() );
331}
332
333#if !defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_SIMULATE_PARTIAL_SPEC_FOR_TYPE_TRAITS)
334#  define _STLP_DECLARE_COPY_TRIVIAL(_Tp)                                       \
335inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result)          \
336{ return (_Tp*)_STLP_PRIV __copy_trivial(__first, __last, __result); }          \
337inline _Tp* copy_backward(const _Tp* __first, const _Tp* __last, _Tp* __result) \
338{ return (_Tp*)_STLP_PRIV __copy_trivial_backward(__first, __last, __result); }
339
340#  if !defined (_STLP_NO_BOOL)
341_STLP_DECLARE_COPY_TRIVIAL(bool)
342#  endif
343_STLP_DECLARE_COPY_TRIVIAL(char)
344#  if !defined (_STLP_NO_SIGNED_BUILTINS)
345_STLP_DECLARE_COPY_TRIVIAL(signed char)
346#  endif
347_STLP_DECLARE_COPY_TRIVIAL(unsigned char)
348_STLP_DECLARE_COPY_TRIVIAL(short)
349_STLP_DECLARE_COPY_TRIVIAL(unsigned short)
350_STLP_DECLARE_COPY_TRIVIAL(int)
351_STLP_DECLARE_COPY_TRIVIAL(unsigned int)
352_STLP_DECLARE_COPY_TRIVIAL(long)
353_STLP_DECLARE_COPY_TRIVIAL(unsigned long)
354#  if !defined(_STLP_NO_WCHAR_T) && !defined (_STLP_WCHAR_T_IS_USHORT)
355_STLP_DECLARE_COPY_TRIVIAL(wchar_t)
356#  endif
357#  if defined (_STLP_LONG_LONG)
358_STLP_DECLARE_COPY_TRIVIAL(_STLP_LONG_LONG)
359_STLP_DECLARE_COPY_TRIVIAL(unsigned _STLP_LONG_LONG)
360#  endif
361_STLP_DECLARE_COPY_TRIVIAL(float)
362_STLP_DECLARE_COPY_TRIVIAL(double)
363#  if !defined (_STLP_NO_LONG_DOUBLE)
364_STLP_DECLARE_COPY_TRIVIAL(long double)
365#  endif
366#  undef _STLP_DECLARE_COPY_TRIVIAL
367#endif
368
369//--------------------------------------------------
370// copy_n (not part of the C++ standard)
371
372#if !defined (_STLP_NO_EXTENSIONS)
373_STLP_MOVE_TO_PRIV_NAMESPACE
374
375template <class _InputIter, class _Size, class _OutputIter>
376_STLP_INLINE_LOOP _STLP_STD::pair<_InputIter, _OutputIter>
377__copy_n(_InputIter __first, _Size __count, _OutputIter __result,
378         const input_iterator_tag &) {
379  for ( ; __count > 0; --__count) {
380    *__result = *__first;
381    ++__first;
382    ++__result;
383  }
384  return _STLP_STD::pair<_InputIter, _OutputIter>(__first, __result);
385}
386
387template <class _RAIter, class _Size, class _OutputIter>
388inline _STLP_STD::pair<_RAIter, _OutputIter>
389__copy_n(_RAIter __first, _Size __count, _OutputIter __result,
390         const random_access_iterator_tag &) {
391  _RAIter __last = __first + __count;
392  return _STLP_STD::pair<_RAIter, _OutputIter>(__last, _STLP_STD::copy(__first, __last, __result));
393}
394
395_STLP_MOVE_TO_STD_NAMESPACE
396
397template <class _InputIter, class _Size, class _OutputIter>
398inline pair<_InputIter, _OutputIter>
399copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
400  _STLP_FIX_LITERAL_BUG(__first)
401  return _STLP_PRIV __copy_n(__first, __count, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
402}
403#endif
404
405//--------------------------------------------------
406// fill and fill_n
407_STLP_MOVE_TO_PRIV_NAMESPACE
408
409template <class _ForwardIter, class _Tp>
410_STLP_INLINE_LOOP
411void __fill_fwd(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
412  for ( ; __first != __last; ++__first)
413    *__first = __val;
414}
415
416template <class _ForwardIter, class _Tp, class _Distance>
417inline void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
418                   const input_iterator_tag &, _Distance*) {
419  _STLP_PRIV __fill_fwd(__first, __last, __val);
420}
421
422#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
423template <class _ForwardIter, class _Tp, class _Distance>
424_STLP_INLINE_LOOP
425void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
426            const forward_iterator_tag &, _Distance*) {
427  _STLP_PRIV __fill_fwd(__first, __last, __val);
428}
429
430template <class _ForwardIter, class _Tp, class _Distance>
431_STLP_INLINE_LOOP
432void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
433            const bidirectional_iterator_tag &, _Distance*) {
434  _STLP_PRIV __fill_fwd(__first, __last, __val);
435}
436#endif
437
438template <class _RandomAccessIter, class _Tp, class _Distance>
439_STLP_INLINE_LOOP
440void __fill(_RandomAccessIter __first, _RandomAccessIter __last, const _Tp& __val,
441            const random_access_iterator_tag &, _Distance*) {
442  for (_Distance __n = __last - __first ; __n > 0; ++__first, --__n)
443    *__first = __val;
444}
445
446_STLP_MOVE_TO_STD_NAMESPACE
447
448template <class _ForwardIter, class _Tp>
449inline void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
450  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
451  _STLP_PRIV __fill(__first, __last, __val,
452                    _STLP_ITERATOR_CATEGORY(__first, _ForwardIter),
453                    _STLP_DISTANCE_TYPE(__first, _ForwardIter));
454}
455
456// Specialization: for one-byte types we can use memset.
457inline void fill(unsigned char* __first, unsigned char* __last,
458                 const unsigned char& __val) {
459  unsigned char __tmp = __val;
460  memset(__first, __tmp, __last - __first);
461}
462#if !defined (_STLP_NO_SIGNED_BUILTINS)
463inline void fill(signed char* __first, signed char* __last,
464                 const signed char& __val) {
465  signed char __tmp = __val;
466  memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
467}
468#endif
469inline void fill(char* __first, char* __last, const char& __val) {
470  char __tmp = __val;
471  memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
472}
473
474_STLP_MOVE_TO_PRIV_NAMESPACE
475
476template <class _OutputIter, class _Size, class _Tp>
477_STLP_INLINE_LOOP
478_OutputIter __fill_n(_OutputIter __first, _Size __n, const _Tp& __val) {
479  _STLP_FIX_LITERAL_BUG(__first)
480  for ( ; __n > 0; --__n, ++__first)
481    *__first = __val;
482  return __first;
483}
484
485#if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
486template <class _Size>
487inline unsigned char* __fill_n(unsigned char* __first, _Size __n,
488                               const unsigned char& __val) {
489  _STLP_STD::fill(__first, __first + __n, __val);
490  return __first + __n;
491}
492#if !defined (_STLP_NO_SIGNED_BUILTINS)
493template <class _Size>
494inline signed char* __fill_n(signed char* __first, _Size __n,
495                             const signed char& __val) {
496  _STLP_STD::fill(__first, __first + __n, __val);
497  return __first + __n;
498}
499#endif
500template <class _Size>
501inline char* __fill_n(char* __first, _Size __n,
502                      const char& __val) {
503  _STLP_STD::fill(__first, __first + __n, __val);
504  return __first + __n;
505}
506#endif
507
508_STLP_MOVE_TO_STD_NAMESPACE
509
510template <class _OutputIter, class _Size, class _Tp>
511inline void fill_n(_OutputIter __first, _Size __n, const _Tp& __val) {
512  _STLP_FIX_LITERAL_BUG(__first)
513  _STLP_PRIV __fill_n(__first, __n, __val);
514}
515
516
517//--------------------------------------------------
518// equal and mismatch
519
520template <class _InputIter1, class _InputIter2>
521_STLP_INLINE_LOOP
522_STLP_STD::pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
523                                                   _InputIter1 __last1,
524                                                   _InputIter2 __first2) {
525  _STLP_FIX_LITERAL_BUG(__first2)
526  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
527  while (__first1 != __last1 && *__first1 == *__first2) {
528    ++__first1;
529    ++__first2;
530  }
531  return _STLP_STD::pair<_InputIter1, _InputIter2>(__first1, __first2);
532}
533
534template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
535_STLP_INLINE_LOOP
536_STLP_STD::pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
537                                                   _InputIter1 __last1,
538                                                   _InputIter2 __first2,
539                                                   _BinaryPredicate __binary_pred) {
540  _STLP_FIX_LITERAL_BUG(__first2)
541  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
542  while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
543    ++__first1;
544    ++__first2;
545  }
546  return _STLP_STD::pair<_InputIter1, _InputIter2>(__first1, __first2);
547}
548
549template <class _InputIter1, class _InputIter2>
550_STLP_INLINE_LOOP
551bool equal(_InputIter1 __first1, _InputIter1 __last1,
552           _InputIter2 __first2) {
553  _STLP_FIX_LITERAL_BUG(__first1) _STLP_FIX_LITERAL_BUG(__last1)  _STLP_FIX_LITERAL_BUG(__first2)
554  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
555  for ( ; __first1 != __last1; ++__first1, ++__first2)
556    if (!(*__first1 == *__first2))
557      return false;
558  return true;
559}
560
561template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
562_STLP_INLINE_LOOP
563bool equal(_InputIter1 __first1, _InputIter1 __last1,
564           _InputIter2 __first2, _BinaryPredicate __binary_pred) {
565  _STLP_FIX_LITERAL_BUG(__first2)
566  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
567  for ( ; __first1 != __last1; ++__first1, ++__first2)
568    if (!__binary_pred(*__first1, *__first2))
569      return false;
570  return true;
571}
572
573//--------------------------------------------------
574// lexicographical_compare and lexicographical_compare_3way.
575// (the latter is not part of the C++ standard.)
576
577template <class _InputIter1, class _InputIter2>
578bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
579                             _InputIter2 __first2, _InputIter2 __last2);
580
581template <class _InputIter1, class _InputIter2, class _Compare>
582bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
583                             _InputIter2 __first2, _InputIter2 __last2,
584                             _Compare __comp);
585
586inline bool
587lexicographical_compare(const unsigned char* __first1,
588                        const unsigned char* __last1,
589                        const unsigned char* __first2,
590                        const unsigned char* __last2) {
591  const size_t __len1 = __last1 - __first1;
592  const size_t __len2 = __last2 - __first2;
593  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
594  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
595
596  const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
597  return __result != 0 ? (__result < 0) : (__len1 < __len2);
598}
599
600
601#if !(CHAR_MAX == SCHAR_MAX)
602inline bool lexicographical_compare(const char* __first1, const char* __last1,
603                                    const char* __first2, const char* __last2) {
604  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
605  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
606
607  return lexicographical_compare((const unsigned char*) __first1,
608                                 (const unsigned char*) __last1,
609                                 (const unsigned char*) __first2,
610                                 (const unsigned char*) __last2);
611}
612#endif /* CHAR_MAX == SCHAR_MAX */
613
614_STLP_MOVE_TO_PRIV_NAMESPACE
615
616template <class _InputIter1, class _InputIter2>
617int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
618                                   _InputIter2 __first2, _InputIter2 __last2);
619
620inline int
621__lexicographical_compare_3way(const unsigned char* __first1,
622                               const unsigned char* __last1,
623                               const unsigned char* __first2,
624                               const unsigned char* __last2) {
625  const ptrdiff_t __len1 = __last1 - __first1;
626  const ptrdiff_t __len2 = __last2 - __first2;
627  const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
628  return __result != 0 ? __result
629                       : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
630}
631
632
633#if !(CHAR_MAX == SCHAR_MAX)
634inline int
635__lexicographical_compare_3way(const char* __first1, const char* __last1,
636                               const char* __first2, const char* __last2) {
637  return __lexicographical_compare_3way((const unsigned char*) __first1,
638                                        (const unsigned char*) __last1,
639                                        (const unsigned char*) __first2,
640                                        (const unsigned char*) __last2);
641}
642#endif
643
644_STLP_MOVE_TO_STD_NAMESPACE
645
646#if !defined (_STLP_NO_EXTENSIONS)
647template <class _InputIter1, class _InputIter2>
648int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
649                                 _InputIter2 __first2, _InputIter2 __last2);
650
651#endif
652
653// count
654template <class _InputIter, class _Tp>
655_STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter)
656count(_InputIter __first, _InputIter __last, const _Tp& __val) {
657  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
658  _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;
659  for ( ; __first != __last; ++__first)
660    if (*__first == __val)
661      ++__n;
662  return __n;
663}
664
665// find and find_if. Note find may be expressed in terms of find_if if appropriate binder was available.
666template <class _InputIter, class _Tp>
667_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val);
668
669template <class _InputIter, class _Predicate>
670_InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred);
671
672// search.
673template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
674_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
675                     _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred  __predicate);
676
677_STLP_MOVE_TO_PRIV_NAMESPACE
678
679// find_first_of
680template <class _InputIter, class _ForwardIter>
681_InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
682                           _ForwardIter __first2, _ForwardIter __last2);
683
684template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
685_InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
686                           _ForwardIter __first2, _ForwardIter __last2,
687                           _BinaryPredicate __comp);
688
689_STLP_MOVE_TO_STD_NAMESPACE
690
691template <class _ForwardIter1, class _ForwardIter2,
692          class _BinaryPredicate>
693_ForwardIter1
694find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
695         _ForwardIter2 __first2, _ForwardIter2 __last2,
696         _BinaryPredicate __comp);
697
698// replace
699template <class _ForwardIter, class _Tp>
700_STLP_INLINE_LOOP void
701replace(_ForwardIter __first, _ForwardIter __last,
702        const _Tp& __old_value, const _Tp& __new_value) {
703  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
704  for ( ; __first != __last; ++__first)
705    if (*__first == __old_value)
706      *__first = __new_value;
707}
708
709_STLP_MOVE_TO_PRIV_NAMESPACE
710
711template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
712_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
713                           const _Tp& __val, _Compare1 __comp1, _Compare2 __comp2, _Distance*);
714
715_STLP_MOVE_TO_STD_NAMESPACE
716
717_STLP_END_NAMESPACE
718
719#if !defined (_STLP_LINK_TIME_INSTANTIATION)
720#  include <stl/_algobase.c>
721#endif
722
723#endif /* _STLP_INTERNAL_ALGOBASE_H */
724
725// Local Variables:
726// mode:C++
727// End:
728
729