[libc++] Implement ranges::{reverse, rotate}_copy
Reviewed By: var-const, #libc
Spies: huixie90, libcxx-commits, mgorny
Differential Revision: https://reviews.llvm.org/D127211
NOKEYCHECK=True
GitOrigin-RevId: 7d426a392f7391007c1b65e8d632e3fff4b07328
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index 7c6a43c..f72c7c6 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -112,6 +112,8 @@
__algorithm/ranges_replace.h
__algorithm/ranges_replace_if.h
__algorithm/ranges_reverse.h
+ __algorithm/ranges_reverse_copy.h
+ __algorithm/ranges_rotate_copy.h
__algorithm/ranges_set_difference.h
__algorithm/ranges_set_intersection.h
__algorithm/ranges_sort.h
diff --git a/include/__algorithm/ranges_reverse_copy.h b/include/__algorithm/ranges_reverse_copy.h
new file mode 100644
index 0000000..e2da9b4
--- /dev/null
+++ b/include/__algorithm/ranges_reverse_copy.h
@@ -0,0 +1,67 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H
+#define _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H
+
+#include <__algorithm/in_out_result.h>
+#include <__algorithm/ranges_copy.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/next.h>
+#include <__iterator/reverse_iterator.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__ranges/subrange.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _InIter, class _OutIter>
+using reverse_copy_result = in_out_result<_InIter, _OutIter>;
+
+namespace __reverse_copy {
+struct __fn {
+
+ template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter>
+ requires indirectly_copyable<_InIter, _OutIter>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ reverse_copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const {
+ return (*this)(subrange(std::move(__first), std::move(__last)), std::move(__result));
+ }
+
+ template <bidirectional_range _Range, weakly_incrementable _OutIter>
+ requires indirectly_copyable<iterator_t<_Range>, _OutIter>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ reverse_copy_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range, _OutIter __result) const {
+ auto __ret = ranges::copy(std::__reverse_range(__range), std::move(__result));
+ return {ranges::next(ranges::begin(__range), ranges::end(__range)), std::move(__ret.out)};
+ }
+
+};
+} // namespace __reverse_copy
+
+inline namespace __cpo {
+ inline constexpr auto reverse_copy = __reverse_copy::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H
diff --git a/include/__algorithm/ranges_rotate_copy.h b/include/__algorithm/ranges_rotate_copy.h
new file mode 100644
index 0000000..d7a282c
--- /dev/null
+++ b/include/__algorithm/ranges_rotate_copy.h
@@ -0,0 +1,68 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H
+#define _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H
+
+#include <__algorithm/in_out_result.h>
+#include <__algorithm/ranges_copy.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/reverse_iterator.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _InIter, class _OutIter>
+using rotate_copy_result = in_out_result<_InIter, _OutIter>;
+
+namespace __rotate_copy {
+struct __fn {
+
+ template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter>
+ requires indirectly_copyable<_InIter, _OutIter>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ rotate_copy_result<_InIter, _OutIter>
+ operator()(_InIter __first, _InIter __middle, _Sent __last, _OutIter __result) const {
+ auto __res1 = ranges::copy(__middle, __last, std::move(__result));
+ auto __res2 = ranges::copy(__first, __middle, std::move(__res1.out));
+ return {std::move(__res1.in), std::move(__res2.out)};
+ }
+
+ template <bidirectional_range _Range, weakly_incrementable _OutIter>
+ requires indirectly_copyable<iterator_t<_Range>, _OutIter>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ rotate_copy_result<borrowed_iterator_t<_Range>, _OutIter>
+ operator()(_Range&& __range, iterator_t<_Range> __middle, _OutIter __result) const {
+ return (*this)(ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__result));
+ }
+
+};
+} // namespace __rotate_copy
+
+inline namespace __cpo {
+ inline constexpr auto rotate_copy = __rotate_copy::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H
diff --git a/include/__iterator/reverse_iterator.h b/include/__iterator/reverse_iterator.h
index eaa0778..a915609 100644
--- a/include/__iterator/reverse_iterator.h
+++ b/include/__iterator/reverse_iterator.h
@@ -15,15 +15,20 @@
#include <__compare/three_way_comparable.h>
#include <__concepts/convertible_to.h>
#include <__config>
+#include <__iterator/advance.h>
#include <__iterator/concepts.h>
#include <__iterator/incrementable_traits.h>
#include <__iterator/iter_move.h>
#include <__iterator/iter_swap.h>
#include <__iterator/iterator.h>
#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
#include <__iterator/prev.h>
#include <__iterator/readable_traits.h>
#include <__memory/addressof.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/subrange.h>
#include <__utility/move.h>
#include <type_traits>
@@ -365,6 +370,16 @@
}
};
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+template <ranges::bidirectional_range _Range>
+_LIBCPP_HIDE_FROM_ABI constexpr ranges::
+ subrange<reverse_iterator<ranges::iterator_t<_Range>>, reverse_iterator<ranges::iterator_t<_Range>>>
+ __reverse_range(_Range&& __range) {
+ auto __first = ranges::begin(__range);
+ return {std::make_reverse_iterator(ranges::next(__first, ranges::end(__range))), std::make_reverse_iterator(__first)};
+}
+#endif
+
_LIBCPP_END_NAMESPACE_STD
#endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H
diff --git a/include/algorithm b/include/algorithm
index 0cc4195..387aebe 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -585,9 +585,9 @@
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R>
ranges::remove_if(R&& r, Pred pred, Proj proj = {}); // since C++20
-
+
template<class I, class O>
- using set_difference_result = in_out_result<I, O>; // since C++20
+ using set_difference_result = in_out_result<I, O>; // since C++20
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
weakly_incrementable O, class Comp = ranges::less,
@@ -623,6 +623,32 @@
set_intersection(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
+ template <class _InIter, class _OutIter>
+ using reverse_copy_result = in_out_result<_InIter, _OutIter>; // since C++20
+
+ template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
+ requires indirectly_copyable<I, O>
+ constexpr ranges::reverse_copy_result<I, O>
+ ranges::reverse_copy(I first, S last, O result); // since C++20
+
+ template<bidirectional_range R, weakly_incrementable O>
+ requires indirectly_copyable<iterator_t<R>, O>
+ constexpr ranges::reverse_copy_result<borrowed_iterator_t<R>, O>
+ ranges::reverse_copy(R&& r, O result); // since C++20
+
+ template <class _InIter, class _OutIter>
+ using rotate_copy_result = in_out_result<_InIter, _OutIter>; // since C++20
+
+ template<forward_iterator I, sentinel_for<I> S, weakly_incrementable O>
+ requires indirectly_copyable<I, O>
+ constexpr ranges::rotate_copy_result<I, O>
+ ranges::rotate_copy(I first, I middle, S last, O result); // since C++20
+
+ template<forward_range R, weakly_incrementable O>
+ requires indirectly_copyable<iterator_t<R>, O>
+ constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
+ ranges::rotate_copy(R&& r, iterator_t<R> middle, O result); // since C++20
+
}
constexpr bool // constexpr in C++20
@@ -1396,6 +1422,8 @@
#include <__algorithm/ranges_replace.h>
#include <__algorithm/ranges_replace_if.h>
#include <__algorithm/ranges_reverse.h>
+#include <__algorithm/ranges_reverse_copy.h>
+#include <__algorithm/ranges_rotate_copy.h>
#include <__algorithm/ranges_set_difference.h>
#include <__algorithm/ranges_set_intersection.h>
#include <__algorithm/ranges_sort.h>
diff --git a/include/module.modulemap.in b/include/module.modulemap.in
index bb10484..0912127 100644
--- a/include/module.modulemap.in
+++ b/include/module.modulemap.in
@@ -351,6 +351,8 @@
module ranges_replace { private header "__algorithm/ranges_replace.h" }
module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" }
module ranges_reverse { private header "__algorithm/ranges_reverse.h" }
+ module ranges_reverse_copy { private header "__algorithm/ranges_reverse_copy.h" }
+ module ranges_rotate_copy { private header "__algorithm/ranges_rotate_copy.h" }
module ranges_set_difference { private header "__algorithm/ranges_set_difference.h" }
module ranges_set_intersection { private header "__algorithm/ranges_set_intersection.h" }
module ranges_sort { private header "__algorithm/ranges_sort.h" }