Package groupthink :: Module aatree :: Class MonoidTree

Class MonoidTree

Known Subclasses:

AAMonoidTree

A Monoid Annotation Tree is a binary tree whose nodes are each annotated by values from some monoid. The annotation of an internal node is computed by applying the operation to the annotations of its children. The annotation of a leaf node is specified by the user. Every node must either have two children or be a leaf node.

Each leaf node may also be associated with an arbitrary opaque value of the user's choosing. This node and value will remain associated.

Nested Classes

[hide private]

makenode
a factory function that returns nodes of the type required for this tree.

Instance Methods

[hide private]

__init__(self, operation, rootnode)
Let M be the monoid type.

source code

_update(self, node, sentinel=None)
node must be an internal node

source code

_update_add(self, node, sentinel=None)
node must be an internal node

source code

_update_del(self, node, sentinel=None)
node must be an internal node

source code

_split_link(self, node)
Introduce and return a new node (newparent) between node and its parent

source code

addleft(self, new, old)
Add a new leaf node to the left of an old leaf node.

source code

addright(self, new, old)
Add a new leaf node to the right of an old leaf node.

source code

add(self, new, walker)
Add a new leaf node at a position determined by walker.

source code

remove(self, leaf)
Remove a leaf node.

source code

change_annotation(self, leaf, newann)
When changing the annotation of a leaf, it is required to use this method, so that the change may be propagated up through the tree according to the operation.

source code

getnext(self, leaf, skip=None)
Get the next rightward leaf node from leaf.

source code

_build_subtree(self, nodes)

source code

Method Details

[hide private]

init(self, operation, rootnode)
(Constructor)

source code

Let M be the monoid type.

Parameters:

operation (f(M,M) -> M) - a function taking two arguments from the monoid set and returning another element from the monoid set. The monoid operation must obey an associativity criterion; see http://en.wikipedia.org/wiki/Monoid#Definition.
rootnode (makenode) - The root node for the tree. rootnode must have a valid annotation, and its parent and children must be None.

addleft(self, new, old)

source code

Add a new leaf node to the left of an old leaf node. The new node's parent will be assigned to be a new internal node.

Parameters:

new (makenode) - a new node, not yet present in the tree
old (makenode) - A leaf node currently in the tree.

addright(self, new, old)

source code

Add a new leaf node to the right of an old leaf node. The new node's parent will be assigned to be a new internal node.

Parameters:

new (makenode) - a new node, not yet present in the tree
old (makenode) - A leaf node currently in the tree.

add(self, new, walker)

source code

Add a new leaf node at a position determined by walker. Acts as a thin wrapper around aatree.descend and addleft or addright. If the walker descent process returns a position of zero, the new node will be added left of the returned node.

Parameters:

new (makenode) - a new node to add to the tree.
walker (Walker) - A walker that will determine the insertion position

remove(self, leaf)

source code

Remove a leaf node. The leaf will be removed from the tree, and the tree will retain no reference to it.

Parameters:

leaf (makenode) - A leaf node to remove.

change_annotation(self, leaf, newann)

source code

When changing the annotation of a leaf, it is required to use this method, so that the change may be propagated up through the tree according to the operation. Note that no such method is needed for the value of a leaf, because the value is opaque to the tree.

Parameters:

leaf (makenode) - the node whose annotation should be altered
newann (element of the monoid set) - the new annotation which should be associated with leaf

getnext(self, leaf, skip=None)

source code

Get the next rightward leaf node from leaf. Optionally, skip any nodes meeting some criterion.

Parameters:

leaf (makenode) - The leaf node whose next rightward neighbor will be returned
skip (f(makenode)->bool) - An optional function returning True if a given node should be skipped. This function will be called on each internal node during the search, not only on leaf nodes. It will typically implement a criterion on the annotation such that a node will be skipped only if every descendant of that node would also be skipped if considered individually.

Class MonoidTree

__init__(self, operation, rootnode) (Constructor)

addleft(self, new, old)

addright(self, new, old)

add(self, new, walker)

remove(self, leaf)

change_annotation(self, leaf, newann)

getnext(self, leaf, skip=None)

init(self, operation, rootnode)
(Constructor)