[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add Jonathan's initial constrained algorithms implementation
Patrick Palka
ppalka@gcc.gnu.org
Wed Jan 15 15:35:00 GMT 2020
https://gcc.gnu.org/g:20d84d7749d0cf9254ed6dea812e3313b6c40722
commit 20d84d7749d0cf9254ed6dea812e3313b6c40722
Author: Patrick Palka <ppalka@gcc.gnu.org>
Date: Fri Jan 10 17:11:07 2020 -0500
Add Jonathan's initial constrained algorithms implementation
Diff:
---
libstdc++-v3/include/Makefile.am | 1 +
libstdc++-v3/include/Makefile.in | 1 +
libstdc++-v3/include/bits/ranges_algo.h | 228 +++++++++++++++++++++
libstdc++-v3/include/std/algorithm | 3 +
.../testsuite/25_algorithms/all_of/constrained.cc | 88 ++++++++
5 files changed, 321 insertions(+)
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index b38defc..5f45328 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -156,6 +156,7 @@ bits_headers = \
${bits_srcdir}/random.tcc \
${bits_srcdir}/range_access.h \
${bits_srcdir}/range_cmp.h \
+ ${bits_srcdir}/ranges_algo.h \
${bits_srcdir}/refwrap.h \
${bits_srcdir}/regex.h \
${bits_srcdir}/regex.tcc \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index ae4a493..885c7ce 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -500,6 +500,7 @@ bits_headers = \
${bits_srcdir}/random.tcc \
${bits_srcdir}/range_access.h \
${bits_srcdir}/range_cmp.h \
+ ${bits_srcdir}/ranges_algo.h \
${bits_srcdir}/refwrap.h \
${bits_srcdir}/regex.h \
${bits_srcdir}/regex.tcc \
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
new file mode 100644
index 0000000..2853849
--- /dev/null
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -0,0 +1,228 @@
+// Core algorithmic facilities -*- C++ -*-
+
+// Copyright (C) 2019 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
+// <http://www.gnu.org/licenses/>.
+
+/** @file bits/ranges_algo.h
+ * This is an internal header file, included by other library headers.
+ * Do not attempt to use it directly. @headername{algorithm}
+ */
+
+#ifndef _RANGES_ALGO_H
+#define _RANGES_ALGO_H 1
+
+#if __cplusplus > 201703L
+
+#include <compare>
+#include <iterator>
+// #include <bits/range_concepts.h>
+#include <ranges>
+#include <bits/invoke.h>
+#include <bits/cpp_type_traits.h> // __is_byte
+
+#if __cpp_lib_concepts
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+namespace ranges
+{
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+ constexpr bool
+ all_of(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ {
+ for (; __first != __last; ++__first)
+ if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
+ return false;
+ return true;
+ }
+
+ template<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
+ constexpr bool
+ all_of(_Range&& __r, _Pred __pred, _Proj __proj = {})
+ {
+ return ranges::all_of(ranges::begin(__r), ranges::end(__r),
+ std::move(__pred), std::move(__proj));
+ }
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+ constexpr bool
+ any_of(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ {
+ for (; __first != __last; ++__first)
+ if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
+ return true;
+ return false;
+ }
+
+ template<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
+ constexpr bool
+ any_of(_Range&& __r, _Pred __pred, _Proj __proj = {})
+ {
+ return ranges::any_of(ranges::begin(__r), ranges::end(__r),
+ std::move(__pred), std::move(__proj));
+ }
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+ constexpr bool
+ none_of(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ {
+ for (; __first != __last; ++__first)
+ if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
+ return false;
+ return true;
+ }
+
+ template<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
+ constexpr bool
+ none_of(_Range&& __r, _Pred __pred, _Proj __proj = {})
+ {
+ return ranges::none_of(ranges::begin(__r), ranges::end(__r),
+ std::move(__pred), std::move(__proj));
+ }
+
+ template<typename _Iter, typename _F>
+ struct for_each_result
+ {
+ [[no_unique_address]] _Iter in;
+ [[no_unique_address]] _F fun;
+
+ template<typename _Iter2, typename _F2>
+ requires convertible_to<const _Iter&, _Iter2>
+ && convertible_to<const _F&, _F2>
+ operator for_each_result<_Iter2, _F2>() const &
+ {
+ return {in, fun};
+ }
+
+ template<typename _Iter2, typename _F2>
+ requires convertible_to<_Iter, _Iter2> && convertible_to<_F, _F2>
+ operator for_each_result<_Iter2, _F2>() &&
+ {
+ return {std::move(in), std::move(fun)};
+ }
+ };
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
+ constexpr for_each_result<_Iter, _Fun>
+ for_each(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {})
+ {
+ for (; __first != __last; ++__first)
+ std::__invoke(__f, std::__invoke(__proj, *__first));
+ return { __last, std::move(__f) };
+ }
+
+ template<input_range _Range, typename _Proj = identity,
+ indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
+ _Fun>
+ constexpr for_each_result<safe_iterator_t<_Range>, _Fun>
+ for_each(_Range&& __r, _Fun __f, _Proj __proj = {})
+ {
+ return ranges::for_each(ranges::begin(__r), ranges::end(__r),
+ std::move(__f), std::move(__proj));
+ }
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
+ typename _Proj = identity>
+ requires indirect_binary_predicate<ranges::equal_to,
+ projected<_Iter, _Proj>, const _Tp*>
+ constexpr _Iter
+ find(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {})
+ {
+ while (__first != __last
+ && !(std::__invoke(__proj, *__first) == __value))
+ ++__first;
+ return __first;
+ }
+
+ template<input_range _Range, typename _Tp, typename _Proj = identity>
+ requires indirect_binary_predicate<ranges::equal_to,
+ projected<iterator_t<_Range>, _Proj>,
+ const _Tp*>
+ constexpr safe_iterator_t<_Range>
+ find(_Range&& __r, const _Tp& __value, _Proj __proj = {})
+ {
+ return ranges::find(ranges::begin(__r), ranges::end(__r), __value,
+ std::move(__proj));
+ }
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+ constexpr _Iter
+ find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ {
+ while (__first != __last
+ && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
+ ++__first;
+ return __first;
+ }
+
+ template<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
+ _Pred>
+ constexpr safe_iterator_t<_Range>
+ find_if(_Range&& __r, _Pred __pred, _Proj __proj = {})
+ {
+ return ranges::find_if(ranges::begin(__r), ranges::end(__r),
+ std::move(__pred), std::move(__proj));
+ }
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+ constexpr _Iter
+ find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ {
+ while (__first != __last
+ && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
+ ++__first;
+ return __first;
+ }
+
+ template<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
+ _Pred>
+ constexpr safe_iterator_t<_Range>
+ find_if_not(_Range&& __r, _Pred __pred, _Proj __proj = {})
+ {
+ return ranges::find_if_not(ranges::begin(__r), ranges::end(__r),
+ std::move(__pred), std::move(__proj));
+ }
+
+} // namespace ranges
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+#endif // concepts
+#endif // C++20
+#endif // _RANGES_ALGO_H
+
diff --git a/libstdc++-v3/include/std/algorithm b/libstdc++-v3/include/std/algorithm
index e3d3402..4b956b8 100644
--- a/libstdc++-v3/include/std/algorithm
+++ b/libstdc++-v3/include/std/algorithm
@@ -60,6 +60,9 @@
#include <utility> // UK-300.
#include <bits/stl_algobase.h>
#include <bits/stl_algo.h>
+#if __cplusplus > 201703L
+# include <bits/ranges_algo.h>
+#endif
#if __cplusplus > 201402L
// Parallel STL algorithms
diff --git a/libstdc++-v3/testsuite/25_algorithms/all_of/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/all_of/constrained.cc
new file mode 100644
index 0000000..fe100bb
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/all_of/constrained.cc
@@ -0,0 +1,88 @@
+// Copyright (C) 2019 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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::test_range;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::forward_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+struct X { int i; };
+
+struct XLess
+{
+ int val;
+ bool operator()(X& x) const { return x.i < val; }
+};
+
+struct ILess
+{
+ int val;
+ bool operator()(int& i) const { return i < val; }
+};
+
+template<typename T>
+struct NotZero
+{
+ bool operator()(T& t) const { return t != 0; }
+};
+
+void
+test01()
+{
+ X x[] = { {2}, {4}, {6}, {8}, {10}, {11} };
+
+ VERIFY( ranges::all_of(x, x+5, XLess{11}) );
+ VERIFY( ranges::all_of(x, x+5, ILess{11}, &X::i) );
+ VERIFY( !ranges::all_of(x, x+6, ILess{11}, &X::i) );
+ VERIFY( !ranges::all_of(x, XLess{11}) );
+ VERIFY( ranges::all_of(x, XLess{12}) );
+ VERIFY( ranges::all_of(x, ILess{12}, &X::i) );
+ VERIFY( !ranges::all_of(x, ILess{11}, &X::i) );
+
+ test_container<X, forward_iterator_wrapper> c(x);
+ VERIFY( ranges::all_of(c, NotZero<int>{}, &X::i) );
+
+ test_range<X, input_iterator_wrapper> r(x);
+ VERIFY( ranges::all_of(r, NotZero<int>{}, &X::i) );
+ VERIFY( ranges::all_of(r, NotZero<X* const>{}, [](X& x) { return &x; }) );
+}
+
+struct Y { int i; int j; };
+
+void
+test02()
+{
+ static constexpr Y y[] = { {1,2}, {2,4}, {3,6} };
+ static_assert(ranges::all_of(y, [](int j) { return j%2 == 0; }, &Y::j));
+ static_assert(ranges::all_of(y, [](const Y& y) { return y.j == y.i * 2; }));
+}
+
+int
+main()
+{
+ test01();
+ test02();
+}
More information about the Libstdc++-cvs
mailing list