algorithm

mingw32.rar

  */
  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);
    }

  /**
   *  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);
    }

  // 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;
    }
} // namespace __gnu_cxx

#endif /* _EXT_ALGORITHM */