README
¶
Concurrent Tree Operations
There are many tree implementations around. This one supports trees of a fairly simple structure. However, this package makes heavy use of concurrency for all kinds of tree operations. Tree traversal and modification are often performed asynchronously by creating pipelines of concurrent filters. This is done transparently for the client, only reflected by getting a promise as a return type.
For small trees the overhead of concurrency may hurt, from a performance point of view. This package is meant for fairly large DOMs with potentially complex styling information. However, it is generalized enough to be useful in other scenarios as well. And to be honest: I wrote it because concurrency in Go is kind of fun!
DSL
We support a set of search & filter functions on tree nodes. Clients will chain these to perform tasks on nodes (see examples below). You may think of the set of operations to form a small Domain Specific Language (DSL). This is similar in concept to JQuery, but of course with a much smaller set of functions.
Navigation functions:
TopDown(action) // operate on all nodes, starting at the top
Parent() // find parent for all selected nodes
AncestorWith(predicate) // find ancestor with a given predicate
DescendentsWith(predicate) // find descendets with a given predicate
AllDescendents() // find all descendents of selected nodes
Filter functions:
AttributeIs(key, value) // filter for nodes with a given attribute value
SetAttribute(key, value) // set an attribute value for nodes
Filter(userfunc) // apply a user-provided filter function
More operations will follow as I get experience from using the tree in more real life contexts.
Tree Walker
Operations on trees start with creating a Walker for the tree. A typical usage of a Walker looks like this ("FindNodesAndDoSomething()" is a placeholder for a sequence of DSL function calls):
w := NewWalker(rootnode)
futureResult := w.FindNodesAndDoSomething(...).Promise()
nodes, err := futureResult()
Clients always have to call Promise() as the final link of the DSL expression chain, even if they do not expect the expression to return a non-empty set of nodes.
Documentation
¶
Overview ¶
Package tree implements an all-purpose tree type.
There are many tree implementations around. This one supports trees of a fairly simple structure. However, this package makes heavy use of concurrency for all kinds of tree operations. Tree traversal and modification are often performed asynchronously by creating pipelines of concurrent filters. This is done transparently for the client, only reflected by getting a promise (https://en.wikipedia.org/wiki/Futures_and_promises) as a return type.
For small trees the overhead of concurrency may hurt, from a performance point of view. This package is meant for fairly large DOMs with potentially complex styling information. However, it is generalized enough to be useful in other scenarios as well. And to be honest: I wrote it because concurrency in Go is kind of fun!
We support a set of search & filter functions on tree nodes. Clients will chain these to perform tasks on nodes (see examples below). You may think of the set of operations to form a small Domain Specific Language (DSL). This is similar in concept to JQuery, but of course with a much smaller set of functions.
Navigation functions:
Parent() // find parent for all selected nodes AncestorWith(predicate) // find ancestor with a given predicate DescendentsWith(predicate) // find descendets with a given predicate TopDown(action) // traverse all nodes top down (breadth first)
Filter functions:
AttributeIs(key, value) // filter for nodes with a given attribute value SetAttribute(key, value) // set an attribute value for nodes Filter(userfunc) // apply a user-provided filter function
More operations will follow as I get experience from using the tree in more real life contexts.
License ¶
Governed by a 3-Clause BSD license. License file may be found in the root folder of this module.
Copyright © 2017–2022 Norbert Pillmayer <norbert@pillmayer.com>
Index ¶
- Variables
- func AppendFilter[S, T, U comparable](pipe *pipeline[S, T], f *filter[T, U]) *pipeline[S, U]
- type Action
- type Node
- func (node *Node[T]) AddChild(ch *Node[T]) *Node[T]
- func (node *Node[T]) Child(n int) (*Node[T], bool)
- func (node *Node[T]) ChildCount() int
- func (node *Node[T]) Children(omitNilChildren bool) []*Node[T]
- func (node *Node[T]) IndexOfChild(ch *Node[T]) int
- func (node *Node[T]) InsertChildAt(i int, ch *Node[T]) *Node[T]
- func (node *Node[T]) Isolate() *Node[T]
- func (node *Node[T]) Parent() *Node[T]
- func (node *Node[T]) SetChildAt(i int, ch *Node[T]) *Node[T]
- func (node *Node[T]) String() string
- type Predicate
- type Walker
- func (w *Walker[S, T]) AllDescendents() *Walker[S, T]
- func (w *Walker[S, T]) AncestorWith(predicate Predicate[T]) *Walker[S, T]
- func (w *Walker[S, T]) BottomUp(action Action[T]) *Walker[S, T]
- func (w *Walker[S, T]) DescendentsWith(predicate Predicate[T]) *Walker[S, T]
- func (w *Walker[S, T]) Filter(f Predicate[T]) *Walker[S, T]
- func (w *Walker[S, T]) Parent() *Walker[S, T]
- func (w *Walker[S, T]) Promise() func() ([]*Node[T], error)
- func (w *Walker[S, T]) TopDown(action Action[T]) *Walker[S, T]
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrEmptyTree = errors.New("cannot walk empty tree")
ErrEmptyTree is thrown if a Walker is called with an empty tree. Refer to the documentation of NewWalker() for details about this scenario.
var ErrInvalidFilter = errors.New("filter stage is invalid")
ErrInvalidFilter is thrown if a pipeline filter step is defunct.
var ErrNoMoreFiltersAccepted = errors.New("in promise mode; will not accept new filters; use a new walker")
ErrNoMoreFiltersAccepted is thrown if a client already called Promise(), but tried to re-use a walker with another filter.
Functions ¶
func AppendFilter ¶
func AppendFilter[S, T, U comparable](pipe *pipeline[S, T], f *filter[T, U]) *pipeline[S, U]
appendFilter appends a filter to a pipeline, i.e. as the last stage of the pipeline. Connects input- and output-channels appropriately and sets an environment for the filter.
Types ¶
type Action ¶
Action is a function type to operate on tree nodes. Resulting nodes will be pushed to the next pipeline stage, if no error occured.
type Node ¶
type Node[T comparable] struct { Payload T // nodes may carry a payload of arbitrary type Rank uint32 // rank is used for preserving sequence // contains filtered or unexported fields }
Node is the base type our tree is built of.
func CalcRank ¶
CalcRank is an action for bottom-up processing. It Calculates the 'rank'-member for each node, meaning: the number of child-nodes + 1. The root node will hold the number of nodes in the entire tree. Leaf nodes will have a rank of 1.
func NewNode ¶
func NewNode[T comparable](payload T) *Node[T]
NewNode creates a new tree node with a given payload.
func (*Node[T]) AddChild ¶
AddChild inserts a new child node into the tree. The newly inserted node is connected to this node as its parent. It returns the parent node to allow for chaining.
This operation is concurrency-safe.
func (*Node[T]) ChildCount ¶
ChildCount returns the number of children-nodes for a node (concurrency-safe).
func (*Node[T]) Children ¶
Children returns a slice with all children of a node. If omitNilChildren is set, empty children aren't included in the slice
func (*Node[T]) IndexOfChild ¶
IndexOfChild returns the index of a child within the list of children of its parent. ch may not be nil.
func (*Node[T]) InsertChildAt ¶
InsertChildAt inserts a new child node into the tree. The newly inserted node is connected to this node as its parent. The child is set at a given position in relation to other children, shifting children at later positions. It returns the parent node to allow for chaining.
This operation is concurrency-safe.
func (*Node[T]) Isolate ¶
Isolate removes a node from its parent. Isolate returns the isolated node.
func (*Node[T]) SetChildAt ¶
SetChildAt inserts a new child node into the tree. The newly inserted node is connected to this node as its parent. The child is set at a given position in relation to other children, replacing the child at position i if it exists. It returns the parent node to allow for chaining.
This operation is concurrency-safe.
type Predicate ¶
type Predicate[T comparable] func(test *Node[T], node *Node[T]) (match *Node[T], err error)
Predicate is a function type to match against nodes of a tree. Is is used as an argument for various Walker functions to collect a selection of nodes. test is the node under test, node is the input node.
func NodeIsLeaf ¶
func NodeIsLeaf[T comparable]() Predicate[T]
NodeIsLeaf is a predicate to match leafs of a tree.
func Whatever ¶
func Whatever[T comparable]() Predicate[T]
Whatever is a predicate to match anything (see type Predicate). It is useful to match the first node in a given direction.
type Walker ¶
type Walker[S, T comparable] struct { *sync.Mutex // contains filtered or unexported fields }
Walker holds information for operating on trees: finding nodes and doing work on them. Clients usually create a Walker for a (sub-)tree to search for a selection of nodes matching certain criteria, and then perform some operation on this selection.
A Walker will eventually return two client-level values: A slice of tree nodes and the last error occured. Often these fields are accessed through a Promise-object, which represents future values for the two fields.
A typical usage of a Walker looks like this ("FindNodesAndDoSomething()" is a placeholder for a sequence of function calls, see below):
w := NewWalker(node) futureResult := w.FindNodesAndDoSomething(...).Promise() nodes, err := futureResult()
Walker support a set of search & filter functions. Clients will chain some of these to perform tasks on tree nodes (see examples). You may think of the set of operations to form a small Domain Specific Language (DSL), similar in concept to JQuery.
ATTENTION: Clients must call Promise() as the final link of the DSL expression chain, even if they do not expect the expression to return a non-empty set of nodes. Firstly, they need to check for errors, and secondly without fetching the (possibly empty) result set by calling the promise, the Walker may leak goroutines.
func NewWalker ¶
func NewWalker[T comparable](initial *Node[T]) *Walker[T, T]
NewWalker creates a Walker for the initial node of a (sub-)tree. The first subsequent call to a node filter function will have this initial node as input.
If initial is nil, NewWalker will return a nil-Walker, resulting in a NOP-pipeline of operations, resulting in an empty set of nodes and an error (ErrEmptyTree).
func (*Walker[S, T]) AllDescendents ¶
AllDescendents traverses all descendents. The traversal does not include the start node. This is just a wrapper around `w.DescendentsWith(Whatever)`.
If w is nil, AllDescendents will return nil.
func (*Walker[S, T]) AncestorWith ¶
AncestorWith finds an ancestor matching the given predicate. The search does not include the start node.
If w is nil, AncestorWith will return nil.
func (*Walker[S, T]) BottomUp ¶
BottomUp traverses a tree starting at (and including) all the current nodes. Usually clients will select all of the tree's leafs before calling *BottomUp*(). The traversal guarantees that parents are not processed before all of their children.
If the action function returns an error for a node, the parent is processed regardless.
If w is nil, BottomUp will return nil.
func (*Walker[S, T]) DescendentsWith ¶
DescendentsWith finds descendents matching a predicate. The search does not include the start node.
If w is nil, DescendentsWith will return nil.
func (*Walker[S, T]) Filter ¶
Filter calls a client-provided function on each node of the selection. The user function should return the input node if it is accepted and nil otherwise.
If w is nil, Filter will return nil.
func (*Walker[S, T]) Promise ¶
Promise is a future synchronisation point. Walkers may decide to perform certain tasks asynchronously. Clients will not receive the resulting node list immediately, but rather get handed a Promise. Clients will then—any time after they received the Promise—call the Promise (which is of function type) to receive a slice of nodes and a possible error value. Calling the Promise will block until all concurrent operations on the tree nodes have finished, i.e. it is a synchronization point.
Example ¶
// Build a tree:
//
// (root:1)
// (n2:2)----+----(n4:10)
// (n3:10)----+
//
// Then query for nodes with value > 5
//
root, n2, n3, n4 := NewNode(1), NewNode(2), NewNode(10), NewNode(10)
root.AddChild(n2).AddChild(n4)
n2.AddChild(n3)
// Define our ad-hoc predicate
greater5 := func(node *Node[int], n *Node[int]) (*Node[int], error) {
val := node.Payload
if val > 5 { // match nodes with value > 5
return node, nil
}
return nil, nil
}
// Now navigate the tree (concurrently)
future := NewWalker(root).DescendentsWith(greater5).Promise()
// Any time later call the promise ...
nodes, err := future() // will block until walking is finished
if err != nil {
fmt.Print(err)
}
for _, node := range nodes {
fmt.Printf("matching descendent found: (Node %d)\n", node.Payload)
}
Output: matching descendent found: (Node 10) matching descendent found: (Node 10)
func (*Walker[S, T]) TopDown ¶
TopDown traverses a tree starting at (and including) the root node. The traversal guarantees that parents are always processed before their children.
If the action function returns an error for a node, descending the branch below this node is aborted.
If w is nil, TopDown will return nil.
Source Files