I'm not nessecerily trying it iterate over the children of a node. Rather I
have defined a series of types that facilitate traversing a tree in various
ways for my Phylogenetics.jl package, for example by depth first:
type TraverserCore
Start::PhyNode
Behind::Stack
History::Array{PhyNode, 1}
Current::PhyNode
end
type DepthFirstTraverser <: TreeTraverser
Ahead::Stack
Core::TraverserCore
function DepthFirstTraverser(tree::Phylogeny)
x = new(Stack(PhyNode), TraverserCore(tree.Root, Stack(PhyNode), PhyNode
[], tree.Root))
for i in x.Core.Current.Children
push!(x.Ahead, i)
end
return x
end
end
It has methods like:
function next!(x::DepthFirstTraverser)
push!(x.Core.Behind, x.Core.Current)
x.Core.Current = pop!(x.Ahead)
for i in x.Core.Current.Children
push!(x.Ahead, i)
end
end
function getCurrent(x::TreeTraverser)
return x.Core.Current
end
function hasReachedEnd(x::TreeTraverser)
length(x.Ahead) > 0 ? false : true
end
Which seem similar to start, next, and done. I'd use them in a loop like so
again from Phylogenetics.jl:
while true
show(getCurrent(traverser))
if hasReachedEnd(traverser)
break
end
next!(traverser)
end
But I'd like to make it behave more like an iterator - so be able to define
the iterator methods for it so I can do something like
for i = DepthFirstTraverser(myTree)
# BLARGH
end
And it will be translated accordingly. I think this is doable by defining
the three methods, making use of the types the method already has.
The idea is to have a load of types that allow the user to code iteration
over the tree in any possible way, easily, providing there is a
TreeTraverser type for it.
Best,
Ben.
On Sunday, July 27, 2014 2:14:38 PM UTC+1, Tim Holy wrote:
>
> for x in obj
> # blah
> end
>
> will iterate if you've defined start, next, and done functions for which
> the
> first argument has typeof(obj). In your case you'd presumably use a node
> as
> obj, and the traversal would be recursively over all children of that
> node.
>
> If you want a specific tree example, check out ProfileView.jl/src/tree.jl.
>
> Best,
> --Tim
>
> On Sunday, July 27, 2014 05:13:39 AM Ben Ward wrote:
> > Hi,
> >
> > I've been writing a type for recursive tree structures, and several
> types
> > that traverse that tree in various manners like breadth first or depth
> > first. They have their own methods for getting the current tree node,
> > moving to the next node, whether an end has been reached and so on. The
> > contain fields for the nodes several steps ahead, those past etc. I
> > wondered if I might make it so as these types might easier be used in
> loops
> > by giving them the iterator protocol methods? I've not seen how to
> define
> > custom operators, is it as simple as defining start next and done? How
> is
> > the current value gotten? I guess its returned by next().
> >
> > Thanks,
> > Ben.
>
>
