Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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. #include <bits/c++config.h>
  36. #ifndef __SGI_STL_INTERNAL_PAIR_H
  37. #include <bits/stl_pair.h>
  38. #endif
  39. #ifndef _CPP_BITS_TYPE_TRAITS_H
  40. #include <bits/type_traits.h>
  41. #endif
  42. #include <bits/std_cstring.h>
  43. #include <bits/std_climits.h>
  44. #include <bits/std_cstdlib.h>
  45. #include <bits/std_cstddef.h>
  46. #include <new>
  47.  
  48. #include <bits/std_iosfwd.h>
  49. #include <bits/stl_iterator_base_types.h>
  50. #include <bits/stl_iterator_base_funcs.h>
  51. #include <bits/stl_iterator.h>
  52. #include <bits/concept_check.h>
  53.  
  54. namespace std
  55. {
  56.  
  57. // swap and iter_swap
  58.  
  59. template <class _ForwardIter1, class _ForwardIter2, class _Tp>
  60. inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*)
  61. {
  62.   _Tp __tmp = *__a;
  63.   *__a = *__b;
  64.   *__b = __tmp;
  65. }
  66.  
  67. template <class _ForwardIter1, class _ForwardIter2>
  68. inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b)
  69. {
  70.   // concept requirements
  71.   __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>);
  72.   __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>);
  73.   __glibcpp_function_requires(_ConvertibleConcept<
  74.         typename iterator_traits<_ForwardIter1>::value_type,
  75.         typename iterator_traits<_ForwardIter2>::value_type>);
  76.   __glibcpp_function_requires(_ConvertibleConcept<
  77.         typename iterator_traits<_ForwardIter2>::value_type,
  78.         typename iterator_traits<_ForwardIter1>::value_type>);
  79.  
  80.   __iter_swap(__a, __b, __value_type(__a));
  81. }
  82.  
  83. template <class _Tp>
  84. inline void swap(_Tp& __a, _Tp& __b)
  85. {
  86.   // concept requirements
  87.   __glibcpp_function_requires(_SGIAssignableConcept<_Tp>);
  88.  
  89.   _Tp __tmp = __a;
  90.   __a = __b;
  91.   __b = __tmp;
  92. }
  93.  
  94. //--------------------------------------------------
  95. // min and max
  96.  
  97. #undef min
  98. #undef max
  99.  
  100. template <class _Tp>
  101. inline const _Tp& min(const _Tp& __a, const _Tp& __b) {
  102.   // concept requirements
  103.   __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
  104.   //return __b < __a ? __b : __a;
  105.   if (__b < __a) return __b; return __a;
  106. }
  107.  
  108. template <class _Tp>
  109. inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
  110.   // concept requirements
  111.   __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
  112.   //return  __a < __b ? __b : __a;
  113.   if (__a < __b) return __b; return __a;
  114. }
  115.  
  116. template <class _Tp, class _Compare>
  117. inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  118.   //return __comp(__b, __a) ? __b : __a;
  119.   if (__comp(__b, __a)) return __b; return __a;
  120. }
  121.  
  122. template <class _Tp, class _Compare>
  123. inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  124.   //return __comp(__a, __b) ? __b : __a;
  125.   if (__comp(__a, __b)) return __b; return __a;
  126. }
  127.  
  128. //--------------------------------------------------
  129. // copy
  130.  
  131. // All of these auxiliary functions serve two purposes.  (1) Replace
  132. // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
  133. // because the input and output ranges are permitted to overlap.)
  134. // (2) If we're using random access iterators, then write the loop as
  135. // a for loop with an explicit count.
  136.  
  137. template <class _InputIter, class _OutputIter, class _Distance>
  138. inline _OutputIter __copy(_InputIter __first, _InputIter __last,
  139.                           _OutputIter __result,
  140.                           input_iterator_tag, _Distance*)
  141. {
  142.   for ( ; __first != __last; ++__result, ++__first)
  143.     *__result = *__first;
  144.   return __result;
  145. }
  146.  
  147. template <class _RandomAccessIter, class _OutputIter, class _Distance>
  148. inline _OutputIter
  149. __copy(_RandomAccessIter __first, _RandomAccessIter __last,
  150.        _OutputIter __result, random_access_iterator_tag, _Distance*)
  151. {
  152.   for (_Distance __n = __last - __first; __n > 0; --__n) {
  153.     *__result = *__first;
  154.     ++__first;
  155.     ++__result;
  156.   }
  157.   return __result;
  158. }
  159.  
  160. template <class _Tp>
  161. inline _Tp*
  162. __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
  163. {
  164.   memmove(__result, __first, sizeof(_Tp) * (__last - __first));
  165.   return __result + (__last - __first);
  166. }
  167.  
  168.  
  169. template <class _InputIter, class _OutputIter>
  170. inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
  171.                                _OutputIter __result, __false_type)
  172. {
  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. {
  182.   return __copy(__first, __last, __result,
  183.                 __iterator_category(__first),
  184.                 __distance_type(__first));
  185. }
  186.  
  187. template <class _Tp>
  188. inline _Tp* __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result,
  189.                         __true_type)
  190. {
  191.   return __copy_trivial(__first, __last, __result);
  192. }
  193.  
  194. template <class _Tp>
  195. inline _Tp* __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,
  196.                         __true_type)
  197. {
  198.   return __copy_trivial(__first, __last, __result);
  199. }
  200.  
  201.  
  202. template <class _InputIter, class _OutputIter, class _Tp>
  203. inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last,
  204.                               _OutputIter __result, _Tp*)
  205. {
  206.   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
  207.           _Trivial;
  208.   return __copy_aux2(__first, __last, __result, _Trivial());
  209. }
  210.  
  211. template<typename _InputIter, typename _OutputIter>
  212. inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,
  213.                                _OutputIter __result, __true_type)
  214. {
  215.   return _OutputIter(__copy_aux(__first, __last, __result.base(),
  216.                                 __value_type(__first)));
  217. }
  218.  
  219. template<typename _InputIter, typename _OutputIter>
  220. inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,
  221.                               _OutputIter __result, __false_type)
  222. {
  223.   return __copy_aux(__first, __last, __result, __value_type(__first));
  224. }
  225.  
  226. template<typename _InputIter, typename _OutputIter>
  227. inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,
  228.                                _OutputIter __result, __true_type)
  229. {
  230.   typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
  231.   return __copy_ni2(__first.base(), __last.base(), __result, __Normal());
  232. }
  233.  
  234. template<typename _InputIter, typename _OutputIter>
  235. inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,
  236.                                _OutputIter __result, __false_type)
  237. {
  238.   typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
  239.   return __copy_ni2(__first, __last, __result, __Normal());
  240. }
  241.  
  242. template <class _InputIter, class _OutputIter>
  243. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  244.                         _OutputIter __result)
  245. {
  246.   // concept requirements
  247.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  248.   __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  249.         typename iterator_traits<_InputIter>::value_type>);
  250.  
  251.    typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal;
  252.    return __copy_ni1(__first, __last, __result, __Normal());
  253. }
  254.  
  255. //--------------------------------------------------
  256. // copy_backward
  257.  
  258. template <class _BidirectionalIter1, class _BidirectionalIter2,
  259.           class _Distance>
  260. inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
  261.                                            _BidirectionalIter1 __last,
  262.                                            _BidirectionalIter2 __result,
  263.                                            bidirectional_iterator_tag,
  264.                                            _Distance*)
  265. {
  266.   while (__first != __last)
  267.     *--__result = *--__last;
  268.   return __result;
  269. }
  270.  
  271. template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
  272. inline _BidirectionalIter __copy_backward(_RandomAccessIter __first,
  273.                                           _RandomAccessIter __last,
  274.                                           _BidirectionalIter __result,
  275.                                           random_access_iterator_tag,
  276.                                           _Distance*)
  277. {
  278.   for (_Distance __n = __last - __first; __n > 0; --__n)
  279.     *--__result = *--__last;
  280.   return __result;
  281. }
  282.  
  283.  
  284. // This dispatch class is a workaround for compilers that do not
  285. // have partial ordering of function templates.  All we're doing is
  286. // creating a specialization so that we can turn a call to copy_backward
  287. // into a memmove whenever possible.
  288.  
  289. template <class _BidirectionalIter1, class _BidirectionalIter2,
  290.           class _BoolType>
  291. struct __copy_backward_dispatch
  292. {
  293.   typedef typename iterator_traits<_BidirectionalIter1>::iterator_category
  294.           _Cat;
  295.   typedef typename iterator_traits<_BidirectionalIter1>::difference_type
  296.           _Distance;
  297.  
  298.   static _BidirectionalIter2 copy(_BidirectionalIter1 __first,
  299.                                   _BidirectionalIter1 __last,
  300.                                   _BidirectionalIter2 __result) {
  301.     return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
  302.   }
  303. };
  304.  
  305. template <class _Tp>
  306. struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  307. {
  308.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  309.     const ptrdiff_t _Num = __last - __first;
  310.     memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
  311.     return __result - _Num;
  312.   }
  313. };
  314.  
  315. template <class _Tp>
  316. struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
  317. {
  318.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  319.     return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  320.       ::copy(__first, __last, __result);
  321.   }
  322. };
  323.  
  324. template <class _BI1, class _BI2>
  325. inline _BI2 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) {
  326.   typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
  327.                         ::has_trivial_assignment_operator
  328.           _Trivial;
  329.   return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
  330.               ::copy(__first, __last, __result);
  331. }
  332.  
  333. template <typename _BI1, typename _BI2>
  334. inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
  335.                                                    _BI2 __result, __true_type) {
  336.   return _BI2(__copy_backward_aux(__first, __last, __result.base()));
  337. }
  338.  
  339. template <typename _BI1, typename _BI2>
  340. inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
  341.                                                    _BI2 __result, __false_type){
  342.   return __copy_backward_aux(__first, __last, __result);
  343. }
  344.  
  345. template <typename _BI1, typename _BI2>
  346. inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
  347.                                                   _BI2 __result, __true_type) {
  348.   typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
  349.   return __copy_backward_output_normal_iterator(__first.base(), __last.base(),
  350.                                                 __result, __Normal());
  351. }
  352.  
  353. template <typename _BI1, typename _BI2>
  354. inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
  355.                                                   _BI2 __result, __false_type) {
  356.   typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
  357.   return __copy_backward_output_normal_iterator(__first, __last, __result,
  358.                                                 __Normal());
  359. }
  360.  
  361. template <typename _BI1, typename _BI2>
  362. inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
  363. {
  364.   // concept requirements
  365.   __glibcpp_function_requires(_BidirectionalIteratorConcept<_BI1>);
  366.   __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>);
  367.   __glibcpp_function_requires(_ConvertibleConcept<
  368.         typename iterator_traits<_BI1>::value_type,
  369.         typename iterator_traits<_BI2>::value_type>);
  370.  
  371.   typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
  372.   return __copy_backward_input_normal_iterator(__first, __last, __result,
  373.                                                __Normal());
  374. }
  375.  
  376. //--------------------------------------------------
  377. // copy_n (not part of the C++ standard)
  378.  
  379. template <class _InputIter, class _Size, class _OutputIter>
  380. pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
  381.                                        _OutputIter __result,
  382.                                        input_iterator_tag) {
  383.   for ( ; __count > 0; --__count) {
  384.     *__result = *__first;
  385.     ++__first;
  386.     ++__result;
  387.   }
  388.   return pair<_InputIter, _OutputIter>(__first, __result);
  389. }
  390.  
  391. template <class _RAIter, class _Size, class _OutputIter>
  392. inline pair<_RAIter, _OutputIter>
  393. __copy_n(_RAIter __first, _Size __count,
  394.          _OutputIter __result,
  395.          random_access_iterator_tag) {
  396.   _RAIter __last = __first + __count;
  397.   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
  398. }
  399.  
  400. template <class _InputIter, class _Size, class _OutputIter>
  401. inline pair<_InputIter, _OutputIter>
  402. __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  403.   return __copy_n(__first, __count, __result,
  404.                   __iterator_category(__first));
  405. }
  406.  
  407. template <class _InputIter, class _Size, class _OutputIter>
  408. inline pair<_InputIter, _OutputIter>
  409. copy_n(_InputIter __first, _Size __count, _OutputIter __result)
  410. {
  411.   // concept requirements
  412.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  413.   __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  414.         typename iterator_traits<_InputIter>::value_type>);
  415.  
  416.   return __copy_n(__first, __count, __result);
  417. }
  418.  
  419. //--------------------------------------------------
  420. // fill and fill_n
  421.  
  422.  
  423. template <class _ForwardIter, class _Tp>
  424. void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)
  425. {
  426.   // concept requirements
  427.   __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
  428.  
  429.   for ( ; __first != __last; ++__first)
  430.     *__first = __value;
  431. }
  432.  
  433. template <class _OutputIter, class _Size, class _Tp>
  434. _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value)
  435. {
  436.   // concept requirements
  437.   __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,_Tp>);
  438.  
  439.   for ( ; __n > 0; --__n, ++__first)
  440.     *__first = __value;
  441.   return __first;
  442. }
  443.  
  444. // Specialization: for one-byte types we can use memset.
  445.  
  446. inline void fill(unsigned char* __first, unsigned char* __last,
  447.                  const unsigned char& __c)
  448. {
  449.   unsigned char __tmp = __c;
  450.   memset(__first, __tmp, __last - __first);
  451. }
  452.  
  453. inline void fill(signed char* __first, signed char* __last,
  454.                  const signed char& __c)
  455. {
  456.   signed char __tmp = __c;
  457.   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
  458. }
  459.  
  460. inline void fill(char* __first, char* __last, const char& __c)
  461. {
  462.   char __tmp = __c;
  463.   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
  464. }
  465.  
  466. template <class _Size>
  467. inline unsigned char* fill_n(unsigned char* __first, _Size __n,
  468.                              const unsigned char& __c)
  469. {
  470.   fill(__first, __first + __n, __c);
  471.   return __first + __n;
  472. }
  473.  
  474. template <class _Size>
  475. inline signed char* fill_n(char* __first, _Size __n,
  476.                            const signed char& __c)
  477. {
  478.   fill(__first, __first + __n, __c);
  479.   return __first + __n;
  480. }
  481.  
  482. template <class _Size>
  483. inline char* fill_n(char* __first, _Size __n, const char& __c)
  484. {
  485.   fill(__first, __first + __n, __c);
  486.   return __first + __n;
  487. }
  488.  
  489.  
  490. //--------------------------------------------------
  491. // equal and mismatch
  492.  
  493. template <class _InputIter1, class _InputIter2>
  494. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  495.                                         _InputIter1 __last1,
  496.                                         _InputIter2 __first2)
  497. {
  498.   // concept requirements
  499.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
  500.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
  501.   __glibcpp_function_requires(_EqualityComparableConcept<
  502.         typename iterator_traits<_InputIter1>::value_type>);
  503.   __glibcpp_function_requires(_EqualityComparableConcept<
  504.         typename iterator_traits<_InputIter2>::value_type>);
  505.  
  506.   while (__first1 != __last1 && *__first1 == *__first2) {
  507.     ++__first1;
  508.     ++__first2;
  509.   }
  510.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  511. }
  512.  
  513. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  514. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  515.                                         _InputIter1 __last1,
  516.                                         _InputIter2 __first2,
  517.                                         _BinaryPredicate __binary_pred)
  518. {
  519.   // concept requirements
  520.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
  521.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
  522.  
  523.   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
  524.     ++__first1;
  525.     ++__first2;
  526.   }
  527.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  528. }
  529.  
  530. template <class _InputIter1, class _InputIter2>
  531. inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
  532.                   _InputIter2 __first2)
  533. {
  534.   // concept requirements
  535.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
  536.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
  537.   __glibcpp_function_requires(_EqualOpConcept<
  538.         typename iterator_traits<_InputIter1>::value_type,
  539.         typename iterator_traits<_InputIter2>::value_type>);
  540.  
  541.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  542.     if (!(*__first1 == *__first2))
  543.       return false;
  544.   return true;
  545. }
  546.  
  547. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  548. inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
  549.                   _InputIter2 __first2, _BinaryPredicate __binary_pred)
  550. {
  551.   // concept requirements
  552.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
  553.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
  554.  
  555.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  556.     if (!__binary_pred(*__first1, *__first2))
  557.       return false;
  558.   return true;
  559. }
  560.  
  561. //--------------------------------------------------
  562. // lexicographical_compare and lexicographical_compare_3way.
  563. // (the latter is not part of the C++ standard.)
  564.  
  565. template <class _InputIter1, class _InputIter2>
  566. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  567.                              _InputIter2 __first2, _InputIter2 __last2)
  568. {
  569.   // concept requirements
  570.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
  571.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
  572.   __glibcpp_function_requires(_LessThanComparableConcept<
  573.         typename iterator_traits<_InputIter1>::value_type>);
  574.   __glibcpp_function_requires(_LessThanComparableConcept<
  575.         typename iterator_traits<_InputIter2>::value_type>);
  576.  
  577.   for ( ; __first1 != __last1 && __first2 != __last2
  578.         ; ++__first1, ++__first2) {
  579.     if (*__first1 < *__first2)
  580.       return true;
  581.     if (*__first2 < *__first1)
  582.       return false;
  583.   }
  584.   return __first1 == __last1 && __first2 != __last2;
  585. }
  586.  
  587. template <class _InputIter1, class _InputIter2, class _Compare>
  588. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  589.                              _InputIter2 __first2, _InputIter2 __last2,
  590.                              _Compare __comp)
  591. {
  592.   // concept requirements
  593.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
  594.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
  595.  
  596.   for ( ; __first1 != __last1 && __first2 != __last2
  597.         ; ++__first1, ++__first2) {
  598.     if (__comp(*__first1, *__first2))
  599.       return true;
  600.     if (__comp(*__first2, *__first1))
  601.       return false;
  602.   }
  603.   return __first1 == __last1 && __first2 != __last2;
  604. }
  605.  
  606. inline bool
  607. lexicographical_compare(const unsigned char* __first1,
  608.                         const unsigned char* __last1,
  609.                         const unsigned char* __first2,
  610.                         const unsigned char* __last2)
  611. {
  612.   const size_t __len1 = __last1 - __first1;
  613.   const size_t __len2 = __last2 - __first2;
  614.   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  615.   return __result != 0 ? __result < 0 : __len1 < __len2;
  616. }
  617.  
  618. inline bool lexicographical_compare(const char* __first1, const char* __last1,
  619.                                     const char* __first2, const char* __last2)
  620. {
  621. #if CHAR_MAX == SCHAR_MAX
  622.   return lexicographical_compare((const signed char*) __first1,
  623.                                  (const signed char*) __last1,
  624.                                  (const signed char*) __first2,
  625.                                  (const signed char*) __last2);
  626. #else /* CHAR_MAX == SCHAR_MAX */
  627.   return lexicographical_compare((const unsigned char*) __first1,
  628.                                  (const unsigned char*) __last1,
  629.                                  (const unsigned char*) __first2,
  630.                                  (const unsigned char*) __last2);
  631. #endif /* CHAR_MAX == SCHAR_MAX */
  632. }
  633.  
  634. template <class _InputIter1, class _InputIter2>
  635. int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  636.                                    _InputIter2 __first2, _InputIter2 __last2)
  637. {
  638.   while (__first1 != __last1 && __first2 != __last2) {
  639.     if (*__first1 < *__first2)
  640.       return -1;
  641.     if (*__first2 < *__first1)
  642.       return 1;
  643.     ++__first1;
  644.     ++__first2;
  645.   }
  646.   if (__first2 == __last2) {
  647.     return !(__first1 == __last1);
  648.   }
  649.   else {
  650.     return -1;
  651.   }
  652. }
  653.  
  654. inline int
  655. __lexicographical_compare_3way(const unsigned char* __first1,
  656.                                const unsigned char* __last1,
  657.                                const unsigned char* __first2,
  658.                                const unsigned char* __last2)
  659. {
  660.   const ptrdiff_t __len1 = __last1 - __first1;
  661.   const ptrdiff_t __len2 = __last2 - __first2;
  662.   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  663.   return __result != 0 ? __result
  664.                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
  665. }
  666.  
  667. inline int
  668. __lexicographical_compare_3way(const char* __first1, const char* __last1,
  669.                                const char* __first2, const char* __last2)
  670. {
  671. #if CHAR_MAX == SCHAR_MAX
  672.   return __lexicographical_compare_3way(
  673.                                 (const signed char*) __first1,
  674.                                 (const signed char*) __last1,
  675.                                 (const signed char*) __first2,
  676.                                 (const signed char*) __last2);
  677. #else
  678.   return __lexicographical_compare_3way((const unsigned char*) __first1,
  679.                                         (const unsigned char*) __last1,
  680.                                         (const unsigned char*) __first2,
  681.                                         (const unsigned char*) __last2);
  682. #endif
  683. }
  684.  
  685. template <class _InputIter1, class _InputIter2>
  686. int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  687.                                  _InputIter2 __first2, _InputIter2 __last2)
  688. {
  689.   // concept requirements
  690.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
  691.   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
  692.   __glibcpp_function_requires(_LessThanComparableConcept<
  693.         typename iterator_traits<_InputIter1>::value_type>);
  694.   __glibcpp_function_requires(_LessThanComparableConcept<
  695.         typename iterator_traits<_InputIter2>::value_type>);
  696.  
  697.   return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
  698. }
  699.  
  700. } // namespace std
  701.  
  702. #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
  703.  
  704. // Local Variables:
  705. // mode:C++
  706. // End:
  707.