libcxx/include/__cxx03/__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 <__cxx03/__algorithm/min_max_result.h>
  13 #include <__cxx03/__algorithm/minmax_element.h>
  14 #include <__cxx03/__assert>
  15 #include <__cxx03/__concepts/copyable.h>
  16 #include <__cxx03/__concepts/same_as.h>
  17 #include <__cxx03/__config>
  18 #include <__cxx03/__functional/identity.h>
  19 #include <__cxx03/__functional/invoke.h>
  20 #include <__cxx03/__functional/ranges_operations.h>
  21 #include <__cxx03/__iterator/concepts.h>
  22 #include <__cxx03/__iterator/next.h>
  23 #include <__cxx03/__iterator/projected.h>
  24 #include <__cxx03/__ranges/access.h>
  25 #include <__cxx03/__ranges/concepts.h>
  26 #include <__cxx03/__type_traits/desugars_to.h>
  27 #include <__cxx03/__type_traits/is_reference.h>
  28 #include <__cxx03/__type_traits/is_trivially_copyable.h>
  29 #include <__cxx03/__type_traits/remove_cvref.h>
  30 #include <__cxx03/__utility/forward.h>
  31 #include <__cxx03/__utility/move.h>
  32 #include <__cxx03/__utility/pair.h>
  33 #include <__cxx03/initializer_list>
  34
  35 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  36 #  pragma GCC system_header
  37 #endif
  38
  39 #if _LIBCPP_STD_VER >= 20
  40
  41 _LIBCPP_PUSH_MACROS
  42 #  include <__cxx03/__undef_macros>
  43
  44 _LIBCPP_BEGIN_NAMESPACE_STD
  45
  46 namespace ranges {
  47 template <class _T1>
  48 using minmax_result = min_max_result<_T1>;
  49
  50 namespace __minmax {
  51 struct __fn {
  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 } // namespace __minmax
 163
 164 inline namespace __cpo {
 165 inline constexpr auto minmax = __minmax::__fn{};
 166 } // namespace __cpo
 167 } // namespace ranges
 168
 169 _LIBCPP_END_NAMESPACE_STD
 170
 171 _LIBCPP_POP_MACROS
 172
 173 #endif // _LIBCPP_STD_VER >= 20
 174
 175 #endif // _LIBCPP___ALGORITHM_RANGES_MINMAX_H