pyTooling.Tree

A powerful tree data structure for Python.

See also

pyTooling.Graph: → A graph, of which a tree is the acyclic single-rooted case.
pyTooling.Graph.GraphML: → Writing a tree as a GraphML document.
pyTooling.LinkedList: → An object-oriented doubly linked-list data structure.

Exceptions

TreeException: Base exception of all exceptions raised by pyTooling.Tree.
InternalError: The exception is raised when a data structure corruption is detected.
NoSiblingsError: The exception is raised when a node has no parent and thus has no siblings.
AlreadyInTreeError: The exception is raised when the current node and the other node are already in the same tree.
NotInSameTreeError: The exception is raised when the current node and the other node are not in the same tree.

Classes

Node: A tree data structure can be constructed of Node instances.

Exceptions

exception pyTooling.Tree.TreeException[source]

Base exception of all exceptions raised by pyTooling.Tree.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.Tree.InternalError[source]

The exception is raised when a data structure corruption is detected.

Danger

This exception should never be raised.

If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed.
⇒ Bug Tracker at GitHub

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.Tree.NoSiblingsError[source]

The exception is raised when a node has no parent and thus has no siblings.

Hint

A node with no parent is the root node of the tree.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.Tree.AlreadyInTreeError[source]

The exception is raised when the current node and the other node are already in the same tree.

Hint

A tree a an acyclic graph without cross-edges. Thus backward edges and cross edges are permitted.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.Tree.NotInSameTreeError[source]

The exception is raised when the current node and the other node are not in the same tree.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

Classes

class pyTooling.Tree.Node[source]

A tree data structure can be constructed of Node instances.

Therefore, nodes can be connected to parent nodes or a parent node can add child nodes. This allows to construct a tree top-down or bottom-up.

Hint

The top-down construction should be preferred, because it’s slightly faster.

Each tree uses the root node (a.k.a. tree-representative) to store some per-tree data structures. E.g. a list of all IDs in a tree. For easy and quick access to such data structures, each sibling node contains a reference to the root node (_root). In case of adding a tree to an existing tree, such data structures get merged and all added nodes get assigned with new root references. Use the read-only property Root to access the root reference.

The reference to the parent node (_parent) can be access via property Parent. If the property’s setter is used, a node and all its siblings are added to another tree or to a new position in the same tree.

The references to all node’s children is stored in a list (_children). Children, siblings, ancestors, can be accessed via various generators:

GetAncestors() → iterate all ancestors bottom-up.
GetChildren() → iterate all direct children.
GetDescendants() → iterate all descendants.
IterateLevelOrder() → IterateLevelOrder.
IteratePreOrder() → iterate siblings in pre-order.
IteratePostOrder() → iterate siblings in post-order.

Each node can have a unique ID or no ID at all (nodeID=None). The root node is used to store all IDs in a dictionary (_nodesWithID). In case no ID is given, all such ID-less nodes are collected in a single bin and store as a list of nodes. An ID can be modified after the Node was created. Use the read-only property ID to access the ID.

Each node can have a value (_value), which can be given at node creation time, or it can be assigned and/or modified later. Use the property Value to get or set the value.

Moreover, each node can store various key-value-pairs (_dict). Use the dictionary syntax to get and set key-value-pairs.

Inheritance

__init__(nodeID=None, value=None, keyValuePairs=None, parent=None, children=None, format=None)[source]

Todo

TREE::Node::init Needs documentation.

Parameters:

nodeID (Optional[TypeVar(IDType, bound= Hashable)]) – Optional, unique ID of a node within the whole tree data structure.
value (Optional[TypeVar(ValueType)]) – Optional, value of the node.
keyValuePairs (Optional[Mapping[TypeVar(DictKeyType), TypeVar(DictValueType)]]) – Optional, mapping (dictionary) of key-value-pairs.
parent (Node) – Optional, parent node in the tree.
children (Optional[Iterable[Node]]) – Optional, list of child nodes.
format (Optional[Callable[[Node], str]]) – Optional, node formatting function returning a one-line representation for tree-rendering.

Raises:

TypeError – If parameter parent is not an instance of Node.
ValueError – If nodeID already exists in the tree.
TypeError – If parameter children is not iterable.
ValueError – If an element of children is not an instance of Node.

Return type:

None

_id: IDType | None: Unique identifier of a node. None if not used.

_value: ValueType | None: Field to store the node’s value.

_dict: dict[DictKeyType, DictValueType]: Dictionary to store key-value-pairs attached to the node.

_format: Callable[[Node], str] | None: A node formatting function returning a one-line representation for tree-rendering.

_root: Node: Reference to the root of a tree. self if it’s the root node.

_parent: Node | None: Reference to the parent node. None if it’s the root node.

_level: int: Level of the node (distance to the root).

_nodesWithID: dict[IDType, Node] | None: Dictionary of all IDs in the tree. None if it’s not the root node.

_nodesWithoutID: list[Node] | None: List of all nodes without an ID in the tree. None if it’s not the root node.

_children: list[Node]: List of all children

property ID: IDType | None

Read-only property to access the unique ID of a node (_id).

If no ID was given at node construction time, ID return None.

Returns:: Unique ID of a node, if ID was given at node creation time, else None.

property Value: ValueType | None

Property to get and set the value (_value) of a node.

Returns:: The value of a node.

__getitem__(key)[source]

Read a node’s attached attributes (key-value-pairs) by key.

Parameters:: key (TypeVar(DictKeyType)) – The key to look for.
Return type:: TypeVar(DictValueType)
Returns:: The value associated to the given key.

__setitem__(key, value)[source]

Create or update a node’s attached attributes (key-value-pairs) by key.

If a key doesn’t exist yet, a new key-value-pair is created.

Parameters:

key (TypeVar(DictKeyType)) – The key to create or update.
value (TypeVar(DictValueType)) – Optional, the value to associate to the given key.

Return type:

None

__delitem__(key)[source]

Todo

TREE::Node::__delitem__ Needs documentation.

Return type:: None
Parameters:: key (DictKeyType)

__contains__(key)[source]

Check if a key exists in the node’s attached attributes.

Parameters:: key (TypeVar(DictKeyType)) – The key to look for.
Return type:: bool
Returns:: True, if the key exists.

property Root: Node

Read-only property to access the tree’s root node (_root).

Returns:: The root node (representative node) of a tree.

property Parent: Node | None

Property to access the parent (_parent) of a node.

Assigning None detaches the node from its tree, which makes it the root node of the subtree it carries. Assigning a node appends this node - and everything below it - to that node’s tree.

Note

As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and especially to a merge of IDs. As IDs are unique, it might raise an Exception.

Returns:

The parent of a node, or None if the node is a root node.

Raises:

TypeError – If a node that is not a Node is assigned.
AlreadyInTreeError – If the assigned parent is already a child node in this tree.

property Siblings: tuple[Node, ...]

A read-only property to return a tuple of all siblings from the current node.

If the current node is the only child, the tuple is empty.

Siblings are child nodes of the current node’s parent node, without the current node itself.

Returns:: A tuple of all siblings of the current node.
Raises:: NoSiblingsError – If the current node has no parent node and thus no siblings.

property LeftSiblings: tuple[Node, ...]

A read-only property to return a tuple of all siblings left from the current node.

If the current node is the only child, the tuple is empty.

Siblings are child nodes of the current node’s parent node, without the current node itself.

Returns:

A tuple of all siblings left of the current node.

Raises:

NoSiblingsError – If the current node has no parent node and thus no siblings.
InternalError – If the tree’s data structure is corrupted, because this node is not one of its parent’s children.

property RightSiblings: tuple[Node, ...]

A read-only property to return a tuple of all siblings right from the current node.

If the current node is the only child, the tuple is empty.

Siblings are child nodes of the current node’s parent node, without the current node itself.

Returns:

A tuple of all siblings right of the current node.

Raises:

NoSiblingsError – If the current node has no parent node and thus no siblings.
InternalError – If the tree’s data structure is corrupted, because this node is not one of its parent’s children.

_GetPathAsLinkedList()[source]

Compute the path from current node to root node by using a linked list (deque).

Return type:: Deque[Node]
Returns:: Path from node to root node as double-ended queue (deque).

property Path: tuple[Node]

Read-only property to return the path from root node to the node as a tuple of nodes.

Returns:: A tuple of nodes describing the path from root node to the node.

property Level: int

Read-only property to access a node’s level in the tree.

The level is the distance to the root node.

Returns:: The node’s level.

property Size: int

Read-only property to return the size of the tree.

Returns:: Count of all nodes in the tree structure.

property IsRoot: bool

Returns true, if the node is the root node (representative node of the tree).

Returns:: True, if node is the root node.

property IsLeaf: bool

Returns true, if the node is a leaf node (has no children).

Returns:: True, if node has no children.

property HasChildren: bool

Returns true, if the node has child nodes.

Returns:: True, if node has children.

_SetNewRoot(nodesWithIDs, nodesWithoutIDs)[source]

Move the given nodes into this node’s tree.

Parameters:

nodesWithIDs (dict[Node, Node]) – Nodes with an ID, which have to stay unique within the tree.
nodesWithoutIDs (list[Node]) – Nodes without an ID.

Raises:

ValueError – If one of the IDs already exists in this tree.

Return type:

None

AddChild(child)[source]

Add a child node to the current node of the tree.

If child is a subtree, both trees get merged. So all nodes in child get a new _root assigned and all IDs are merged into the node’s root’s ID lists (_nodesWithID).

Parameters:

child (Node) – The child node to be added to the tree.

Raises:

TypeError – If parameter child is not a Node.
AlreadyInTreeError – If parameter child is already a node in the tree.

Return type:

None

See also

Parent: → Set the parent of a node.
AddChildren(): → Add multiple children at once.

Return type:: None
Parameters:: child (Node)

AddChildren(children)[source]

Add multiple children nodes to the current node of the tree.

Parameters:

children (Iterable[Node]) – Optional, the list of children nodes to be added to the tree.

Raises:

TypeError – If parameter children contains an item, which is not a Node.
AlreadyInTreeError – If parameter children contains an item, which is already a node in the tree.

Return type:

None

See also

Parent: → Set the parent of a node.
AddChild(): → Add a child node to the tree.

Return type:: None
Parameters:: children (Iterable[Node])

GetPath()[source]

Compute the path from the root node to this node.

Return type:: Generator[Node, None, None]
Returns:: A generator yielding the nodes from the root down to this node.

GetAncestors()[source]

Iterate the ancestors of this node.

Return type:: Generator[Node, None, None]
Returns:: A generator yielding the parent, its parent, and so on up to the root node.

classmethod GetMethodsWithAttributes(predicate: Nullable[TAttributeFilter[TAttr]] = None) → dict[Callable[..., Any], tuple[Attribute, ...]]

Return the class’ methods that carry at least one matching attribute.

Parameters:

predicate (Nullable[TAttributeFilter[TAttr]]) – Optional, an attribute class, an iterable of attribute classes, or None to accept every attribute.

Return type:

dict[Callable[…, Any], tuple[Attribute, …]]

Returns:

Dictionary of methods and the matching attributes attached to them.

Raises:

ValueError – If an element of parameter ‘predicate’ is not a sub-class of Attribute.
ValueError – If parameter ‘predicate’ is neither an attribute class nor an iterable of those.

__getstate__() → dict[str, Any]

Return the object’s state for pickling, collecting every slot of the class hierarchy.

Return type:: dict[str, Any]
Returns:: Dictionary of slot names and their values.
Raises:: ExtendedTypeError – If a slot was never assigned, so it has no value to serialize.

__setstate__(state: dict[str, Any]) → None

Restore the object’s state from unpickling, requiring exactly the slots of the class hierarchy.

Parameters:: state (dict[str, Any]) – Dictionary of slot names and their values.
Raises:: ExtendedTypeError – If the given state misses a slot or carries an unexpected one.
Return type:: None

GetCommonAncestors(others)[source]

Compute the common ancestors of this node and one or more other nodes.

The nodes’ paths from the root are walked in parallel and yielded as long as they are identical, so the last yielded node is the nearest common ancestor.

Parameters:

others (Union[Node, Iterable[Node]]) – Another node, or an iterable of nodes, to compute the common ancestors with.

Return type:

Generator[Node, None, None]

Returns:

A generator yielding the common ancestors, starting at the root node.

Raises:

NotInSameTreeError – If one of the given nodes is not in the same tree.
NotImplementedError – If more than one other node is given; the common ancestors of a set of nodes are not computed yet.

GetChildren()[source]

A generator to iterate all direct children of the current node.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all children.

See also

GetDescendants(): → Iterate all descendants.
IterateLevelOrder(): → Iterate items level-by-level, which includes the node itself as a first returned node.
IteratePreOrder(): → Iterate items in pre-order, which includes the node itself as a first returned node.
IteratePostOrder(): → Iterate items in post-order, which includes the node itself as a last returned node.

GetSiblings()[source]

A generator to iterate all siblings.

Siblings are child nodes of the current node’s parent node, without the current node itself.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all siblings of the current node.
Raises:: NoSiblingsError – If the current node has no parent node and thus no siblings.

GetLeftSiblings()[source]

A generator to iterate all siblings left from the current node.

Siblings are child nodes of the current node’s parent node, without the current node itself.

Return type:

Generator[Node, None, None]

Returns:

A generator to iterate all siblings left of the current node.

Raises:

NoSiblingsError – If the current node has no parent node and thus no siblings.
InternalError – If the tree’s data structure is corrupted, because this node is not one of its parent’s children.

GetRightSiblings()[source]

A generator to iterate all siblings right from the current node.

Siblings are child nodes of the current node’s parent node, without the current node itself.

Return type:

Generator[Node, None, None]

Returns:

A generator to iterate all siblings right of the current node.

Raises:

NoSiblingsError – If the current node has no parent node and thus no siblings.
InternalError – If the tree’s data structure is corrupted, because this node is not one of its parent’s children.

GetDescendants()[source]

A generator to iterate all descendants of the current node. In contrast to IteratePreOrder and IteratePostOrder it doesn’t include the node itself.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all descendants.

See also

GetChildren(): → Iterate all children, but no grand-children.
IterateLevelOrder(): → Iterate items level-by-level, which includes the node itself as a first returned node.
IteratePreOrder(): → Iterate items in pre-order, which includes the node itself as a first returned node.
IteratePostOrder(): → Iterate items in post-order, which includes the node itself as a last returned node.

GetRelatives()[source]

A generator to iterate all relatives (all siblings and all their descendants) of the current node.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all relatives.

GetLeftRelatives()[source]

A generator to iterate all left relatives (left siblings and all their descendants) of the current node.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all left relatives.

GetRightRelatives()[source]

A generator to iterate all right relatives (right siblings and all their descendants) of the current node.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all right relatives.

IterateLeafs()[source]

A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate leaf-nodes reachable from current node.

IterateLevelOrder()[source]

A generator to iterate all siblings of the current node level-by-level top-down. In contrast to GetDescendants, this includes also the node itself as the first returned node.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all siblings level-by-level.

See also

GetChildren(): → Iterate all children, but no grand-children.
GetDescendants(): → Iterate all descendants.
IteratePreOrder(): → Iterate items in pre-order, which includes the node itself as a first returned node.
IteratePostOrder(): → Iterate items in post-order, which includes the node itself as a last returned node.

IteratePreOrder()[source]

A generator to iterate all siblings of the current node in pre-order. In contrast to GetDescendants, this includes also the node itself as the first returned node.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all siblings in pre-order.

See also

GetChildren(): → Iterate all children, but no grand-children.
GetDescendants(): → Iterate all descendants.
IterateLevelOrder(): → Iterate items level-by-level, which includes the node itself as a first returned node.
IteratePostOrder(): → Iterate items in post-order, which includes the node itself as a last returned node.

IteratePostOrder()[source]

A generator to iterate all siblings of the current node in post-order. In contrast to GetDescendants, this includes also the node itself as the last returned node.

Return type:: Generator[Node, None, None]
Returns:: A generator to iterate all siblings in post-order.

See also

GetChildren(): → Iterate all children, but no grand-children.
GetDescendants(): → Iterate all descendants.
IterateLevelOrder(): → Iterate items level-by-level, which includes the node itself as a first returned node.
IteratePreOrder(): → Iterate items in pre-order, which includes the node itself as a first returned node.

WalkTo(other)[source]

Returns a generator to iterate the path from node to another node.

Parameters:: other (Node) – Node to walk to.
Return type:: Generator[Node, None, None]
Returns:: Generator to iterate the path from node to other node.
Raises:: NotInSameTreeError – If parameter other is not part of the same tree.

GetNodeByID(nodeID)[source]

Lookup a node by its unique ID.

Parameters:

nodeID (TypeVar(IDType, bound= Hashable)) – Optional, ID of a node to lookup in the tree.

Return type:

Node

Returns:

Node for the given ID.

Raises:

ValueError – If parameter nodeID is None.
KeyError – If parameter nodeID is not found in the tree.

Find(predicate)[source]

Search the tree for nodes matching a predicate.

Parameters:: predicate (Callable[[Node], bool]) – Filter function accepting a node and returning a boolean.
Return type:: Generator[Node, None, None]
Returns:: A generator yielding the matching nodes.
Raises:: NotImplementedError – Searching a tree is not implemented yet.

__iter__()[source]

Returns an iterator to iterate all child nodes.

Return type:: Iterator[Node]
Returns:: Children iterator.

__len__()[source]

Returns the number of children, but not including grand-children.

Return type:: int
Returns:: Number of child nodes.

__repr__()[source]

Returns a detailed string representation of the node.

Return type:: str
Returns:: The detailed string representation of the node.

__str__()[source]

Return a string representation of the node.

Order of resolution:

If _value is not None, return the string representation of _value.
If _id is not None, return the string representation of _id.
Else, return __repr__().

Return type:: str
Returns:: The resolved string representation of the node.

Render(prefix='', lineend='\\n', nodeMarker='├─', lastNodeMarker='└─', bypassMarker='│ ')[source]

Render the tree as ASCII art.

Parameters:

prefix (str) – Optional, a string printed in front of every line, e.g. for indentation. Default: "".
lineend (str) – Optional, a string printed at the end of every line. Default: "\n".
nodeMarker (str) – Optional, a string printed before every non-last tree node. Default: "├─".
lastNodeMarker (str) – Optional, a string printed before every last tree node. Default: "└─".
bypassMarker (str) – Optional, a string printed when there are further nodes in the parent level. Default: "│ ".

Return type:

str

Returns:

A rendered tree as multiline string.