v3/view/zip_with.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-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
0014 #ifndef RANGES_V3_VIEW_ZIP_WITH_HPP
0015 #define RANGES_V3_VIEW_ZIP_WITH_HPP
0016
0017 #include <limits>
0018 #include <tuple>
0019 #include <type_traits>
0020 #include <utility>
0021
0022 #include <meta/meta.hpp>
0023
0024 #include <range/v3/range_fwd.hpp>
0025
0026 #include <range/v3/functional/bind_back.hpp>
0027 #include <range/v3/functional/indirect.hpp>
0028 #include <range/v3/functional/invoke.hpp>
0029 #include <range/v3/iterator/operations.hpp>
0030 #include <range/v3/range/access.hpp>
0031 #include <range/v3/range/concepts.hpp>
0032 #include <range/v3/range/traits.hpp>
0033 #include <range/v3/utility/common_type.hpp>
0034 #include <range/v3/utility/semiregular_box.hpp>
0035 #include <range/v3/utility/static_const.hpp>
0036 #include <range/v3/utility/tuple_algorithm.hpp>
0037 #include <range/v3/view/all.hpp>
0038 #include <range/v3/view/empty.hpp>
0039 #include <range/v3/view/facade.hpp>
0040
0041 #include <range/v3/detail/prologue.hpp>
0042
0043 namespace ranges
0044 {
0045     /// \cond
0046     namespace detail
0047     {
0048         struct equal_to_
0049         {
0050             template<typename T, typename U>
0051             bool operator()(T const & t, U const & u) const
0052             {
0053                 return static_cast<bool>(t == u);
0054             }
0055         };
0056         RANGES_INLINE_VARIABLE(equal_to_, equal_to)
0057
0058         struct dec_
0059         {
0060             template<typename T>
0061             void operator()(T & t) const
0062             {
0063                 --t;
0064             }
0065         };
0066         RANGES_INLINE_VARIABLE(dec_, dec)
0067
0068         struct inc_
0069         {
0070             template<typename T>
0071             void operator()(T & t) const
0072             {
0073                 ++t;
0074             }
0075         };
0076         RANGES_INLINE_VARIABLE(inc_, inc)
0077
0078         struct _advance_
0079         {
0080             template(typename I, typename Diff)(
0081                 requires input_or_output_iterator<I> AND integer_like_<Diff>)
0082             void operator()(I & i, Diff n) const
0083             {
0084                 advance(i, static_cast<iter_difference_t<I>>(n));
0085             }
0086         };
0087         RANGES_INLINE_VARIABLE(_advance_, advance_)
0088
0089         struct distance_to_
0090         {
0091             template<typename T>
0092             constexpr auto operator()(T const & t, T const & u) const -> decltype(u - t)
0093             {
0094                 return u - t;
0095             }
0096         };
0097         RANGES_INLINE_VARIABLE(distance_to_, distance_to)
0098
0099         struct _min_
0100         {
0101             template<typename T, typename U>
0102             constexpr auto operator()(T const & t, U const & u) const
0103                 -> decltype(true ? t : u)
0104             {
0105                 return u < t ? u : t;
0106             }
0107         };
0108         RANGES_INLINE_VARIABLE(_min_, min_)
0109
0110         struct _max_
0111         {
0112             template<typename T, typename U>
0113             constexpr auto operator()(T const & t, U const & u) const
0114                 -> decltype(true ? u : t)
0115             {
0116                 return u < t ? t : u;
0117             }
0118         };
0119         RANGES_INLINE_VARIABLE(_max_, max_)
0120
0121         template<typename State, typename Value>
0122         using zip_cardinality = std::integral_constant<
0123             cardinality,
0124             State::value >= 0 && Value::value >= 0
0125                 ? min_(State::value, Value::value)
0126                 : State::value >=0 && Value::value == infinite
0127                     ? State::value
0128                     : State::value == infinite && Value::value >= 0
0129                         ? Value::value
0130                         : State::value == finite || Value::value == finite
0131                             ? finite
0132                             : State::value == unknown || Value::value == unknown
0133                                     ? unknown
0134                                     : infinite>;
0135     } // namespace detail
0136     /// \endcond
0137
0138     namespace views
0139     {
0140         // clang-format off
0141         /// \concept zippable_with_
0142         /// \brief The \c zippable_with_ concept
0143         template(typename Fun, typename... Rngs)(
0144         concept (zippable_with_)(Fun, Rngs...),
0145             invocable<Fun&, iterator_t<Rngs>...> AND
0146             invocable<Fun&, copy_tag, iterator_t<Rngs>...> AND
0147             invocable<Fun&, move_tag, iterator_t<Rngs>...>
0148         );
0149         /// \concept zippable_with
0150         /// \brief The \c zippable_with concept
0151         template<typename Fun, typename ...Rngs>
0152         CPP_concept zippable_with =
0153             and_v<input_range<Rngs>...> &&
0154             copy_constructible<Fun> &&
0155             CPP_concept_ref(views::zippable_with_, Fun, Rngs...);
0156         // clang-format on
0157     } // namespace views
0158
0159     /// \addtogroup group-views
0160     /// @{
0161     template<typename Fun, typename... Rngs>
0162     struct iter_zip_with_view
0163       : view_facade<iter_zip_with_view<Fun, Rngs...>,
0164                     meta::fold<meta::list<range_cardinality<Rngs>...>,
0165                                std::integral_constant<cardinality, cardinality::infinite>,
0166                                meta::quote<detail::zip_cardinality>>::value>
0167     {
0168     private:
0169         CPP_assert(sizeof...(Rngs) != 0);
0170         friend range_access;
0171
0172         semiregular_box_t<Fun> fun_;
0173         std::tuple<Rngs...> rngs_;
0174         using difference_type_ = common_type_t<range_difference_t<Rngs>...>;
0175
0176         template<bool Const>
0177         struct cursor;
0178
0179         template<bool Const>
0180         struct sentinel
0181         {
0182         private:
0183             friend struct cursor<Const>;
0184             friend struct sentinel<!Const>;
0185             std::tuple<sentinel_t<meta::const_if_c<Const, Rngs>>...> ends_;
0186
0187         public:
0188             sentinel() = default;
0189             sentinel(detail::ignore_t,
0190                      std::tuple<sentinel_t<meta::const_if_c<Const, Rngs>>...> ends)
0191               : ends_(std::move(ends))
0192             {}
0193             template(bool Other)(
0194                 requires Const AND CPP_NOT(Other)) //
0195             sentinel(sentinel<Other> that)
0196               : ends_(std::move(that.ends_))
0197             {}
0198         };
0199
0200         template<bool Const>
0201         struct cursor
0202         {
0203         private:
0204             friend struct cursor<!Const>;
0205             using fun_ref_ = semiregular_box_ref_or_val_t<Fun, Const>;
0206             fun_ref_ fun_;
0207             std::tuple<iterator_t<meta::const_if_c<Const, Rngs>>...> its_;
0208
0209         public:
0210             using difference_type =
0211                 common_type_t<range_difference_t<meta::const_if_c<Const, Rngs>>...>;
0212             using single_pass = meta::or_c<(
0213                 bool)single_pass_iterator_<iterator_t<meta::const_if_c<Const, Rngs>>>...>;
0214             using value_type = detail::decay_t<invoke_result_t<
0215                 fun_ref_ &, copy_tag, iterator_t<meta::const_if_c<Const, Rngs>>...>>;
0216
0217             cursor() = default;
0218             cursor(fun_ref_ fun,
0219                    std::tuple<iterator_t<meta::const_if_c<Const, Rngs>>...> its)
0220               : fun_(std::move(fun))
0221               , its_(std::move(its))
0222             {}
0223             template(bool Other)(
0224                 requires Const AND CPP_NOT(Other)) //
0225             cursor(cursor<Other> that)
0226               : fun_(std::move(that.fun_))
0227               , its_(std::move(that.its_))
0228             {}
0229             // clang-format off
0230             auto CPP_auto_fun(read)()(const)
0231             (
0232                 return tuple_apply(fun_, its_)
0233             )
0234             // clang-format on
0235             void next()
0236             {
0237                 tuple_for_each(its_, detail::inc);
0238             }
0239             CPP_member
0240             auto equal(cursor const & that) const //
0241                 -> CPP_ret(bool)(
0242                     requires and_v<
0243                         sentinel_for<iterator_t<meta::const_if_c<Const, Rngs>>,
0244                                     iterator_t<meta::const_if_c<Const, Rngs>>>...>)
0245             {
0246                 // By returning true if *any* of the iterators are equal, we allow
0247                 // zipped ranges to be of different lengths, stopping when the first
0248                 // one reaches the last.
0249                 return tuple_foldl(tuple_transform(its_, that.its_, detail::equal_to),
0250                                    false,
0251                                    [](bool a, bool b) { return a || b; });
0252             }
0253             bool equal(sentinel<Const> const & s) const
0254             {
0255                 // By returning true if *any* of the iterators are equal, we allow
0256                 // zipped ranges to be of different lengths, stopping when the first
0257                 // one reaches the last.
0258                 return tuple_foldl(tuple_transform(its_, s.ends_, detail::equal_to),
0259                                    false,
0260                                    [](bool a, bool b) { return a || b; });
0261             }
0262             CPP_member
0263             auto prev() //
0264                 -> CPP_ret(void)(
0265                     requires and_v<bidirectional_range<meta::const_if_c<Const, Rngs>>...>)
0266             {
0267                 tuple_for_each(its_, detail::dec);
0268             }
0269             CPP_member
0270             auto advance(difference_type n) //
0271                 -> CPP_ret(void)(
0272                     requires and_v<random_access_range<meta::const_if_c<Const, Rngs>>...>)
0273             {
0274                 tuple_for_each(its_, bind_back(detail::advance_, n));
0275             }
0276             CPP_member
0277             auto distance_to(cursor const & that) const //
0278                 -> CPP_ret(difference_type)(
0279                     requires and_v<
0280                         sized_sentinel_for<iterator_t<meta::const_if_c<Const, Rngs>>,
0281                                            iterator_t<meta::const_if_c<Const, Rngs>>>...>)
0282             {
0283                 // Return the smallest distance (in magnitude) of any of the iterator
0284                 // pairs. This is to accommodate zippers of sequences of different length.
0285                 if(0 < std::get<0>(that.its_) - std::get<0>(its_))
0286                     return tuple_foldl(
0287                         tuple_transform(its_, that.its_, detail::distance_to),
0288                         (std::numeric_limits<difference_type>::max)(),
0289                         detail::min_);
0290                 else
0291                     return tuple_foldl(
0292                         tuple_transform(its_, that.its_, detail::distance_to),
0293                         (std::numeric_limits<difference_type>::min)(),
0294                         detail::max_);
0295             }
0296             // clang-format off
0297             template<std::size_t... Is>
0298             auto CPP_auto_fun(move_)(meta::index_sequence<Is...>)(const)
0299             (
0300                 return invoke(fun_, move_tag{}, std::get<Is>(its_)...)
0301             )
0302                 // clang-format on
0303                 auto move() const noexcept(noexcept(std::declval<cursor const &>().move_(
0304                     meta::make_index_sequence<sizeof...(Rngs)>{})))
0305                     -> decltype(std::declval<cursor const &>().move_(
0306                         meta::make_index_sequence<sizeof...(Rngs)>{}))
0307             {
0308                 return move_(meta::make_index_sequence<sizeof...(Rngs)>{});
0309             }
0310         };
0311
0312         template<bool Const>
0313         using end_cursor_t =
0314             meta::if_c<concepts::and_v<(bool)common_range<Rngs>...,
0315                                        !(bool)single_pass_iterator_<iterator_t<Rngs>>...>,
0316                        cursor<Const>, sentinel<Const>>;
0317
0318         cursor<false> begin_cursor()
0319         {
0320             return {fun_, tuple_transform(rngs_, ranges::begin)};
0321         }
0322         end_cursor_t<false> end_cursor()
0323         {
0324             return {fun_, tuple_transform(rngs_, ranges::end)};
0325         }
0326         template(bool Const = true)(
0327             requires Const AND and_v<range<Rngs const>...> AND
0328                 views::zippable_with<Fun, meta::if_c<Const, Rngs const>...>)
0329         cursor<Const> begin_cursor() const
0330         {
0331             return {fun_, tuple_transform(rngs_, ranges::begin)};
0332         }
0333         template(bool Const = true)(
0334             requires Const AND and_v<range<Rngs const>...> AND
0335                 views::zippable_with<Fun, meta::if_c<Const, Rngs const>...>)
0336         end_cursor_t<Const> end_cursor() const
0337         {
0338             return {fun_, tuple_transform(rngs_, ranges::end)};
0339         }
0340
0341     public:
0342         iter_zip_with_view() = default;
0343         explicit iter_zip_with_view(Rngs... rngs)
0344           : fun_(Fun{})
0345           , rngs_{std::move(rngs)...}
0346         {}
0347         explicit iter_zip_with_view(Fun fun, Rngs... rngs)
0348           : fun_(std::move(fun))
0349           , rngs_{std::move(rngs)...}
0350         {}
0351         CPP_auto_member
0352         constexpr auto CPP_fun(size)()(const //
0353             requires and_v<sized_range<Rngs const>...>)
0354         {
0355             using size_type = common_type_t<range_size_t<Rngs const>...>;
0356             return range_cardinality<iter_zip_with_view>::value >= 0
0357                        ? size_type{(
0358                              std::size_t)range_cardinality<iter_zip_with_view>::value}
0359                        : tuple_foldl(tuple_transform(rngs_,
0360                                                      [](auto && r) -> size_type {
0361                                                          return ranges::size(r);
0362                                                      }),
0363                                      (std::numeric_limits<size_type>::max)(),
0364                                      detail::min_);
0365         }
0366     };
0367
0368     template<typename Fun, typename... Rngs>
0369     struct zip_with_view : iter_zip_with_view<indirected<Fun>, Rngs...>
0370     {
0371         CPP_assert(sizeof...(Rngs) != 0);
0372
0373         zip_with_view() = default;
0374         explicit zip_with_view(Rngs... rngs)
0375           : iter_zip_with_view<indirected<Fun>, Rngs...>{{Fun{}}, std::move(rngs)...}
0376         {}
0377         explicit zip_with_view(Fun fun, Rngs... rngs)
0378           : iter_zip_with_view<indirected<Fun>, Rngs...>{{std::move(fun)},
0379                                                          std::move(rngs)...}
0380         {}
0381     };
0382
0383 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0384     template(typename Fun, typename... Rng)(
0385         requires copy_constructible<Fun>)
0386     zip_with_view(Fun, Rng &&...)
0387         -> zip_with_view<Fun, views::all_t<Rng>...>;
0388 #endif
0389
0390     namespace views
0391     {
0392         struct iter_zip_with_fn
0393         {
0394             template(typename... Rngs, typename Fun)(
0395                 requires and_v<viewable_range<Rngs>...> AND
0396                     zippable_with<Fun, Rngs...> AND (sizeof...(Rngs) != 0)) //
0397             iter_zip_with_view<Fun, all_t<Rngs>...> //
0398             operator()(Fun fun, Rngs &&... rngs) const
0399             {
0400                 return iter_zip_with_view<Fun, all_t<Rngs>...>{
0401                     std::move(fun), all(static_cast<Rngs &&>(rngs))...};
0402             }
0403
0404             template(typename Fun)(
0405                 requires zippable_with<Fun>) //
0406                 constexpr empty_view<detail::decay_t<invoke_result_t<Fun &>>>
0407                 operator()(Fun) const noexcept
0408             {
0409                 return {};
0410             }
0411         };
0412
0413         /// \relates iter_zip_with_fn
0414         /// \ingroup group-views
0415         RANGES_INLINE_VARIABLE(iter_zip_with_fn, iter_zip_with)
0416
0417         struct zip_with_fn
0418         {
0419             template(typename... Rngs, typename Fun)(
0420                 requires and_v<viewable_range<Rngs>...> AND
0421                     and_v<input_range<Rngs>...> AND copy_constructible<Fun> AND
0422                     invocable<Fun &, range_reference_t<Rngs>...> AND
0423                     (sizeof...(Rngs) != 0)) //
0424             zip_with_view<Fun, all_t<Rngs>...> operator()(Fun fun, Rngs &&... rngs) const
0425             {
0426                 return zip_with_view<Fun, all_t<Rngs>...>{
0427                     std::move(fun), all(static_cast<Rngs &&>(rngs))...};
0428             }
0429
0430             template(typename Fun)(
0431                 requires copy_constructible<Fun> AND invocable<Fun &>) //
0432                 constexpr empty_view<detail::decay_t<invoke_result_t<Fun &>>>
0433                 operator()(Fun) const noexcept
0434             {
0435                 return {};
0436             }
0437         };
0438
0439         /// \relates zip_with_fn
0440         /// \ingroup group-views
0441         RANGES_INLINE_VARIABLE(zip_with_fn, zip_with)
0442     } // namespace views
0443     /// @}
0444 } // namespace ranges
0445
0446 #include <range/v3/detail/epilogue.hpp>
0447
0448 #include <range/v3/detail/satisfy_boost_range.hpp>
0449 RANGES_SATISFY_BOOST_RANGE(::ranges::iter_zip_with_view)
0450 RANGES_SATISFY_BOOST_RANGE(::ranges::zip_with_view)
0451
0452 #endif