Possible ways to make this `cartesian_product_with_filter` function variadic?-CodePudding

I am trying to implement a function that calculates the Cartesian product of ranges. I know there's views::zip and views::cartesian_product available, and am just deepening my understanding of the use of the range library by writing this function with for_each and yield_if.

While it's quite simple to implement it on a fixed number of ranges like below code, I found no way to apply it to a function that has a arbitrary number of ranges.

I viewed P2374R4 - Motivation and found there's a find_tuples_satisfying which is similar to my code but returns a container.

The expected function signature is:

template <typename Pred, std::ranges::viewable_range... Ranges>
  requires std::predicate<Pred&, std::ranges::range_reference_t<Ranges>...>
[[nodiscard]] constexpr auto cartesian_product_with_filter(Pred pred,
                                                           Ranges&&... ranges)
    -> std::ranges::view auto;

Can anyone figure this out?

Current live demo.

#include <concepts>
#include <ranges>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#include <fmt/core.h>
#include <fmt/ranges.h>
#include <range/v3/all.hpp>

inline constexpr auto for_each{[] [[nodiscard]] (auto&& function) {
  return std::views::transform(std::forward<decltype(function)>(function))
         | std::views::join;
}};

inline constexpr auto yield_if{
    [] [[nodiscard]] (bool should_yield, auto&& value) {
      // std::views::repeat(...);
      return ranges::views::repeat_n(std::forward<decltype(value)>(value),
                                     should_yield ? 1 : 0);
    }};

[[nodiscard]] constexpr auto cartesian_product_with_filter(auto pred,
                                                           auto&& range1,
                                                           auto&& range2,
                                                           auto&& range3)
    -> std::ranges::view auto{
  return range1 | for_each([&pred, &range2, &range3](auto&& value) {
           return range2 | for_each([&pred, &range3, value](auto&& value2) {
                    return range3
                           | for_each([&pred, value, value2](auto&& value3) {
                               return yield_if(
                                   pred(value, value2, value3),
                                   std::tuple{value, value2, value3});
                             });
                  });
         });
}

auto main() -> int {
  std::vector<int> const vec1{1, 2, 3};
  std::vector<std::string> const vec2{"hello", "world"};
  std::vector<double> const vec3{1.2, 3.4, 8.7};
  fmt::print(
      "{}\n",
      fmt::join(cartesian_product_with_filter(
                    [](int value, auto&&, auto&&) { return value % 2 == 1; },
                    vec1, vec2, vec3),
                "\n"));
}

CodePudding user response：

The usual way of writing a variadic funciton like this is to split it up into cases:

the base case (0 or 1 elements, depending on the context)
the recursive case (some number of elements on top of that)

Now, writing cartesian_product_with_filter recursively is a little hard - because of how to propagate the filter part. So instead, I'm just going to walk through cartesian_product itself (since then adding the filter at the end is easy).

Note in advance: this is not a great implementation of cartesian product.

Our base case here is going to be 1 range, since the 0 element case isn't especially interesting (well, it's actually pretty interesting, but let's just skip it). So our structure is going to be something like:

struct CartesianProduct {
    template <typename R>
    [[nodiscard]] constexpr auto operator()(R&& range) const;

    template <typename R, typename... Rs>
    [[nodiscard]] constexpr auto operator()(R&& first, Rs&&... rest) const;
};

inline constexpr auto cartesian_product = CartesianProduct{};

If we're doing a cartesian product of a single range, that's not just outputting the range - we need to wrap it in a tuple. Since cartesian product is always a range of tuples. So that overload is going to be a transform:

template <typename R>
[[nodiscard]] constexpr auto operator()(R&& range) const {
    return FWD(range) | std::views::transform([](auto&& elem){
        return std::tuple<std::ranges::range_reference_t<R>>(FWD(elem));
    });
}

Two things to note here:

we need to make sure we yield the correct tuple type
we need to make sure that we forward the range into transform and that we forward the element into the tuple.

Our recursive case is as follows: if we have at least 2 ranges, then we can peel off the first one and perform what in every other language is called a flat_map: we map every element from the initial range onto every element from the recursive call, and then tuple_cat the result together.

That's:

template <typename R, typename... Rs>
[[nodiscard]] constexpr auto operator()(R&& first, Rs&&... rest) const {
    return (*this)(FWD(first)) | flat_map([&](auto init){
        return (*this)(FWD(rest)...)
            | std::views::transform([=](auto fin){
                return std::tuple_cat(init, fin);
            });
    });
}

Lots to note here.

I'm passing (*this)(FWD(first)) rather than just FWD(first) so that I don't have to repeat the wrap-single-element-in-tuple logic. It's not strictly necessary, but that tuple construction is a mouthful so it's fine.

Then, (*this)(FWD(rest)...) in the body of flat_map is going to turn the rest of our ranges of T, U, V, ... into a range of tuple<T, U, V>, based on recursion.

That gives me two tuples: init (from first) and fin (from rest...), which we now have to tuple_cat together. In both cases, auto is fine because we know it's always a prvalue anyway - these are always ranges of rvalue tuples.

Once we have cartesian_product implemented, adding a filter on top of that is just that: adding a filter on top:

inline constexpr auto cartesian_product_with_filter =
    [] [[nodiscard]] (auto pred, auto&&... ranges){
        return cartesian_product(FWD(ranges)...)
            | std::views::filter([=](auto tuple){
                  return std::apply(pred, tuple);
              });
    };

Note that your original implementation was capturing the predicate by reference, so it dangles. This one copies it. Should ideally move, but the important thing is that the filter owns the predicate, rather than simply referring to it.

Also note that auto tuple is fine here because cartesian_product is a range of prvalue tuples, there's no extra copy in this particular case.

Demo of the complete implementation:

#define FWD(x) static_cast<decltype(x)&&>(x)

inline constexpr auto flat_map = [] [[nodiscard]] (auto&& function) {
  return std::views::transform(FWD(function)) | std::views::join;
};

struct CartesianProduct {
    template <typename R>
    [[nodiscard]] constexpr auto operator()(R&& range) const {
        return FWD(range) | std::views::transform([](auto&& elem){
            return std::tuple<std::ranges::range_reference_t<R>>(FWD(elem));
        });
    }

    template <typename R, typename... Rs>
    [[nodiscard]] constexpr auto operator()(R&& first, Rs&&... rest) const {
        return (*this)(FWD(first)) | flat_map([&](auto init){
            return (*this)(FWD(rest)...)
                | std::views::transform([=](auto fin){
                    return std::tuple_cat(init, fin);
                });
        });
    }
};

inline constexpr auto cartesian_product = CartesianProduct{};

inline constexpr auto cartesian_product_with_filter =
    [] [[nodiscard]] (auto pred, auto&&... ranges){
        return cartesian_product(FWD(ranges)...)
            | std::views::filter([=](auto tuple){
                  return std::apply(pred, tuple);
              });
    };