Introduction
The API is built on top of a number of simple concepts.
- It is assumed that a tree is not identified with its root. If this happens to be the case in your concrete data structure, implement
ClusterTrees.rootas a no-op. - There are a number of different iterators that a tree can produce. The simplest kind of iterators are nodes. Nodes can be assumed to be small and of fixed type. As a result it is cheap and efficient to store nodes in external containers for additional bookkeeping and traversal.
rootandchildrenproduce nodes.
The core of the tree API consists of the following functions:
ClusterTrees.root — Function.root(tree)Return a proxy for the root of the tree.
ClusterTrees.children — Function.The expression children(tree,node) returns an iterator that will produce a sequence of nodes. These values do not have a lot of meaning by themselves, but can be used in conjunction with the tree object. E.g:
data(tree, node_itr)
children(tree, node_itr)In fact, the node iterators should be regarded as lightweight proxies for the underlying node and their attached data payload. The node objects themselves are of limited use for the client programmer as they are an implementation detail of the specific tree being used.
ClusterTrees.data — Function.data(tree, node)Retrieve the data aka payload associated with the given node.
Based on this simple API, the following algorithms are enabled:
ClusterTrees.depthfirst — Function.Traverse the tree depth first, executing the function f(tree, node, level) at every node. If f returns false, recursion is halted and the next node on the current level is visited.
Missing docstring for ClusterTrees.print_tree. Check Documenter's build log for details.
ClusterTrees.DepthFirstIterator — Type.DepthFirstIterator(tree, node)Creates an iterable that when traversed visits the nodes of the subtree (tree, node) in depthfirst order. Children of a node are visited before that node itself.
To update the tree (this includes both modifying already attached data and inserting new data):
ClusterTrees.update! — Function.update!(f, tree, state, data, target)Algorithm to update or add data to the tree. router! and updater! are user supplied functions:
route!(tree, state, target)Returns the next candidate node until the node for insertion is reaches. Note that this function potentially created new nodes. Arrival at the destination is indicated by returning the same node that was passed as the second argument.
f(tree, node, data)Update the destination node node. Typically, data is added in some sense to the data residing at the desitination node.
Pointer based trees
Tree implementations based on pointers (or indices into Vector-backed memory buffers) are very popular and allow for the efficient implementation of most common traversal and mutation patterns. These trees support an enriched API. We only consider trees with nodes that link back to their parents.
Missing docstring for nextsibling. Check Documenter's build log for details.
Base.parent — Function.parent(A)Return the underlying "parent array”. This parent array of objects of types SubArray, ReshapedArray or LinearAlgebra.Transpose is what was passed as an argument to view, reshape, transpose, etc. during object creation. If the input is not a wrapped object, return the input itself.
Examples
julia> A = [1 2; 3 4]
2×2 Array{Int64,2}:
1 2
3 4
julia> V = view(A, 1:2, :)
2×2 view(::Array{Int64,2}, 1:2, :) with eltype Int64:
1 2
3 4
julia> parent(V)
2×2 Array{Int64,2}:
1 2
3 4Missing docstring for firstchild. Check Documenter's build log for details.