Gcc 3.1.0 pre-release's C++ support bits from the FSF anoncvs repo

on 9-May-2002 15:57:15 EDT.

1 files changed, 496 insertions, 0 deletions

diff --git a/contrib/libstdc++/include/ext/algorithm b/contrib/libstdc++/include/ext/algorithm
new file mode 100644
index 0000000..bf72765
--- /dev/null
+++ b/contrib/libstdc++/include/ext/algorithm
@@ -0,0 +1,496 @@
+// 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
+
+#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 _InputIter, typename _Size, typename _OutputIter>
+    pair<_InputIter, _OutputIter>
+    __copy_n(_InputIter __first, _Size __count,
+	     _OutputIter __result,
+	     input_iterator_tag)
+    {
+      for ( ; __count > 0; --__count) {
+	*__result = *__first;
+	++__first;
+	++__result;
+      }
+      return pair<_InputIter, _OutputIter>(__first, __result);
+    }
+
+  template<typename _RAIter, typename _Size, typename _OutputIter>
+    inline pair<_RAIter, _OutputIter>
+    __copy_n(_RAIter __first, _Size __count,
+	     _OutputIter __result,
+	     random_access_iterator_tag)
+    {
+      _RAIter __last = __first + __count;
+      return pair<_RAIter, _OutputIter>(__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 _InputIter, typename _Size, typename _OutputIter>
+    inline pair<_InputIter, _OutputIter>
+    copy_n(_InputIter __first, _Size __count, _OutputIter __result)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
+	    typename iterator_traits<_InputIter>::value_type>)
+
+      return __copy_n(__first, __count, __result,
+		      std::__iterator_category(__first));
+    }
+
+  template<typename _InputIter1, typename _InputIter2>
+    int
+    __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
+				   _InputIter2 __first2, _InputIter2 __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 _InputIter1, typename _InputIter2>
+    int
+    lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
+				 _InputIter2 __first2, _InputIter2 __last2)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
+      __glibcpp_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_InputIter1>::value_type>)
+      __glibcpp_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_InputIter2>::value_type>)
+
+      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 _InputIter, typename _Tp, typename _Size>
+    void
+    count(_InputIter __first, _InputIter __last,
+	  const _Tp& __value,
+	  _Size& __n)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+      __glibcpp_function_requires(_EqualityComparableConcept<
+	    typename iterator_traits<_InputIter>::value_type >)
+      __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
+      for ( ; __first != __last; ++__first)
+	if (*__first == __value)
+	  ++__n;
+    }
+
+  template<typename _InputIter, typename _Predicate, typename _Size>
+    void
+    count_if(_InputIter __first, _InputIter __last,
+	     _Predicate __pred,
+	     _Size& __n)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+      __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
+	    typename iterator_traits<_InputIter>::value_type>)
+      for ( ; __first != __last; ++__first)
+	if (__pred(*__first))
+	  ++__n;
+    }
+
+  // random_sample and random_sample_n (extensions, not part of the standard).
+
+  template<typename _ForwardIter, typename _OutputIter, typename _Distance>
+    _OutputIter
+    random_sample_n(_ForwardIter __first, _ForwardIter __last,
+                    _OutputIter __out, const _Distance __n)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
+		typename iterator_traits<_ForwardIter>::value_type>)
+
+      _Distance __remaining = std::distance(__first, __last);
+      _Distance __m = min(__n, __remaining);
+
+      while (__m > 0) {
+	if (std::__random_number(__remaining) < __m) {
+	      *__out = *__first;
+	      ++__out;
+	      --__m;
+	}
+
+	--__remaining;
+	++__first;
+      }
+      return __out;
+    }
+
+  template<typename _ForwardIter, typename _OutputIter, typename _Distance,
+	   typename _RandomNumberGenerator>
+    _OutputIter
+    random_sample_n(_ForwardIter __first, _ForwardIter __last,
+                   _OutputIter __out, const _Distance __n, 
+		   _RandomNumberGenerator& __rand)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
+		typename iterator_traits<_ForwardIter>::value_type>)
+      __glibcpp_function_requires(_UnaryFunctionConcept<
+		_RandomNumberGenerator, _Distance, _Distance>)
+
+      _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 _InputIter, typename _RandomAccessIter, typename _Distance>
+    _RandomAccessIter
+    __random_sample(_InputIter __first, _InputIter __last,
+		    _RandomAccessIter __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::__random_number(__t);
+	if (__M < __n)
+	  __out[__M] = *__first;
+	++__first;
+      }
+
+      return __out + __m;
+    }
+
+  template<typename _InputIter, typename _RandomAccessIter,
+	   typename _RandomNumberGenerator, typename _Distance>
+    _RandomAccessIter
+    __random_sample(_InputIter __first, _InputIter __last,
+		    _RandomAccessIter __out,
+		    _RandomNumberGenerator& __rand,
+		    const _Distance __n)
+    {
+      // concept requirements
+      __glibcpp_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;
+    }
+
+  template<typename _InputIter, typename _RandomAccessIter>
+    inline _RandomAccessIter
+    random_sample(_InputIter __first, _InputIter __last,
+		  _RandomAccessIter __out_first, _RandomAccessIter __out_last) 
+    {
+      // concept requirements
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIter>)
+
+      return __random_sample(__first, __last,
+			     __out_first, __out_last - __out_first);
+    }
+
+  template<typename _InputIter, typename _RandomAccessIter, 
+	   typename _RandomNumberGenerator>
+    inline _RandomAccessIter
+    random_sample(_InputIter __first, _InputIter __last,
+		  _RandomAccessIter __out_first, _RandomAccessIter __out_last,
+		  _RandomNumberGenerator& __rand) 
+    {
+      // concept requirements
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIter>)
+
+      return __random_sample(__first, __last,
+			     __out_first, __rand,
+			     __out_last - __out_first);
+    }
+  
+  // is_heap, a predicate testing whether or not a range is
+  // a heap.  This function is an extension, not part of the C++
+  // standard.
+
+  template<typename _RandomAccessIter, typename _Distance>
+    bool
+    __is_heap(_RandomAccessIter __first, _Distance __n)
+    {
+      _Distance __parent = 0;
+      for (_Distance __child = 1; __child < __n; ++__child) {
+	if (__first[__parent] < __first[__child]) 
+	  return false;
+	if ((__child & 1) == 0)
+	  ++__parent;
+      }
+      return true;
+    }
+
+  template<typename _RandomAccessIter, typename _Distance,
+           typename _StrictWeakOrdering>
+    bool
+    __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
+	      _Distance __n)
+    {
+      _Distance __parent = 0;
+      for (_Distance __child = 1; __child < __n; ++__child) {
+	if (__comp(__first[__parent], __first[__child]))
+	  return false;
+	if ((__child & 1) == 0)
+	  ++__parent;
+      }
+      return true;
+    }
+
+  template<typename _RandomAccessIter>
+    inline bool
+    is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
+      __glibcpp_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIter>::value_type>)
+
+      return __is_heap(__first, __last - __first);
+    }
+
+  template<typename _RandomAccessIter, typename _StrictWeakOrdering>
+    inline bool
+    is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
+	    _StrictWeakOrdering __comp)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
+      __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
+	    typename iterator_traits<_RandomAccessIter>::value_type, 
+	    typename iterator_traits<_RandomAccessIter>::value_type>)
+
+      return __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.
+
+  template<typename _ForwardIter>
+    bool
+    is_sorted(_ForwardIter __first, _ForwardIter __last)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+      __glibcpp_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_ForwardIter>::value_type>)
+
+      if (__first == __last)
+	return true;
+
+      _ForwardIter __next = __first;
+      for (++__next; __next != __last; __first = __next, ++__next) {
+	if (*__next < *__first)
+	  return false;
+      }
+
+      return true;
+    }
+
+  template<typename _ForwardIter, typename _StrictWeakOrdering>
+    bool
+    is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+      __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
+	    typename iterator_traits<_ForwardIter>::value_type, 
+	    typename iterator_traits<_ForwardIter>::value_type>)
+
+      if (__first == __last)
+	return true;
+
+      _ForwardIter __next = __first;
+      for (++__next; __next != __last; __first = __next, ++__next) {
+	if (__comp(*__next, *__first))
+	  return false;
+      }
+
+      return true;
+    }
+
+} // namespace __gnu_cxx
+
+#endif /* _EXT_ALGORITHM */