This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Update backward/algo.h (take2) (was: Re: [PATCH] Update backward/algo.h)
Hi again,
before going through regenerating Makefile.in and everything I would like to ask
if the following approach would be acceptable (would answer Nathan's warning):
more or less the same used by ext/rope: a very simple ext/algorithm including
ext/algorithmimpl.h. Then backward/algo.h includes ext/algorithmimpl.h.
This is the preliminary patch.
Thanks,
Paolo.
///////////
diff -prN libstdc++-v3-orig/include/backward/algo.h
libstdc++-v3/include/backward/algo.h
*** libstdc++-v3-orig/include/backward/algo.h Wed Jun 27 19:09:52 2001
--- libstdc++-v3/include/backward/algo.h Sun Dec 30 11:27:47 2001
***************
*** 62,67 ****
--- 62,68 ----
#include "iterator.h"
#include <bits/stl_algo.h>
#include <bits/stl_numeric.h>
+ #include <ext/algorithmimpl.h>
// Names from <stl_algo.h>
using std::for_each;
*************** using std::reverse_copy;
*** 91,98 ****
using std::rotate;
using std::rotate_copy;
using std::random_shuffle;
- using std::random_sample;
- using std::random_sample_n;
using std::partition;
using std::stable_partition;
using std::sort;
--- 92,97 ----
*************** using std::next_permutation;
*** 117,124 ****
using std::prev_permutation;
using std::find_first_of;
using std::find_end;
- using std::is_sorted;
- using std::is_heap;
// Names from stl_heap.h
using std::push_heap;
--- 116,121 ----
*************** using std::partial_sum;
*** 133,138 ****
--- 130,141 ----
using std::adjacent_difference;
using std::power;
using std::iota;
+
+ // Names from ext/algorithmimpl.h
+ using __gnu_cxx::random_sample;
+ using __gnu_cxx::random_sample_n;
+ using __gnu_cxx::is_sorted;
+ using __gnu_cxx::is_heap;
#endif /* _CPP_BACKWARD_ALGO_H */
diff -prN libstdc++-v3-orig/include/ext/algorithm
libstdc++-v3/include/ext/algorithm
*** libstdc++-v3-orig/include/ext/algorithm Fri Dec 28 18:43:00 2001
--- libstdc++-v3/include/ext/algorithm Sun Dec 30 11:42:49 2001
***************
*** 54,345 ****
*/
#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 */
--- 54,61 ----
*/
#ifndef _EXT_ALGORITHM
! #define _EXT_ALGORITHM 1
! #include <ext/algorithmimpl.h>
#endif /* _EXT_ALGORITHM */
diff -prN libstdc++-v3-orig/include/ext/algorithmimpl.h
libstdc++-v3/include/ext/algorithmimpl.h
*** libstdc++-v3-orig/include/ext/algorithmimpl.h Thu Jan 1 01:00:00 1970
--- libstdc++-v3/include/ext/algorithmimpl.h Sun Dec 30 11:43:03 2001
***************
*** 0 ****
--- 1,345 ----
+ // Algorithm extensions implementation -*- 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_BITS_ALGORITHM
+ #define _EXT_BITS_ALGORITHM 1
+
+ #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_BITS_ALGORITHM */