Recursive Iterators (or some other way to do this)

General Usage
, ,
1

Hi, I am experimenting with some custom iterators, and I’m wondering why this particular construction does not work as I would think (it returns nothing):

struct TreeNodeLeaves{T <: TreeNode}
    node::T
end

function iterate(leaves::TreeNodeLeaves, state::Tuple{Vector{BranchNode}, Vector{Int}})
    function transverse(substate::Tuple{Vector{BranchNode}, Vector{Int}})
        if length(substate[1]) == 0
            return nothing
        end
        current = pop!(substate[1])
    
        if length(current.children) == 0
            return ((current.data, copy(substate[2])), substate)
        end
        for index = eachindex(current.children)
            nextnode = current.children[index]
            push!(substate[1], nextnode)
            push!(substate[2], index)
            transverse(substate)
            pop!(substate[2])
        end
    end
    return transverse(state)
end

function iterate(leaves::TreeNodeLeaves)
    nodes = Vector{BranchNode}()
    indices = Int[]
    
    push!(nodes, leaves.node)

    return iterate(leaves, (nodes, indices))
end

The expected output is to return something like ("a", [2, 2, 1, 2, 2]) from each iteration (where the integer array is the path to get to that node) until I’ve traversed the entire tree. If iterators are not the way to go with this, is there something else I can do such that I can iterate over something and get this type of return value with each iteration?

2

Hi

This is difficult to debug without the rest of the code to make it a minimal working example (missing definitions of TreeNode, BranchNode and TreeNodeLeaves as well as example input).

However if I assume you are calling:
iterate(leaves)
which then calls
iterate(leaves, ( Vector{BranchNode}(), Int[]) )
that in turn calls
transverse( ( Vector{BranchNode}(), Int[]) )
which finds a length(substate[1]) which is Vector{BranchNode}() is 0, and returns the nothing

I only partially understand your logic based on a quick scan.
My first guess was your check is the wrong way around (should check for not equal to 0), however that doesn’t make sense. Even removing the if length substate[1] check also wouldn’t work, since you need to check that there is stuff to pop.

I think on this line there might be a problem:
push!(substate[2], index)
I think you need to also be pushing a copy of the path (substate[2]) to get to current, not just the last step, but I might be wrong.

But I think the real problem is the setup in the first call, which needs to be calling with the root element of the tree already populated in nodes, instead of an empty vector.

3

yeah - I wasn’t able to really get it working with an iterator, but using channels I get my desired output:

    code = Int[]
    function traverse(node::TreeNode, c::Channel)
        if node == nullnode
            return
        end
        if length(node.children) == 0
            put!(c, (node.data, copy(code)))    # notice that we should copy the current state of code
        end
        for index = eachindex(node.children)
            child = node.children[index]
            push!(code, index)
            traverse(child, c)
            pop!(code)
        end
    end
    return Channel((channel_arg) -> traverse(root, channel_arg))
end

I was trying to update this little package: https://github.com/tanmaykm/Word2Vec.jl to work in 1.0/1.1, but the author was using Tasks (with produce/consume etc) which is obviously long deprecated.