arm-marvell-linux-uclibcgnueabi/include/c++/4.6.4/ext/algorithm - toolchains/armada - Git at Google

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

 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
 // 2009, 2010, 2011
 // 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 3, 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.

 // Under Section 7 of GPL version 3, you are granted additional
 // permissions described in the GCC Runtime Library Exception, version
 // 3.1, as published by the Free Software Foundation.

 // You should have received a copy of the GNU General Public License and
 // a copy of the GCC Runtime Library Exception along with this program;
 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 // <http://www.gnu.org/licenses/>.

 /*
  *
  * 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.
  */

 /** @file ext/algorithm
  *  This file is a GNU extension to the Standard C++ Library (possibly
  *  containing extensions from the HP/SGI STL subset).
  */

 #ifndef _EXT_ALGORITHM
 #define _EXT_ALGORITHM 1

 #pragma GCC system_header

 #include <algorithm>

 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION

   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 _InputIterator, typename _Size, typename _OutputIterator>
     pair<_InputIterator, _OutputIterator>
     __copy_n(_InputIterator __first, _Size __count,
 	     _OutputIterator __result,
 	     input_iterator_tag)
     {
       for ( ; __count > 0; --__count)
 	{
 	  *__result = *__first;
 	  ++__first;
 	  ++__result;
 	}
       return pair<_InputIterator, _OutputIterator>(__first, __result);
     }

   template<typename _RAIterator, typename _Size, typename _OutputIterator>
     inline pair<_RAIterator, _OutputIterator>
     __copy_n(_RAIterator __first, _Size __count,
 	     _OutputIterator __result,
 	     random_access_iterator_tag)
     {
       _RAIterator __last = __first + __count;
       return pair<_RAIterator, _OutputIterator>(__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 _InputIterator, typename _Size, typename _OutputIterator>
     inline pair<_InputIterator, _OutputIterator>
     copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 	    typename iterator_traits<_InputIterator>::value_type>)

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

   template<typename _InputIterator1, typename _InputIterator2>
     int
     __lexicographical_compare_3way(_InputIterator1 __first1,
 				   _InputIterator1 __last1,
 				   _InputIterator2 __first2,
 				   _InputIterator2 __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 = __builtin_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
    *  <em>lexigraphically less than</em> the second, greater than zero
    *  if the second range is <em>lexigraphically less than</em> the
    *  first, and zero otherwise.
    *  This is an SGI extension.
    *  @ingroup SGIextensions
   */
   template<typename _InputIterator1, typename _InputIterator2>
     int
     lexicographical_compare_3way(_InputIterator1 __first1,
 				 _InputIterator1 __last1,
 				 _InputIterator2 __first2,
 				 _InputIterator2 __last2)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_requires_valid_range(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);

       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 _InputIterator, typename _Tp, typename _Size>
     void
     count(_InputIterator __first, _InputIterator __last,
 	  const _Tp& __value,
 	  _Size& __n)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_EqualityComparableConcept<
 	    typename iterator_traits<_InputIterator>::value_type >)
       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
       __glibcxx_requires_valid_range(__first, __last);

       for ( ; __first != __last; ++__first)
 	if (*__first == __value)
 	  ++__n;
     }

   template<typename _InputIterator, typename _Predicate, typename _Size>
     void
     count_if(_InputIterator __first, _InputIterator __last,
 	     _Predicate __pred,
 	     _Size& __n)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 	    typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);

       for ( ; __first != __last; ++__first)
 	if (__pred(*__first))
 	  ++__n;
     }

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

   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
   */
   template<typename _ForwardIterator, typename _OutputIterator,
 	   typename _Distance>
     _OutputIterator
     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
                     _OutputIterator __out, const _Distance __n)
     {
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 		typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);

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

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

   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
   */
   template<typename _ForwardIterator, typename _OutputIterator,
 	   typename _Distance, typename _RandomNumberGenerator>
     _OutputIterator
     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
                    _OutputIterator __out, const _Distance __n,
 		   _RandomNumberGenerator& __rand)
     {
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 		typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_function_requires(_UnaryFunctionConcept<
 		_RandomNumberGenerator, _Distance, _Distance>)
       __glibcxx_requires_valid_range(__first, __last);

       _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 _InputIterator, typename _RandomAccessIterator,
 	   typename _Distance>
     _RandomAccessIterator
     __random_sample(_InputIterator __first, _InputIterator __last,
 		    _RandomAccessIterator __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::rand() % (__t);
 	  if (__M < __n)
 	    __out[__M] = *__first;
 	  ++__first;
 	}
       return __out + __m;
     }

   template<typename _InputIterator, typename _RandomAccessIterator,
 	   typename _RandomNumberGenerator, typename _Distance>
     _RandomAccessIterator
     __random_sample(_InputIterator __first, _InputIterator __last,
 		    _RandomAccessIterator __out,
 		    _RandomNumberGenerator& __rand,
 		    const _Distance __n)
     {
       // concept requirements
       __glibcxx_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;
     }

   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
   */
   template<typename _InputIterator, typename _RandomAccessIterator>
     inline _RandomAccessIterator
     random_sample(_InputIterator __first, _InputIterator __last,
 		  _RandomAccessIterator __out_first,
 		  _RandomAccessIterator __out_last)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_valid_range(__out_first, __out_last);

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

   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
   */
   template<typename _InputIterator, typename _RandomAccessIterator,
 	   typename _RandomNumberGenerator>
     inline _RandomAccessIterator
     random_sample(_InputIterator __first, _InputIterator __last,
 		  _RandomAccessIterator __out_first,
 		  _RandomAccessIterator __out_last,
 		  _RandomNumberGenerator& __rand)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_valid_range(__out_first, __out_last);

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

 #ifdef __GXX_EXPERIMENTAL_CXX0X__
   using std::is_heap;
 #else
   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
   */
   template<typename _RandomAccessIterator>
     inline bool
     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
       // concept requirements
       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 				  _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);

       return std::__is_heap(__first, __last - __first);
     }

   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
   */
   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
     inline bool
     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 	    _StrictWeakOrdering __comp)
     {
       // concept requirements
       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 				  _RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 	    typename iterator_traits<_RandomAccessIterator>::value_type,
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);

       return std::__is_heap(__first, __comp, __last - __first);
     }
 #endif

 #ifdef __GXX_EXPERIMENTAL_CXX0X__
   using std::is_sorted;
 #else
   // is_sorted, a predicated testing whether a range is sorted in
   // nondescending order.  This is an extension, not part of the C++
   // standard.

   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
   */
   template<typename _ForwardIterator>
     bool
     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
     {
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);

       if (__first == __last)
 	return true;

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

   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
   */
   template<typename _ForwardIterator, typename _StrictWeakOrdering>
     bool
     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
 	      _StrictWeakOrdering __comp)
     {
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 	    typename iterator_traits<_ForwardIterator>::value_type,
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);

       if (__first == __last)
 	return true;

       _ForwardIterator __next = __first;
       for (++__next; __next != __last; __first = __next, ++__next)
 	if (__comp(*__next, *__first))
 	  return false;
       return true;
     }
 #endif  // __GXX_EXPERIMENTAL_CXX0X__

   /**
    *  @brief Find the median of three values.
    *  @param  a  A value.
    *  @param  b  A value.
    *  @param  c  A value.
    *  @return One of @p a, @p b or @p c.
    *
    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
    *  then the value returned will be @c m.
    *  This is an SGI extension.
    *  @ingroup SGIextensions
   */
   template<typename _Tp>
     const _Tp&
     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
     {
       // concept requirements
       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
       if (__a < __b)
 	if (__b < __c)
 	  return __b;
 	else if (__a < __c)
 	  return __c;
 	else
 	  return __a;
       else if (__a < __c)
 	return __a;
       else if (__b < __c)
 	return __c;
       else
 	return __b;
     }

   /**
    *  @brief Find the median of three values using a predicate for comparison.
    *  @param  a     A value.
    *  @param  b     A value.
    *  @param  c     A value.
    *  @param  comp  A binary predicate.
    *  @return One of @p a, @p b or @p c.
    *
    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
    *  and @p comp(m,n) are both true then the value returned will be @c m.
    *  This is an SGI extension.
    *  @ingroup SGIextensions
   */
   template<typename _Tp, typename _Compare>
     const _Tp&
     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
     {
       // concept requirements
       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
 				                         _Tp, _Tp>)
       if (__comp(__a, __b))
 	if (__comp(__b, __c))
 	  return __b;
 	else if (__comp(__a, __c))
 	  return __c;
 	else
 	  return __a;
       else if (__comp(__a, __c))
 	return __a;
       else if (__comp(__b, __c))
 	return __c;
       else
 	return __b;
     }

 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace

 #endif /* _EXT_ALGORITHM */
	// Algorithm extensions -- C++ --

	// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
	// 2009, 2010, 2011
	// 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 3, 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.

	// Under Section 7 of GPL version 3, you are granted additional
	// permissions described in the GCC Runtime Library Exception, version
	// 3.1, as published by the Free Software Foundation.

	// You should have received a copy of the GNU General Public License and
	// a copy of the GCC Runtime Library Exception along with this program;
	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	// <http://www.gnu.org/licenses/>.

	/*
	*
	* 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.
	*/

	/** @file ext/algorithm
	* This file is a GNU extension to the Standard C++ Library (possibly
	* containing extensions from the HP/SGI STL subset).
	*/

	#ifndef _EXT_ALGORITHM
	#define _EXT_ALGORITHM 1

	#pragma GCC system_header

	#include <algorithm>

	namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
	{
	_GLIBCXX_BEGIN_NAMESPACE_VERSION

	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 _InputIterator, typename _Size, typename _OutputIterator>
	pair<_InputIterator, _OutputIterator>
	__copy_n(_InputIterator __first, _Size __count,
	_OutputIterator __result,
	input_iterator_tag)
	{
	for ( ; __count > 0; --__count)
	{
	__result = __first;
	++__first;
	++__result;
	}
	return pair<_InputIterator, _OutputIterator>(__first, __result);
	}

	template<typename _RAIterator, typename _Size, typename _OutputIterator>
	inline pair<_RAIterator, _OutputIterator>
	__copy_n(_RAIterator __first, _Size __count,
	_OutputIterator __result,
	random_access_iterator_tag)
	{
	_RAIterator __last = __first + __count;
	return pair<_RAIterator, _OutputIterator>(__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 _InputIterator, typename _Size, typename _OutputIterator>
	inline pair<_InputIterator, _OutputIterator>
	copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
	{
	// concept requirements
	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
	typename iterator_traits<_InputIterator>::value_type>)

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

	template<typename _InputIterator1, typename _InputIterator2>
	int
	__lexicographical_compare_3way(_InputIterator1 __first1,
	_InputIterator1 __last1,
	_InputIterator2 __first2,
	_InputIterator2 __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 = __builtin_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
	* <em>lexigraphically less than</em> the second, greater than zero
	* if the second range is <em>lexigraphically less than</em> the
	* first, and zero otherwise.
	* This is an SGI extension.
	* @ingroup SGIextensions
	*/
	template<typename _InputIterator1, typename _InputIterator2>
	int
	lexicographical_compare_3way(_InputIterator1 __first1,
	_InputIterator1 __last1,
	_InputIterator2 __first2,
	_InputIterator2 __last2)
	{
	// concept requirements
	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
	__glibcxx_function_requires(_LessThanComparableConcept<
	typename iterator_traits<_InputIterator1>::value_type>)
	__glibcxx_function_requires(_LessThanComparableConcept<
	typename iterator_traits<_InputIterator2>::value_type>)
	__glibcxx_requires_valid_range(__first1, __last1);
	__glibcxx_requires_valid_range(__first2, __last2);

	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 _InputIterator, typename _Tp, typename _Size>
	void
	count(_InputIterator __first, _InputIterator __last,
	const _Tp& __value,
	_Size& __n)
	{
	// concept requirements
	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
	__glibcxx_function_requires(_EqualityComparableConcept<
	typename iterator_traits<_InputIterator>::value_type >)
	__glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
	__glibcxx_requires_valid_range(__first, __last);

	for ( ; __first != __last; ++__first)
	if (*__first == __value)
	++__n;
	}

	template<typename _InputIterator, typename _Predicate, typename _Size>
	void
	count_if(_InputIterator __first, _InputIterator __last,
	_Predicate __pred,
	_Size& __n)
	{
	// concept requirements
	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
	typename iterator_traits<_InputIterator>::value_type>)
	__glibcxx_requires_valid_range(__first, __last);

	for ( ; __first != __last; ++__first)
	if (__pred(*__first))
	++__n;
	}

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

	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<typename _ForwardIterator, typename _OutputIterator,
	typename _Distance>
	_OutputIterator
	random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
	_OutputIterator __out, const _Distance __n)
	{
	// concept requirements
	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
	typename iterator_traits<_ForwardIterator>::value_type>)
	__glibcxx_requires_valid_range(__first, __last);

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

	while (__m > 0)
	{
	if ((std::rand() % __remaining) < __m)
	{
	__out = __first;
	++__out;
	--__m;
	}
	--__remaining;
	++__first;
	}
	return __out;
	}

	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<typename _ForwardIterator, typename _OutputIterator,
	typename _Distance, typename _RandomNumberGenerator>
	_OutputIterator
	random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
	_OutputIterator __out, const _Distance __n,
	_RandomNumberGenerator& __rand)
	{
	// concept requirements
	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
	typename iterator_traits<_ForwardIterator>::value_type>)
	__glibcxx_function_requires(_UnaryFunctionConcept<
	_RandomNumberGenerator, _Distance, _Distance>)
	__glibcxx_requires_valid_range(__first, __last);

	_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 _InputIterator, typename _RandomAccessIterator,
	typename _Distance>
	_RandomAccessIterator
	__random_sample(_InputIterator __first, _InputIterator __last,
	_RandomAccessIterator __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::rand() % (__t);
	if (__M < __n)
	__out[__M] = *__first;
	++__first;
	}
	return __out + __m;
	}

	template<typename _InputIterator, typename _RandomAccessIterator,
	typename _RandomNumberGenerator, typename _Distance>
	_RandomAccessIterator
	__random_sample(_InputIterator __first, _InputIterator __last,
	_RandomAccessIterator __out,
	_RandomNumberGenerator& __rand,
	const _Distance __n)
	{
	// concept requirements
	__glibcxx_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;
	}

	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<typename _InputIterator, typename _RandomAccessIterator>
	inline _RandomAccessIterator
	random_sample(_InputIterator __first, _InputIterator __last,
	_RandomAccessIterator __out_first,
	_RandomAccessIterator __out_last)
	{
	// concept requirements
	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	_RandomAccessIterator>)
	__glibcxx_requires_valid_range(__first, __last);
	__glibcxx_requires_valid_range(__out_first, __out_last);

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

	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<typename _InputIterator, typename _RandomAccessIterator,
	typename _RandomNumberGenerator>
	inline _RandomAccessIterator
	random_sample(_InputIterator __first, _InputIterator __last,
	_RandomAccessIterator __out_first,
	_RandomAccessIterator __out_last,
	_RandomNumberGenerator& __rand)
	{
	// concept requirements
	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	_RandomAccessIterator>)
	__glibcxx_requires_valid_range(__first, __last);
	__glibcxx_requires_valid_range(__out_first, __out_last);

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

	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	using std::is_heap;
	#else
	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<typename _RandomAccessIterator>
	inline bool
	is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
	{
	// concept requirements
	__glibcxx_function_requires(_RandomAccessIteratorConcept<
	_RandomAccessIterator>)
	__glibcxx_function_requires(_LessThanComparableConcept<
	typename iterator_traits<_RandomAccessIterator>::value_type>)
	__glibcxx_requires_valid_range(__first, __last);

	return std::__is_heap(__first, __last - __first);
	}

	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
	inline bool
	is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	_StrictWeakOrdering __comp)
	{
	// concept requirements
	__glibcxx_function_requires(_RandomAccessIteratorConcept<
	_RandomAccessIterator>)
	__glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
	typename iterator_traits<_RandomAccessIterator>::value_type,
	typename iterator_traits<_RandomAccessIterator>::value_type>)
	__glibcxx_requires_valid_range(__first, __last);

	return std::__is_heap(__first, __comp, __last - __first);
	}
	#endif

	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	using std::is_sorted;
	#else
	// is_sorted, a predicated testing whether a range is sorted in
	// nondescending order. This is an extension, not part of the C++
	// standard.

	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<typename _ForwardIterator>
	bool
	is_sorted(_ForwardIterator __first, _ForwardIterator __last)
	{
	// concept requirements
	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
	__glibcxx_function_requires(_LessThanComparableConcept<
	typename iterator_traits<_ForwardIterator>::value_type>)
	__glibcxx_requires_valid_range(__first, __last);

	if (__first == __last)
	return true;

	_ForwardIterator __next = __first;
	for (++__next; __next != __last; __first = __next, ++__next)
	if (__next < __first)
	return false;
	return true;
	}

	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<typename _ForwardIterator, typename _StrictWeakOrdering>
	bool
	is_sorted(_ForwardIterator __first, _ForwardIterator __last,
	_StrictWeakOrdering __comp)
	{
	// concept requirements
	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
	__glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
	typename iterator_traits<_ForwardIterator>::value_type,
	typename iterator_traits<_ForwardIterator>::value_type>)
	__glibcxx_requires_valid_range(__first, __last);

	if (__first == __last)
	return true;

	_ForwardIterator __next = __first;
	for (++__next; __next != __last; __first = __next, ++__next)
	if (__comp(__next, __first))
	return false;
	return true;
	}
	#endif // __GXX_EXPERIMENTAL_CXX0X__

	/**
	* @brief Find the median of three values.
	* @param a A value.
	* @param b A value.
	* @param c A value.
	* @return One of @p a, @p b or @p c.
	*
	* If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
	* then the value returned will be @c m.
	* This is an SGI extension.
	* @ingroup SGIextensions
	*/
	template<typename _Tp>
	const _Tp&
	__median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
	{
	// concept requirements
	__glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
	if (__a < __b)
	if (__b < __c)
	return __b;
	else if (__a < __c)
	return __c;
	else
	return __a;
	else if (__a < __c)
	return __a;
	else if (__b < __c)
	return __c;
	else
	return __b;
	}

	/**
	* @brief Find the median of three values using a predicate for comparison.
	* @param a A value.
	* @param b A value.
	* @param c A value.
	* @param comp A binary predicate.
	* @return One of @p a, @p b or @p c.
	*
	* If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
	* and @p comp(m,n) are both true then the value returned will be @c m.
	* This is an SGI extension.
	* @ingroup SGIextensions
	*/
	template<typename _Tp, typename _Compare>
	const _Tp&
	__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
	{
	// concept requirements
	__glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
	_Tp, _Tp>)
	if (__comp(__a, __b))
	if (__comp(__b, __c))
	return __b;
	else if (__comp(__a, __c))
	return __c;
	else
	return __a;
	else if (__comp(__a, __c))
	return __a;
	else if (__comp(__b, __c))
	return __c;
	else
	return __b;
	}

	_GLIBCXX_END_NAMESPACE_VERSION
	} // namespace

	#endif /* _EXT_ALGORITHM */