// Algorithm extensions -*- C++ -*-// Copyright (C) 2001, 2002 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. *//** @file ext/algorithm *  This file is a GNU extension to the Standard C++ Library (possibly *  containing extensions from the HP/SGI STL subset).  You should only *  include this header if you are using GCC 3 or later. */#ifndef _EXT_ALGORITHM#define _EXT_ALGORITHM 1#pragma GCC system_header#include <algorithm>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 _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 __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 = 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 _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