[gcc] GCC 4.5.0=>4.5.1

gcc/libstdc++-v3/include/ext/algorithm

Index: gcc/libstdc++-v3/include/ext/algorithm
diff --git a/gcc/libstdc++-v3/include/ext/algorithm b/gcc/libstdc++-v3/include/ext/algorithm
deleted file mode 100644
index 3337d6c07403860904f73a93915ce147f08ba6ab..0000000000000000000000000000000000000000
--- a/gcc/libstdc++-v3/include/ext/algorithm
+++ /dev/null
@@ -1,524 +0,0 @@
-// Algorithm extensions -*- C++ -*-
-
-// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
-// 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>
-
-_GLIBCXX_BEGIN_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 = __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
-   *  "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
-  */
-  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;
-    }
-
-_GLIBCXX_END_NAMESPACE
-
-#endif /* _EXT_ALGORITHM */