home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _algobase.h < prev    next >
C/C++ Source or Header  |  2002-02-02  |  22KB  |  584 lines
  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.  
  31. #ifndef _STLP_INTERNAL_ALGOBASE_H
  32. #define _STLP_INTERNAL_ALGOBASE_H
  33.  
  34. # if ! defined (_STLP_CSTDDEF)
  35. #  include <cstddef>
  36. # endif
  37.  
  38. #ifndef _STLP_CSTRING
  39. # include <cstring>
  40. #endif
  41.  
  42. #ifndef _STLP_CLIMITS
  43. # include <climits>
  44. #endif
  45.  
  46. # if ! defined (_STLP_CSTDLIB)
  47. #  include <cstdlib>
  48. # endif
  49.  
  50. # ifndef _STLP_INTERNAL_PAIR_H
  51. #  include <stl/_pair.h>
  52. # endif
  53.  
  54. #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
  55. # include <stl/_iterator_base.h>
  56. #endif
  57.  
  58. _STLP_BEGIN_NAMESPACE
  59. // swap and iter_swap
  60. template <class _Tp>
  61. inline void swap(_Tp& __a, _Tp& __b) {
  62.   _Tp __tmp = __a;
  63.   __a = __b;
  64.   __b = __tmp;
  65. }
  66.  
  67. template <class _ForwardIter1, class _ForwardIter2>
  68. inline void iter_swap(_ForwardIter1 __i1, _ForwardIter2 __i2) {
  69.   swap(*__i1, *__i2);
  70. }
  71.  
  72. //--------------------------------------------------
  73. // min and max
  74.  
  75. # if !defined (__BORLANDC__) || defined (_STLP_USE_OWN_NAMESPACE)
  76. template <class _Tp>
  77. inline const _Tp& (min)(const _Tp& __a, const _Tp& __b) { return __b < __a ? __b : __a; }
  78. template <class _Tp>
  79. inline const _Tp& (max)(const _Tp& __a, const _Tp& __b) {  return  __a < __b ? __b : __a; }
  80. #endif /* __BORLANDC__ */
  81.  
  82. # if defined (__BORLANDC__) && ( __BORLANDC__ < 0x530 || defined (_STLP_USE_OWN_NAMESPACE))
  83. inline unsigned long (min) (unsigned long __a, unsigned long __b) { return __b < __a ? __b : __a; }
  84. inline unsigned long (max) (unsigned long __a, unsigned long __b) {  return  __a < __b ? __b : __a; }
  85. # endif
  86.  
  87. template <class _Tp, class _Compare>
  88. inline const _Tp& (min)(const _Tp& __a, const _Tp& __b, _Compare __comp) { 
  89.   return __comp(__b, __a) ? __b : __a;
  90. }
  91.  
  92. template <class _Tp, class _Compare>
  93. inline const _Tp& (max)(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  94.   return __comp(__a, __b) ? __b : __a;
  95. }
  96.  
  97. //--------------------------------------------------
  98. // copy
  99.  
  100. // All of these auxiliary functions serve two purposes.  (1) Replace
  101. // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
  102. // because the input and output ranges are permitted to overlap.)
  103. // (2) If we're using random access iterators, then write the loop as
  104. // a for loop with an explicit count.
  105.  
  106. template <class _InputIter, class _OutputIter, class _Distance>
  107. inline _OutputIter __copy(_InputIter __first, _InputIter __last,
  108.                           _OutputIter __result,
  109.                           const input_iterator_tag &, _Distance*) {
  110.   for ( ; __first != __last; ++__result, ++__first)
  111.     *__result = *__first;
  112.   return __result;
  113. }
  114.  
  115. # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 
  116. template <class _InputIter, class _OutputIter, class _Distance>
  117. inline _OutputIter __copy(_InputIter __first, _InputIter __last,
  118.               _OutputIter __result, const forward_iterator_tag &, _Distance* ) {
  119.   for ( ; __first != __last; ++__result, ++__first)
  120.     *__result = *__first;
  121.   return __result;
  122. }
  123.  
  124.  
  125. template <class _InputIter, class _OutputIter, class _Distance>
  126. inline _OutputIter __copy(_InputIter __first, _InputIter __last,
  127.               _OutputIter __result, const bidirectional_iterator_tag &, _Distance* __dis) {
  128.   for ( ; __first != __last; ++__result, ++__first)
  129.     *__result = *__first;
  130.   return __result;
  131. }
  132. # endif 
  133.  
  134. template <class _RandomAccessIter, class _OutputIter, class _Distance>
  135. inline _OutputIter
  136. __copy(_RandomAccessIter __first, _RandomAccessIter __last,
  137.        _OutputIter __result, const random_access_iterator_tag &, _Distance*) {
  138.   for (_Distance __n = __last - __first; __n > 0; --__n) {
  139.     *__result = *__first;
  140.     ++__first;
  141.     ++__result;
  142.   }
  143.   return __result;
  144. }
  145.  
  146. inline void*
  147. __copy_trivial(const void* __first, const void* __last, void* __result) {
  148.   return (__last == __first) ? __result : 
  149.     ((char*)memmove(__result, __first, ((const char*)__last - (const char*)__first))) + 
  150.     ((const char*)__last - (const char*)__first);
  151. }
  152.  
  153. //--------------------------------------------------
  154. // copy_backward auxiliary functions
  155.  
  156. template <class _BidirectionalIter1, class _BidirectionalIter2, 
  157.           class _Distance>
  158. inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, 
  159.                                            _BidirectionalIter1 __last, 
  160.                                            _BidirectionalIter2 __result,
  161.                                            const bidirectional_iterator_tag &,
  162.                                            _Distance*) 
  163. {
  164.   while (__first != __last)
  165.     *--__result = *--__last;
  166.   return __result;
  167. }
  168.  
  169. template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
  170. inline _BidirectionalIter __copy_backward(_RandomAccessIter __first, 
  171.                                           _RandomAccessIter __last, 
  172.                                           _BidirectionalIter __result,
  173.                                           const random_access_iterator_tag &,
  174.                                           _Distance*)
  175. {
  176.   for (_Distance __n = __last - __first; __n > 0; --__n)
  177.     *--__result = *--__last;
  178.   return __result;
  179. }
  180.  
  181. inline void*
  182. __copy_trivial_backward(const void* __first, const void* __last, void* __result) {
  183.   const ptrdiff_t _Num = (const char*)__last - (const char*)__first;
  184.   return (_Num > 0) ? memmove((char*)__result - _Num, __first, _Num) : __result ;
  185. }
  186.  
  187. template <class _InputIter, class _OutputIter>
  188. inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
  189.   return __copy(__first, __last, __result, 
  190.                 _STLP_ITERATOR_CATEGORY(__first, _InputIter), 
  191.                 _STLP_DISTANCE_TYPE(__first, _InputIter));
  192. }
  193. template <class _InputIter, class _OutputIter>
  194. inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
  195. // we know they all pointers, so this cast is OK 
  196.   //  return (_OutputIter)__copy_trivial(&(*__first), &(*__last), &(*__result));
  197.   return (_OutputIter)__copy_trivial(__first, __last, __result);
  198. }
  199.  
  200. template <class _InputIter, class _OutputIter>
  201. inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
  202.   return __copy_ptrs(__first, __last, __result, 
  203.                      _IsOKToMemCpy(_STLP_VALUE_TYPE(__first, _InputIter), 
  204.                                    _STLP_VALUE_TYPE(__result, _OutputIter))._Ret());
  205. }
  206.  
  207. template <class _InputIter, class _OutputIter>
  208. inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
  209.   return __copy(__first, __last, __result, 
  210.         _STLP_ITERATOR_CATEGORY(__first, _InputIter), _STLP_DISTANCE_TYPE(__first, _InputIter));
  211. }
  212.  
  213. template <class _InputIter, class _OutputIter>
  214. inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
  215.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  216.     return __copy_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter> :: _Ret());
  217. }
  218.  
  219. template <class _InputIter, class _OutputIter>
  220. inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
  221.   return __copy_backward(__first, __last, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter), _STLP_DISTANCE_TYPE(__first, _InputIter));
  222. }
  223. template <class _InputIter, class _OutputIter>
  224. inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
  225.   return (_OutputIter)__copy_trivial_backward(__first, __last, __result);  
  226. }
  227.  
  228. template <class _InputIter, class _OutputIter>
  229. inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
  230.   return __copy_backward(__first, __last, __result, _STLP_ITERATOR_CATEGORY(__first,_InputIter), _STLP_DISTANCE_TYPE(__first, _InputIter));
  231. }
  232.  
  233. template <class _InputIter, class _OutputIter>
  234. inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
  235.   return __copy_backward_ptrs(__first, __last, __result,  
  236.                               _IsOKToMemCpy(_STLP_VALUE_TYPE(__first, _InputIter), 
  237.                                             _STLP_VALUE_TYPE(__result, _OutputIter))._Ret());
  238. }
  239.  
  240. template <class _InputIter, class _OutputIter>
  241. inline _OutputIter copy_backward(_InputIter __first, _InputIter __last, _OutputIter __result) {
  242.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  243.     return __copy_backward_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter> :: _Ret() );
  244. }
  245.  
  246. #if ! defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && ! defined ( _STLP_SIMULATE_PARTIAL_SPEC_FOR_TYPE_TRAITS )
  247. #define _STLP_DECLARE_COPY_TRIVIAL(_Tp)                                \
  248. inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) \
  249. { return (_Tp*)__copy_trivial(__first, __last, __result); } \
  250. inline _Tp* copy_backward(const _Tp* __first, const _Tp* __last, _Tp* __result) \
  251. { return (_Tp*)__copy_trivial_backward(__first, __last, __result); }
  252.  
  253. _STLP_DECLARE_COPY_TRIVIAL(char)
  254. # ifndef _STLP_NO_SIGNED_BUILTINS
  255. _STLP_DECLARE_COPY_TRIVIAL(signed char)
  256. # endif
  257. _STLP_DECLARE_COPY_TRIVIAL(unsigned char)
  258. _STLP_DECLARE_COPY_TRIVIAL(short)
  259. _STLP_DECLARE_COPY_TRIVIAL(unsigned short)
  260. _STLP_DECLARE_COPY_TRIVIAL(int)
  261. _STLP_DECLARE_COPY_TRIVIAL(unsigned int)
  262. _STLP_DECLARE_COPY_TRIVIAL(long)
  263. _STLP_DECLARE_COPY_TRIVIAL(unsigned long)
  264. #if !defined(_STLP_NO_WCHAR_T) && !defined (_STLP_WCHAR_T_IS_USHORT) 
  265. _STLP_DECLARE_COPY_TRIVIAL(wchar_t)
  266. #endif
  267. #ifdef _STLP_LONG_LONG
  268. _STLP_DECLARE_COPY_TRIVIAL(long long)
  269. _STLP_DECLARE_COPY_TRIVIAL(unsigned long long)
  270. #endif 
  271. _STLP_DECLARE_COPY_TRIVIAL(float)
  272. _STLP_DECLARE_COPY_TRIVIAL(double)
  273. # ifndef _STLP_NO_LONG_DOUBLE
  274. _STLP_DECLARE_COPY_TRIVIAL(long double)
  275. # endif
  276. #undef _STLP_DECLARE_COPY_TRIVIAL
  277. #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
  278.  
  279. //--------------------------------------------------
  280. // copy_n (not part of the C++ standard)
  281.  
  282. template <class _InputIter, class _Size, class _OutputIter>
  283. _STLP_INLINE_LOOP 
  284. pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
  285.                                        _OutputIter __result,
  286.                                        const input_iterator_tag &) {
  287.   for ( ; __count > 0; --__count) {
  288.     *__result = *__first;
  289.     ++__first;
  290.     ++__result;
  291.   }
  292.   return pair<_InputIter, _OutputIter>(__first, __result);
  293. }
  294.  
  295. template <class _RAIter, class _Size, class _OutputIter>
  296. inline pair<_RAIter, _OutputIter>
  297. __copy_n(_RAIter __first, _Size __count,
  298.          _OutputIter __result,
  299.          const random_access_iterator_tag &) {
  300.   _RAIter __last = __first + __count;
  301.   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
  302. }
  303.  
  304. template <class _InputIter, class _Size, class _OutputIter>
  305. inline pair<_InputIter, _OutputIter>
  306. __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  307.   _STLP_FIX_LITERAL_BUG(__first)
  308.   return __copy_n(__first, __count, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
  309. }
  310.  
  311. template <class _InputIter, class _Size, class _OutputIter>
  312. inline pair<_InputIter, _OutputIter>
  313. copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  314.   _STLP_FIX_LITERAL_BUG(__first)
  315.   return __copy_n(__first, __count, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
  316. }
  317.  
  318. //--------------------------------------------------
  319. // fill and fill_n
  320.  
  321.  
  322. template <class _ForwardIter, class _Tp>
  323. _STLP_INLINE_LOOP
  324. void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
  325.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  326.   for ( ; __first != __last; ++__first)
  327.     *__first = __val;
  328. }
  329.  
  330. template <class _OutputIter, class _Size, class _Tp>
  331. _STLP_INLINE_LOOP
  332. _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __val) {
  333.   _STLP_FIX_LITERAL_BUG(__first)
  334.   for ( ; __n > 0; --__n, ++__first)
  335.     *__first = __val;
  336.   return __first;
  337. }
  338.  
  339.  
  340. // Specialization: for one-byte types we can use memset.
  341.  
  342. inline void fill(unsigned char* __first, unsigned char* __last,
  343.                  const unsigned char& __val) {
  344.   unsigned char __tmp = __val;
  345.   memset(__first, __tmp, __last - __first);
  346. }
  347. # ifndef _STLP_NO_SIGNED_BUILTINS
  348. inline void fill(signed char* __first, signed char* __last,
  349.                  const signed char& __val) {
  350.   signed char __tmp = __val;
  351.   memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
  352. }
  353. # endif
  354. inline void fill(char* __first, char* __last, const char& __val) {
  355.   char __tmp = __val;
  356.   memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
  357. }
  358.  
  359. #ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
  360.  
  361. template <class _Size>
  362. inline unsigned char* fill_n(unsigned char* __first, _Size __n,
  363.                              const unsigned char& __val) {
  364.   fill(__first, __first + __n, __val);
  365.   return __first + __n;
  366. }
  367.  
  368. template <class _Size>
  369. inline signed char* fill_n(char* __first, _Size __n,
  370.                            const signed char& __val) {
  371.   fill(__first, __first + __n, __val);
  372.   return __first + __n;
  373. }
  374.  
  375. template <class _Size>
  376. inline char* fill_n(char* __first, _Size __n, const char& __val) {
  377.   fill(__first, __first + __n, __val);
  378.   return __first + __n;
  379. }
  380.  
  381. #endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */
  382.  
  383.  
  384. //--------------------------------------------------
  385. // equal and mismatch
  386.  
  387. template <class _InputIter1, class _InputIter2>
  388. _STLP_INLINE_LOOP
  389. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  390.                                         _InputIter1 __last1,
  391.                                         _InputIter2 __first2) {
  392.   _STLP_FIX_LITERAL_BUG(__first2)
  393.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  394.   while (__first1 != __last1 && *__first1 == *__first2) {
  395.     ++__first1;
  396.     ++__first2;
  397.   }
  398.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  399. }
  400.  
  401. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  402. _STLP_INLINE_LOOP
  403. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  404.                                         _InputIter1 __last1,
  405.                                         _InputIter2 __first2,
  406.                                         _BinaryPredicate __binary_pred) {
  407.   _STLP_FIX_LITERAL_BUG(__first2)
  408.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  409.   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
  410.     ++__first1;
  411.     ++__first2;
  412.   }
  413.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  414. }
  415.  
  416. template <class _InputIter1, class _InputIter2>
  417. _STLP_INLINE_LOOP
  418. bool equal(_InputIter1 __first1, _InputIter1 __last1,
  419.                   _InputIter2 __first2) {
  420.   _STLP_FIX_LITERAL_BUG(__first1) _STLP_FIX_LITERAL_BUG(__last1)  _STLP_FIX_LITERAL_BUG(__first2)
  421.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  422.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  423.     if (!(*__first1 == *__first2))
  424.       return false;
  425.   return true;
  426. }
  427.  
  428. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  429. _STLP_INLINE_LOOP
  430. bool equal(_InputIter1 __first1, _InputIter1 __last1,
  431.                   _InputIter2 __first2, _BinaryPredicate __binary_pred) {
  432.   _STLP_FIX_LITERAL_BUG(__first2)
  433.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  434.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  435.     if (!__binary_pred(*__first1, *__first2))
  436.       return false;
  437.   return true;
  438. }
  439.  
  440. //--------------------------------------------------
  441. // lexicographical_compare and lexicographical_compare_3way.
  442. // (the latter is not part of the C++ standard.)
  443.  
  444. template <class _InputIter1, class _InputIter2>
  445. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  446.                              _InputIter2 __first2, _InputIter2 __last2);
  447.  
  448. template <class _InputIter1, class _InputIter2, class _Compare>
  449. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  450.                              _InputIter2 __first2, _InputIter2 __last2,
  451.                              _Compare __comp);
  452.  
  453. inline bool 
  454. lexicographical_compare(const unsigned char* __first1,
  455.                         const unsigned char* __last1,
  456.                         const unsigned char* __first2,
  457.                         const unsigned char* __last2)
  458. {
  459.   const size_t __len1 = __last1 - __first1;
  460.   const size_t __len2 = __last2 - __first2;
  461.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  462.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  463.  
  464.   const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
  465.   return __result != 0 ? (__result < 0) : (__len1 < __len2);
  466. }
  467.  
  468.  
  469. # if !(CHAR_MAX == SCHAR_MAX)
  470. inline bool lexicographical_compare(const char* __first1, const char* __last1,
  471.                                     const char* __first2, const char* __last2)
  472. {
  473.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) 
  474.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  475.  
  476.   return lexicographical_compare((const unsigned char*) __first1,
  477.                                  (const unsigned char*) __last1,
  478.                                  (const unsigned char*) __first2,
  479.                                  (const unsigned char*) __last2);
  480. }
  481. #endif /* CHAR_MAX == SCHAR_MAX */
  482.  
  483. template <class _InputIter1, class _InputIter2>
  484. int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  485.                                    _InputIter2 __first2, _InputIter2 __last2);
  486.  
  487. inline int
  488. __lexicographical_compare_3way(const unsigned char* __first1,
  489.                                const unsigned char* __last1,
  490.                                const unsigned char* __first2,
  491.                                const unsigned char* __last2)
  492. {
  493.   const ptrdiff_t __len1 = __last1 - __first1;
  494.   const ptrdiff_t __len2 = __last2 - __first2;
  495.   const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
  496.   return __result != 0 ? __result 
  497.                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
  498. }
  499.  
  500.  
  501. # if !(CHAR_MAX == SCHAR_MAX)
  502. inline int 
  503. __lexicographical_compare_3way(const char* __first1, const char* __last1,
  504.                                const char* __first2, const char* __last2)
  505. {
  506.   return __lexicographical_compare_3way((const unsigned char*) __first1,
  507.                                         (const unsigned char*) __last1,
  508.                                         (const unsigned char*) __first2,
  509.                                         (const unsigned char*) __last2);
  510. }
  511. # endif
  512.  
  513. # ifndef _STLP_NO_EXTENSIONS
  514.  
  515. template <class _InputIter1, class _InputIter2>
  516. int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  517.                                  _InputIter2 __first2, _InputIter2 __last2);
  518.  
  519. # endif /* EXTENSIONS */
  520.  
  521. // count
  522. template <class _InputIter, class _Tp>
  523. _STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter)
  524. count(_InputIter __first, _InputIter __last, const _Tp& __val) {
  525.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  526.   _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;
  527.   for ( ; __first != __last; ++__first)
  528.     if (*__first == __val)
  529.       ++__n;
  530.   return __n;
  531. }
  532.  
  533. // find and find_if. Note find may be expressed in terms of find_if if appropriate binder was available.
  534. template <class _InputIter, class _Tp>
  535. _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val);
  536. template <class _InputIter, class _Predicate>
  537. _InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred);
  538.  
  539. // search.
  540. template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
  541. _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  542.                      _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred  __predicate);
  543.  
  544. // find_first_of
  545. template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
  546. _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
  547.                            _ForwardIter __first2, _ForwardIter __last2,
  548.                            _BinaryPredicate __comp);
  549.  
  550. template <class _ForwardIter1, class _ForwardIter2, 
  551.           class _BinaryPredicate>
  552. _ForwardIter1 
  553. find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
  554.          _ForwardIter2 __first2, _ForwardIter2 __last2,
  555.          _BinaryPredicate __comp);
  556.  
  557. // replace
  558. template <class _ForwardIter, class _Tp>
  559. _STLP_INLINE_LOOP void 
  560. replace(_ForwardIter __first, _ForwardIter __last,
  561.         const _Tp& __old_value, const _Tp& __new_value) {
  562.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  563.   for ( ; __first != __last; ++__first)
  564.     if (*__first == __old_value)
  565.       *__first = __new_value;
  566. }
  567.  
  568. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  569. _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
  570.                               const _Tp& __val, _Compare __comp, _Distance*);
  571.  
  572. _STLP_END_NAMESPACE
  573.  
  574. # if !defined (_STLP_LINK_TIME_INSTANTIATION)
  575. #  include <stl/_algobase.c>
  576. # endif
  577.  
  578. #endif /* _STLP_INTERNAL_ALGOBASE_H */
  579.  
  580. // Local Variables:
  581. // mode:C++
  582. // End:
  583.  
  584.