From 2c1bc4ebc98009ceac7a6df0bdafd63ce5cf0d13 Mon Sep 17 00:00:00 2001 From: Paolo Carlini Date: Fri, 28 Dec 2001 19:46:54 +0100 Subject: [PATCH] stl_algo.h (count returning void, [...]): Move to... 2001-12-28 Paolo Carlini * 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 . From-SVN: r48350 --- libstdc++-v3/ChangeLog | 10 + libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 181 +++++++------- libstdc++-v3/include/bits/stl_algo.h | 285 +-------------------- libstdc++-v3/include/ext/algorithm | 345 ++++++++++++++++++++++++++ libstdc++-v3/testsuite/ext/headers.cc | 1 + 6 files changed, 447 insertions(+), 376 deletions(-) create mode 100644 libstdc++-v3/include/ext/algorithm diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index af9d997dad9..f28b8cc227c 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,13 @@ +2001-12-28 Paolo Carlini + + * 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 . + 2001-12-28 Paolo Carlini Nathan Myers diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 383e3917e02..a54bfcb6c2b 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -172,6 +172,7 @@ backward_headers = \ ext_srcdir = ${glibcpp_srcdir}/include/ext ext_builddir = ./ext ext_headers = \ + ${ext_srcdir}/algorithm \ ${ext_srcdir}/rope \ ${ext_srcdir}/ropeimpl.h \ ${ext_srcdir}/stl_rope.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index f16780f2472..038ad09efe1 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -1,6 +1,7 @@ -# Makefile.in generated automatically by automake 1.4-p5 from Makefile.am +# Makefile.in generated automatically by automake 1.5 from Makefile.am. -# Copyright (C) 1994, 1995-8, 1999, 2001 Free Software Foundation, Inc. +# Copyright 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001 +# Free Software Foundation, Inc. # This Makefile.in is free software; the Free Software Foundation # gives unlimited permission to copy and/or distribute it, # with or without modifications, as long as this notice is preserved. @@ -10,6 +11,7 @@ # even the implied warranty of MERCHANTABILITY or FITNESS FOR A # PARTICULAR PURPOSE. +@SET_MAKE@ SHELL = @SHELL@ @@ -31,13 +33,9 @@ infodir = @infodir@ mandir = @mandir@ includedir = @includedir@ oldincludedir = /usr/include - -DESTDIR = - pkgdatadir = $(datadir)/@PACKAGE@ pkglibdir = $(libdir)/@PACKAGE@ pkgincludedir = $(includedir)/@PACKAGE@ - top_builddir = .. ACLOCAL = @ACLOCAL@ @@ -46,11 +44,11 @@ AUTOMAKE = @AUTOMAKE@ AUTOHEADER = @AUTOHEADER@ INSTALL = @INSTALL@ -INSTALL_PROGRAM = @INSTALL_PROGRAM@ $(AM_INSTALL_PROGRAM_FLAGS) +INSTALL_PROGRAM = @INSTALL_PROGRAM@ INSTALL_DATA = @INSTALL_DATA@ INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_HEADER = $(INSTALL_DATA) transform = @program_transform_name@ - NORMAL_INSTALL = : PRE_INSTALL = : POST_INSTALL = : @@ -84,7 +82,6 @@ C_INCLUDE_DIR = @C_INCLUDE_DIR@ DATADIRNAME = @DATADIRNAME@ DEBUG_FLAGS = @DEBUG_FLAGS@ DLLTOOL = @DLLTOOL@ -EXEEXT = @EXEEXT@ EXTRA_CXX_FLAGS = @EXTRA_CXX_FLAGS@ GCJ = @GCJ@ GCJFLAGS = @GCJFLAGS@ @@ -108,7 +105,6 @@ LIBSUPCXX_PICFLAGS = @LIBSUPCXX_PICFLAGS@ LIBTOOL = @LIBTOOL@ LN_S = @LN_S@ MAINT = @MAINT@ -MAKEINFO = @MAKEINFO@ MKINSTALLDIRS = @MKINSTALLDIRS@ MSGFMT = @MSGFMT@ OBJDUMP = @OBJDUMP@ @@ -146,16 +142,23 @@ libtool_VERSION = @libtool_VERSION@ release_VERSION = @release_VERSION@ toplevel_srcdir = @toplevel_srcdir@ +# Cross compiler and multilib support. +CXX = @glibcpp_CXX@ +glibcpp_builddir = @glibcpp_builddir@ +glibcpp_srcdir = @glibcpp_srcdir@ + +# Target includes for threads +glibcpp_thread_h = @glibcpp_thread_h@ + +# One big happy istallation: just copy everything from the build to the +# install tree (except for the build stamps). +gxx_include_dir = @gxx_include_dir@ + AUTOMAKE_OPTIONS = 1.3 gnits MAINT_CHARSET = latin1 mkinstalldirs = $(SHELL) $(toplevel_srcdir)/mkinstalldirs -# Cross compiler and multilib support. -CXX = @glibcpp_CXX@ -glibcpp_srcdir = @glibcpp_srcdir@ -glibcpp_builddir = @glibcpp_builddir@ - bits_srcdir = ${glibcpp_srcdir}/include/bits bits_builddir = ./bits bits_headers = \ @@ -299,6 +302,7 @@ backward_headers = \ ext_srcdir = ${glibcpp_srcdir}/include/ext ext_builddir = ./ext ext_headers = \ + ${ext_srcdir}/algorithm \ ${ext_srcdir}/rope \ ${ext_srcdir}/ropeimpl.h \ ${ext_srcdir}/stl_rope.h \ @@ -408,114 +412,108 @@ thread_headers = \ allstamps = stamp-std stamp-bits stamp-c_base stamp-backward stamp-ext \ stamp-target stamp-thread - -# Target includes for threads -glibcpp_thread_h = @glibcpp_thread_h@ uppercase = [ABCDEFGHIJKLMNOPQRSTUVWXYZ_] +subdir = include +CONFIG_HEADER = $(top_builddir)/config.h +CONFIG_CLEAN_FILES = +depcomp = +DIST_SOURCES = +all: all-am -# One big happy istallation: just copy everything from the build to the -# install tree (except for the build stamps). -gxx_include_dir = @gxx_include_dir@ -CONFIG_HEADER = ../config.h -CONFIG_CLEAN_FILES = -DIST_COMMON = Makefile.am Makefile.in - - -DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST) - -TAR = gtar -GZIP_ENV = --best -all: all-redirect .SUFFIXES: -$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ Makefile.am $(top_srcdir)/configure.in $(ACLOCAL_M4) - cd $(top_srcdir) && $(AUTOMAKE) --cygnus include/Makefile -Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status - cd $(top_builddir) \ - && CONFIG_FILES=$(subdir)/$@ CONFIG_HEADERS= $(SHELL) ./config.status +mostlyclean-libtool: + -rm -f *.lo + +clean-libtool: + -rm -rf .libs _libs +distclean-libtool: + -rm -f libtool +$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ Makefile.am $(top_srcdir)/configure.in $(ACLOCAL_M4) + cd $(top_srcdir) && \ + $(AUTOMAKE) --cygnus include/Makefile +Makefile: @MAINTAINER_MODE_TRUE@ $(srcdir)/Makefile.in $(top_builddir)/config.status + cd $(top_builddir) && \ + CONFIG_HEADERS= CONFIG_LINKS= \ + CONFIG_FILES=$(subdir)/$@ $(SHELL) ./config.status +uninstall-info-am: tags: TAGS TAGS: - -distdir = $(top_builddir)/$(PACKAGE)-$(VERSION)/$(subdir) - -subdir = include - -distdir: $(DISTFILES) - @for file in $(DISTFILES); do \ - if test -f $$file; then d=.; else d=$(srcdir); fi; \ - if test -d $$d/$$file; then \ - cp -pr $$d/$$file $(distdir)/$$file; \ - else \ - test -f $(distdir)/$$file \ - || ln $$d/$$file $(distdir)/$$file 2> /dev/null \ - || cp -p $$d/$$file $(distdir)/$$file || :; \ - fi; \ - done -info-am: -info: info-am -dvi-am: -dvi: dvi-am check-am: check: check-am -installcheck-am: -installcheck: installcheck-am -install-info-am: -install-info: install-info-am -install-exec-am: -install-exec: install-exec-am +all-am: Makefile all-local -install-data-am: install-data-local -install-data: install-data-am +installdirs: -install-am: all-am - @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am install: install-am -uninstall-am: +install-exec: install-exec-am +install-data: install-data-am uninstall: uninstall-am -all-am: Makefile all-local -all-redirect: all-am -install-strip: - $(MAKE) $(AM_MAKEFLAGS) AM_INSTALL_PROGRAM_FLAGS=-s install -installdirs: +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am +installcheck: installcheck-am +install-strip: + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + `test -z '$(STRIP)' || \ + echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install mostlyclean-generic: clean-generic: distclean-generic: - -rm -f Makefile $(CONFIG_CLEAN_FILES) - -rm -f config.cache config.log stamp-h stamp-h[0-9]* + -rm -f Makefile $(CONFIG_CLEAN_FILES) stamp-h stamp-h[0-9]* maintainer-clean-generic: -mostlyclean-am: mostlyclean-generic + @echo "This command is intended for maintainers to use" + @echo "it deletes files that may require special tools to rebuild." +clean: clean-am -mostlyclean: mostlyclean-am +clean-am: clean-generic clean-libtool mostlyclean-am -clean-am: clean-generic mostlyclean-am +distclean: distclean-am -clean: clean-am +distclean-am: clean-am distclean-generic distclean-libtool -distclean-am: distclean-generic clean-am - -rm -f libtool +dvi: dvi-am -distclean: distclean-am +dvi-am: -maintainer-clean-am: maintainer-clean-generic distclean-am - @echo "This command is intended for maintainers to use;" - @echo "it deletes files that may require special tools to rebuild." +info: info-am + +info-am: + +install-data-am: install-data-local + +install-exec-am: + +install-info: + +install-man: + +installcheck-am: maintainer-clean: maintainer-clean-am -.PHONY: tags distdir info-am info dvi-am dvi check check-am \ -installcheck-am installcheck install-info-am install-info \ -install-exec-am install-exec install-data-local install-data-am \ -install-data install-am install uninstall-am uninstall all-local \ -all-redirect all-am all installdirs mostlyclean-generic \ -distclean-generic clean-generic maintainer-clean-generic clean \ -mostlyclean distclean maintainer-clean +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-am + +mostlyclean-am: mostlyclean-generic mostlyclean-libtool + +uninstall-am: + +.PHONY: all all-am all-local check check-am clean clean-generic \ + clean-libtool distclean distclean-generic distclean-libtool dvi \ + dvi-am info info-am install install-am install-data \ + install-data-am install-data-local install-exec install-exec-am \ + install-info install-info-am install-man install-strip \ + installcheck installcheck-am installdirs maintainer-clean \ + maintainer-clean-generic mostlyclean mostlyclean-generic \ + mostlyclean-libtool uninstall uninstall-am uninstall-info-am # Here are the rules for building the headers @@ -622,7 +620,6 @@ install-data-local: # By adding these files here, automake will remove them for 'make clean' #CLEANFILES = ${allstamps} - # Tell versions [3.59,3.63) of GNU make to not export all variables. # Otherwise a system limit (for SysV at least) may be exceeded. .NOEXPORT: diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 1afadfa3fe8..1bcd98f6c40 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -292,42 +292,7 @@ namespace std 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 - 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 - 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 iterator_traits<_InputIter>::difference_type @@ -1177,146 +1142,6 @@ __result, __binary_pred, _IterType()); iter_swap(__i, __first + __rand((__i - __first) + 1)); } - // random_sample and random_sample_n (extensions, not part of the standard). - - template - _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 - _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 - _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 - _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 - 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 - 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 @@ -3491,114 +3316,6 @@ __result, __binary_pred, _IterType()); __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 - 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 - 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 - 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 - 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 - 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 - 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 #endif /* __GLIBCPP_INTERNAL_ALGO_H */ 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 + +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 + 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 + 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 + _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 + _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 + _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 + _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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 */ diff --git a/libstdc++-v3/testsuite/ext/headers.cc b/libstdc++-v3/testsuite/ext/headers.cc index 297674db1c3..4bda2db02b0 100644 --- a/libstdc++-v3/testsuite/ext/headers.cc +++ b/libstdc++-v3/testsuite/ext/headers.cc @@ -23,6 +23,7 @@ // This should include a list of all headers in the extension // subdirectory that are meant to be directly included. +#include #include #include #include -- 2.30.2