Cursors

Tree iteration algorithms rely on TreeCursor objects. A TreeCursor is a wrapper for a tree node which contains all information needed to navigate to other positions within the tree. They themselves are nodes of a tree with the StoredParents and StoredSiblings traits.

To achieve this, tree cursors must be declared on root nodes.

AbstractTrees.TreeCursor — Type
TreeCursor{N,P}

Abstract type for tree cursors which when constructed from a node can be used to navigate the entire tree descended from that node.

Tree cursors satisfy the abstract tree interface with a few additional guarantees:

  • Tree cursors all have the StoredParents and StoredSiblings traits.
  • All functions acting on a cursor which returns a tree node is guaranteed to return another TreeCursor. For example, children, parent and nextsiblin all return a TreeCursor of the same type as the argument.

Tree nodes which define children and have the traits StoredParents and StoredSiblings satisfy the TreeCursor interface, but calling TreeCursor(node) on such a node wraps them in a TrivialCursor to maintain a consistent interface.

Note that any TreeCursor created from a non-cursor node is the root of its own tree, but can be created from any tree node. For example the cursor created from the tree [1,[2,3]] corresponding to node with value [2,3] has no parent and children 2 and 3. This is because a cursor created this way cannot infer the iteration state of its siblings. These constructors are still allowed so that users can run tree algorithms over non-root nodes but they do not permit ascension from the initial node.

Constructors

All TreeCursors possess (at least) the following constructors

  • T(node)
  • T(parent, node)

In the former case the TreeCursor is constructed for the tree of which node is the root.

AbstractTrees.TrivialCursor — Type
TrivialCursor{N,P} <: TreeCursor{N,P}

A TreeCursor which matches the functionality of the underlying node. Tree nodes wrapped by this cursor themselves have most of the functionality required of a TreeCursor, this type exists entirely for the sake of maintaining a fully consistent interface with other TreeCursor objects.

AbstractTrees.ImplicitCursor — Type
ImplicitCursor{N,P,S} <: TreeCursor{N,P}

A TreeCursor which wraps nodes which cannot efficiently access either their parents or siblings directly. This should be thought of as a "worst case scenario" tree cursor. In particular, ImplicitCursors store the child iteration state of type S and for any of ImplicitCursors method to be type-stable it must be possible to infer the child iteration state type, see childstatetype.

AbstractTrees.IndexedCursor — Type
IndexedCursor{N,P} <: TreeCursor{N,P}

A TreeCursor for tree nodes with the IndexedChildren trait but for which parents and siblings are not directly accessible.

This type is very similar to ImplicitCursor except that it is free to assume that the child iteration state is an integer starting at 1 which drastically simplifies type inference and slightly simplifies the iteration methods.

Supporting Types and Functions

AbstractTrees.InitialState — Type
InitialState

A type used for some AbstractTrees.jl iterators to indicate that iteration is in its initial state. Typically this is used for wrapper types to indicate that the iterate function has not yet been called on the wrapped object.

AbstractTrees.parenttype — Function
parenttype(csr::TreeCursor)

The return type of parent(csr). For properly constructed TreeCursors this is guaranteed to be another TreeCursor.