libcxx/include/__algorithm/ranges_minmax.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___ALGORITHM_RANGES_MINMAX_H
  10 #define _LIBCPP___ALGORITHM_RANGES_MINMAX_H
  11
  12 #include <__algorithm/min_max_result.h>
  13 #include <__algorithm/minmax_element.h>
  14 #include <__assert>
  15 #include <__concepts/copyable.h>
  16 #include <__concepts/same_as.h>
  17 #include <__config>
  18 #include <__functional/identity.h>
  19 #include <__functional/invoke.h>
  20 #include <__functional/ranges_operations.h>
  21 #include <__iterator/concepts.h>
  22 #include <__iterator/next.h>
  23 #include <__iterator/projected.h>
  24 #include <__ranges/access.h>
  25 #include <__ranges/concepts.h>
  26 #include <__type_traits/is_reference.h>
  27 #include <__type_traits/remove_cvref.h>
  28 #include <__utility/forward.h>
  29 #include <__utility/move.h>
  30 #include <__utility/pair.h>
  31 #include <initializer_list>
  32
  33 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  34 #  pragma GCC system_header
  35 #endif
  36
  37 #if _LIBCPP_STD_VER >= 20
  38
  39 _LIBCPP_PUSH_MACROS
  40 #  include <__undef_macros>
  41
  42 _LIBCPP_BEGIN_NAMESPACE_STD
  43
  44 namespace ranges {
  45 template <class _T1>
  46 using minmax_result = min_max_result<_T1>;
  47
  48 namespace __minmax {
  49 struct __fn {
  50   template <class _Type,
  51             class _Proj                                                      = identity,
  52             indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less>
  53   _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr ranges::minmax_result<const _Type&>
  54   operator()(_LIBCPP_LIFETIMEBOUND const _Type& __a,
  55              _LIBCPP_LIFETIMEBOUND const _Type& __b,
  56              _Comp __comp = {},
  57              _Proj __proj = {}) const {
  58     if (std::invoke(__comp, std::invoke(__proj, __b), std::invoke(__proj, __a)))
  59       return {__b, __a};
  60     return {__a, __b};
  61   }
  62
  63   template <copyable _Type,
  64             class _Proj                                                      = identity,
  65             indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less>
  66   _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr ranges::minmax_result<_Type>
  67   operator()(initializer_list<_Type> __il, _Comp __comp = {}, _Proj __proj = {}) const {
  68     _LIBCPP_ASSERT_UNCATEGORIZED(__il.begin() != __il.end(), "initializer_list has to contain at least one element");
  69     auto __iters = std::__minmax_element_impl(__il.begin(), __il.end(), __comp, __proj);
  70     return ranges::minmax_result<_Type>{*__iters.first, *__iters.second};
  71   }
  72
  73   template <input_range _Range,
  74             class _Proj                                                            = identity,
  75             indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
  76     requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
  77   _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr ranges::minmax_result<range_value_t<_Range>>
  78   operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
  79     auto __first  = ranges::begin(__r);
  80     auto __last   = ranges::end(__r);
  81     using _ValueT = range_value_t<_Range>;
  82
  83     _LIBCPP_ASSERT_UNCATEGORIZED(__first != __last, "range has to contain at least one element");
  84
  85     if constexpr (forward_range<_Range>) {
  86       // Special-case the one element case. Avoid repeatedly initializing objects from the result of an iterator
  87       // dereference when doing so might not be idempotent. The `if constexpr` avoids the extra branch in cases where
  88       // it's not needed.
  89       if constexpr (!same_as<remove_cvref_t<range_reference_t<_Range>>, _ValueT> ||
  90                     is_rvalue_reference_v<range_reference_t<_Range>>) {
  91         if (ranges::next(__first) == __last) {
  92           // During initialization, members are allowed to refer to already initialized members
  93           // (see http://eel.is/c++draft/dcl.init.aggr#6)
  94           minmax_result<_ValueT> __result = {*__first, __result.min};
  95           return __result;
  96         }
  97       }
  98       auto __result = std::__minmax_element_impl(__first, __last, __comp, __proj);
  99       return {*__result.first, *__result.second};
 100     } else {
 101       // input_iterators can't be copied, so the implementation for input_iterators has to store
 102       // the values instead of a pointer to the correct values
 103       auto __less = [&](auto&& __a, auto&& __b) -> bool {
 104         return std::invoke(__comp,
 105                            std::invoke(__proj, std::forward<decltype(__a)>(__a)),
 106                            std::invoke(__proj, std::forward<decltype(__b)>(__b)));
 107       };
 108
 109       // During initialization, members are allowed to refer to already initialized members
 110       // (see http://eel.is/c++draft/dcl.init.aggr#6)
 111       ranges::minmax_result<_ValueT> __result = {*__first, __result.min};
 112       if (__first == __last || ++__first == __last)
 113         return __result;
 114
 115       if (__less(*__first, __result.min))
 116         __result.min = *__first;
 117       else
 118         __result.max = *__first;
 119
 120       while (++__first != __last) {
 121         _ValueT __i = *__first;
 122         if (++__first == __last) {
 123           if (__less(__i, __result.min))
 124             __result.min = __i;
 125           else if (!__less(__i, __result.max))
 126             __result.max = __i;
 127           return __result;
 128         }
 129
 130         if (__less(*__first, __i)) {
 131           if (__less(*__first, __result.min))
 132             __result.min = *__first;
 133           if (!__less(__i, __result.max))
 134             __result.max = std::move(__i);
 135         } else {
 136           if (__less(__i, __result.min))
 137             __result.min = std::move(__i);
 138           if (!__less(*__first, __result.max))
 139             __result.max = *__first;
 140         }
 141       }
 142       return __result;
 143     }
 144   }
 145 };
 146 } // namespace __minmax
 147
 148 inline namespace __cpo {
 149 inline constexpr auto minmax = __minmax::__fn{};
 150 } // namespace __cpo
 151 } // namespace ranges
 152
 153 _LIBCPP_END_NAMESPACE_STD
 154
 155 _LIBCPP_POP_MACROS
 156
 157 #endif // _LIBCPP_STD_VER >= 20
 158
 159 #endif // _LIBCPP___ALGORITHM_RANGES_MINMAX_H