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/desugars_to.h>
  27 #include <__type_traits/is_integral.h>
  28 #include <__type_traits/is_reference.h>
  29 #include <__type_traits/is_trivially_copyable.h>
  30 #include <__type_traits/remove_cvref.h>
  31 #include <__utility/forward.h>
  32 #include <__utility/move.h>
  33 #include <__utility/pair.h>
  34 #include <initializer_list>
  35
  36 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  37 #  pragma GCC system_header
  38 #endif
  39
  40 #if _LIBCPP_STD_VER >= 20
  41
  42 _LIBCPP_PUSH_MACROS
  43 #  include <__undef_macros>
  44
  45 _LIBCPP_BEGIN_NAMESPACE_STD
  46
  47 namespace ranges {
  48 template <class _T1>
  49 using minmax_result = min_max_result<_T1>;
  50
  51 struct __minmax {
  52   template <class _Type,
  53             class _Proj                                                      = identity,
  54             indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less>
  55   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr ranges::minmax_result<const _Type&>
  56   operator()(_LIBCPP_LIFETIMEBOUND const _Type& __a,
  57              _LIBCPP_LIFETIMEBOUND const _Type& __b,
  58              _Comp __comp = {},
  59              _Proj __proj = {}) const {
  60     if (std::invoke(__comp, std::invoke(__proj, __b), std::invoke(__proj, __a)))
  61       return {__b, __a};
  62     return {__a, __b};
  63   }
  64
  65   template <copyable _Type,
  66             class _Proj                                                      = identity,
  67             indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less>
  68   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr ranges::minmax_result<_Type>
  69   operator()(initializer_list<_Type> __il, _Comp __comp = {}, _Proj __proj = {}) const {
  70     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
  71         __il.begin() != __il.end(), "initializer_list has to contain at least one element");
  72     auto __iters = std::__minmax_element_impl(__il.begin(), __il.end(), __comp, __proj);
  73     return ranges::minmax_result<_Type>{*__iters.first, *__iters.second};
  74   }
  75
  76   template <input_range _Range,
  77             class _Proj                                                            = identity,
  78             indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
  79     requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
  80   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr ranges::minmax_result<range_value_t<_Range>>
  81   operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
  82     auto __first  = ranges::begin(__r);
  83     auto __last   = ranges::end(__r);
  84     using _ValueT = range_value_t<_Range>;
  85
  86     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__first != __last, "range has to contain at least one element");
  87
  88     // This optimiation is not in minmax_element because clang doesn't see through the pointers and as a result doesn't
  89     // vectorize the code.
  90     if constexpr (contiguous_range<_Range> && is_integral_v<_ValueT> &&
  91                   __is_cheap_to_copy<_ValueT> & __is_identity<_Proj>::value &&
  92                   __desugars_to_v<__less_tag, _Comp, _ValueT, _ValueT>) {
  93       minmax_result<_ValueT> __result = {__r[0], __r[0]};
  94       for (auto __e : __r) {
  95         if (__e < __result.min)
  96           __result.min = __e;
  97         if (__result.max < __e)
  98           __result.max = __e;
  99       }
 100       return __result;
 101     } else if constexpr (forward_range<_Range>) {
 102       // Special-case the one element case. Avoid repeatedly initializing objects from the result of an iterator
 103       // dereference when doing so might not be idempotent. The `if constexpr` avoids the extra branch in cases where
 104       // it's not needed.
 105       if constexpr (!same_as<remove_cvref_t<range_reference_t<_Range>>, _ValueT> ||
 106                     is_rvalue_reference_v<range_reference_t<_Range>>) {
 107         if (ranges::next(__first) == __last) {
 108           // During initialization, members are allowed to refer to already initialized members
 109           // (see http://eel.is/c++draft/dcl.init.aggr#6)
 110           minmax_result<_ValueT> __result = {*__first, __result.min};
 111           return __result;
 112         }
 113       }
 114       auto __result = std::__minmax_element_impl(__first, __last, __comp, __proj);
 115       return {*__result.first, *__result.second};
 116     } else {
 117       // input_iterators can't be copied, so the implementation for input_iterators has to store
 118       // the values instead of a pointer to the correct values
 119       auto __less = [&](auto&& __a, auto&& __b) -> bool {
 120         return std::invoke(__comp,
 121                            std::invoke(__proj, std::forward<decltype(__a)>(__a)),
 122                            std::invoke(__proj, std::forward<decltype(__b)>(__b)));
 123       };
 124
 125       // During initialization, members are allowed to refer to already initialized members
 126       // (see http://eel.is/c++draft/dcl.init.aggr#6)
 127       ranges::minmax_result<_ValueT> __result = {*__first, __result.min};
 128       if (__first == __last || ++__first == __last)
 129         return __result;
 130
 131       if (__less(*__first, __result.min))
 132         __result.min = *__first;
 133       else
 134         __result.max = *__first;
 135
 136       while (++__first != __last) {
 137         _ValueT __i = *__first;
 138         if (++__first == __last) {
 139           if (__less(__i, __result.min))
 140             __result.min = __i;
 141           else if (!__less(__i, __result.max))
 142             __result.max = __i;
 143           return __result;
 144         }
 145
 146         if (__less(*__first, __i)) {
 147           if (__less(*__first, __result.min))
 148             __result.min = *__first;
 149           if (!__less(__i, __result.max))
 150             __result.max = std::move(__i);
 151         } else {
 152           if (__less(__i, __result.min))
 153             __result.min = std::move(__i);
 154           if (!__less(*__first, __result.max))
 155             __result.max = *__first;
 156         }
 157       }
 158       return __result;
 159     }
 160   }
 161 };
 162
 163 inline namespace __cpo {
 164 inline constexpr auto minmax = __minmax{};
 165 } // namespace __cpo
 166 } // namespace ranges
 167
 168 _LIBCPP_END_NAMESPACE_STD
 169
 170 _LIBCPP_POP_MACROS
 171
 172 #endif // _LIBCPP_STD_VER >= 20
 173
 174 #endif // _LIBCPP___ALGORITHM_RANGES_MINMAX_H