home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _algo.h < prev    next >
C/C++ Source or Header  |  2002-02-02  |  26KB  |  731 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. #ifndef _STLP_INTERNAL_ALGO_H
  31. #define _STLP_INTERNAL_ALGO_H
  32.  
  33. # ifndef _STLP_INTERNAL_ALGOBASE_H
  34. #  include <stl/_algobase.h>
  35. # endif
  36.  
  37. # ifndef _STLP_INTERNAL_TEMPBUF_H
  38. #  include <stl/_tempbuf.h>
  39. # endif
  40.  
  41. # ifndef _STLP_INTERNAL_HEAP_H
  42. #  include <stl/_heap.h>
  43. # endif
  44.  
  45. # ifndef _STLP_INTERNAL_ITERATOR_H
  46. #  include <stl/_iterator.h>
  47. # endif
  48.  
  49. # ifndef _STLP_INTERNAL_FUNCTION_BASE_H
  50. #  include <stl/_function_base.h>
  51. # endif
  52.  
  53. # ifdef __SUNPRO_CC
  54. // remove() conflict
  55. #  include <cstdio>
  56. # endif
  57.  
  58. _STLP_BEGIN_NAMESPACE
  59.  
  60. // for_each.  Apply a function to every element of a range.
  61. template <class _InputIter, class _Function>
  62. _STLP_INLINE_LOOP _Function 
  63. for_each(_InputIter __first, _InputIter __last, _Function __f) {
  64.   for ( ; __first != __last; ++__first)
  65.     __f(*__first);
  66.   return __f;
  67. }
  68.  
  69. // count_if
  70. template <class _InputIter, class _Predicate>
  71. _STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter)
  72. count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
  73.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  74. _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;
  75.   for ( ; __first != __last; ++__first)
  76.     if (__pred(*__first))
  77.       ++__n;
  78.   return __n;
  79. }
  80.  
  81. // adjacent_find.
  82. template <class _ForwardIter>
  83. _STLP_INLINE_LOOP _ForwardIter 
  84. adjacent_find(_ForwardIter __first, _ForwardIter __last) {
  85.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  86.     if (__first == __last)
  87.       return __last;
  88.   _ForwardIter __next = __first;
  89.   while(++__next != __last) {
  90.     if (*__first == *__next)
  91.       return __first;
  92.     __first = __next;
  93.   }
  94.   return __last;
  95. }
  96.  
  97. template <class _ForwardIter, class _BinaryPredicate>
  98. _STLP_INLINE_LOOP _ForwardIter 
  99. adjacent_find(_ForwardIter __first, _ForwardIter __last,
  100.               _BinaryPredicate __binary_pred) {
  101.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  102.   if (__first == __last)
  103.     return __last;
  104.   _ForwardIter __next = __first;
  105.   while(++__next != __last) {
  106.     if (__binary_pred(*__first, *__next))
  107.       return __first;
  108.     __first = __next;
  109.   }
  110.   return __last;
  111. }
  112.  
  113. # ifndef _STLP_NO_ANACHRONISMS
  114. template <class _InputIter, class _Tp, class _Size>
  115. _STLP_INLINE_LOOP void 
  116. count(_InputIter __first, _InputIter __last, const _Tp& __val, _Size& __n) {
  117.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  118.     for ( ; __first != __last; ++__first)
  119.       if (*__first == __val)
  120.         ++__n;
  121. }
  122.  
  123. template <class _InputIter, class _Predicate, class _Size>
  124. _STLP_INLINE_LOOP void 
  125. count_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) {
  126.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  127.   for ( ; __first != __last; ++__first)
  128.     if (__pred(*__first))
  129.       ++__n;
  130. }
  131. # endif
  132.  
  133. template <class _ForwardIter1, class _ForwardIter2>
  134. _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  135.                      _ForwardIter2 __first2, _ForwardIter2 __last2);
  136.  
  137. // search_n.  Search for __count consecutive copies of __val.
  138. template <class _ForwardIter, class _Integer, class _Tp>
  139. _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
  140.                       _Integer __count, const _Tp& __val);
  141. template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
  142. _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
  143.                       _Integer __count, const _Tp& __val, _BinaryPred __binary_pred);
  144.  
  145. template <class _InputIter, class _ForwardIter>
  146. inline _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
  147.                                 _ForwardIter __first2, _ForwardIter __last2) {
  148.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  149.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  150.   return __find_first_of(__first1, __last1, __first2, __last2,__equal_to(_STLP_VALUE_TYPE(__first1, _InputIter)));
  151. }
  152.  
  153. template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
  154. inline _InputIter 
  155. find_first_of(_InputIter __first1, _InputIter __last1,
  156.               _ForwardIter __first2, _ForwardIter __last2,_BinaryPredicate __comp) {
  157.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  158.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  159.   return __find_first_of(__first1, __last1, __first2, __last2,__comp);
  160. }
  161.  
  162. template <class _ForwardIter1, class _ForwardIter2>
  163. _ForwardIter1 
  164. find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
  165.          _ForwardIter2 __first2, _ForwardIter2 __last2);
  166.  
  167. // swap_ranges
  168. template <class _ForwardIter1, class _ForwardIter2>
  169. _STLP_INLINE_LOOP _ForwardIter2 
  170. swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2) {
  171.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  172.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  173.     iter_swap(__first1, __first2);
  174.   return __first2;
  175. }
  176.  
  177. // transform
  178. template <class _InputIter, class _OutputIter, class _UnaryOperation>
  179. _STLP_INLINE_LOOP _OutputIter 
  180. transform(_InputIter __first, _InputIter __last, _OutputIter __result, _UnaryOperation __opr) {
  181.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  182.   for ( ; __first != __last; ++__first, ++__result)
  183.     *__result = __opr(*__first);
  184.   return __result;
  185. }
  186. template <class _InputIter1, class _InputIter2, class _OutputIter, class _BinaryOperation>
  187. _STLP_INLINE_LOOP _OutputIter 
  188. transform(_InputIter1 __first1, _InputIter1 __last1, 
  189.           _InputIter2 __first2, _OutputIter __result,_BinaryOperation __binary_op) {
  190.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  191.   for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
  192.     *__result = __binary_op(*__first1, *__first2);
  193.   return __result;
  194. }
  195.  
  196. // replace_if, replace_copy, replace_copy_if
  197.  
  198. template <class _ForwardIter, class _Predicate, class _Tp>
  199. _STLP_INLINE_LOOP void 
  200. replace_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const _Tp& __new_value) {
  201.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  202.   for ( ; __first != __last; ++__first)
  203.     if (__pred(*__first))
  204.       *__first = __new_value;
  205. }
  206.  
  207. template <class _InputIter, class _OutputIter, class _Tp>
  208. _STLP_INLINE_LOOP  _OutputIter 
  209. replace_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
  210.              const _Tp& __old_value, const _Tp& __new_value) {
  211.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  212.   for ( ; __first != __last; ++__first, ++__result)
  213.     *__result = *__first == __old_value ? __new_value : *__first;
  214.   return __result;
  215. }
  216.  
  217. template <class _Iterator, class _OutputIter, class _Predicate, class _Tp>
  218. _STLP_INLINE_LOOP _OutputIter 
  219. replace_copy_if(_Iterator __first, _Iterator __last,
  220.                 _OutputIter __result,
  221.                 _Predicate __pred, const _Tp& __new_value) {
  222.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  223.   for ( ; __first != __last; ++__first, ++__result)
  224.     *__result = __pred(*__first) ? __new_value : *__first;
  225.   return __result;
  226. }
  227.  
  228. // generate and generate_n
  229.  
  230. template <class _ForwardIter, class _Generator>
  231. _STLP_INLINE_LOOP void 
  232. generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
  233.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  234.   for ( ; __first != __last; ++__first)
  235.     *__first = __gen();
  236. }
  237.  
  238. template <class _OutputIter, class _Size, class _Generator>
  239. _STLP_INLINE_LOOP _OutputIter 
  240. generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
  241.   for ( ; __n > 0; --__n, ++__first)
  242.     *__first = __gen();
  243.   return __first;
  244. }
  245.  
  246. // remove, remove_if, remove_copy, remove_copy_if
  247.  
  248. template <class _InputIter, class _OutputIter, class _Tp>
  249. _STLP_INLINE_LOOP _OutputIter 
  250. remove_copy(_InputIter __first, _InputIter __last,_OutputIter __result, const _Tp& __val) {
  251.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  252.   for ( ; __first != __last; ++__first)
  253.     if (!(*__first == __val)) {
  254.       *__result = *__first;
  255.       ++__result;
  256.     }
  257.   return __result;
  258. }
  259.  
  260. template <class _InputIter, class _OutputIter, class _Predicate>
  261. _STLP_INLINE_LOOP _OutputIter 
  262. remove_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred) {
  263.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  264.   for ( ; __first != __last; ++__first)
  265.     if (!__pred(*__first)) {
  266.       *__result = *__first;
  267.       ++__result;
  268.     }
  269.   return __result;
  270. }
  271.  
  272. template <class _ForwardIter, class _Tp>
  273. _STLP_INLINE_LOOP _ForwardIter 
  274. remove(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
  275.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  276.   __first = find(__first, __last, __val);
  277.   if (__first == __last)
  278.     return __first;
  279.   else { 
  280.     _ForwardIter __next = __first;
  281.     return remove_copy(++__next, __last, __first, __val);
  282.   }
  283. }
  284.  
  285. template <class _ForwardIter, class _Predicate>
  286. _STLP_INLINE_LOOP _ForwardIter 
  287. remove_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
  288.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  289.   __first = find_if(__first, __last, __pred);
  290.   if ( __first == __last )
  291.     return __first;
  292.   else {
  293.     _ForwardIter __next = __first;
  294.     return remove_copy_if(++__next, __last, __first, __pred);
  295.   }
  296. }
  297.  
  298. // unique and unique_copy
  299. template <class _InputIter, class _OutputIter>
  300. _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result);
  301.  
  302. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  303. _OutputIter unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
  304.                         _BinaryPredicate __binary_pred);
  305.  
  306. template <class _ForwardIter>
  307. inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
  308.   __first = adjacent_find(__first, __last);
  309.   return unique_copy(__first, __last, __first);
  310. }
  311.  
  312. template <class _ForwardIter, class _BinaryPredicate>
  313. inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
  314.                     _BinaryPredicate __binary_pred) {
  315.   __first = adjacent_find(__first, __last, __binary_pred);
  316.   return unique_copy(__first, __last, __first, __binary_pred);
  317. }
  318.  
  319. // reverse and reverse_copy, and their auxiliary functions
  320.  
  321. template <class _BidirectionalIter>
  322. _STLP_INLINE_LOOP void 
  323. __reverse(_BidirectionalIter __first, _BidirectionalIter __last, const bidirectional_iterator_tag &) {
  324.   while (true)
  325.     if (__first == __last || __first == --__last)
  326.       return;
  327.     else
  328.       iter_swap(__first++, __last);
  329. }
  330.  
  331.  
  332. template <class _RandomAccessIter>
  333. _STLP_INLINE_LOOP void 
  334. __reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) {
  335.   for (; __first < __last; ++__first) iter_swap(__first, --__last);
  336. }
  337.  
  338. template <class _BidirectionalIter>
  339. inline void 
  340. reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
  341.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  342.   __reverse(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _BidirectionalIter));
  343. }
  344.  
  345. template <class _BidirectionalIter, class _OutputIter>
  346. _STLP_INLINE_LOOP
  347. _OutputIter reverse_copy(_BidirectionalIter __first,
  348.                             _BidirectionalIter __last,
  349.                             _OutputIter __result) {
  350.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  351.   while (__first != __last) {
  352.     --__last;
  353.     *__result = *__last;
  354.     ++__result;
  355.   }
  356.   return __result;
  357. }
  358.  
  359. // rotate and rotate_copy, and their auxiliary functions
  360.  
  361. template <class _EuclideanRingElement>
  362. _STLP_INLINE_LOOP
  363. _EuclideanRingElement __gcd(_EuclideanRingElement __m,
  364.                             _EuclideanRingElement __n)
  365. {
  366.   while (__n != 0) {
  367.     _EuclideanRingElement __t = __m % __n;
  368.     __m = __n;
  369.     __n = __t;
  370.   }
  371.   return __m;
  372. }
  373.  
  374. template <class _ForwardIter>
  375. _ForwardIter 
  376. rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last);
  377.  
  378. template <class _ForwardIter, class _OutputIter>
  379. inline _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
  380.                                _ForwardIter __last, _OutputIter __result) {
  381.   return copy(__first, __middle, copy(__middle, __last, __result));
  382. }
  383.  
  384. // random_shuffle
  385.  
  386. template <class _RandomAccessIter>
  387. void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last);
  388.  
  389. template <class _RandomAccessIter, class _RandomNumberGenerator>
  390. void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
  391.                     _RandomNumberGenerator& __rand);
  392.  
  393. # ifndef _STLP_NO_EXTENSIONS
  394. // random_sample and random_sample_n (extensions, not part of the standard).
  395.  
  396. template <class _ForwardIter, class _OutputIter, class _Distance>
  397. _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
  398.                             _OutputIter __out, const _Distance __n);
  399.  
  400. template <class _ForwardIter, class _OutputIter, class _Distance,
  401.           class _RandomNumberGenerator>
  402. _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
  403.                             _OutputIter __out, const _Distance __n,
  404.                             _RandomNumberGenerator& __rand);
  405.  
  406. template <class _InputIter, class _RandomAccessIter>
  407. _RandomAccessIter
  408. random_sample(_InputIter __first, _InputIter __last,
  409.               _RandomAccessIter __out_first, _RandomAccessIter __out_last);
  410.  
  411. template <class _InputIter, class _RandomAccessIter, 
  412.           class _RandomNumberGenerator>
  413. _RandomAccessIter
  414. random_sample(_InputIter __first, _InputIter __last,
  415.               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
  416.               _RandomNumberGenerator& __rand);
  417.  
  418. # endif /* _STLP_NO_EXTENSIONS */
  419.  
  420. // partition, stable_partition, and their auxiliary functions
  421.  
  422. template <class _ForwardIter, class _Predicate>
  423. _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred);
  424.  
  425.  
  426. template <class _ForwardIter, class _Predicate>
  427. _ForwardIter 
  428. stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred);
  429.  
  430. // sort() and its auxiliary functions. 
  431.  
  432. template <class _Size>
  433. inline _Size __lg(_Size __n) {
  434.   _Size __k;
  435.   for (__k = 0; __n != 1; __n >>= 1) ++__k;
  436.   return __k;
  437. }
  438.  
  439. template <class _RandomAccessIter>
  440. void sort(_RandomAccessIter __first, _RandomAccessIter __last);
  441. template <class _RandomAccessIter, class _Compare>
  442. void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp);
  443.  
  444. // stable_sort() and its auxiliary functions.
  445. template <class _RandomAccessIter>
  446. void stable_sort(_RandomAccessIter __first,
  447.          _RandomAccessIter __last);
  448.  
  449. template <class _RandomAccessIter, class _Compare>
  450. void stable_sort(_RandomAccessIter __first,
  451.          _RandomAccessIter __last, _Compare __comp);
  452.  
  453. // partial_sort, partial_sort_copy, and auxiliary functions.
  454.  
  455. template <class _RandomAccessIter>
  456. void 
  457. partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last);
  458.  
  459. template <class _RandomAccessIter, class _Compare>
  460. void 
  461. partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, 
  462.              _RandomAccessIter __last, _Compare __comp);
  463.  
  464. template <class _InputIter, class _RandomAccessIter>
  465. _RandomAccessIter
  466. partial_sort_copy(_InputIter __first, _InputIter __last,
  467.                   _RandomAccessIter __result_first, _RandomAccessIter __result_last);
  468.  
  469. template <class _InputIter, class _RandomAccessIter, class _Compare>
  470. _RandomAccessIter
  471. partial_sort_copy(_InputIter __first, _InputIter __last,
  472.                   _RandomAccessIter __result_first,
  473.                   _RandomAccessIter __result_last, _Compare __comp);
  474.  
  475. // nth_element() and its auxiliary functions.  
  476.  
  477. template <class _RandomAccessIter>
  478. void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  479.                  _RandomAccessIter __last);
  480.  
  481. template <class _RandomAccessIter, class _Compare>
  482. void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  483.                  _RandomAccessIter __last, _Compare __comp);
  484.  
  485. // Binary search (lower_bound, upper_bound, equal_range, binary_search).
  486.  
  487. template <class _ForwardIter, class _Tp>
  488. inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
  489.                                    const _Tp& __val) {
  490.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  491.   return __lower_bound(__first, __last, __val, less<_Tp>(), _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  492. }
  493.  
  494. template <class _ForwardIter, class _Tp, class _Compare>
  495. inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
  496.                                 const _Tp& __val, _Compare __comp) {
  497.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  498.   return __lower_bound(__first, __last, __val, __comp, _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  499. }
  500.  
  501. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  502. _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
  503.                            const _Tp& __val, _Compare __comp, _Distance*);
  504.  
  505. template <class _ForwardIter, class _Tp>
  506. inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
  507.                                 const _Tp& __val) {
  508.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  509.   return __upper_bound(__first, __last, __val, less<_Tp>(), 
  510.                        _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  511. }
  512.  
  513. template <class _ForwardIter, class _Tp, class _Compare>
  514. inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
  515.                                 const _Tp& __val, _Compare __comp) {
  516.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  517.   return __upper_bound(__first, __last, __val, __comp,
  518.                        _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  519. }
  520.  
  521. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  522. pair<_ForwardIter, _ForwardIter>
  523. __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  524.               _Compare __comp, _Distance*);
  525.  
  526. template <class _ForwardIter, class _Tp>
  527. inline pair<_ForwardIter, _ForwardIter>
  528. equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
  529.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  530.   return __equal_range(__first, __last, __val,  less<_Tp>(),
  531.                        _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  532. }
  533.  
  534. template <class _ForwardIter, class _Tp, class _Compare>
  535. inline pair<_ForwardIter, _ForwardIter>
  536. equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  537.             _Compare __comp) {
  538.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  539.   return __equal_range(__first, __last, __val, __comp,
  540.                        _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  541. } 
  542.  
  543. template <class _ForwardIter, class _Tp>
  544. inline bool binary_search(_ForwardIter __first, _ForwardIter __last,
  545.                    const _Tp& __val) {
  546.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  547.   _ForwardIter __i = __lower_bound(__first, __last, __val, less<_Tp>(), _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  548.   return __i != __last && !(__val < *__i);
  549. }
  550.  
  551. template <class _ForwardIter, class _Tp, class _Compare>
  552. inline bool binary_search(_ForwardIter __first, _ForwardIter __last,
  553.                    const _Tp& __val,
  554.                    _Compare __comp) {
  555.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  556.   _ForwardIter __i = __lower_bound(__first, __last, __val, __comp, _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  557.   return __i != __last && !__comp(__val, *__i);
  558. }
  559.  
  560. // merge, with and without an explicitly supplied comparison function.
  561.  
  562. template <class _InputIter1, class _InputIter2, class _OutputIter>
  563. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  564.                   _InputIter2 __first2, _InputIter2 __last2,
  565.                   _OutputIter __result);
  566.  
  567. template <class _InputIter1, class _InputIter2, class _OutputIter,
  568.           class _Compare>
  569. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  570.                   _InputIter2 __first2, _InputIter2 __last2,
  571.                   _OutputIter __result, _Compare __comp);
  572.  
  573.  
  574. // inplace_merge and its auxiliary functions. 
  575.  
  576.  
  577. template <class _BidirectionalIter>
  578. void inplace_merge(_BidirectionalIter __first,
  579.            _BidirectionalIter __middle,
  580.            _BidirectionalIter __last) ;
  581.  
  582. template <class _BidirectionalIter, class _Compare>
  583. void inplace_merge(_BidirectionalIter __first,
  584.            _BidirectionalIter __middle,
  585.            _BidirectionalIter __last, _Compare __comp);
  586.  
  587. // Set algorithms: includes, set_union, set_intersection, set_difference,
  588. // set_symmetric_difference.  All of these algorithms have the precondition
  589. // that their input ranges are sorted and the postcondition that their output
  590. // ranges are sorted.
  591.  
  592. template <class _InputIter1, class _InputIter2>
  593. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  594.               _InputIter2 __first2, _InputIter2 __last2);
  595.  
  596. template <class _InputIter1, class _InputIter2, class _Compare>
  597. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  598.               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp);
  599.  
  600. template <class _InputIter1, class _InputIter2, class _OutputIter>
  601. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  602.                       _InputIter2 __first2, _InputIter2 __last2,
  603.                       _OutputIter __result);
  604.  
  605. template <class _InputIter1, class _InputIter2, class _OutputIter,
  606.           class _Compare>
  607. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  608.                       _InputIter2 __first2, _InputIter2 __last2,
  609.                       _OutputIter __result, _Compare __comp);
  610.  
  611. template <class _InputIter1, class _InputIter2, class _OutputIter>
  612. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  613.                              _InputIter2 __first2, _InputIter2 __last2,
  614.                              _OutputIter __result);
  615.  
  616. template <class _InputIter1, class _InputIter2, class _OutputIter,
  617.           class _Compare>
  618. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  619.                              _InputIter2 __first2, _InputIter2 __last2,
  620.                              _OutputIter __result, _Compare __comp);
  621.  
  622.  
  623.  
  624. template <class _InputIter1, class _InputIter2, class _OutputIter>
  625. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  626.                            _InputIter2 __first2, _InputIter2 __last2,
  627.                            _OutputIter __result);
  628.  
  629. template <class _InputIter1, class _InputIter2, class _OutputIter, 
  630.           class _Compare>
  631. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  632.                            _InputIter2 __first2, _InputIter2 __last2, 
  633.                            _OutputIter __result, _Compare __comp);
  634.  
  635. template <class _InputIter1, class _InputIter2, class _OutputIter>
  636. _OutputIter 
  637. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  638.                          _InputIter2 __first2, _InputIter2 __last2,
  639.                          _OutputIter __result);
  640.  
  641.  
  642. template <class _InputIter1, class _InputIter2, class _OutputIter,
  643.           class _Compare>
  644. _OutputIter 
  645. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  646.                          _InputIter2 __first2, _InputIter2 __last2,
  647.                          _OutputIter __result,
  648.                          _Compare __comp);
  649.  
  650.  
  651. // min_element and max_element, with and without an explicitly supplied
  652. // comparison function.
  653.  
  654. template <class _ForwardIter>
  655. _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last);
  656. template <class _ForwardIter, class _Compare>
  657. _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
  658.                             _Compare __comp);
  659.  
  660. template <class _ForwardIter>
  661. _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last);
  662.  
  663. template <class _ForwardIter, class _Compare>
  664. _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
  665.                             _Compare __comp);
  666.  
  667. // next_permutation and prev_permutation, with and without an explicitly 
  668. // supplied comparison function.
  669.  
  670. template <class _BidirectionalIter>
  671. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last);
  672.  
  673. template <class _BidirectionalIter, class _Compare>
  674. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  675.                       _Compare __comp);
  676.  
  677.  
  678. template <class _BidirectionalIter>
  679. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last);
  680.  
  681.  
  682. template <class _BidirectionalIter, class _Compare>
  683. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  684.                       _Compare __comp);
  685.  
  686. # ifndef _STLP_NO_EXTENSIONS
  687.  
  688. // is_heap, a predicate testing whether or not a range is
  689. // a heap.  This function is an extension, not part of the C++
  690. // standard.
  691.  
  692. template <class _RandomAccessIter>
  693. bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last);
  694.  
  695. template <class _RandomAccessIter, class _StrictWeakOrdering>
  696. bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
  697.          _StrictWeakOrdering __comp);
  698.  
  699.  
  700. // is_sorted, a predicated testing whether a range is sorted in
  701. // nondescending order.  This is an extension, not part of the C++
  702. // standard.
  703. template <class _ForwardIter, class _StrictWeakOrdering>
  704. bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
  705.                  _StrictWeakOrdering __comp);
  706.  
  707. template <class _ForwardIter>
  708. inline bool is_sorted(_ForwardIter __first, _ForwardIter __last) {
  709.   return __is_sorted(__first, __last, __less(_STLP_VALUE_TYPE(__first, _ForwardIter)));
  710. }
  711.  
  712. template <class _ForwardIter, class _StrictWeakOrdering>
  713. inline bool is_sorted(_ForwardIter __first, _ForwardIter __last,
  714.                       _StrictWeakOrdering __comp) {
  715.   return __is_sorted(__first, __last, __comp);
  716. }
  717. # endif
  718.  
  719. _STLP_END_NAMESPACE
  720.  
  721. # if !defined (_STLP_LINK_TIME_INSTANTIATION)
  722. #  include <stl/_algo.c>
  723. # endif
  724.  
  725. #endif /* _STLP_INTERNAL_ALGO_H */
  726.  
  727. // Local Variables:
  728. // mode:C++
  729. // End:
  730.  
  731.