v3/algorithm/fold_right.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_RIGHT_HPP
0014 #define RANGES_V3_ALGORITHM_FOLD_RIGHT_HPP
0015
0016 #include <meta/meta.hpp>
0017
0018 #include <range/v3/algorithm/fold_left.hpp>
0019 #include <range/v3/functional/identity.hpp>
0020 #include <range/v3/functional/invoke.hpp>
0021 #include <range/v3/iterator/operations.hpp>
0022 #include <range/v3/range/access.hpp>
0023 #include <range/v3/range/concepts.hpp>
0024 #include <range/v3/utility/optional.hpp>
0025
0026 #include <range/v3/detail/prologue.hpp>
0027
0028 namespace ranges
0029 {
0030     namespace detail
0031     {
0032         template<typename F>
0033         struct flipped
0034         {
0035             F f;
0036
0037             template(class T, class U)(requires invocable<F &, U, T>) //
0038                 invoke_result_t<F &, U, T>
0039                 operator()(T &&, U &&);
0040         };
0041     } // namespace detail
0042
0043     // clang-format off
0044     /// \concept indirectly_binary_right_foldable
0045     /// \brief The \c indirectly_binary_right_foldable concept
0046     template<class F, class T, class I>
0047     CPP_concept indirectly_binary_right_foldable =
0048         indirectly_binary_left_foldable<detail::flipped<F>, T, I>;
0049     // clang-format on
0050
0051     /// \addtogroup group-algorithms
0052     /// @{
0053     RANGES_FUNC_BEGIN(fold_right)
0054
0055         template(typename I, typename S, typename T, typename Op)(
0056             requires sentinel_for<S, I> AND bidirectional_iterator<I> AND
0057                 indirectly_binary_right_foldable<Op, T, I>) //
0058             constexpr auto
0059             RANGES_FUNC(fold_right)(I first, S last, T init, Op op)
0060         {
0061             using U = std::decay_t<invoke_result_t<Op &, iter_reference_t<I>, T>>;
0062
0063             if(first == last)
0064             {
0065                 return U(std::move(init));
0066             }
0067
0068             I tail = next(first, last);
0069             U accum = invoke(op, *--tail, std::move(init));
0070             while(first != tail)
0071             {
0072                 accum = invoke(op, *--tail, std::move(accum));
0073             }
0074             return accum;
0075         }
0076
0077         template(typename Rng, typename T, typename Op)(
0078             requires bidirectional_range<Rng> AND
0079                 indirectly_binary_right_foldable<Op, T, iterator_t<Rng>>) //
0080             constexpr auto
0081             RANGES_FUNC(fold_right)(Rng && rng, T init, Op op)
0082         {
0083             return (*this)(begin(rng), end(rng), std::move(init), std::move(op));
0084         }
0085
0086     RANGES_FUNC_END(fold_right)
0087
0088     RANGES_FUNC_BEGIN(fold_right_last)
0089
0090         template(typename I, typename S, typename Op)(
0091             requires sentinel_for<S, I> AND bidirectional_iterator<I> AND
0092                 indirectly_binary_right_foldable<Op, iter_value_t<I>, I>
0093                     AND constructible_from<iter_value_t<I>, iter_reference_t<I>>) //
0094             constexpr auto
0095             RANGES_FUNC(fold_right_last)(I first, S last, Op op)
0096         {
0097             using U = invoke_result_t<fold_right_fn, I, S, iter_value_t<I>, Op>;
0098             if(first == last)
0099             {
0100                 return optional<U>();
0101             }
0102
0103             I tail = prev(next(first, std::move(last)));
0104             return optional<U>(
0105                 in_place,
0106                 fold_right_fn{}(
0107                     std::move(first), tail, iter_value_t<I>(*tail), std::move(op)));
0108         }
0109
0110         template(typename R, typename Op)(
0111             requires bidirectional_range<R> AND
0112                 indirectly_binary_right_foldable<Op, range_value_t<R>, iterator_t<R>>
0113                     AND constructible_from<range_value_t<R>, range_reference_t<R>>) //
0114             constexpr auto
0115             RANGES_FUNC(fold_right_last)(R && rng, Op op)
0116         {
0117             return (*this)(begin(rng), end(rng), std::move(op));
0118         }
0119
0120     RANGES_FUNC_END(fold_right_last)
0121     /// @}
0122 } // namespace ranges
0123
0124 #include <range/v3/detail/epilogue.hpp>
0125
0126 #endif