[libc++][ranges] Implement ranges::min_element
Implement ranges::min_element
Reviewed By: Quuxplusone, Mordante, #libc
Spies: miscco, libcxx-commits, mgorny
Differential Revision: https://reviews.llvm.org/D117025
NOKEYCHECK=True
GitOrigin-RevId: 3b470d1ce992407df81662c04cf0137850338af6
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index 39f2721..f2a85c7 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -64,6 +64,7 @@
__algorithm/pop_heap.h
__algorithm/prev_permutation.h
__algorithm/push_heap.h
+ __algorithm/ranges_min_element.h
__algorithm/ranges_swap_ranges.h
__algorithm/remove.h
__algorithm/remove_copy.h
diff --git a/include/__algorithm/ranges_min_element.h b/include/__algorithm/ranges_min_element.h
new file mode 100644
index 0000000..2af503d
--- /dev/null
+++ b/include/__algorithm/ranges_min_element.h
@@ -0,0 +1,72 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_MIN_ELEMENT_H
+#define _LIBCPP___ALGORITHM_RANGES_MIN_ELEMENT_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+#ifndef _LIBCPP_HAS_NO_CONCEPTS
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __min_element {
+struct __fn {
+ template <class _Ip, class _Sp, class _Proj, class _Comp>
+ _LIBCPP_HIDE_FROM_ABI static constexpr
+ _Ip __go(_Ip __first, _Sp __last, _Comp& __comp, _Proj& __proj) {
+ if (__first == __last)
+ return __first;
+
+ _Ip __i = __first;
+ while (++__i != __last)
+ if (std::invoke(__comp, std::invoke(__proj, *__i), std::invoke(__proj, *__first)))
+ __first = __i;
+ return __first;
+ }
+
+ template <forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity,
+ indirect_strict_weak_order<projected<_Ip, _Proj>> _Comp = ranges::less>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ _Ip operator()(_Ip __first, _Sp __last, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __go(__first, __last, __comp, __proj);
+ }
+
+ template <forward_range _Rp, class _Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __go(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+ }
+};
+} // namespace __min_element
+
+inline namespace __cpo {
+ inline constexpr auto min_element = __min_element::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_HAS_NO_RANGES
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MIN_ELEMENT_H
diff --git a/include/algorithm b/include/algorithm
index be10e30..b35ad67 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -31,8 +31,13 @@
template <class I, class O1, class O2>
struct in_out_out_result; // since C++20
- template<class I, class O>
- struct in_out_result; // since C++20
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> // since C++20
+ constexpr I min_element(I first, S last, Comp comp = {}, Proj proj = {});
+
+ template<forward_range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> // since C++20
+ constexpr borrowed_iterator_t<R> min_element(R&& r, Comp comp = {}, Proj proj = {});
}
template <class InputIterator, class Predicate>
@@ -749,6 +754,7 @@
#include <__algorithm/pop_heap.h>
#include <__algorithm/prev_permutation.h>
#include <__algorithm/push_heap.h>
+#include <__algorithm/ranges_min_element.h>
#include <__algorithm/ranges_swap_ranges.h>
#include <__algorithm/remove.h>
#include <__algorithm/remove_copy.h>
diff --git a/include/module.modulemap b/include/module.modulemap
index 35e57be..5c21e5d 100644
--- a/include/module.modulemap
+++ b/include/module.modulemap
@@ -285,6 +285,7 @@
module pop_heap { private header "__algorithm/pop_heap.h" }
module prev_permutation { private header "__algorithm/prev_permutation.h" }
module push_heap { private header "__algorithm/push_heap.h" }
+ module ranges_min_element { private header "__algorithm/ranges_min_element.h" }
module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" }
module remove { private header "__algorithm/remove.h" }
module remove_copy { private header "__algorithm/remove_copy.h" }