130 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___ALGORITHM_RANGES_FOLD_H11#define _LIBCPP___ALGORITHM_RANGES_FOLD_H12 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_header34#endif35 36_LIBCPP_PUSH_MACROS37#include <__undef_macros>38 39_LIBCPP_BEGIN_NAMESPACE_STD40 41#if _LIBCPP_STD_VER >= 2342 43namespace ranges {44template <class _Ip, class _Tp>45struct 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 62template <class _Ip, class _Tp>63using fold_left_with_iter_result = in_value_result<_Ip, _Tp>;64 65template <class _Fp, class _Tp, class _Ip, class _Rp, class _Up = decay_t<_Rp>>66concept __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 74template <class _Fp, class _Tp, class _Ip>75concept __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 80struct __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 106inline constexpr auto fold_left_with_iter = __fold_left_with_iter();107 108struct __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 120inline constexpr auto fold_left = __fold_left();121} // namespace ranges122 123#endif // _LIBCPP_STD_VER >= 23124 125_LIBCPP_END_NAMESPACE_STD126 127_LIBCPP_POP_MACROS128 129#endif // _LIBCPP___ALGORITHM_RANGES_FOLD_H130