libcxx/include/__algorithm/ranges_fold.h

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP___ALGORITHM_RANGES_FOLD_H
  11 #define _LIBCPP___ALGORITHM_RANGES_FOLD_H
  12
  13 #include <__concepts/assignable.h>
  14 #include <__concepts/constructible.h>
  15 #include <__concepts/convertible_to.h>
  16 #include <__concepts/invocable.h>
  17 #include <__concepts/movable.h>
  18 #include <__config>
  19 #include <__functional/invoke.h>
  20 #include <__functional/reference_wrapper.h>
  21 #include <__iterator/concepts.h>
  22 #include <__iterator/iterator_traits.h>
  23 #include <__iterator/next.h>
  24 #include <__ranges/access.h>
  25 #include <__ranges/concepts.h>
  26 #include <__ranges/dangling.h>
  27 #include <__type_traits/decay.h>
  28 #include <__type_traits/invoke.h>
  29 #include <__utility/forward.h>
  30 #include <__utility/move.h>
  31
  32 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  33 #  pragma GCC system_header
  34 #endif
  35
  36 _LIBCPP_PUSH_MACROS
  37 #include <__undef_macros>
  38
  39 _LIBCPP_BEGIN_NAMESPACE_STD
  40
  41 #if _LIBCPP_STD_VER >= 23
  42
  43 namespace ranges {
  44 template <class _Ip, class _Tp>
  45 struct in_value_result {
  46   _LIBCPP_NO_UNIQUE_ADDRESS _Ip in;
  47   _LIBCPP_NO_UNIQUE_ADDRESS _Tp value;
  48
  49   template <class _I2, class _T2>
  50     requires convertible_to<const _Ip&, _I2> && convertible_to<const _Tp&, _T2>
  51   _LIBCPP_HIDE_FROM_ABI constexpr operator in_value_result<_I2, _T2>() const& {
  52     return {in, value};
  53   }
  54
  55   template <class _I2, class _T2>
  56     requires convertible_to<_Ip, _I2> && convertible_to<_Tp, _T2>
  57   _LIBCPP_HIDE_FROM_ABI constexpr operator in_value_result<_I2, _T2>() && {
  58     return {std::move(in), std::move(value)};
  59   }
  60 };
  61
  62 template <class _Ip, class _Tp>
  63 using fold_left_with_iter_result = in_value_result<_Ip, _Tp>;
  64
  65 template <class _Fp, class _Tp, class _Ip, class _Rp, class _Up = decay_t<_Rp>>
  66 concept __indirectly_binary_left_foldable_impl =
  67     convertible_to<_Rp, _Up> &&                    //
  68     movable<_Tp> &&                                //
  69     movable<_Up> &&                                //
  70     convertible_to<_Tp, _Up> &&                    //
  71     invocable<_Fp&, _Up, iter_reference_t<_Ip>> && //
  72     assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Ip>>>;
  73
  74 template <class _Fp, class _Tp, class _Ip>
  75 concept __indirectly_binary_left_foldable =
  76     copy_constructible<_Fp> &&                     //
  77     invocable<_Fp&, _Tp, iter_reference_t<_Ip>> && //
  78     __indirectly_binary_left_foldable_impl<_Fp, _Tp, _Ip, invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>;
  79
  80 struct __fold_left_with_iter {
  81   template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp>
  82   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) {
  83     using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>;
  84
  85     if (__first == __last) {
  86       return fold_left_with_iter_result<_Ip, _Up>{std::move(__first), _Up(std::move(__init))};
  87     }
  88
  89     _Up __result = std::invoke(__f, std::move(__init), *__first);
  90     for (++__first; __first != __last; ++__first) {
  91       __result = std::invoke(__f, std::move(__result), *__first);
  92     }
  93
  94     return fold_left_with_iter_result<_Ip, _Up>{std::move(__first), std::move(__result)};
  95   }
  96
  97   template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp>
  98   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) {
  99     auto __result = operator()(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f));
 100
 101     using _Up = decay_t<invoke_result_t<_Fp&, _Tp, range_reference_t<_Rp>>>;
 102     return fold_left_with_iter_result<borrowed_iterator_t<_Rp>, _Up>{std::move(__result.in), std::move(__result.value)};
 103   }
 104 };
 105
 106 inline constexpr auto fold_left_with_iter = __fold_left_with_iter();
 107
 108 struct __fold_left {
 109   template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp>
 110   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) {
 111     return fold_left_with_iter(std::move(__first), std::move(__last), std::move(__init), std::ref(__f)).value;
 112   }
 113
 114   template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp>
 115   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) {
 116     return fold_left_with_iter(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f)).value;
 117   }
 118 };
 119
 120 inline constexpr auto fold_left = __fold_left();
 121 } // namespace ranges
 122
 123 #endif // _LIBCPP_STD_VER >= 23
 124
 125 _LIBCPP_END_NAMESPACE_STD
 126
 127 _LIBCPP_POP_MACROS
 128
 129 #endif // _LIBCPP___ALGORITHM_RANGES_FOLD_H