v3/algorithm/fold_left.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2021-present
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012
0013 #ifndef RANGES_V3_ALGORITHM_FOLD_LEFT_HPP
0014 #define RANGES_V3_ALGORITHM_FOLD_LEFT_HPP
0015
0016 #include <meta/meta.hpp>
0017
0018 #include <range/v3/functional/identity.hpp>
0019 #include <range/v3/functional/invoke.hpp>
0020 #include <range/v3/range/access.hpp>
0021 #include <range/v3/range/concepts.hpp>
0022 #include <range/v3/utility/optional.hpp>
0023
0024 #include <range/v3/detail/prologue.hpp>
0025
0026 namespace ranges
0027 {
0028     // clang-format off
0029     /// \concept indirectly_binary_left_foldable_impl
0030     /// \brief The \c indirectly_binary_left_foldable_impl concept
0031     template<class F, class T, class I, class U>
0032     CPP_concept indirectly_binary_left_foldable_impl =
0033         movable<T> &&
0034         movable<U> &&
0035         convertible_to<T, U> &&
0036         invocable<F&, U, iter_reference_t<I>> &&
0037         assignable_from<U&, invoke_result_t<F&, U, iter_reference_t<I>>>;
0038
0039     /// \concept indirectly_binary_left_foldable
0040     /// \brief The \c indirectly_binary_left_foldable concept
0041     template<class F, class T, class I>
0042     CPP_concept indirectly_binary_left_foldable =
0043         copy_constructible<F> &&
0044         indirectly_readable<I> &&
0045         invocable<F&, T, iter_reference_t<I>> &&
0046         convertible_to<invoke_result_t<F&, T, iter_reference_t<I>>,
0047           std::decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>> &&
0048         indirectly_binary_left_foldable_impl<F, T, I, std::decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>>;
0049     // clang-format on
0050
0051     /// \addtogroup group-algorithms
0052     /// @{
0053     RANGES_FUNC_BEGIN(fold_left)
0054
0055         template(typename I, typename S, typename T, typename Op)(
0056             requires sentinel_for<S, I> AND input_iterator<I> AND
0057                 indirectly_binary_left_foldable<Op, T, I>) //
0058             constexpr auto
0059             RANGES_FUNC(fold_left)(I first, S last, T init, Op op)
0060         {
0061             using U = std::decay_t<invoke_result_t<Op &, T, iter_reference_t<I>>>;
0062
0063             if(first == last)
0064             {
0065                 return U(std::move(init));
0066             }
0067
0068             U accum = invoke(op, std::move(init), *first);
0069             for(++first; first != last; ++first)
0070             {
0071                 accum = invoke(op, std::move(accum), *first);
0072             }
0073             return accum;
0074         }
0075
0076         template(typename Rng, typename T, typename Op)(
0077             requires input_range<Rng> AND
0078                 indirectly_binary_left_foldable<Op, T, iterator_t<Rng>>) //
0079             constexpr auto
0080             RANGES_FUNC(fold_left)(Rng && rng, T init, Op op)
0081         {
0082             return (*this)(begin(rng), end(rng), std::move(init), std::move(op));
0083         }
0084
0085     RANGES_FUNC_END(fold_left)
0086
0087     RANGES_FUNC_BEGIN(fold_left_first)
0088
0089         template(typename I, typename S, typename Op)(
0090             requires sentinel_for<S, I> AND input_iterator<I> AND
0091                 indirectly_binary_left_foldable<Op, iter_value_t<I>, I>
0092                     AND constructible_from<iter_value_t<I>, iter_reference_t<I>>) //
0093             constexpr auto
0094             RANGES_FUNC(fold_left_first)(I first, S last, Op op)
0095         {
0096             using U = invoke_result_t<fold_left_fn, I, S, iter_value_t<I>, Op>;
0097             if(first == last)
0098             {
0099                 return optional<U>();
0100             }
0101
0102             iter_value_t<I> init = *first;
0103             ++first;
0104             return optional<U>(
0105                 in_place,
0106                 fold_left_fn{}(std::move(first), std::move(last), std::move(init), op));
0107         }
0108
0109         template(typename R, typename Op)(
0110             requires input_range<R> AND
0111                 indirectly_binary_left_foldable<Op, range_value_t<R>, iterator_t<R>>
0112                     AND constructible_from<range_value_t<R>, range_reference_t<R>>) //
0113             constexpr auto
0114             RANGES_FUNC(fold_left_first)(R && rng, Op op)
0115         {
0116             return (*this)(begin(rng), end(rng), std::move(op));
0117         }
0118
0119     RANGES_FUNC_END(fold_left_first)
0120     /// @}
0121 } // namespace ranges
0122
0123 #include <range/v3/detail/epilogue.hpp>
0124
0125 #endif