[thirdparty/gcc.git] / libstdc++-v3 / include / ext / algorithm

// Algorithm extensions -*- C++ -*-

// Copyright (C) 2001 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

#ifndef _EXT_ALGORITHM
#define _EXT_ALGORITHM

#pragma GCC system_header
#include <bits/std_algorithm.h>

namespace __gnu_cxx
{
  using std::ptrdiff_t;
  using std::min;
  using std::pair;
  using std::input_iterator_tag;
  using std::random_access_iterator_tag;
  using std::iterator_traits;

  //--------------------------------------------------
  // copy_n (not part of the C++ standard)

  template<typename _InputIter, typename _Size, typename _OutputIter>
    pair<_InputIter, _OutputIter>
    __copy_n(_InputIter __first, _Size __count,
	     _OutputIter __result,
	     input_iterator_tag)
    {
      for ( ; __count > 0; --__count) {
	*__result = *__first;
	++__first;
	++__result;
      }
      return pair<_InputIter, _OutputIter>(__first, __result);
    }

  template<typename _RAIter, typename _Size, typename _OutputIter>
    inline pair<_RAIter, _OutputIter>
    __copy_n(_RAIter __first, _Size __count,
	     _OutputIter __result,
	     random_access_iterator_tag)
    {
      _RAIter __last = __first + __count;
      return pair<_RAIter, _OutputIter>(__last,
					std::copy(__first, __last, __result));
    }

  /**
   *  @brief Copies the range [first,first+count) into [result,result+count).
   *  @param  first  An input iterator.
   *  @param  count  The number of elements to copy.
   *  @param  result An output iterator.
   *  @return   A std::pair composed of first+count and result+count.
   *
   *  This is an SGI extension.
   *  This inline function will boil down to a call to @c memmove whenever
   *  possible.  Failing that, if random access iterators are passed, then the
   *  loop count will be known (and therefore a candidate for compiler
   *  optimizations such as unrolling).
   *  @ingroup SGIextensions
  */
  template<typename _InputIter, typename _Size, typename _OutputIter>
    inline pair<_InputIter, _OutputIter>
    copy_n(_InputIter __first, _Size __count, _OutputIter __result)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
	    typename iterator_traits<_InputIter>::value_type>)

      return __copy_n(__first, __count, __result,
		      std::__iterator_category(__first));
    }

  template<typename _InputIter1, typename _InputIter2>
    int
    __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
				   _InputIter2 __first2, _InputIter2 __last2)
    {
      while (__first1 != __last1 && __first2 != __last2) {
	if (*__first1 < *__first2)
	  return -1;
	if (*__first2 < *__first1)
	  return 1;
	++__first1;
	++__first2;
      }
      if (__first2 == __last2) {
	return !(__first1 == __last1);
      }
      else {
	return -1;
      }
    }

  inline int
  __lexicographical_compare_3way(const unsigned char* __first1,
				 const unsigned char* __last1,
				 const unsigned char* __first2,
				 const unsigned char* __last2)
  {
    const ptrdiff_t __len1 = __last1 - __first1;
    const ptrdiff_t __len2 = __last2 - __first2;
    const int __result = std::memcmp(__first1, __first2, min(__len1, __len2));
    return __result != 0 ? __result 
			 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
  }

  inline int 
  __lexicographical_compare_3way(const char* __first1, const char* __last1,
				 const char* __first2, const char* __last2)
  {
#if CHAR_MAX == SCHAR_MAX
    return __lexicographical_compare_3way(
				  (const signed char*) __first1,
				  (const signed char*) __last1,
				  (const signed char*) __first2,
				  (const signed char*) __last2);
#else
    return __lexicographical_compare_3way((const unsigned char*) __first1,
					  (const unsigned char*) __last1,
					  (const unsigned char*) __first2,
					  (const unsigned char*) __last2);
#endif
  }

  /**
   *  @brief @c memcmp on steroids.
   *  @param  first1  An input iterator.
   *  @param  last1   An input iterator.
   *  @param  first2  An input iterator.
   *  @param  last2   An input iterator.
   *  @return   An int, as with @c memcmp.
   *
   *  The return value will be less than zero if the first range is
   *  "lexigraphically less than" the second, greater than zero if the second
   *  range is "lexigraphically less than" the first, and zero otherwise.
   *  This is an SGI extension.
   *  @ingroup SGIextensions
  */
  template<typename _InputIter1, typename _InputIter2>
    int
    lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
				 _InputIter2 __first2, _InputIter2 __last2)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
      __glibcpp_function_requires(_LessThanComparableConcept<
	    typename iterator_traits<_InputIter1>::value_type>)
      __glibcpp_function_requires(_LessThanComparableConcept<
	    typename iterator_traits<_InputIter2>::value_type>)

      return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
    }

  // count and count_if: this version, whose return type is void, was present
  // in the HP STL, and is retained as an extension for backward compatibility.

  template<typename _InputIter, typename _Tp, typename _Size>
    void
    count(_InputIter __first, _InputIter __last,
	  const _Tp& __value,
	  _Size& __n)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_EqualityComparableConcept<
	    typename iterator_traits<_InputIter>::value_type >)
      __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
      for ( ; __first != __last; ++__first)
	if (*__first == __value)
	  ++__n;
    }

  template<typename _InputIter, typename _Predicate, typename _Size>
    void
    count_if(_InputIter __first, _InputIter __last,
	     _Predicate __pred,
	     _Size& __n)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
	    typename iterator_traits<_InputIter>::value_type>)
      for ( ; __first != __last; ++__first)
	if (__pred(*__first))
	  ++__n;
    }

  // random_sample and random_sample_n (extensions, not part of the standard).

  template<typename _ForwardIter, typename _OutputIter, typename _Distance>
    _OutputIter
    random_sample_n(_ForwardIter __first, _ForwardIter __last,
                    _OutputIter __out, const _Distance __n)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		typename iterator_traits<_ForwardIter>::value_type>)

      _Distance __remaining = std::distance(__first, __last);
      _Distance __m = min(__n, __remaining);

      while (__m > 0) {
	if (std::__random_number(__remaining) < __m) {
	      *__out = *__first;
	      ++__out;
	      --__m;
	}

	--__remaining;
	++__first;
      }
      return __out;
    }

  template<typename _ForwardIter, typename _OutputIter, typename _Distance,
	   typename _RandomNumberGenerator>
    _OutputIter
    random_sample_n(_ForwardIter __first, _ForwardIter __last,
                   _OutputIter __out, const _Distance __n, 
		   _RandomNumberGenerator& __rand)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		typename iterator_traits<_ForwardIter>::value_type>)
      __glibcpp_function_requires(_UnaryFunctionConcept<
		_RandomNumberGenerator, _Distance, _Distance>)

      _Distance __remaining = std::distance(__first, __last);
      _Distance __m = min(__n, __remaining);

      while (__m > 0) {
	if (__rand(__remaining) < __m) {
	      *__out = *__first;
	      ++__out;
	      --__m;
	}

	--__remaining;
	++__first;
      }
      return __out;
    }

  template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
    _RandomAccessIter
    __random_sample(_InputIter __first, _InputIter __last,
		    _RandomAccessIter __out,
		    const _Distance __n)
    {
      _Distance __m = 0;
      _Distance __t = __n;
      for ( ; __first != __last && __m < __n; ++__m, ++__first) 
	__out[__m] = *__first;

      while (__first != __last) {
	++__t;
	_Distance __M = std::__random_number(__t);
	if (__M < __n)
	  __out[__M] = *__first;
	++__first;
      }

      return __out + __m;
    }

  template<typename _InputIter, typename _RandomAccessIter,
	   typename _RandomNumberGenerator, typename _Distance>
    _RandomAccessIter
    __random_sample(_InputIter __first, _InputIter __last,
		    _RandomAccessIter __out,
		    _RandomNumberGenerator& __rand,
		    const _Distance __n)
    {
      // concept requirements
      __glibcpp_function_requires(_UnaryFunctionConcept<
	    _RandomNumberGenerator, _Distance, _Distance>)

      _Distance __m = 0;
      _Distance __t = __n;
      for ( ; __first != __last && __m < __n; ++__m, ++__first)
	__out[__m] = *__first;

      while (__first != __last) {
	++__t;
	_Distance __M = __rand(__t);
	if (__M < __n)
	  __out[__M] = *__first;
	++__first;
      }

      return __out + __m;
    }

  template<typename _InputIter, typename _RandomAccessIter>
    inline _RandomAccessIter
    random_sample(_InputIter __first, _InputIter __last,
		  _RandomAccessIter __out_first, _RandomAccessIter __out_last) 
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIter>)

      return __random_sample(__first, __last,
			     __out_first, __out_last - __out_first);
    }

  template<typename _InputIter, typename _RandomAccessIter, 
	   typename _RandomNumberGenerator>
    inline _RandomAccessIter
    random_sample(_InputIter __first, _InputIter __last,
		  _RandomAccessIter __out_first, _RandomAccessIter __out_last,
		  _RandomNumberGenerator& __rand) 
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIter>)

      return __random_sample(__first, __last,
			     __out_first, __rand,
			     __out_last - __out_first);
    }
  
  // is_heap, a predicate testing whether or not a range is
  // a heap.  This function is an extension, not part of the C++
  // standard.

  template<typename _RandomAccessIter, typename _Distance>
    bool
    __is_heap(_RandomAccessIter __first, _Distance __n)
    {
      _Distance __parent = 0;
      for (_Distance __child = 1; __child < __n; ++__child) {
	if (__first[__parent] < __first[__child]) 
	  return false;
	if ((__child & 1) == 0)
	  ++__parent;
      }
      return true;
    }

  template<typename _RandomAccessIter, typename _Distance,
           typename _StrictWeakOrdering>
    bool
    __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
	      _Distance __n)
    {
      _Distance __parent = 0;
      for (_Distance __child = 1; __child < __n; ++__child) {
	if (__comp(__first[__parent], __first[__child]))
	  return false;
	if ((__child & 1) == 0)
	  ++__parent;
      }
      return true;
    }

  template<typename _RandomAccessIter>
    inline bool
    is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
    {
      // concept requirements
      __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
      __glibcpp_function_requires(_LessThanComparableConcept<
	    typename iterator_traits<_RandomAccessIter>::value_type>)

      return __is_heap(__first, __last - __first);
    }

  template<typename _RandomAccessIter, typename _StrictWeakOrdering>
    inline bool
    is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
	    _StrictWeakOrdering __comp)
    {
      // concept requirements
      __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
      __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
	    typename iterator_traits<_RandomAccessIter>::value_type, 
	    typename iterator_traits<_RandomAccessIter>::value_type>)

      return __is_heap(__first, __comp, __last - __first);
    }

  // is_sorted, a predicated testing whether a range is sorted in
  // nondescending order.  This is an extension, not part of the C++
  // standard.

  template<typename _ForwardIter>
    bool
    is_sorted(_ForwardIter __first, _ForwardIter __last)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_LessThanComparableConcept<
	    typename iterator_traits<_ForwardIter>::value_type>)

      if (__first == __last)
	return true;

      _ForwardIter __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next) {
	if (*__next < *__first)
	  return false;
      }

      return true;
    }

  template<typename _ForwardIter, typename _StrictWeakOrdering>
    bool
    is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
	    typename iterator_traits<_ForwardIter>::value_type, 
	    typename iterator_traits<_ForwardIter>::value_type>)

      if (__first == __last)
	return true;

      _ForwardIter __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next) {
	if (__comp(*__next, *__first))
	  return false;
      }

      return true;
    }

} // namespace __gnu_cxx

#endif /* _EXT_ALGORITHM */
Commit	Line	Data
2c1bc4eb PC	1	// Algorithm extensions -- C++ --
	2
	3	// Copyright (C) 2001 Free Software Foundation, Inc.
	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
	8	// Free Software Foundation; either version 2, or (at your option)
	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
	16	// You should have received a copy of the GNU General Public License along
	17	// with this library; see the file COPYING. If not, write to the Free
	18	// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
	19	// USA.
	20
	21	// As a special exception, you may use this file as part of a free software
	22	// library without restriction. Specifically, if other files instantiate
	23	// templates or use macros or inline functions from this file, or you compile
	24	// this file and link it with other files to produce an executable, this
	25	// file does not by itself cause the resulting executable to be covered by
	26	// the GNU General Public License. This exception does not however
	27	// invalidate any other reasons why the executable file might be covered by
	28	// the GNU General Public License.
	29
	30	/*
	31	*
	32	* Copyright (c) 1994
	33	* Hewlett-Packard Company
	34	*
	35	* Permission to use, copy, modify, distribute and sell this software
	36	* and its documentation for any purpose is hereby granted without fee,
	37	* provided that the above copyright notice appear in all copies and
	38	* that both that copyright notice and this permission notice appear
	39	* in supporting documentation. Hewlett-Packard Company makes no
	40	* representations about the suitability of this software for any
	41	* purpose. It is provided "as is" without express or implied warranty.
	42	*
	43	*
	44	* Copyright (c) 1996
	45	* Silicon Graphics Computer Systems, Inc.
	46	*
	47	* Permission to use, copy, modify, distribute and sell this software
	48	* and its documentation for any purpose is hereby granted without fee,
	49	* provided that the above copyright notice appear in all copies and
	50	* that both that copyright notice and this permission notice appear
	51	* in supporting documentation. Silicon Graphics makes no
	52	* representations about the suitability of this software for any
	53	* purpose. It is provided "as is" without express or implied warranty.
	54	*/
	55
	56	#ifndef _EXT_ALGORITHM
	57	#define _EXT_ALGORITHM
	58
36955a95	59	#pragma GCC system_header
2c1bc4eb PC	60	#include <bits/std_algorithm.h>
	61
	62	namespace __gnu_cxx
	63	{
f53d0ff1 PC	64	using std::ptrdiff_t;
	65	using std::min;
	66	using std::pair;
	67	using std::input_iterator_tag;
	68	using std::random_access_iterator_tag;
	69	using std::iterator_traits;
	70
	71	//--------------------------------------------------
	72	// copy_n (not part of the C++ standard)
	73
	74	template<typename _InputIter, typename _Size, typename _OutputIter>
	75	pair<_InputIter, _OutputIter>
	76	__copy_n(_InputIter __first, _Size __count,
	77	_OutputIter __result,
	78	input_iterator_tag)
	79	{
	80	for ( ; __count > 0; --__count) {
	81	__result = __first;
	82	++__first;
	83	++__result;
	84	}
	85	return pair<_InputIter, _OutputIter>(__first, __result);
	86	}
	87
	88	template<typename _RAIter, typename _Size, typename _OutputIter>
	89	inline pair<_RAIter, _OutputIter>
	90	__copy_n(_RAIter __first, _Size __count,
	91	_OutputIter __result,
	92	random_access_iterator_tag)
	93	{
	94	_RAIter __last = __first + __count;
	95	return pair<_RAIter, _OutputIter>(__last,
	96	std::copy(__first, __last, __result));
	97	}
	98
	99	/**
	100	* @brief Copies the range [first,first+count) into [result,result+count).
	101	* @param first An input iterator.
	102	* @param count The number of elements to copy.
	103	* @param result An output iterator.
	104	* @return A std::pair composed of first+count and result+count.
	105	*
	106	* This is an SGI extension.
	107	* This inline function will boil down to a call to @c memmove whenever
	108	* possible. Failing that, if random access iterators are passed, then the
	109	* loop count will be known (and therefore a candidate for compiler
	110	* optimizations such as unrolling).
	111	* @ingroup SGIextensions
	112	*/
	113	template<typename _InputIter, typename _Size, typename _OutputIter>
	114	inline pair<_InputIter, _OutputIter>
	115	copy_n(_InputIter __first, _Size __count, _OutputIter __result)
	116	{
	117	// concept requirements
	118	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
	119	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
	120	typename iterator_traits<_InputIter>::value_type>)
	121
	122	return __copy_n(__first, __count, __result,
	123	std::__iterator_category(__first));
	124	}
	125
	126	template<typename _InputIter1, typename _InputIter2>
	127	int
128	__lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
129	_InputIter2 __first2, _InputIter2 __last2)
130	{
131	while (__first1 != __last1 && __first2 != __last2) {
132	if (__first1 < __first2)
133	return -1;
134	if (__first2 < __first1)
135	return 1;
136	++__first1;
137	++__first2;
138	}
139	if (__first2 == __last2) {
140	return !(__first1 == __last1);
141	}
142	else {
143	return -1;
144	}
145	}
146
147	inline int
148	__lexicographical_compare_3way(const unsigned char* __first1,
149	const unsigned char* __last1,
150	const unsigned char* __first2,
151	const unsigned char* __last2)
152	{
153	const ptrdiff_t __len1 = __last1 - __first1;
154	const ptrdiff_t __len2 = __last2 - __first2;
155	const int __result = std::memcmp(__first1, __first2, min(__len1, __len2));
156	return __result != 0 ? __result
157	: (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
158	}
159
160	inline int
161	__lexicographical_compare_3way(const char* __first1, const char* __last1,
162	const char* __first2, const char* __last2)
163	{
164	#if CHAR_MAX == SCHAR_MAX
165	return __lexicographical_compare_3way(
166	(const signed char*) __first1,
167	(const signed char*) __last1,
168	(const signed char*) __first2,
169	(const signed char*) __last2);
170	#else
171	return __lexicographical_compare_3way((const unsigned char*) __first1,
172	(const unsigned char*) __last1,
173	(const unsigned char*) __first2,
174	(const unsigned char*) __last2);
175	#endif
176	}
177
178	/**
179	* @brief @c memcmp on steroids.
180	* @param first1 An input iterator.
181	* @param last1 An input iterator.
182	* @param first2 An input iterator.
183	* @param last2 An input iterator.
184	* @return An int, as with @c memcmp.
185	*
186	* The return value will be less than zero if the first range is
187	* "lexigraphically less than" the second, greater than zero if the second
188	* range is "lexigraphically less than" the first, and zero otherwise.
189	* This is an SGI extension.
190	* @ingroup SGIextensions
191	*/
192	template<typename _InputIter1, typename _InputIter2>
193	int
194	lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
195	_InputIter2 __first2, _InputIter2 __last2)
196	{
197	// concept requirements
198	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
199	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
200	__glibcpp_function_requires(_LessThanComparableConcept<
201	typename iterator_traits<_InputIter1>::value_type>)
202	__glibcpp_function_requires(_LessThanComparableConcept<
203	typename iterator_traits<_InputIter2>::value_type>)
204
205	return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
206	}
207
2c1bc4eb PC	208	// count and count_if: this version, whose return type is void, was present
	209	// in the HP STL, and is retained as an extension for backward compatibility.
	210
	211	template<typename _InputIter, typename _Tp, typename _Size>
	212	void
	213	count(_InputIter __first, _InputIter __last,
	214	const _Tp& __value,
	215	_Size& __n)
	216	{
	217	// concept requirements
	218	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
	219	__glibcpp_function_requires(_EqualityComparableConcept<
f53d0ff1	220	typename iterator_traits<_InputIter>::value_type >)
2c1bc4eb PC	221	__glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
	222	for ( ; __first != __last; ++__first)
	223	if (*__first == __value)
	224	++__n;
	225	}
	226
	227	template<typename _InputIter, typename _Predicate, typename _Size>
	228	void
	229	count_if(_InputIter __first, _InputIter __last,
	230	_Predicate __pred,
	231	_Size& __n)
	232	{
	233	// concept requirements
	234	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
	235	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
f53d0ff1	236	typename iterator_traits<_InputIter>::value_type>)
2c1bc4eb PC	237	for ( ; __first != __last; ++__first)
	238	if (__pred(*__first))
	239	++__n;
	240	}
	241
	242	// random_sample and random_sample_n (extensions, not part of the standard).
	243
	244	template<typename _ForwardIter, typename _OutputIter, typename _Distance>
	245	_OutputIter
	246	random_sample_n(_ForwardIter __first, _ForwardIter __last,
	247	_OutputIter __out, const _Distance __n)
	248	{
	249	// concept requirements
	250	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
	251	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
f53d0ff1	252	typename iterator_traits<_ForwardIter>::value_type>)
2c1bc4eb PC	253
2c1bc4eb PC	254	_Distance __remaining = std::distance(__first, __last);
f53d0ff1	255	_Distance __m = min(__n, __remaining);
2c1bc4eb PC	256
	257	while (__m > 0) {
	258	if (std::__random_number(__remaining) < __m) {
	259	__out = __first;
	260	++__out;
	261	--__m;
	262	}
	263
	264	--__remaining;
	265	++__first;
	266	}
	267	return __out;
	268	}
	269
	270	template<typename _ForwardIter, typename _OutputIter, typename _Distance,
	271	typename _RandomNumberGenerator>
	272	_OutputIter
	273	random_sample_n(_ForwardIter __first, _ForwardIter __last,
	274	_OutputIter __out, const _Distance __n,
	275	_RandomNumberGenerator& __rand)
	276	{
	277	// concept requirements
	278	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
	279	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
f53d0ff1	280	typename iterator_traits<_ForwardIter>::value_type>)
2c1bc4eb PC	281	__glibcpp_function_requires(_UnaryFunctionConcept<
	282	_RandomNumberGenerator, _Distance, _Distance>)
	283
	284	_Distance __remaining = std::distance(__first, __last);
f53d0ff1	285	_Distance __m = min(__n, __remaining);
2c1bc4eb PC	286
	287	while (__m > 0) {
	288	if (__rand(__remaining) < __m) {
	289	__out = __first;
	290	++__out;
	291	--__m;
	292	}
	293
	294	--__remaining;
	295	++__first;
	296	}
	297	return __out;
	298	}
	299
	300	template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
	301	_RandomAccessIter
	302	__random_sample(_InputIter __first, _InputIter __last,
	303	_RandomAccessIter __out,
	304	const _Distance __n)
	305	{
	306	_Distance __m = 0;
	307	_Distance __t = __n;
	308	for ( ; __first != __last && __m < __n; ++__m, ++__first)
	309	__out[__m] = *__first;
	310
	311	while (__first != __last) {
	312	++__t;
	313	_Distance __M = std::__random_number(__t);
	314	if (__M < __n)
	315	__out[__M] = *__first;
	316	++__first;
	317	}
	318
	319	return __out + __m;
	320	}
	321
	322	template<typename _InputIter, typename _RandomAccessIter,
	323	typename _RandomNumberGenerator, typename _Distance>
	324	_RandomAccessIter
	325	__random_sample(_InputIter __first, _InputIter __last,
	326	_RandomAccessIter __out,
	327	_RandomNumberGenerator& __rand,
	328	const _Distance __n)
	329	{
	330	// concept requirements
	331	__glibcpp_function_requires(_UnaryFunctionConcept<
	332	_RandomNumberGenerator, _Distance, _Distance>)
	333
	334	_Distance __m = 0;
	335	_Distance __t = __n;
	336	for ( ; __first != __last && __m < __n; ++__m, ++__first)
	337	__out[__m] = *__first;
	338
	339	while (__first != __last) {
	340	++__t;
	341	_Distance __M = __rand(__t);
	342	if (__M < __n)
	343	__out[__M] = *__first;
	344	++__first;
	345	}
	346
	347	return __out + __m;
	348	}
	349
350	template<typename _InputIter, typename _RandomAccessIter>
351	inline _RandomAccessIter
352	random_sample(_InputIter __first, _InputIter __last,
353	_RandomAccessIter __out_first, _RandomAccessIter __out_last)
354	{
355	// concept requirements
356	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
357	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
358	_RandomAccessIter>)
359
360	return __random_sample(__first, __last,
361	__out_first, __out_last - __out_first);
362	}
363
364	template<typename _InputIter, typename _RandomAccessIter,
365	typename _RandomNumberGenerator>
366	inline _RandomAccessIter
367	random_sample(_InputIter __first, _InputIter __last,
368	_RandomAccessIter __out_first, _RandomAccessIter __out_last,
369	_RandomNumberGenerator& __rand)
370	{
371	// concept requirements
372	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
373	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
374	_RandomAccessIter>)
375
376	return __random_sample(__first, __last,
377	__out_first, __rand,
378	__out_last - __out_first);
379	}
380
381	// is_heap, a predicate testing whether or not a range is
382	// a heap. This function is an extension, not part of the C++
383	// standard.
384
385	template<typename _RandomAccessIter, typename _Distance>
386	bool
387	__is_heap(_RandomAccessIter __first, _Distance __n)
388	{
389	_Distance __parent = 0;
390	for (_Distance __child = 1; __child < __n; ++__child) {
391	if (__first[__parent] < __first[__child])
392	return false;
393	if ((__child & 1) == 0)
394	++__parent;
395	}
396	return true;
397	}
398
399	template<typename _RandomAccessIter, typename _Distance,
400	typename _StrictWeakOrdering>
401	bool
402	__is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
403	_Distance __n)
404	{
405	_Distance __parent = 0;
406	for (_Distance __child = 1; __child < __n; ++__child) {
407	if (__comp(__first[__parent], __first[__child]))
408	return false;
409	if ((__child & 1) == 0)
410	++__parent;
411	}
412	return true;
413	}
414
415	template<typename _RandomAccessIter>
416	inline bool
417	is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
418	{
419	// concept requirements
420	__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
421	__glibcpp_function_requires(_LessThanComparableConcept<
f53d0ff1	422	typename iterator_traits<_RandomAccessIter>::value_type>)
2c1bc4eb PC	423
	424	return __is_heap(__first, __last - __first);
	425	}
	426
	427	template<typename _RandomAccessIter, typename _StrictWeakOrdering>
	428	inline bool
	429	is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
	430	_StrictWeakOrdering __comp)
	431	{
	432	// concept requirements
	433	__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
	434	__glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
f53d0ff1 PC	435	typename iterator_traits<_RandomAccessIter>::value_type,
f53d0ff1 PC	436	typename iterator_traits<_RandomAccessIter>::value_type>)
2c1bc4eb PC	437
	438	return __is_heap(__first, __comp, __last - __first);
	439	}
	440
	441	// is_sorted, a predicated testing whether a range is sorted in
	442	// nondescending order. This is an extension, not part of the C++
	443	// standard.
	444
	445	template<typename _ForwardIter>
	446	bool
	447	is_sorted(_ForwardIter __first, _ForwardIter __last)
	448	{
	449	// concept requirements
	450	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
	451	__glibcpp_function_requires(_LessThanComparableConcept<
f53d0ff1	452	typename iterator_traits<_ForwardIter>::value_type>)
2c1bc4eb PC	453
	454	if (__first == __last)
	455	return true;
	456
	457	_ForwardIter __next = __first;
	458	for (++__next; __next != __last; __first = __next, ++__next) {
	459	if (__next < __first)
	460	return false;
	461	}
	462
	463	return true;
	464	}
	465
	466	template<typename _ForwardIter, typename _StrictWeakOrdering>
	467	bool
	468	is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
	469	{
	470	// concept requirements
	471	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
	472	__glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
f53d0ff1 PC	473	typename iterator_traits<_ForwardIter>::value_type,
f53d0ff1 PC	474	typename iterator_traits<_ForwardIter>::value_type>)
2c1bc4eb PC	475
	476	if (__first == __last)
	477	return true;
	478
	479	_ForwardIter __next = __first;
	480	for (++__next; __next != __last; __first = __next, ++__next) {
	481	if (__comp(__next, __first))
	482	return false;
	483	}
	484
	485	return true;
	486	}
	487
	488	} // namespace __gnu_cxx
	489
	490	#endif /* _EXT_ALGORITHM */