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.c < prev    next >
C/C++ Source or Header  |  2002-02-02  |  12KB  |  393 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. #ifndef _STLP_ALGOBASE_C
  26. #define _STLP_ALGOBASE_C
  27.  
  28. # if !defined (_STLP_INTERNAL_ALGOBASE_H)
  29. #  include <stl/_algobase.h>
  30. # endif
  31.  
  32. _STLP_BEGIN_NAMESPACE
  33.  
  34. template <class _InputIter1, class _InputIter2>
  35. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  36.                              _InputIter2 __first2, _InputIter2 __last2) {
  37.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  38.     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  39.     for ( ; __first1 != __last1 && __first2 != __last2
  40.         ; ++__first1, ++__first2) {
  41.       if (*__first1 < *__first2)
  42.     return true;
  43.       if (*__first2 < *__first1)
  44.     return false;
  45.     }
  46.   return __first1 == __last1 && __first2 != __last2;
  47. }
  48.  
  49. template <class _InputIter1, class _InputIter2, class _Compare>
  50. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  51.                              _InputIter2 __first2, _InputIter2 __last2,
  52.                              _Compare __comp) {
  53.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  54.     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  55.     for ( ; __first1 != __last1 && __first2 != __last2
  56.         ; ++__first1, ++__first2) {
  57.       if (__comp(*__first1, *__first2))
  58.     return true;
  59.       if (__comp(*__first2, *__first1))
  60.     return false;
  61.     }
  62.   return __first1 == __last1 && __first2 != __last2;
  63. }
  64.  
  65. # ifndef _STLP_NO_EXTENSIONS
  66.  
  67. template <class _InputIter1, class _InputIter2>
  68. int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  69.                                    _InputIter2 __first2, _InputIter2 __last2)
  70. {
  71.   while (__first1 != __last1 && __first2 != __last2) {
  72.     if (*__first1 < *__first2)
  73.       return -1;
  74.     if (*__first2 < *__first1)
  75.       return 1;
  76.     ++__first1;
  77.     ++__first2;
  78.   }
  79.   if (__first2 == __last2) {
  80.     return !(__first1 == __last1);
  81.   }
  82.   else {
  83.     return -1;
  84.   }
  85. }
  86.  
  87.  
  88. template <class _InputIter1, class _InputIter2>
  89. int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  90.                                  _InputIter2 __first2, _InputIter2 __last2)
  91. {
  92.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  93.     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  94.     return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
  95. }
  96. # endif
  97.  
  98. template <class _RandomAccessIter, class _Tp>
  99. _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
  100.                                            const _Tp& __val,
  101.                                            const random_access_iterator_tag &)
  102. {
  103.   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
  104.  
  105.   for ( ; __trip_count > 0 ; --__trip_count) {
  106.     if (*__first == __val) return __first;
  107.     ++__first;
  108.  
  109.     if (*__first == __val) return __first;
  110.     ++__first;
  111.  
  112.     if (*__first == __val) return __first;
  113.     ++__first;
  114.  
  115.     if (*__first == __val) return __first;
  116.     ++__first;
  117.   }
  118.  
  119.   switch(__last - __first) {
  120.   case 3:
  121.     if (*__first == __val) return __first;
  122.     ++__first;
  123.   case 2:
  124.     if (*__first == __val) return __first;
  125.     ++__first;
  126.   case 1:
  127.     if (*__first == __val) return __first;
  128.     ++__first;
  129.   case 0:
  130.   default:
  131.     return __last;
  132.   }
  133. }
  134.  
  135. template <class _RandomAccessIter, class _Predicate>
  136. _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
  137.                                               _Predicate __pred,
  138.                                               const random_access_iterator_tag &)
  139. {
  140.   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
  141.  
  142.   for ( ; __trip_count > 0 ; --__trip_count) {
  143.     if (__pred(*__first)) return __first;
  144.     ++__first;
  145.  
  146.     if (__pred(*__first)) return __first;
  147.     ++__first;
  148.  
  149.     if (__pred(*__first)) return __first;
  150.     ++__first;
  151.  
  152.     if (__pred(*__first)) return __first;
  153.     ++__first;
  154.   }
  155.  
  156.   switch(__last - __first) {
  157.   case 3:
  158.     if (__pred(*__first)) return __first;
  159.     ++__first;
  160.   case 2:
  161.     if (__pred(*__first)) return __first;
  162.     ++__first;
  163.   case 1:
  164.     if (__pred(*__first)) return __first;
  165.     //    ++__first;
  166.   case 0:
  167.   default:
  168.     return __last;
  169.   }
  170. }
  171.  
  172. template <class _InputIter, class _Tp>
  173. inline _InputIter __find(_InputIter __first, _InputIter __last,
  174.              const _Tp& __val,
  175.              const input_iterator_tag &)
  176. {
  177.   while (__first != __last && !(*__first == __val))
  178.     ++__first;
  179.   return __first;
  180. }
  181.  
  182. template <class _InputIter, class _Predicate>
  183. inline _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
  184.                             _Predicate __pred,
  185.                             const input_iterator_tag &)
  186. {
  187.   while (__first != __last && !__pred(*__first))
  188.     ++__first;
  189.   return __first;
  190. }
  191.  
  192. template <class _InputIter, class _Predicate>
  193. _InputIter find_if(_InputIter __first, _InputIter __last,
  194.                    _Predicate __pred) {
  195.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  196.     return __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
  197. }
  198.  
  199. template <class _InputIter, class _Tp>
  200. _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val)
  201. {
  202.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  203.     return __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
  204. }
  205.  
  206. template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
  207. _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  208.                      _ForwardIter2 __first2, _ForwardIter2 __last2,
  209.                      _BinaryPred  __predicate) 
  210. {
  211.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  212.     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  213.     // Test for empty ranges
  214.     if (__first1 == __last1 || __first2 == __last2)
  215.       return __first1;
  216.  
  217.   // Test for a pattern of length 1.
  218.   _ForwardIter2 __tmp(__first2);
  219.   ++__tmp;
  220.   if (__tmp == __last2) {
  221.     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
  222.       ++__first1;
  223.     return __first1;    
  224.   }
  225.   
  226.   // General case.
  227.  
  228.   _ForwardIter2 __p1, __p;
  229.  
  230.   __p1 = __first2; ++__p1;
  231.  
  232.   //  _ForwardIter1 __current = __first1;
  233.  
  234.   while (__first1 != __last1) {
  235.     while (__first1 != __last1) {
  236.       if (__predicate(*__first1, *__first2))
  237.         break;
  238.       ++__first1;
  239.     }
  240.     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
  241.       ++__first1;
  242.     if (__first1 == __last1)
  243.       return __last1;
  244.  
  245.     __p = __p1;
  246.     _ForwardIter1 __current = __first1; 
  247.     if (++__current == __last1) return __last1;
  248.  
  249.     while (__predicate(*__current, *__p)) {
  250.       if (++__p == __last2)
  251.         return __first1;
  252.       if (++__current == __last1)
  253.         return __last1;
  254.     }
  255.  
  256.     ++__first1;
  257.   }
  258.   return __first1;
  259. }
  260.  
  261. // find_first_of, with and without an explicitly supplied comparison function.
  262.  
  263. template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
  264. _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
  265.                            _ForwardIter __first2, _ForwardIter __last2,
  266.                            _BinaryPredicate __comp) {
  267.   for ( ; __first1 != __last1; ++__first1) 
  268.     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
  269.       if (__comp(*__first1, *__iter))
  270.         return __first1;
  271.   return __last1;
  272. }
  273.  
  274.  
  275. // find_end, with and without an explicitly supplied comparison function.
  276. // Search [first2, last2) as a subsequence in [first1, last1), and return
  277. // the *last* possible match.  Note that find_end for bidirectional iterators
  278. // is much faster than for forward iterators.
  279.  
  280. // find_end for forward iterators. 
  281.  
  282. template <class _ForwardIter1, class _ForwardIter2,
  283.   class _BinaryPredicate>
  284. _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
  285.                          _ForwardIter2 __first2, _ForwardIter2 __last2,
  286.                          const forward_iterator_tag &, const forward_iterator_tag &,
  287.                          _BinaryPredicate __comp)
  288. {
  289.   if (__first2 == __last2)
  290.     return __last1;
  291.   else {
  292.     _ForwardIter1 __result = __last1;
  293.     while (1) {
  294.       _ForwardIter1 __new_result
  295.         = search(__first1, __last1, __first2, __last2, __comp);
  296.       if (__new_result == __last1)
  297.         return __result;
  298.       else {
  299.         __result = __new_result;
  300.         __first1 = __new_result;
  301.         ++__first1;
  302.       }
  303.     }
  304.   }
  305. }
  306.  
  307. // find_end for bidirectional iterators.  Requires partial specialization.
  308. #if defined ( _STLP_CLASS_PARTIAL_SPECIALIZATION )
  309.  
  310. #if ! defined (_STLP_INTERNAL_ITERATOR_H)
  311. _STLP_END_NAMESPACE
  312. # include <stl/_iterator.h>
  313. _STLP_BEGIN_NAMESPACE 
  314. #endif
  315.  
  316. template <class _BidirectionalIter1, class _BidirectionalIter2,
  317.   class _BinaryPredicate>
  318. _BidirectionalIter1
  319. __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
  320.            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
  321.            const bidirectional_iterator_tag &, const bidirectional_iterator_tag &, 
  322.            _BinaryPredicate __comp)
  323. {
  324.   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
  325.   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
  326.  
  327.   _RevIter1 __rlast1(__first1);
  328.   _RevIter2 __rlast2(__first2);
  329.   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
  330.                                _RevIter2(__last2), __rlast2,
  331.                                __comp);
  332.  
  333.   if (__rresult == __rlast1)
  334.     return __last1;
  335.   else {
  336.     _BidirectionalIter1 __result = __rresult.base();
  337.     advance(__result, -distance(__first2, __last2));
  338.     return __result;
  339.   }
  340. }
  341. #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
  342.  
  343. template <class _ForwardIter1, class _ForwardIter2, 
  344.   class _BinaryPredicate>
  345. _ForwardIter1 
  346. find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
  347.          _ForwardIter2 __first2, _ForwardIter2 __last2,
  348.          _BinaryPredicate __comp)
  349. {
  350.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  351.     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  352.     return __find_end(__first1, __last1, __first2, __last2,
  353. # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
  354.               _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
  355.               _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
  356. # else
  357.               forward_iterator_tag(),
  358.               forward_iterator_tag(),
  359. # endif
  360.               __comp);
  361. }
  362.  
  363. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  364. _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
  365.                const _Tp& __val, _Compare __comp, _Distance*)
  366. {
  367.   _Distance __len = distance(__first, __last);
  368.   _Distance __half;
  369.   _ForwardIter __middle;
  370.  
  371.   while (__len > 0) {
  372.     __half = __len >> 1;
  373.     __middle = __first;
  374.     advance(__middle, __half);
  375.     if (__comp(*__middle, __val)) {
  376.       __first = __middle;
  377.       ++__first;
  378.       __len = __len - __half - 1;
  379.     }
  380.     else
  381.       __len = __half;
  382.   }
  383.   return __first;
  384. }
  385.  
  386. _STLP_END_NAMESPACE
  387.  
  388. #endif /* _STLP_ALGOBASE_C */
  389.  
  390. // Local Variables:
  391. // mode:C++
  392. // End:
  393.