CODEWITHSUNDEEP
c++recursionstd-ranges
Amir Kirsh
Amir Kirsh

Reputation: 13842

Solution or alternative for recursive view

We want to implement a tree of items:

       +----------------------+
       |   Item (interface)   |
       +----------------------+
       | + getName(): string  |-----------+
       +----------------------+           |
                    ^                     |
                    |                     |
             +------+------+              |
             |             |              |
   +-------------+      +------------+    |
   | SimpleItem  |      |   Group    |<>--+
   +-------------+      +------------+
                        | +add(Item) |
                        | +all()     |
                        +------------+

The Group::all() function shall return a flattened recursive view of all items including self, as pairs of: {recursion level, item}.

An implementation using ranges::views fails, as the return type of all, depends on the level (a view of a view of items is not the same type as a view of items).

So this code doesn't compile:

auto all(size_t level = 0) const {
    return views::concat(
        views::single(std::pair<size_t, std::shared_ptr<const Item>>(level, shared_from_this())), 
        views::join(items | 
            views::transform([level](const auto& item) {
                auto group = std::dynamic_pointer_cast<Group>(item);
                if (group == nullptr) {
                    return views::single(std::pair{level + 1, item});
                }
                else {
                    return group->all(level + 1);
                }
            })
        )
    );
}

Code: https://compiler-explorer.com/z/fdc8rsWae

Any idea how to make the all function work and return the desired flattened view of all recursive items?

* Note: the code uses ranges-v3, as we use concat, which is added to std::ranges only in C++26. Solutions may rely either on std::ranges or on ranges-v3.

Upvotes: 1

Views: 112

Answers (2)

康桓瑋
康桓瑋

Reputation: 43026

In C++23, you can do this simply via std::generator (instead of depending on concat_view):

using Ret = std::pair<size_t, std::shared_ptr<const Item>>;
auto all(size_t level = 0) const -> std::generator<Ret> {
    co_yield Ret(level, shared_from_this());
    for (auto&& item : items) {
      auto group = std::dynamic_pointer_cast<Group>(item);
      if (group == nullptr)
        co_yield Ret(level + 1, item);
      else
        co_yield std::ranges::elements_of(group->all(level + 1));
    }
}

Demo

Upvotes: 3

Ahmed AEK
Ahmed AEK

Reputation: 18090

A function needs to have a single return type, and every time concat is called recursively the type changes, you need to type-erase the result at some point, like the return of the lambda.

one way to type-erase ranges is ranges::any_view.

using erased_view = ranges::any_view<std::pair<size_t, std::shared_ptr<const Item>>,ranges::category::input>;
auto all(size_t level = 0) const {
    return views::concat(
        views::single(std::pair<size_t, std::shared_ptr<const Item>>(level, shared_from_this())), 
        views::join(items | 
            views::transform([level](const auto& item)->erased_view {
                auto group = std::dynamic_pointer_cast<Group>(item);
                if (group == nullptr) {
                    return views::single(std::pair{level + 1, item});
                }
                else {
                    return group->all(level + 1);
                }
            })
        )
    );
}

godbolt demo

Upvotes: 4

Related Questions