This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[PATCH] For SGI stl_algo.h extensions (was: Re: [RFC] Moving apart SGI extensions)
Ok, since we all more or less agree that the approach suggested by Benjamin is the
right one, I have prepared this patch.
It eviscerates SGI extensions from stl_algo.h, put them in a separate file
(ext/algorithm_ext.h), inside namespace __gnu_cxx, not mangled, including
std_algorithm.h in order to have available all the bits necessary for the
implementation.
Comments? A better name than algorithm_ext.h ?
Cheers,
Paolo.
//////////////
diff -urN libstdc++-v3-orig/include/bits/stl_algo.h
libstdc++-v3/include/bits/stl_algo.h
--- libstdc++-v3-orig/include/bits/stl_algo.h Sun Dec 23 10:58:20 2001
+++ libstdc++-v3-alt/include/bits/stl_algo.h Thu Dec 27 12:06:48 2001
@@ -292,42 +292,7 @@
return __last;
}
- // count and count_if. There are two version of each, one whose return type
- // type is void and one (present only if we have partial specialization)
- // whose return type is iterator_traits<_InputIter>::difference_type. The
- // C++ standard only has the latter version, but the former, which was present
- // in the HP STL, is retained 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;
- }
+ // count and count_if.
template<typename _InputIter, typename _Tp>
typename iterator_traits<_InputIter>::difference_type
@@ -1177,146 +1142,6 @@
iter_swap(__i, __first + __rand((__i - __first) + 1));
}
- // 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 = distance(__first, __last);
- _Distance __m = min(__n, __remaining);
-
- while (__m > 0) {
- if (__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 = 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 = __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);
- }
-
// partition, stable_partition, and their auxiliary functions
template<typename _ForwardIter, typename _Predicate>
@@ -3489,114 +3314,6 @@
__iterator_category(__first1),
__iterator_category(__first2),
__comp);
- }
-
- // 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 std
diff -urN libstdc++-v3-orig/include/ext/algorithm_ext.h
libstdc++-v3/include/ext/algorithm_ext.h
--- libstdc++-v3-orig/include/ext/algorithm_ext.h Thu Jan 1 01:00:00 1970
+++ libstdc++-v3-alt/include/ext/algorithm_ext.h Thu Dec 27 12:07:20 2001
@@ -0,0 +1,319 @@
+// 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.
+
+#ifndef _ALGORITHM_EXT_H
+#define _ALGORITHM_EXT_H
+
+#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 /* _ALGORITHM_EXT_H */