Feature: walk_tree_to_children

[ioquatix]

I'd like to see something like this included next to TreeWalker::walk_tree:

module ActsAsTree::TreeWalker
    def self.prune
        throw :prune
    end

    def walk_tree_to_children(children, &block)
        marked = Set.new(children.collect(&:self_and_ancestors).flatten)

        walk_tree do |node, level|
            throw :prune unless marked.include?(node)

            yield node, level
        end
    end

    def walk_tree_dfs(where = {}, node = nil, level = 0, &block)
        nodes = (node.nil? ? roots : node.children).where(where)

        nodes.each do |child|
            catch(:prune) do
                yield(child, level)

                walk_tree_dfs(where, child, level + 1, &block)
            end
        end
    end
end

[felixbuenemann]

What are you trying to achieve and what would be common use cases?

[ioquatix]

Given one or more children, walk a partial tree that goes to all children. A use case is when you have, say, a hierarchy of categories and want to build a sub-tree which allows selection of any specific category or it's ancestors.

[felixbuenemann]

Wouldn't this be much more efficient using a path based tree that stores the components of the path as a string or array in the database (like the ancestry gem)?

[ioquatix]

It's O(N) where N is the number of children and their ancestors, so while it could be a bit less memory intensive and possibly more efficient pulling data from the database, it's not that inefficient. Honestly it was a quick hack to get what we wanted.

The main benefit of this approach is that it produces the same order as walk_tree but only with specific paths.

It might make sense to use the ancestry gem but we have a data model that suits the acts_as_tree approach.

[felixbuenemann]

Maybe it makes sense to implement a generic abort mechanism into both walk_tree_bfs and walk_tree_dfs, so it's easier to build more complex behavior on top of it.

[ioquatix]

@felixbuenemann yes as you can see this is part of the proposal.

[felixbuenemann]

I'd be open to a PR that adds an :abort or :stop signal to the bfs/dfs methods. I think the walk_tree_to_children itself is a bit use case specific, because there are many possible variants, eg. walk all trees containing at least one of the specified children. One interesting question is where to catch the signal in the bfs case (around a single node or all nodes of the current level).

[ioquatix]

I'm not sure if this is really logical for BFS.

[felixbuenemann]

I'd be weird to have the feature only work for DFS, don't you think that would be confusing for the users?

[ioquatix]

I didn't say it's not possible to implement something, I'm just not sure that it has the same behaviour or is even useful?