text: // Algorithm extensions -*- C++ -*-
  
  // Copyright (C) 2001-2014 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);
      }
  
  #if __cplusplus >= 201103L
    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
  
  #if __cplusplus >= 201103L
    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  // C++11
  
    /**
     *  @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 */
  