From 43e9f72225b84f101fed8d86b27d47b008d0910f Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 29 Oct 2014 18:21:59 +0000 Subject: [PATCH] Add and . * doc/xml/manual/status_cxx2014.xml: Update TS status. * include/Makefile.am: Add new headers. * include/Makefile.in: Regenerate. * include/experimental/algorithm: New. * include/experimental/functional: New. * testsuite/experimental/algorithm/sample.cc: New. * testsuite/experimental/algorithm/search.cc: New. * testsuite/experimental/functional/not_fn.cc: New. * testsuite/experimental/functional/searchers.cc: New. * testsuite/experimental/functional/value.cc: New. * testsuite/experimental/feat-lib-fund.cc: Add headers and reorder. From-SVN: r216847 --- libstdc++-v3/ChangeLog | 14 + .../doc/xml/manual/status_cxx2014.xml | 6 +- libstdc++-v3/include/Makefile.am | 2 + libstdc++-v3/include/Makefile.in | 2 + libstdc++-v3/include/experimental/algorithm | 137 ++++++ libstdc++-v3/include/experimental/functional | 428 ++++++++++++++++++ .../experimental/algorithm/sample.cc | 99 ++++ .../experimental/algorithm/search.cc | 44 ++ .../testsuite/experimental/feat-lib-fund.cc | 51 ++- .../experimental/functional/not_fn.cc | 57 +++ .../experimental/functional/searchers.cc | 137 ++++++ .../experimental/functional/value.cc | 43 ++ 12 files changed, 1005 insertions(+), 15 deletions(-) create mode 100644 libstdc++-v3/include/experimental/algorithm create mode 100644 libstdc++-v3/include/experimental/functional create mode 100644 libstdc++-v3/testsuite/experimental/algorithm/sample.cc create mode 100644 libstdc++-v3/testsuite/experimental/algorithm/search.cc create mode 100644 libstdc++-v3/testsuite/experimental/functional/not_fn.cc create mode 100644 libstdc++-v3/testsuite/experimental/functional/searchers.cc create mode 100644 libstdc++-v3/testsuite/experimental/functional/value.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 0cea62e90f2..78ffe5ec764 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,17 @@ +2014-10-29 Jonathan Wakely + + * doc/xml/manual/status_cxx2014.xml: Update TS status. + * include/Makefile.am: Add new headers. + * include/Makefile.in: Regenerate. + * include/experimental/algorithm: New. + * include/experimental/functional: New. + * testsuite/experimental/algorithm/sample.cc: New. + * testsuite/experimental/algorithm/search.cc: New. + * testsuite/experimental/functional/not_fn.cc: New. + * testsuite/experimental/functional/searchers.cc: New. + * testsuite/experimental/functional/value.cc: New. + * testsuite/experimental/feat-lib-fund.cc: Add headers and reorder. + 2014-10-25 François Dumont * doc/xml/manual/status_cxx2011.xml: Update unordered container diff --git a/libstdc++-v3/doc/xml/manual/status_cxx2014.xml b/libstdc++-v3/doc/xml/manual/status_cxx2014.xml index e2a2d942a87..f7d18a2a340 100644 --- a/libstdc++-v3/doc/xml/manual/status_cxx2014.xml +++ b/libstdc++-v3/doc/xml/manual/status_cxx2014.xml @@ -329,14 +329,13 @@ not in any particular release. - N3905 Faster string searching (Boyer-Moore et al.) - N + Y Library Fundamentals TS @@ -387,14 +386,13 @@ not in any particular release. - N3925 A sample proposal - N + Y Library Fundamentals TS diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 89fa4364ebc..5fa243b96f4 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -639,8 +639,10 @@ decimal_headers = \ experimental_srcdir = ${glibcxx_srcdir}/include/experimental experimental_builddir = ./experimental experimental_headers = \ + ${experimental_srcdir}/algorithm \ ${experimental_srcdir}/any \ ${experimental_srcdir}/chrono \ + ${experimental_srcdir}/functional \ ${experimental_srcdir}/optional \ ${experimental_srcdir}/ratio \ ${experimental_srcdir}/string_view \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index bf10d6f45d8..4ae4e41f3ac 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -905,8 +905,10 @@ decimal_headers = \ experimental_srcdir = ${glibcxx_srcdir}/include/experimental experimental_builddir = ./experimental experimental_headers = \ + ${experimental_srcdir}/algorithm \ ${experimental_srcdir}/any \ ${experimental_srcdir}/chrono \ + ${experimental_srcdir}/functional \ ${experimental_srcdir}/optional \ ${experimental_srcdir}/ratio \ ${experimental_srcdir}/string_view \ diff --git a/libstdc++-v3/include/experimental/algorithm b/libstdc++-v3/include/experimental/algorithm new file mode 100644 index 00000000000..3d669b048cc --- /dev/null +++ b/libstdc++-v3/include/experimental/algorithm @@ -0,0 +1,137 @@ +// -*- C++ -*- + +// Copyright (C) 2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file experimental/algorithm + * This is a TS C++ Library header. + */ + +#ifndef _GLIBCXX_EXPERIMENTAL_ALGORITHM +#define _GLIBCXX_EXPERIMENTAL_ALGORITHM 1 + +#pragma GCC system_header + +#if __cplusplus <= 201103L +# include +#else + +#include +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +namespace experimental +{ +inline namespace fundamentals_v1 +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + template + inline _ForwardIterator + search(_ForwardIterator __first, _ForwardIterator __last, + const _Searcher& __searcher) + { return __searcher(__first, __last); } + +#define __cpp_lib_experimental_sample 201402 + + /// Reservoir sampling algorithm. + template + _RandomAccessIterator + __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, + _RandomAccessIterator __out, random_access_iterator_tag, + _Size __n, _UniformRandomNumberGenerator&& __g) + { + using __distrib_type = std::uniform_int_distribution<_Size>; + using __param_type = typename __distrib_type::param_type; + __distrib_type __d{}; + _Size __sample_sz = 0; + while (__first != __last && __sample_sz != __n) + __out[__sample_sz++] = *__first++; + for (auto __pop_sz = __sample_sz; __first != __last; + ++__first, ++__pop_sz) + { + const auto __k = __d(__g, __param_type{0, __pop_sz}); + if (__k < __n) + __out[__k] = *__first; + } + return __out + __sample_sz; + } + + /// Selection sampling algorithm. + template + _OutputIterator + __sample(_ForwardIterator __first, _ForwardIterator __last, + forward_iterator_tag, + _OutputIterator __out, _Cat, + _Size __n, _UniformRandomNumberGenerator&& __g) + { + using __distrib_type = std::uniform_int_distribution<_Size>; + using __param_type = typename __distrib_type::param_type; + __distrib_type __d{}; + _Size __unsampled_sz = std::distance(__first, __last); + for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first) + if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) + { + *__out++ = *__first; + --__n; + } + return __out; + } + + /// Take a random sample from a population. + template + _SampleIterator + sample(_PopulationIterator __first, _PopulationIterator __last, + _SampleIterator __out, _Distance __n, + _UniformRandomNumberGenerator&& __g) + { + using __pop_cat = typename + std::iterator_traits<_PopulationIterator>::iterator_category; + using __samp_cat = typename + std::iterator_traits<_SampleIterator>::iterator_category; + + static_assert( + __or_, + is_convertible<__samp_cat, random_access_iterator_tag>>::value, + "output range must use a RandomAccessIterator when input range" + " does not meet the ForwardIterator requirements"); + + static_assert(is_integral<_Distance>::value, + "sample size must be an integer type"); + + return std::experimental::__sample( + __first, __last, __pop_cat{}, __out, __samp_cat{}, + __n, std::forward<_UniformRandomNumberGenerator>(__g)); + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace fundamentals_v1 +} // namespace experimental +} // namespace std + +#endif // C++14 + +#endif // _GLIBCXX_EXPERIMENTAL_ALGORITHM diff --git a/libstdc++-v3/include/experimental/functional b/libstdc++-v3/include/experimental/functional new file mode 100644 index 00000000000..4ecc6a5fb6d --- /dev/null +++ b/libstdc++-v3/include/experimental/functional @@ -0,0 +1,428 @@ +// -*- C++ -*- + +// Copyright (C) 2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file experimental/functional + * This is a TS C++ Library header. + */ + +#ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL +#define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1 + +#pragma GCC system_header + +#if __cplusplus <= 201103L +# include +#else + +#include +#include +#include +#include +#include +#include +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +namespace experimental +{ +inline namespace fundamentals_v1 +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // See C++14 §20.9.9, Function object binders + + /// Variable template for std::is_bind_expression + template + constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value; + + /// Variable template for std::is_placeholder + template + constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value; + +#define __cpp_lib_experimental_boyer_moore_searching 201402 + + // Searchers + + template> + class default_searcher + { + public: + default_searcher(_ForwardIterator1 __pat_first, + _ForwardIterator1 __pat_last, + _BinaryPredicate __pred = _BinaryPredicate()) + : _M_m(__pat_first, __pat_last, std::move(__pred)) + { } + + template + _ForwardIterator2 + operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const + { + return std::search(__first, __last, + std::get<0>(_M_m), std::get<1>(_M_m), + std::get<2>(_M_m)); + } + + private: + std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m; + }; + + template + struct __boyer_moore_map_base + { + template + __boyer_moore_map_base(_RAIter __pat, size_t __patlen, + _Hash&& __hf, _Pred&& __pred) + : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) } + { + if (__patlen > 0) + for (__diff_type __i = 0; __i < __patlen - 1; ++__i) + _M_bad_char[__pat[__i]] = __patlen - 1 - __i; + } + + using __diff_type = _Tp; + + __diff_type + _M_lookup(_Key __key, __diff_type __not_found) const + { + auto __iter = _M_bad_char.find(__key); + if (__iter == _M_bad_char.end()) + return __not_found; + return __iter->second; + } + + _Pred + _M_pred() const { return _M_bad_char.key_eq(); } + + std::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char; + }; + + template + struct __boyer_moore_array_base + { + template + __boyer_moore_array_base(_RAIter __pat, size_t __patlen, + _Unused&&, _Pred&& __pred) + : _M_bad_char{ {}, std::move(__pred) } + { + std::get<0>(_M_bad_char).fill(__patlen); + if (__patlen > 0) + for (__diff_type __i = 0; __i < __patlen - 1; ++__i) + { + auto __ch = __pat[__i]; + using _UCh = std::make_unsigned_t; + auto __uch = static_cast<_UCh>(__ch); + std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i; + } + } + + using __diff_type = _Tp; + + template + __diff_type + _M_lookup(_Key __key, __diff_type __not_found) const + { + auto __ukey = static_cast>(__key); + if (__ukey >= _Len) + return __not_found; + return std::get<0>(_M_bad_char)[__ukey]; + } + + const _Pred& + _M_pred() const { return std::get<1>(_M_bad_char); } + + std::tuple, _Pred> _M_bad_char; + }; + + template + struct __is_std_equal_to : std::false_type { }; + + template<> + struct __is_std_equal_to> : std::true_type { }; + + // Use __boyer_moore_array_base when pattern consists of narrow characters + // and uses std::equal_to as the predicate. + template::value_type, + typename _Diff = typename iterator_traits<_RAIter>::difference_type> + using __boyer_moore_base_t + = std::conditional_t::value + && __is_std_equal_to<_Pred>::value, + __boyer_moore_array_base<_Diff, 256, _Pred>, + __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; + + template::value_type>, + typename _BinaryPredicate = std::equal_to<>> + class boyer_moore_searcher + : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> + { + using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; + using typename _Base::__diff_type; + + public: + boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, + _Hash __hf = _Hash(), + _BinaryPredicate __pred = _BinaryPredicate()); + + template + _RandomAccessIterator2 + operator()(_RandomAccessIterator2 __first, + _RandomAccessIterator2 __last) const; + + private: + bool + _M_is_prefix(_RAIter __word, __diff_type __len, + __diff_type __pos) + { + const auto& __pred = this->_M_pred(); + __diff_type __suffixlen = __len - __pos; + for (__diff_type __i = 0; __i < __suffixlen; ++__i) + if (!__pred(__word[__i], __word[__pos + __i])) + return false; + return true; + } + + __diff_type + _M_suffix_length(_RAIter __word, __diff_type __len, + __diff_type __pos) + { + const auto& __pred = this->_M_pred(); + __diff_type __i = 0; + while (__pred(__word[__pos - __i], __word[__len - 1 - __i]) + && __i < __pos) + { + ++__i; + } + return __i; + } + + template + __diff_type + _M_bad_char_shift(_Tp __c) const + { return this->_M_lookup(__c, _M_pat_end - _M_pat); } + + _RAIter _M_pat; + _RAIter _M_pat_end; + std::vector<__diff_type> _M_good_suffix; + }; + + template::value_type>, + typename _BinaryPredicate = std::equal_to<>> + class boyer_moore_horspool_searcher + : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> + { + using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; + using typename _Base::__diff_type; + + public: + boyer_moore_horspool_searcher(_RAIter __pat, + _RAIter __pat_end, + _Hash __hf = _Hash(), + _BinaryPredicate __pred + = _BinaryPredicate()) + : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), + _M_pat(__pat), _M_pat_end(__pat_end) + { } + + template + _RandomAccessIterator2 + operator()(_RandomAccessIterator2 __first, + _RandomAccessIterator2 __last) const + { + const auto& __pred = this->_M_pred(); + auto __patlen = _M_pat_end - _M_pat; + if (__patlen == 0) + return __first; + auto __len = __last - __first; + while (__len >= __patlen) + { + for (auto __scan = __patlen - 1; + __pred(__first[__scan], _M_pat[__scan]); --__scan) + if (__scan == 0) + return __first; + auto __shift = _M_bad_char_shift(__first[__patlen - 1]); + __len -= __shift; + __first += __shift; + } + return __last; + } + + private: + template + __diff_type + _M_bad_char_shift(_Tp __c) const + { return this->_M_lookup(__c, _M_pat_end - _M_pat); } + + _RAIter _M_pat; + _RAIter _M_pat_end; + }; + + /// Generator function for default_searcher + template> + inline default_searcher<_ForwardIterator, _BinaryPredicate> + make_default_searcher(_ForwardIterator __pat_first, + _ForwardIterator __pat_last, + _BinaryPredicate __pred = _BinaryPredicate()) + { return { __pat_first, __pat_last, __pred }; } + + /// Generator function for boyer_moore_searcher + template::value_type>, + typename _BinaryPredicate = equal_to<>> + inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate> + make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, + _Hash __hf = _Hash(), + _BinaryPredicate __pred = _BinaryPredicate()) + { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } + + /// Generator function for boyer_moore_horspool_searcher + template::value_type>, + typename _BinaryPredicate = equal_to<>> + inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate> + make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, + _Hash __hf = _Hash(), + _BinaryPredicate __pred + = _BinaryPredicate()) + { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } + + template + boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: + boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end, + _Hash __hf, _BinaryPredicate __pred) + : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), + _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat) + { + auto __patlen = __pat_end - __pat; + if (__patlen == 0) + return; + __diff_type __last_prefix = __patlen - 1; + for (__diff_type __p = __patlen - 1; __p >= 0; --__p) + { + if (_M_is_prefix(__pat, __patlen, __p + 1)) + __last_prefix = __p + 1; + _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p); + } + for (__diff_type __p = 0; __p < __patlen - 1; ++__p) + { + auto __slen = _M_suffix_length(__pat, __patlen, __p); + auto __pos = __patlen - 1 - __slen; + if (!__pred(__pat[__p - __slen], __pat[__pos])) + _M_good_suffix[__pos] = __patlen - 1 - __p + __slen; + } + } + + template + template + _RandomAccessIterator2 + boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: + operator()(_RandomAccessIterator2 __first, + _RandomAccessIterator2 __last) const + { + auto __patlen = _M_pat_end - _M_pat; + if (__patlen == 0) + return __first; + const auto& __pred = this->_M_pred(); + __diff_type __i = __patlen - 1; + auto __stringlen = __last - __first; + while (__i < __stringlen) + { + __diff_type __j = __patlen - 1; + while (__j >= 0 && __pred(__first[__i], _M_pat[__j])) + { + --__i; + --__j; + } + if (__j < 0) + return __first + __i + 1; + __i += std::max(_M_bad_char_shift(__first[__i]), + _M_good_suffix[__j]); + } + return __last; + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace fundamentals_v1 + +inline namespace fundamentals_v2 +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + +#define __cpp_lib_experimental_not_fn 201406 + + /// Generalized negator. + template + struct _Not_fn + { + template + explicit + _Not_fn(_Fn2&& __fn) : _M_fn(std::forward<_Fn2>(__fn)) { } + + _Not_fn(const _Not_fn& __fn) = default; + _Not_fn(_Not_fn&& __fn) = default; + _Not_fn& operator=(const _Not_fn& __fn) = default; + _Not_fn& operator=(_Not_fn&& __fn) = default; + ~_Not_fn() = default; + + template + decltype(auto) + operator()(_Args&&... __args) + { return !_M_fn(std::forward<_Args>(__args)...); } + + template + decltype(auto) + operator()(_Args&&... __args) const + { return !_M_fn(std::forward<_Args>(__args)...); } + + template + decltype(auto) + operator()(_Args&&... __args) volatile + { return !_M_fn(std::forward<_Args>(__args)...); } + + template + decltype(auto) + operator()(_Args&&... __args) const volatile + { return !_M_fn(std::forward<_Args>(__args)...); } + + private: + _Fn _M_fn; + }; + + /// [func.not_fn] Function template not_fn + template + inline auto + not_fn(_Fn&& __fn) + { return _Not_fn>{std::forward<_Fn>(__fn)}; } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace fundamentals_v2 +} // namespace experimental +} // namespace std + +#endif // C++14 + +#endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL diff --git a/libstdc++-v3/testsuite/experimental/algorithm/sample.cc b/libstdc++-v3/testsuite/experimental/algorithm/sample.cc new file mode 100644 index 00000000000..b1d3efecb93 --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/algorithm/sample.cc @@ -0,0 +1,99 @@ +// Copyright (C) 2014 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 3, 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 COPYING3. If not see +// . + +// { dg-options "-std=gnu++14" } + +#include +#include +#include +#include +#include +#include + +std::mt19937 rng; + +using std::experimental::sample; +using std::istream_iterator; +using std::ostream_iterator; + +void +test01() +{ + const int pop[] = { 1, 2 }; + int samp[10] = { }; + + // population smaller than desired sample size + auto it = sample(pop, pop + 2, samp, 10, rng); + VERIFY( it == samp + 2 ); + VERIFY( std::accumulate(samp, samp + 10, 0) == 3 ); +} + +void +test02() +{ + const int pop[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; + int samp[10] = { }; + + auto it = sample(pop, std::end(pop), samp, 10, rng); + VERIFY( it == samp + 10 ); + + std::sort(samp, it); + auto it2 = std::unique(samp, it); + VERIFY( it2 == it ); +} + +void +test03() +{ + std::istringstream pop("0 1 2 3 4 5 6 7 8 9"); + int samp[5] = { }; + + // input iterator for population + auto it = sample(istream_iterator{pop}, {}, samp, 5, rng); + VERIFY( it == samp + 5 ); + + std::sort(samp, it); + auto it2 = std::unique(samp, it); + VERIFY( it2 == it ); +} + +void +test04() +{ + std::forward_list pop{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; + std::stringstream samp; + + // forward iterator for population and output iterator for result + sample(pop.begin(), pop.end(), ostream_iterator{samp, " "}, 5, rng); + + // samp.rdbuf()->pubseekoff(0, std::ios::beg); + std::vector v(istream_iterator{samp}, {}); + VERIFY( v.size() == 5 ); + + std::sort(v.begin(), v.end()); + auto it = std::unique(v.begin(), v.end()); + VERIFY( it == v.end() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/experimental/algorithm/search.cc b/libstdc++-v3/testsuite/experimental/algorithm/search.cc new file mode 100644 index 00000000000..3ec7ed1d882 --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/algorithm/search.cc @@ -0,0 +1,44 @@ +// Copyright (C) 2014 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 3, 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 COPYING3. If not see +// . + +// { dg-options "-std=gnu++14" } + +#include +#include + +struct nocopy +{ + nocopy() = default; + nocopy(const nocopy&) = delete; + nocopy& operator=(const nocopy&) = delete; + + int* operator()(int* f, int* l) const { return f; } +}; + +void +test01() +{ + int i[] = { 1, 2 }; + auto res = std::experimental::search(i, i + 2, nocopy{}); + VERIFY( res == i ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/experimental/feat-lib-fund.cc b/libstdc++-v3/testsuite/experimental/feat-lib-fund.cc index 0c73f097a10..fbc37447076 100644 --- a/libstdc++-v3/testsuite/experimental/feat-lib-fund.cc +++ b/libstdc++-v3/testsuite/experimental/feat-lib-fund.cc @@ -1,29 +1,58 @@ // { dg-options "-std=gnu++14" } // { dg-do compile } -#include -#include +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif #if !__has_include() # error "" #endif -//#if !__has_include() -//# error "" -//#endif - #if !__has_include() # error "" #endif +#if !__has_include() +# error "" +#endif + +//#if !__has_include() +//# error "" +//#endif + //#if !__has_include() //# error "" //#endif -#if !__has_include() -# error "" -#endif +//#if !__has_include() +//# error "" +//#endif -#if !__has_include() -# error "" +#if !__has_include() +# error "" #endif + +//#if !__has_include() +//# error "" +//#endif diff --git a/libstdc++-v3/testsuite/experimental/functional/not_fn.cc b/libstdc++-v3/testsuite/experimental/functional/not_fn.cc new file mode 100644 index 00000000000..d4c8ed94e9b --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/functional/not_fn.cc @@ -0,0 +1,57 @@ +// Copyright (C) 2014 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 3, 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 COPYING3. If not see +// . + +// { dg-options "-std=gnu++14" } + +#include +#include + +int func(int, char) { return 0; } + +struct F +{ + bool operator()() { return false; } + bool operator()() const { return true; } + bool operator()(int) { return false; } + bool operator()(int) volatile { return true; } +}; + +void +test01() +{ + using std::experimental::not_fn; + + auto f1 = not_fn(func); + VERIFY( f1(1, '2') == true ); + + auto f2 = not_fn( [] { return true; } ); + VERIFY( f2() == false ); + + auto f3 = not_fn( F{} ); + VERIFY( f3() == true ); + VERIFY( f3(1) == true ); + const auto f4 = f3; + VERIFY( f4() == false ); + volatile auto f5 = f3; + VERIFY( f5(1) == false ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/experimental/functional/searchers.cc b/libstdc++-v3/testsuite/experimental/functional/searchers.cc new file mode 100644 index 00000000000..ae04f6ffee8 --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/functional/searchers.cc @@ -0,0 +1,137 @@ +// Copyright (C) 2014 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 3, 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 COPYING3. If not see +// . + +// { dg-options "-std=gnu++14" } + +#include +#include +#ifdef _GLIBCXX_USE_WCHAR_T +# include +#endif +#include + +using std::experimental::make_default_searcher; +using std::experimental::make_boyer_moore_searcher; +using std::experimental::make_boyer_moore_horspool_searcher; + +void +test01() +{ + const char s[] = { 'a', (char)-97, 'a', '\0' }; + const char* needles[] = { + s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd" + }; + const char* haystacks[] = { + s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd", + "aaaaaaa", "aabaa", "aaacab", "cdabcdab", "abcdabcd", "xyzabcdxyz" + }; + + for (auto n : needles) + { + auto ne = n + std::strlen(n); + auto d = make_default_searcher(n, ne); + auto bm = make_boyer_moore_searcher(n, ne); + auto bmh = make_boyer_moore_horspool_searcher(n, ne); + for (auto h : haystacks) + { + auto he = h + std::strlen(h); + auto res = std::search(h, he, n, ne); + auto d_res = d(h, he); + VERIFY( d_res == res ); + auto bm_res = bm(h, he); + VERIFY( bm_res == res ); + auto bmh_res = bmh(h, he); + VERIFY( bmh_res == res ); + } + } +} + +void +test02() +{ +#ifdef _GLIBCXX_USE_WCHAR_T + const wchar_t s[] = { L'a', (wchar_t)-97, L'a', L'\0' }; + const wchar_t* needles[] = { + s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd" + }; + const wchar_t* haystacks[] = { + s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd", + L"aaaaaaa", L"aabaa", L"aaacab", L"cdabcdab", L"abcdabcd", L"xyzabcdxyz" + }; + + for (auto n : needles) + { + auto ne = n + std::wcslen(n); + auto d = make_default_searcher(n, ne); + auto bm = make_boyer_moore_searcher(n, ne); + auto bmh = make_boyer_moore_horspool_searcher(n, ne); + for (auto h : haystacks) + { + auto he = h + std::wcslen(h); + auto res = std::search(h, he, n, ne); + auto d_res = d(h, he); + VERIFY( d_res == res ); + auto bm_res = bm(h, he); + VERIFY( bm_res == res ); + auto bmh_res = bmh(h, he); + VERIFY( bmh_res == res ); + } + } +#endif +} + +void +test03() +{ + // custom predicate + struct + { + static unsigned char + norm(unsigned char c) { return std::isalnum(c) ? c : '#'; } + + // equality + bool operator()(char l, char r) const { return norm(l) == norm(r); } + + // hash + std::size_t operator()(char c) const { return std::hash{}(norm(c)); } + } eq; + + const char* needle = " foo 123 "; + const char* haystack = "*****foo*123******"; + const char* ne = needle + std::strlen(needle); + const char* he = haystack + std::strlen(haystack); + + auto d = make_default_searcher(needle, ne, eq); + auto bm = make_boyer_moore_searcher(needle, ne, eq, eq); + auto bmh = make_boyer_moore_horspool_searcher(needle, ne, eq, eq); + + auto res = std::search(haystack, he, needle, ne, eq); + auto d_res = d(haystack, he); + VERIFY( d_res == res ); + auto bm_res = bm(haystack, he); + VERIFY( bm_res == res ); + auto bmh_res = bmh(haystack, he); + VERIFY( bmh_res == res ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/experimental/functional/value.cc b/libstdc++-v3/testsuite/experimental/functional/value.cc new file mode 100644 index 00000000000..8136e7c3ac6 --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/functional/value.cc @@ -0,0 +1,43 @@ +// Copyright (C) 2014 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 3, 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 COPYING3. If not see +// . + +// { dg-options "-std=gnu++14" } +// { dg-do compile } + +#include + +// These tests are rather simple, the front-end tests already test +// variable templates, and the library tests for the underlying +// traits are more elaborate. These are just simple sanity tests. + +int f(int); + +using B = decltype(std::bind(f, std::placeholders::_1)); + +static_assert(!std::experimental::is_bind_expression_v + && !std::is_bind_expression::value, ""); + +static_assert(std::experimental::is_bind_expression_v + && std::is_bind_expression::value, ""); + +using PH = decltype(std::placeholders::_1); + +static_assert(!std::experimental::is_placeholder_v + && !std::is_placeholder::value, ""); + +static_assert(std::experimental::is_placeholder_v + && std::is_placeholder::value, ""); -- 2.30.2