[libc++] Implement ranges::remove{, _if}
Reviewed By: var-const, #libc
Spies: huixie90, sstefan1, libcxx-commits, mgorny
Differential Revision: https://reviews.llvm.org/D128618
NOKEYCHECK=True
GitOrigin-RevId: f8cbe3cdf024865eaa26c14fc8e8f43b3cad455a
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index 621dc31..479c409 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -103,6 +103,8 @@
__algorithm/ranges_move.h
__algorithm/ranges_move_backward.h
__algorithm/ranges_none_of.h
+ __algorithm/ranges_remove.h
+ __algorithm/ranges_remove_if.h
__algorithm/ranges_replace.h
__algorithm/ranges_replace_if.h
__algorithm/ranges_reverse.h
diff --git a/include/__algorithm/ranges_remove.h b/include/__algorithm/ranges_remove.h
new file mode 100644
index 0000000..a6a1200
--- /dev/null
+++ b/include/__algorithm/ranges_remove.h
@@ -0,0 +1,64 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_REMOVE_H
+#define _LIBCPP___ALGORITHM_RANGES_REMOVE_H
+#include <__config>
+
+#include <__algorithm/ranges_remove_if.h>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/permutable.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.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 {
+namespace __remove {
+struct __fn {
+
+ template <permutable _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity>
+ requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ subrange<_Iter> operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const {
+ auto __pred = [&](auto&& __other) { return __value == __other; };
+ return ranges::__remove_if_impl(std::move(__first), std::move(__last), __pred, __proj);
+ }
+
+ template <forward_range _Range, class _Type, class _Proj = identity>
+ requires permutable<iterator_t<_Range>>
+ && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ borrowed_subrange_t<_Range> operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) const {
+ auto __pred = [&](auto&& __other) { return __value == __other; };
+ return ranges::__remove_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj);
+ }
+};
+} // namespace __remove
+
+inline namespace __cpo {
+ inline constexpr auto remove = __remove::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_REMOVE_H
diff --git a/include/__algorithm/ranges_remove_if.h b/include/__algorithm/ranges_remove_if.h
new file mode 100644
index 0000000..d4e382e
--- /dev/null
+++ b/include/__algorithm/ranges_remove_if.h
@@ -0,0 +1,85 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_REMOVE_IF_H
+#define _LIBCPP___ALGORITHM_RANGES_REMOVE_IF_H
+#include <__config>
+
+#include <__algorithm/ranges_find_if.h>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iter_move.h>
+#include <__iterator/permutable.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.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 _Iter, class _Sent, class _Proj, class _Pred>
+_LIBCPP_HIDE_FROM_ABI constexpr
+subrange<_Iter> __remove_if_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) {
+ auto __new_end = ranges::__find_if_impl(__first, __last, __pred, __proj);
+ if (__new_end == __last)
+ return {__new_end, __new_end};
+
+ _Iter __i = __new_end;
+ while (++__i != __last) {
+ if (!std::invoke(__pred, std::invoke(__proj, *__i))) {
+ *__new_end = ranges::iter_move(__i);
+ ++__new_end;
+ }
+ }
+ return {__new_end, __i};
+}
+
+namespace __remove_if {
+struct __fn {
+
+ template <permutable _Iter, sentinel_for<_Iter> _Sent,
+ class _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ subrange<_Iter> operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const {
+ return ranges::__remove_if_impl(std::move(__first), std::move(__last), __pred, __proj);
+ }
+
+ template <forward_range _Range,
+ class _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
+ requires permutable<iterator_t<_Range>>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ borrowed_subrange_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const {
+ return ranges::__remove_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj);
+ }
+
+};
+} // namespace __remove_if
+
+inline namespace __cpo {
+ inline constexpr auto remove_if = __remove_if::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_REMOVE_IF_H
diff --git a/include/algorithm b/include/algorithm
index 76bdf3b..a7236a3 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -511,6 +511,26 @@
merge(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
+ template<permutable I, sentinel_for<I> S, class T, class Proj = identity>
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+ constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {}); // since C++20
+
+ template<forward_range R, class T, class Proj = identity>
+ requires permutable<iterator_t<R>> &&
+ indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+ constexpr borrowed_subrange_t<R>
+ ranges::remove(R&& r, const T& value, Proj proj = {}); // since C++20
+
+ template<permutable I, sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {}); // since C++20
+
+ template<forward_range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires permutable<iterator_t<R>>
+ constexpr borrowed_subrange_t<R>
+ ranges::remove_if(R&& r, Pred pred, Proj proj = {}); // since C++20
+
}
constexpr bool // constexpr in C++20
@@ -1275,6 +1295,8 @@
#include <__algorithm/ranges_move.h>
#include <__algorithm/ranges_move_backward.h>
#include <__algorithm/ranges_none_of.h>
+#include <__algorithm/ranges_remove.h>
+#include <__algorithm/ranges_remove_if.h>
#include <__algorithm/ranges_replace.h>
#include <__algorithm/ranges_replace_if.h>
#include <__algorithm/ranges_reverse.h>
diff --git a/include/module.modulemap.in b/include/module.modulemap.in
index becfec4..b547b50 100644
--- a/include/module.modulemap.in
+++ b/include/module.modulemap.in
@@ -342,6 +342,8 @@
module ranges_move { private header "__algorithm/ranges_move.h" }
module ranges_move_backward { private header "__algorithm/ranges_move_backward.h" }
module ranges_none_of { private header "__algorithm/ranges_none_of.h" }
+ module ranges_remove { private header "__algorithm/ranges_remove.h" }
+ module ranges_remove_if { private header "__algorithm/ranges_remove_if.h" }
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" }