stl_algo.h (count returning void, [...]): Move to...

2001-12-28  Paolo Carlini  <pcarlini@unitus.it>

        * include/bits/stl_algo.h (count returning void,
        count_if returning void, __random_sample, random_sample,
        random_sample_n, __is_heap, is_heap, is_sorted):  Move to...
        * include/ext/algorithm:  ...here, new file.
	* include/Makefile.am (ext_headers):  Add new file.
        * include/Makefile.in:  Regenerate.
	* testsuite/ext/headers.cc:  Include <ext/algorithm>.

From-SVN: r48350

1 files changed, 345 insertions, 0 deletions

diff --git a/libstdc++-v3/include/ext/algorithm b/libstdc++-v3/include/ext/algorithm
new file mode 100644
index 00000000000..929351eda5f
--- /dev/null
+++ b/libstdc++-v3/include/ext/algorithm
@@ -0,0 +1,345 @@
+// Algorithm extensions -*- C++ -*-
+
+// Copyright (C) 2001 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.
+ */
+
+#ifndef _EXT_ALGORITHM
+#define _EXT_ALGORITHM
+
+#include <bits/std_algorithm.h>
+
+namespace __gnu_cxx
+{
+  // 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 std::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 std::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 std::iterator_traits<_ForwardIter>::value_type>)
+
+      _Distance __remaining = std::distance(__first, __last);
+      _Distance __m = std::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 std::iterator_traits<_ForwardIter>::value_type>)
+      __glibcpp_function_requires(_UnaryFunctionConcept<
+		_RandomNumberGenerator, _Distance, _Distance>)
+
+      _Distance __remaining = std::distance(__first, __last);
+      _Distance __m = std::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 std::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 std::iterator_traits<_RandomAccessIter>::value_type, 
+	    typename std::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 std::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 std::iterator_traits<_ForwardIter>::value_type, 
+	    typename std::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 */