[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add ranges::is_sorted and ranges::is_sorted_until
Patrick Palka
ppalka@gcc.gnu.org
Fri Jan 24 13:34:00 GMT 2020
https://gcc.gnu.org/g:acf5c8125fa648c6a617950924b4982098d0fa42
commit acf5c8125fa648c6a617950924b4982098d0fa42
Author: Patrick Palka <ppalka@redhat.com>
Date: Fri Jan 24 08:34:05 2020 -0500
Add ranges::is_sorted and ranges::is_sorted_until
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 59 ++++++++++++++++++
.../25_algorithms/is_sorted/constrained.cc | 67 ++++++++++++++++++++
.../25_algorithms/is_sorted_until/constrained.cc | 72 ++++++++++++++++++++++
3 files changed, 198 insertions(+)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index a81fd972..1d16b86 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2067,6 +2067,65 @@ namespace ranges
std::move(__comp), std::move(__proj));
}
+ template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_strict_weak_order<projected<_Iter, _Proj>> Comp
+ = ranges::less>
+ constexpr _Iter
+ is_sorted_until(_Iter __first, _Sent __last,
+ Comp __comp = {}, _Proj __proj = {})
+ {
+ if (__first == __last)
+ return __first;
+
+ auto __next = __first;
+ for (++__next; __next != __last; __first = __next, (void)++__next)
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__next),
+ std::__invoke(__proj, *__first)))
+ return __next;
+ return __next;
+ }
+
+ template<forward_range _R, typename _Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<_R>, _Proj>>
+ _Comp = ranges::less>
+ constexpr safe_iterator_t<_R>
+ is_sorted_until(_R&& __r, _Comp __comp = {}, _Proj __proj = {})
+ {
+ return ranges::is_sorted_until(ranges::begin(__r), ranges::end(__r),
+ std::move(__comp), std::move(__proj));
+ }
+
+ template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_strict_weak_order<projected<_Iter, _Proj>>
+ Comp = ranges::less>
+ constexpr bool
+ is_sorted(_Iter __first, _Sent __last, Comp __comp = {}, _Proj __proj = {})
+ {
+ if (__first == __last)
+ return true;
+
+ auto __next = __first;
+ for (++__next; __next != __last; __first = __next, (void)++__next)
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__next),
+ std::__invoke(__proj, *__first)))
+ return false;
+ return true;
+ }
+
+ template<forward_range _Range, typename _Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
+ _Comp = ranges::less>
+ constexpr bool
+ is_sorted(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
+ {
+ return ranges::is_sorted(ranges::begin(__r), ranges::end(__r),
+ std::move(__comp), std::move(__proj));
+ }
+
} // namespace ranges
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_sorted/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/is_sorted/constrained.cc
new file mode 100644
index 0000000..af00afe
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_sorted/constrained.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2020 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::forward_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+ int x[] = {3,4,5,1};
+ test_container<int, forward_iterator_wrapper> cx(x);
+ VERIFY( ranges::is_sorted(cx.begin(), ranges::next(cx.begin(), 3)) );
+ VERIFY( !ranges::is_sorted(cx) );
+ VERIFY( !ranges::is_sorted(cx, ranges::greater{}) );
+ VERIFY( ranges::is_sorted(cx, {}, [] (int a) { return 0; }) );
+}
+
+void
+test02()
+{
+ int x[] = {1,2,3,4,5};
+ test_range<int, forward_iterator_wrapper> rx(x);
+ VERIFY( ranges::is_sorted(rx) );
+ VERIFY( !ranges::is_sorted(ranges::begin(rx),
+ next(ranges::begin(rx), 2),
+ ranges::greater{}) );
+}
+
+constexpr bool
+test03()
+{
+ int x[] = { 1,2 };
+ return (ranges::is_sorted(x)
+ && ranges::is_sorted(x, x) );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ static_assert(test03());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_sorted_until/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/is_sorted_until/constrained.cc
new file mode 100644
index 0000000..a81aa49
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_sorted_until/constrained.cc
@@ -0,0 +1,72 @@
+// Copyright (C) 2020 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::forward_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+ int x[] = {3,4,5,1};
+ test_container<int, forward_iterator_wrapper> cx(x);
+ VERIFY( ranges::is_sorted_until(cx.begin(),
+ ranges::next(cx.begin(), 3))
+ == ranges::next(cx.begin(), 3) );
+ VERIFY( ranges::is_sorted_until(cx) == ranges::next(cx.begin(), 3) );
+ VERIFY( ranges::is_sorted_until(cx, ranges::greater{})
+ == ranges::next(cx.begin(), 1) );
+ VERIFY( ranges::is_sorted_until(cx, {}, [] (int a) { return 0; })
+ == cx.end() );
+}
+
+void
+test02()
+{
+ int x[] = {1,2,3,4,5};
+ test_range<int, forward_iterator_wrapper> rx(x);
+ VERIFY( ranges::is_sorted_until(rx) == ranges::end(rx) );
+ VERIFY( ranges::is_sorted_until(ranges::begin(rx),
+ next(ranges::begin(rx), 2),
+ ranges::greater{})
+ == next(ranges::begin(rx), 1) );
+}
+
+constexpr bool
+test03()
+{
+ int x[] = { 1,2 };
+ return (ranges::is_sorted_until(x) == x+2
+ && ranges::is_sorted_until(x, x) == x );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ static_assert(test03());
+}
More information about the Libstdc++-cvs
mailing list