home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / digital marsC compier / dm / stl / stl_algobase.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-08  |  23.8 KB  |  697 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996-1998
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26.  
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31.  
  32. #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
  33. #define __SGI_STL_INTERNAL_ALGOBASE_H
  34.  
  35. #ifndef __STL_CONFIG_H
  36. #include <stl_config.h>
  37. #endif
  38. #ifndef __SGI_STL_INTERNAL_RELOPS
  39. #include <stl_relops.h>
  40. #endif
  41. #ifndef __SGI_STL_INTERNAL_PAIR_H
  42. #include <stl_pair.h>
  43. #endif
  44. #ifndef __TYPE_TRAITS_H
  45. #include <type_traits.h>
  46. #endif
  47.  
  48. #include <string.h>
  49. #include <limits.h>
  50. #include <stdlib.h>
  51. #include <stddef.h>
  52. #include <new.h>
  53.  
  54. #ifdef __STL_USE_NEW_IOSTREAMS 
  55. #include <iosfwd>
  56. #else /* __STL_USE_NEW_IOSTREAMS */
  57. #include <iostream.h>
  58. #endif /* __STL_USE_NEW_IOSTREAMS */
  59.  
  60. #ifndef __SGI_STL_INTERNAL_ITERATOR_H
  61. #include <stl_iterator_base.h>
  62. #include <stl_iterator.h>
  63. #endif
  64.  
  65. // We pick up concept_checks.h from stl_iterator_base.h.
  66.  
  67. __STL_BEGIN_NAMESPACE
  68.  
  69. // swap and iter_swap
  70.  
  71. template <class _ForwardIter1, class _ForwardIter2, class _Tp>
  72. inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) {
  73.   _Tp __tmp = *__a;
  74.   *__a = *__b;
  75.   *__b = __tmp;
  76. }
  77.  
  78. template <class _ForwardIter1, class _ForwardIter2>
  79. inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) {
  80.   __STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator);
  81.   __STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator);
  82.   __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type,
  83.                     typename iterator_traits<_ForwardIter2>::value_type);
  84.   __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type,
  85.                     typename iterator_traits<_ForwardIter1>::value_type);
  86.   __iter_swap(__a, __b, __VALUE_TYPE(__a));
  87. }
  88.  
  89. template <class _Tp>
  90. inline void swap(_Tp& __a, _Tp& __b) {
  91.   __STL_REQUIRES(_Tp, _Assignable);
  92.   _Tp __tmp = __a;
  93.   __a = __b;
  94.   __b = __tmp;
  95. }
  96.  
  97. //--------------------------------------------------
  98. // min and max
  99.  
  100. #if !defined(__BORLANDC__) || __BORLANDC__ >= 0x540 /* C++ Builder 4.0 */
  101.  
  102. #undef min
  103. #undef max
  104.  
  105. template <class _Tp>
  106. inline const _Tp& min(const _Tp& __a, const _Tp& __b) {
  107.   __STL_REQUIRES(_Tp, _LessThanComparable);
  108.   return __b < __a ? __b : __a;
  109. }
  110.  
  111. template <class _Tp>
  112. inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
  113.   __STL_REQUIRES(_Tp, _LessThanComparable);
  114.   return  __a < __b ? __b : __a;
  115. }
  116.  
  117. #endif /* __BORLANDC__ */
  118.  
  119. template <class _Tp, class _Compare>
  120. inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  121.   return __comp(__b, __a) ? __b : __a;
  122. }
  123.  
  124. template <class _Tp, class _Compare>
  125. inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  126.   return __comp(__a, __b) ? __b : __a;
  127. }
  128.  
  129. //--------------------------------------------------
  130. // copy
  131.  
  132. // All of these auxiliary functions serve two purposes.  (1) Replace
  133. // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
  134. // because the input and output ranges are permitted to overlap.)
  135. // (2) If we're using random access iterators, then write the loop as
  136. // a for loop with an explicit count.
  137.  
  138. template <class _InputIter, class _OutputIter, class _Distance>
  139. inline _OutputIter __copy(_InputIter __first, _InputIter __last,
  140.                           _OutputIter __result,
  141.                           input_iterator_tag, _Distance*)
  142. {
  143.   for ( ; __first != __last; ++__result, ++__first)
  144.     *__result = *__first;
  145.   return __result;
  146. }
  147.  
  148. template <class _RandomAccessIter, class _OutputIter, class _Distance>
  149. inline _OutputIter
  150. __copy(_RandomAccessIter __first, _RandomAccessIter __last,
  151.        _OutputIter __result, random_access_iterator_tag, _Distance*)
  152. {
  153.   for (_Distance __n = __last - __first; __n > 0; --__n) {
  154.     *__result = *__first;
  155.     ++__first;
  156.     ++__result;
  157.   }
  158.   return __result;
  159. }
  160.  
  161. template <class _Tp>
  162. inline _Tp*
  163. __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  164.   memmove(__result, __first, sizeof(_Tp) * (__last - __first));
  165.   return __result + (__last - __first);
  166. }
  167.  
  168. #if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
  169.  
  170. template <class _InputIter, class _OutputIter>
  171. inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
  172.                                _OutputIter __result, __false_type) {
  173.   return __copy(__first, __last, __result,
  174.                 __ITERATOR_CATEGORY(__first),
  175.                 __DISTANCE_TYPE(__first));
  176. }
  177.  
  178. template <class _InputIter, class _OutputIter>
  179. inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
  180.                                _OutputIter __result, __true_type) {
  181.   return __copy(__first, __last, __result,
  182.                 __ITERATOR_CATEGORY(__first),
  183.                 __DISTANCE_TYPE(__first));
  184. }
  185.  
  186. #ifndef __USLC__
  187.  
  188. template <class _Tp>
  189. inline _Tp* __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result,
  190.                         __true_type) {
  191.   return __copy_trivial(__first, __last, __result);
  192. }
  193.  
  194. #endif /* __USLC__ */
  195.  
  196. template <class _Tp>
  197. inline _Tp* __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,
  198.                         __true_type) {
  199.   return __copy_trivial(__first, __last, __result);
  200. }
  201.  
  202.  
  203. template <class _InputIter, class _OutputIter, class _Tp>
  204. inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last,
  205.                               _OutputIter __result, _Tp*) {
  206.   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
  207.           _Trivial;
  208.   return __copy_aux2(__first, __last, __result, _Trivial());
  209. }
  210.  
  211. template <class _InputIter, class _OutputIter>
  212. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  213.                         _OutputIter __result) {
  214.   __STL_REQUIRES(_InputIter, _InputIterator);
  215.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  216.   return __copy_aux(__first, __last, __result, __VALUE_TYPE(__first));
  217. }
  218.  
  219. // Hack for compilers that don't have partial ordering of function templates
  220. // but do have partial specialization of class templates.
  221. #elif defined(__STL_CLASS_PARTIAL_SPECIALIZATION)
  222.  
  223. template <class _InputIter, class _OutputIter, class _BoolType>
  224. struct __copy_dispatch {
  225.   static _OutputIter copy(_InputIter __first, _InputIter __last,
  226.                           _OutputIter __result) {
  227.     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
  228.     typedef typename iterator_traits<_InputIter>::difference_type _Distance;
  229.     return __copy(__first, __last, __result, _Category(), (_Distance*) 0);
  230.   }
  231. };
  232.  
  233. template <class _Tp>
  234. struct __copy_dispatch<_Tp*, _Tp*, __true_type>
  235. {
  236.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  237.     return __copy_trivial(__first, __last, __result);
  238.   }
  239. };
  240.  
  241. template <class _Tp>
  242. struct __copy_dispatch<const _Tp*, _Tp*, __true_type>
  243. {
  244.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  245.     return __copy_trivial(__first, __last, __result);
  246.   }
  247. };
  248.  
  249. template <class _InputIter, class _OutputIter>
  250. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  251.                         _OutputIter __result) {
  252.   __STL_REQUIRES(_InputIter, _InputIterator);
  253.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  254.   typedef typename iterator_traits<_InputIter>::value_type _Tp;
  255.   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
  256.           _Trivial;
  257.   return __copy_dispatch<_InputIter, _OutputIter, _Trivial>
  258.     ::copy(__first, __last, __result);
  259. }
  260.  
  261. // Fallback for compilers with neither partial ordering nor partial
  262. // specialization.  Define the faster version for the basic builtin
  263. // types.
  264. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  265.  
  266. template <class _InputIter, class _OutputIter>
  267. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  268.                         _OutputIter __result)
  269. {
  270.   return __copy(__first, __last, __result,
  271.                 __ITERATOR_CATEGORY(__first),
  272.                 __DISTANCE_TYPE(__first));
  273. }
  274.  
  275. #define __SGI_STL_DECLARE_COPY_TRIVIAL(_Tp)                                \
  276.   inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) { \
  277.     memmove(__result, __first, sizeof(_Tp) * (__last - __first));          \
  278.     return __result + (__last - __first);                                  \
  279.   }
  280.  
  281. __SGI_STL_DECLARE_COPY_TRIVIAL(char)
  282. __SGI_STL_DECLARE_COPY_TRIVIAL(signed char)
  283. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned char)
  284. __SGI_STL_DECLARE_COPY_TRIVIAL(short)
  285. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned short)
  286. __SGI_STL_DECLARE_COPY_TRIVIAL(int)
  287. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned int)
  288. __SGI_STL_DECLARE_COPY_TRIVIAL(long)
  289. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned long)
  290. #ifdef __STL_HAS_WCHAR_T
  291. __SGI_STL_DECLARE_COPY_TRIVIAL(wchar_t)
  292. #endif
  293. #ifdef _STL_LONG_LONG
  294. __SGI_STL_DECLARE_COPY_TRIVIAL(long long)
  295. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned long long)
  296. #endif 
  297. __SGI_STL_DECLARE_COPY_TRIVIAL(float)
  298. __SGI_STL_DECLARE_COPY_TRIVIAL(double)
  299. __SGI_STL_DECLARE_COPY_TRIVIAL(long double)
  300.  
  301. #undef __SGI_STL_DECLARE_COPY_TRIVIAL
  302. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  303.  
  304. //--------------------------------------------------
  305. // copy_backward
  306.  
  307. template <class _BidirectionalIter1, class _BidirectionalIter2, 
  308.           class _Distance>
  309. inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, 
  310.                                            _BidirectionalIter1 __last, 
  311.                                            _BidirectionalIter2 __result,
  312.                                            bidirectional_iterator_tag,
  313.                                            _Distance*)
  314. {
  315.   while (__first != __last)
  316.     *--__result = *--__last;
  317.   return __result;
  318. }
  319.  
  320. template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
  321. inline _BidirectionalIter __copy_backward(_RandomAccessIter __first, 
  322.                                           _RandomAccessIter __last, 
  323.                                           _BidirectionalIter __result,
  324.                                           random_access_iterator_tag,
  325.                                           _Distance*)
  326. {
  327.   for (_Distance __n = __last - __first; __n > 0; --__n)
  328.     *--__result = *--__last;
  329.   return __result;
  330. }
  331.  
  332. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
  333.  
  334. // This dispatch class is a workaround for compilers that do not 
  335. // have partial ordering of function templates.  All we're doing is
  336. // creating a specialization so that we can turn a call to copy_backward
  337. // into a memmove whenever possible.
  338.  
  339. template <class _BidirectionalIter1, class _BidirectionalIter2,
  340.           class _BoolType>
  341. struct __copy_backward_dispatch
  342. {
  343.   typedef typename iterator_traits<_BidirectionalIter1>::iterator_category 
  344.           _Cat;
  345.   typedef typename iterator_traits<_BidirectionalIter1>::difference_type
  346.           _Distance;
  347.  
  348.   static _BidirectionalIter2 copy(_BidirectionalIter1 __first, 
  349.                                   _BidirectionalIter1 __last, 
  350.                                   _BidirectionalIter2 __result) {
  351.     return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
  352.   }
  353. };
  354.  
  355. template <class _Tp>
  356. struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  357. {
  358.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  359.     const ptrdiff_t _Num = __last - __first;
  360.     memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
  361.     return __result - _Num;
  362.   }
  363. };
  364.  
  365. template <class _Tp>
  366. struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
  367. {
  368.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  369.     return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  370.       ::copy(__first, __last, __result);
  371.   }
  372. };
  373.  
  374. template <class _BI1, class _BI2>
  375. inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
  376.   __STL_REQUIRES(_BI1, _BidirectionalIterator);
  377.   __STL_REQUIRES(_BI2, _Mutable_BidirectionalIterator);
  378.   __STL_CONVERTIBLE(typename iterator_traits<_BI1>::value_type,
  379.                     typename iterator_traits<_BI2>::value_type);
  380.   typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
  381.                         ::has_trivial_assignment_operator
  382.           _Trivial;
  383.   return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
  384.               ::copy(__first, __last, __result);
  385. }
  386.  
  387. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  388.  
  389. template <class _BI1, class _BI2>
  390. inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
  391.   return __copy_backward(__first, __last, __result,
  392.                          __ITERATOR_CATEGORY(__first),
  393.                          __DISTANCE_TYPE(__first));
  394. }
  395.  
  396. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  397.  
  398. //--------------------------------------------------
  399. // copy_n (not part of the C++ standard)
  400.  
  401. template <class _InputIter, class _Size, class _OutputIter>
  402. pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
  403.                                        _OutputIter __result,
  404.                                        input_iterator_tag) {
  405.   for ( ; __count > 0; --__count) {
  406.     *__result = *__first;
  407.     ++__first;
  408.     ++__result;
  409.   }
  410.   return pair<_InputIter, _OutputIter>(__first, __result);
  411. }
  412.  
  413. template <class _RAIter, class _Size, class _OutputIter>
  414. inline pair<_RAIter, _OutputIter>
  415. __copy_n(_RAIter __first, _Size __count,
  416.          _OutputIter __result,
  417.          random_access_iterator_tag) {
  418.   _RAIter __last = __first + __count;
  419.   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
  420. }
  421.  
  422. template <class _InputIter, class _Size, class _OutputIter>
  423. inline pair<_InputIter, _OutputIter>
  424. __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  425.   return __copy_n(__first, __count, __result,
  426.                   __ITERATOR_CATEGORY(__first));
  427. }
  428.  
  429. template <class _InputIter, class _Size, class _OutputIter>
  430. inline pair<_InputIter, _OutputIter>
  431. copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  432.   __STL_REQUIRES(_InputIter, _InputIterator);
  433.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  434.   return __copy_n(__first, __count, __result);
  435. }
  436.  
  437. //--------------------------------------------------
  438. // fill and fill_n
  439.  
  440.  
  441. template <class _ForwardIter, class _Tp>
  442. void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) {
  443.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  444.   for ( ; __first != __last; ++__first)
  445.     *__first = __value;
  446. }
  447.  
  448. template <class _OutputIter, class _Size, class _Tp>
  449. _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) {
  450.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  451.   for ( ; __n > 0; --__n, ++__first)
  452.     *__first = __value;
  453.   return __first;
  454. }
  455.  
  456. // Specialization: for one-byte types we can use memset.
  457.  
  458. inline void fill(unsigned char* __first, unsigned char* __last,
  459.                  const unsigned char& __c) {
  460.   unsigned char __tmp = __c;
  461.   memset(__first, __tmp, __last - __first);
  462. }
  463.  
  464. inline void fill(signed char* __first, signed char* __last,
  465.                  const signed char& __c) {
  466.   signed char __tmp = __c;
  467.   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
  468. }
  469.  
  470. inline void fill(char* __first, char* __last, const char& __c) {
  471.   char __tmp = __c;
  472.   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
  473. }
  474.  
  475. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  476.  
  477. template <class _Size>
  478. inline unsigned char* fill_n(unsigned char* __first, _Size __n,
  479.                              const unsigned char& __c) {
  480.   fill(__first, __first + __n, __c);
  481.   return __first + __n;
  482. }
  483.  
  484. template <class _Size>
  485. inline signed char* fill_n(char* __first, _Size __n,
  486.                            const signed char& __c) {
  487.   fill(__first, __first + __n, __c);
  488.   return __first + __n;
  489. }
  490.  
  491. template <class _Size>
  492. inline char* fill_n(char* __first, _Size __n, const char& __c) {
  493.   fill(__first, __first + __n, __c);
  494.   return __first + __n;
  495. }
  496.  
  497. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  498.  
  499. //--------------------------------------------------
  500. // equal and mismatch
  501.  
  502. template <class _InputIter1, class _InputIter2>
  503. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  504.                                         _InputIter1 __last1,
  505.                                         _InputIter2 __first2) {
  506.   __STL_REQUIRES(_InputIter1, _InputIterator);
  507.   __STL_REQUIRES(_InputIter2, _InputIterator);
  508.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  509.                  _EqualityComparable);
  510.   __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
  511.                  _EqualityComparable);
  512.   while (__first1 != __last1 && *__first1 == *__first2) {
  513.     ++__first1;
  514.     ++__first2;
  515.   }
  516.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  517. }
  518.  
  519. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  520. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  521.                                         _InputIter1 __last1,
  522.                                         _InputIter2 __first2,
  523.                                         _BinaryPredicate __binary_pred) {
  524.   __STL_REQUIRES(_InputIter1, _InputIterator);
  525.   __STL_REQUIRES(_InputIter2, _InputIterator);
  526.   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
  527.     ++__first1;
  528.     ++__first2;
  529.   }
  530.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  531. }
  532.  
  533. template <class _InputIter1, class _InputIter2>
  534. inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
  535.                   _InputIter2 __first2) {
  536.   __STL_REQUIRES(_InputIter1, _InputIterator);
  537.   __STL_REQUIRES(_InputIter2, _InputIterator);
  538.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  539.                  _EqualityComparable);
  540.   __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
  541.                  _EqualityComparable);
  542.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  543.     if (*__first1 != *__first2)
  544.       return false;
  545.   return true;
  546. }
  547.  
  548. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  549. inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
  550.                   _InputIter2 __first2, _BinaryPredicate __binary_pred) {
  551.   __STL_REQUIRES(_InputIter1, _InputIterator);
  552.   __STL_REQUIRES(_InputIter2, _InputIterator);
  553.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  554.     if (!__binary_pred(*__first1, *__first2))
  555.       return false;
  556.   return true;
  557. }
  558.  
  559. //--------------------------------------------------
  560. // lexicographical_compare and lexicographical_compare_3way.
  561. // (the latter is not part of the C++ standard.)
  562.  
  563. template <class _InputIter1, class _InputIter2>
  564. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  565.                              _InputIter2 __first2, _InputIter2 __last2) {
  566.   __STL_REQUIRES(_InputIter1, _InputIterator);
  567.   __STL_REQUIRES(_InputIter2, _InputIterator);
  568.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  569.                  _LessThanComparable);
  570.   __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
  571.                  _LessThanComparable);
  572.   for ( ; __first1 != __last1 && __first2 != __last2
  573.         ; ++__first1, ++__first2) {
  574.     if (*__first1 < *__first2)
  575.       return true;
  576.     if (*__first2 < *__first1)
  577.       return false;
  578.   }
  579.   return __first1 == __last1 && __first2 != __last2;
  580. }
  581.  
  582. template <class _InputIter1, class _InputIter2, class _Compare>
  583. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  584.                              _InputIter2 __first2, _InputIter2 __last2,
  585.                              _Compare __comp) {
  586.   __STL_REQUIRES(_InputIter1, _InputIterator);
  587.   __STL_REQUIRES(_InputIter2, _InputIterator);
  588.   for ( ; __first1 != __last1 && __first2 != __last2
  589.         ; ++__first1, ++__first2) {
  590.     if (__comp(*__first1, *__first2))
  591.       return true;
  592.     if (__comp(*__first2, *__first1))
  593.       return false;
  594.   }
  595.   return __first1 == __last1 && __first2 != __last2;
  596. }
  597.  
  598. inline bool 
  599. lexicographical_compare(const unsigned char* __first1,
  600.                         const unsigned char* __last1,
  601.                         const unsigned char* __first2,
  602.                         const unsigned char* __last2)
  603. {
  604.   const size_t __len1 = __last1 - __first1;
  605.   const size_t __len2 = __last2 - __first2;
  606.   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  607.   return __result != 0 ? __result < 0 : __len1 < __len2;
  608. }
  609.  
  610. inline bool lexicographical_compare(const char* __first1, const char* __last1,
  611.                                     const char* __first2, const char* __last2)
  612. {
  613. #if CHAR_MAX == SCHAR_MAX
  614.   return lexicographical_compare((const signed char*) __first1,
  615.                                  (const signed char*) __last1,
  616.                                  (const signed char*) __first2,
  617.                                  (const signed char*) __last2);
  618. #else /* CHAR_MAX == SCHAR_MAX */
  619.   return lexicographical_compare((const unsigned char*) __first1,
  620.                                  (const unsigned char*) __last1,
  621.                                  (const unsigned char*) __first2,
  622.                                  (const unsigned char*) __last2);
  623. #endif /* CHAR_MAX == SCHAR_MAX */
  624. }
  625.  
  626. template <class _InputIter1, class _InputIter2>
  627. int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  628.                                    _InputIter2 __first2, _InputIter2 __last2)
  629. {
  630.   while (__first1 != __last1 && __first2 != __last2) {
  631.     if (*__first1 < *__first2)
  632.       return -1;
  633.     if (*__first2 < *__first1)
  634.       return 1;
  635.     ++__first1;
  636.     ++__first2;
  637.   }
  638.   if (__first2 == __last2) {
  639.     return !(__first1 == __last1);
  640.   }
  641.   else {
  642.     return -1;
  643.   }
  644. }
  645.  
  646. inline int
  647. __lexicographical_compare_3way(const unsigned char* __first1,
  648.                                const unsigned char* __last1,
  649.                                const unsigned char* __first2,
  650.                                const unsigned char* __last2)
  651. {
  652.   const ptrdiff_t __len1 = __last1 - __first1;
  653.   const ptrdiff_t __len2 = __last2 - __first2;
  654.   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  655.   return __result != 0 ? __result 
  656.                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
  657. }
  658.  
  659. inline int 
  660. __lexicographical_compare_3way(const char* __first1, const char* __last1,
  661.                                const char* __first2, const char* __last2)
  662. {
  663. #if CHAR_MAX == SCHAR_MAX
  664.   return __lexicographical_compare_3way(
  665.                                 (const signed char*) __first1,
  666.                                 (const signed char*) __last1,
  667.                                 (const signed char*) __first2,
  668.                                 (const signed char*) __last2);
  669. #else
  670.   return __lexicographical_compare_3way((const unsigned char*) __first1,
  671.                                         (const unsigned char*) __last1,
  672.                                         (const unsigned char*) __first2,
  673.                                         (const unsigned char*) __last2);
  674. #endif
  675. }
  676.  
  677. template <class _InputIter1, class _InputIter2>
  678. int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  679.                                  _InputIter2 __first2, _InputIter2 __last2)
  680. {
  681.   __STL_REQUIRES(_InputIter1, _InputIterator);
  682.   __STL_REQUIRES(_InputIter2, _InputIterator);
  683.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  684.                  _LessThanComparable);
  685.   __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
  686.                  _LessThanComparable);
  687.   return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
  688. }
  689.  
  690. __STL_END_NAMESPACE
  691.  
  692. #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
  693.  
  694. // Local Variables:
  695. // mode:C++
  696. // End:
  697.