[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add ranges::{lower_bound, upper_bound, binary_search, equal_range}
Patrick Palka
ppalka@gcc.gnu.org
Fri Jan 24 16:45:00 GMT 2020
https://gcc.gnu.org/g:dd86330dd844591a757fe13044fab24c217daca4
commit dd86330dd844591a757fe13044fab24c217daca4
Author: Patrick Palka <ppalka@redhat.com>
Date: Fri Jan 24 10:45:34 2020 -0500
Add ranges::{lower_bound,upper_bound,binary_search,equal_range}
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 164 +++++++++++++++++++++
.../25_algorithms/binary_search/constrained.cc | 61 ++++++++
.../25_algorithms/equal_range/constrained.cc | 69 +++++++++
.../25_algorithms/lower_bound/constrained.cc | 66 +++++++++
.../25_algorithms/upper_bound/constrained.cc | 66 +++++++++
5 files changed, 426 insertions(+)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 1d16b86..24b4133 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2126,6 +2126,170 @@ namespace ranges
std::move(__comp), std::move(__proj));
}
+ template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
+ _Comp = ranges::less>
+ constexpr _Iter
+ lower_bound(_Iter __first, _Sent __last,
+ const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
+ {
+ auto __len = ranges::distance(__first, __last);
+
+ while (__len > 0)
+ {
+ auto __half = __len / 2;
+ auto __middle = __first;
+ ranges::advance(__middle, __half);
+ if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value))
+ {
+ __first = __middle;
+ ++__first;
+ __len = __len - __half - 1;
+ }
+ else
+ __len = __half;
+ }
+ return __first;
+ }
+
+ template<forward_range _Range, typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<const _Tp*,
+ projected<iterator_t<_Range>, _Proj>>
+ _Comp = ranges::less>
+ constexpr safe_iterator_t<_Range>
+ lower_bound(_Range&& __r,
+ const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
+ {
+ return ranges::lower_bound(ranges::begin(__r), ranges::end(__r),
+ __value,
+ std::move(__comp), std::move(__proj));
+ }
+
+ template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
+ _Comp = ranges::less>
+ constexpr _Iter
+ upper_bound(_Iter __first, _Sent __last,
+ const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
+ {
+ auto __len = ranges::distance(__first, __last);
+
+ while (__len > 0)
+ {
+ auto __half = __len / 2;
+ auto __middle = __first;
+ ranges::advance(__middle, __half);
+ if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle)))
+ __len = __half;
+ else
+ {
+ __first = __middle;
+ ++__first;
+ __len = __len - __half - 1;
+ }
+ }
+ return __first;
+ }
+
+ template<forward_range _Range, typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<const _Tp*,
+ projected<iterator_t<_Range>, _Proj>>
+ _Comp = ranges::less>
+ constexpr safe_iterator_t<_Range>
+ upper_bound(_Range&& __r,
+ const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
+ {
+ return ranges::upper_bound(ranges::begin(__r), ranges::end(__r),
+ __value,
+ std::move(__comp), std::move(__proj));
+ }
+
+ template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
+ _Comp = ranges::less>
+ constexpr subrange<_Iter>
+ equal_range(_Iter __first, _Sent __last,
+ const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
+ {
+ auto __len = ranges::distance(__first, __last);
+
+ while (__len > 0)
+ {
+ auto __half = __len / 2;
+ auto __middle = __first;
+ ranges::advance(__middle, __half);
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__middle),
+ __value))
+ {
+ __first = __middle;
+ ++__first;
+ __len = __len - __half - 1;
+ }
+ else if (std::__invoke(__comp,
+ __value,
+ std::__invoke(__proj, *__middle)))
+ __len = __half;
+ else
+ {
+ auto __left
+ = ranges::lower_bound(__first, __middle,
+ __value, __comp, __proj);
+ ranges::advance(__first, __len);
+ auto __right
+ = ranges::upper_bound(++__middle, __first,
+ __value, __comp, __proj);
+ return {__left, __right};
+ }
+ }
+ return {__first, __first};
+ }
+
+ template<forward_range _Range,
+ typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<const _Tp*,
+ projected<iterator_t<_Range>, _Proj>>
+ _Comp = ranges::less>
+ constexpr safe_subrange_t<_Range>
+ equal_range(_Range&& __r, const _Tp& __value,
+ _Comp __comp = {}, _Proj __proj = {})
+ {
+ return ranges::equal_range(ranges::begin(__r), ranges::end(__r),
+ __value,
+ std::move(__comp), std::move(__proj));
+ }
+
+ template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
+ _Comp = ranges::less>
+ constexpr bool
+ binary_search(_Iter __first, _Sent __last,
+ const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
+ {
+ auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
+ if (__i == __last)
+ return false;
+ return !std::__invoke(__comp, __value, std::__invoke(__proj, *__i));
+ }
+
+ template<forward_range _Range,
+ typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<const _Tp*,
+ projected<iterator_t<_Range>, _Proj>>
+ _Comp = ranges::less>
+ constexpr bool
+ binary_search(_Range&& __r, const _Tp& __value, _Comp __comp = {},
+ _Proj __proj = {})
+ {
+ return ranges::binary_search(ranges::begin(__r), ranges::end(__r),
+ __value,
+ std::move(__comp), std::move(__proj));
+ }
+
} // namespace ranges
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/binary_search/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/binary_search/constrained.cc
new file mode 100644
index 0000000..42aaa8e
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/binary_search/constrained.cc
@@ -0,0 +1,61 @@
+// 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()
+{
+ float x[] = {1, 2, 3, 4, 5, 5, 6, 7};
+ test_container<float, forward_iterator_wrapper> cx(x);
+ for (int i = 0; i < 7; i++)
+ {
+ VERIFY( ranges::binary_search(cx, i, {}, [] (int a) { return a-1; }) );
+ VERIFY( !ranges::binary_search(cx.begin(), cx.end(), i+0.5) );
+ }
+ VERIFY( !ranges::binary_search(cx, 0) );
+
+ ranges::reverse(x);
+ test_range<float, forward_iterator_wrapper> rx(x);
+ VERIFY( ranges::binary_search(rx, 5, ranges::greater{}) );
+}
+
+constexpr bool
+test02()
+{
+ int x[] = {1, 2, 3};
+ return (ranges::binary_search(x, 3)
+ && !ranges::binary_search(x, x, 3));
+}
+
+int
+main()
+{
+ test01();
+ static_assert(test02());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal_range/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/equal_range/constrained.cc
new file mode 100644
index 0000000..4ddf459
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal_range/constrained.cc
@@ -0,0 +1,69 @@
+// 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[] = {1, 2, 3, 4, 5, 5, 6, 7};
+ for (unsigned i = 0; i < 5; i++)
+ for (unsigned j = 6; j < 8; j++)
+ {
+ test_container<int, forward_iterator_wrapper> cx(x);
+ auto range = ranges::equal_range(std::next(cx.begin(), i),
+ std::next(cx.begin(), j),
+ 4, {}, [] (int a) { return a-1; });
+ VERIFY( range.begin().ptr == x+4 && range.end().ptr == x+6 );
+ }
+
+ ranges::reverse(x);
+ test_range<int, forward_iterator_wrapper> rx(x);
+ auto range = ranges::equal_range(rx, 5, ranges::greater{},
+ [] (int a) { return a+1; });
+ VERIFY( range.begin().ptr == x+4 && range.end().ptr == x+5 );
+}
+
+constexpr bool
+test02()
+{
+ int x[] = {1, 2, 3, 4, 5};
+ auto range1 = ranges::equal_range(x, 6);
+ auto range2 = ranges::equal_range(x, x, 6);
+ auto range3 = ranges::equal_range(x, 1);
+ return (range1.begin() == x+5 && range1.end() == x+5
+ && range2.begin() == x && range2.end() == x
+ && range3.begin() == x && range3.end() == x+1);
+}
+
+int
+main()
+{
+ test01();
+ static_assert(test02());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lower_bound/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/lower_bound/constrained.cc
new file mode 100644
index 0000000..df93f41
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lower_bound/constrained.cc
@@ -0,0 +1,66 @@
+// 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[] = {1, 2, 3, 4, 5, 5, 6, 7};
+ for (unsigned i = 0; i < 5; i++)
+ for (unsigned j = 5; j < 8; j++)
+ {
+ test_container<int, forward_iterator_wrapper> cx(x);
+ auto result = ranges::lower_bound(std::next(cx.begin(), i),
+ std::next(cx.begin(), j),
+ 4, {}, [] (int a) { return a-1; });
+ VERIFY( result.ptr == x+4 );
+ }
+
+ ranges::reverse(x);
+ test_range<int, forward_iterator_wrapper> rx(x);
+ auto result = ranges::lower_bound(rx, 5, ranges::greater{},
+ [] (int a) { return a+1; });
+ VERIFY( result.ptr == x+4 );
+}
+
+constexpr bool
+test02()
+{
+ int x[] = {1, 2, 3, 4, 5};
+ return (ranges::lower_bound(x, 6) == x+5
+ && ranges::lower_bound(x, x, 6) == x
+ && ranges::lower_bound(x, 1) == x);
+}
+
+int
+main()
+{
+ test01();
+ static_assert(test02());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/upper_bound/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/upper_bound/constrained.cc
new file mode 100644
index 0000000..5182431
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/upper_bound/constrained.cc
@@ -0,0 +1,66 @@
+// 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[] = {1, 2, 3, 4, 5, 5, 6, 7};
+ for (unsigned i = 0; i < 5; i++)
+ for (unsigned j = 6; j < 8; j++)
+ {
+ test_container<int, forward_iterator_wrapper> cx(x);
+ auto result = ranges::upper_bound(std::next(cx.begin(), i),
+ std::next(cx.begin(), j),
+ 4, {}, [] (int a) { return a-1; });
+ VERIFY( result.ptr == x+6 );
+ }
+
+ ranges::reverse(x);
+ test_range<int, forward_iterator_wrapper> rx(x);
+ auto result = ranges::upper_bound(rx, 5, ranges::greater{},
+ [] (int a) { return a+1; });
+ VERIFY( result.ptr == x+5 );
+}
+
+constexpr bool
+test02()
+{
+ int x[] = {1, 2, 3, 4, 5};
+ return (ranges::upper_bound(x, 6) == x+5
+ && ranges::upper_bound(x, x, 6) == x
+ && ranges::upper_bound(x, 1) == x+1);
+}
+
+int
+main()
+{
+ test01();
+ static_assert(test02());
+}
More information about the Libstdc++-cvs
mailing list