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