Iteration

TreeIterator{T}

An iterator of a tree that implements the AbstractTrees interface. Every TreeIterator is simply a wrapper of an IteratorState which fully determine the iteration state and implement their own alternative protocol using next.

Constructors

All TreeIterators have a one argument constructor T(node) which starts iteration from node.

PreOrderDFS{T,F} <: TreeIterator{T}

Iterator to visit the nodes of a tree, guaranteeing that parents will be visited before their children.

Optionally takes a filter function that determines whether the iterator should continue iterating over a node's children (if it has any) or should consider that node a leaf.

e.g. for the tree

Any[Any[1,2],Any[3,4]]
├─ Any[1,2]
|  ├─ 1
|  └─ 2
└─ Any[3,4]
   ├─ 3
   └─ 4

we will get [[[1, 2], [3, 4]], [1, 2], 1, 2, [3, 4], 3, 4].

PostOrderDFS{T} <: TreeIterator{T}

Iterator to visit the nodes of a tree, guaranteeing that children will be visited before their parents.

e.g. for the tree

Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
   ├─ 2
   └─ 3

we will get [1, 2, 3, [2, 3], [1, [2, 3]]].

Leaves{T} <: TreeIterator{T}

Iterator to visit the leaves of a tree, e.g. for the tree

Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
   ├─ 2
   └─ 3

we will get [1,2,3].

Siblings{T} <: TreeIterator{T}

A TreeIterator which visits the siblings of a node after the provided node.

StatelessBFS{T} <: TreeIterator{T}

Iterator to visit the nodes of a tree, all nodes of a level will be visited before their children

This iterator requires getdescendant to be valid for all nodes in the tree, but the nodes do not necessarily need the IndexedChildren trait.

e.g. for the tree

Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
   ├─ 2
   └─ 3

we will get [[1, [2,3]], 1, [2, 3], 2, 3].

WARNING: This is $O(n^2)$, only use this if you know you need it, as opposed to a more standard statefull approach.

treemap(f, node)

Apply the function f to every node in the tree with root node, where f is a function that returns (v, ch) where v is a new value for the node (i.e. as returned by nodevalue and ch is the new children of the node. f will be called recursively so that all the children returned by f for a parent node will again be called for each child. This means that to maintain the structure of a tree but merely map to new values, one should define f = node -> (g(node), children(node)) for some function g which returns a value for the node.

The nodes of the output tree will all be represented by MapNode objects wrapping the returned values. This is necessary in order to guarantee that the output types can describe any tree topology.

Note that in most common cases tree nodes are of a type which depends on their connectedness and the function f should take this into account. For example the tree [1, [2, 3]] contains integer leaves but two Vector nodes. Therefore, the f in treemap(f, [1, [2,3]]) must be a function that is valid for either Int or Vector. Alternatively, to only operate on leaves do map(𝒻, Leaves(itr)).

It's very easy to write an f that makes treemap stack-overflow. To avoid this, ensure that f eventually termiantes, i.e. that sometimes it returns empty children. For example, if f(n) = (nothing, [0; children(n)]) will stack-overflow because every node will have at least 1 child.

To create a tree with HasNodeType which enables efficient iteration, see StableNode instead.

Examples

julia> t = [1, [2, 3]];

julia> f(n) = n isa AbstractArray ? (nothing, children(n)) : (n+1, children(n))

julia> treemap(f, t)
nothing
├─ 2
└─ nothing
   ├─ 3
   └─ 4

julia> g(n) = isempty(children(n)) ? (nodevalue(n), []) : (nodevalue(n), [0; children(n)])
g (generic function with 1 method)

julia> treemap(g, t)
Any[1, [2, 3]]
├─ 0
├─ 1
└─ [2, 3]
   ├─ 0
   ├─ 2
   └─ 3

IteratorState{T<:TreeCursor}

The state of a TreeIterator object. These are simple wrappers of TreeCursor objects which define a method for next. TreeIterators are in turn simple wrappers of IteratorStates.

Each IteratorState fully determines the current iteration state and therefore the next state can be obtained with next (nothing is returned after the final state is reached).

PreOrderState{T<:TreeCursor} <: IteratorState{T}

The iteration state of a tree iterator which guarantees that parent nodes will be visited before their children, i.e. which descends a tree from root to leaves.

This state implements a next method which accepts a filter function as its first argument, allowing tree branches to be skipped.

See PreOrderDFS.

PostOrderState{T<:TreeCursor} <: IteratorState{T}

The state of a tree iterator which guarantees that parents are visited after their children, i.e. ascends a tree from leaves to root.

See PostOrderDFS.

LeavesState{T<:TreeCursor} <: IteratorState{T}

A IteratorState of an iterator which visits the leaves of a tree.

See Leaves.

SiblingState{T<:TreeCursor} <: IteratorState{T}

A IteratorState of an iterator which visits all of the tree siblings after the current sibling.

See Siblings.

instance(::Type{<:IteratorState}, node; kw...)

Create an instance of the given IteratorState around node node. This is mostly just a constructor for IteratorState except that if node is nothing it will return nothing.

initial(::Type{<:IteratorState}, node)

Obtain the initial IteratorState of the provided type for the node node.

next(s::IteratorState)
next(f, s::IteratorState)

Obtain the next IteratorState after the current one. If s is the final state, this will return nothing.

This provides an alternative iteration protocol which only uses the states directly as opposed to Base.iterate which takes an iterator object and the current state as separate arguments.

statetype(::Type{<:TreeIterator})

Gives the type of IteratorState which is the state of the provided TreeIterator.