pyTooling.Tree

A powerful tree data structure for Python.

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

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

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

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

exception pyTooling.Tree.NotInSameTreeError[source]

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

Inheritance

Classes

class pyTooling.Tree.Node(nodeID=None, value=None, parent=None, children=None)[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

Parameters:

nodeID (IDType | None)
value (ValueType | None)
parent (Node)
children (List[Node] | None)

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

Todo

TREE::Node::init Needs documentation.

Parameters:

nodeID (IDType | None)
value (ValueType | None)
parent (Node)
children (List[Node] | None)

Return type:

None

_id: Optional[TypeVar(IDType, bound= Hashable)]: Unique identifier of a node. None if not used.

_value: Optional[TypeVar(ValueType)]: Field to store the node’s value.

_dict: Dict[TypeVar(DictKeyType), TypeVar(DictValueType)]: Dictionary to store key-value-pairs attached to the node.

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

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

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

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

_nodesWithID: Optional[Dict[TypeVar(IDType, bound= Hashable), Node]]: Dictionary of all IDs 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)) – 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]

Todo

TREE::Node::__contains__ Needs documentation.

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

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 get and set the parent (_parent) of a node.

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.

Raises:

TypeError – If parameter parent is not a Node
AlreadyInTreeError – 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.

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.

_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 return 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.

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.

See also

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

AddChildren(children)[source]

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

Parameters:

children (Iterable[Node]) – 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.

See also

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

GetPath()[source]

Todo

TREE::Node::GetPAth Needs documentation.

Return type:: Generator[Node, None, None]

GetAncestors()[source]

Todo

TREE::Node::GetAncestors Needs documentation.

Return type:: Generator[Node, None, None]

GetCommonAncestors(others)[source]

Todo

TREE::Node::GetCommonAncestors Needs documentation.

Return type:: Generator[Node, None, None]
Parameters:: others (Node | Iterable[Node])

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.

class property HasClassAttributes: bool

Check if class has Attributes.

Returns:: True, if the class has Attributes.

class property HasMethodAttributes: bool

Check if class has any method with Attributes.

Returns:: True, if the class has any method with Attributes.

__class_getitem__()

Parameterizes a generic class.

At least, parameterizing a generic class is the main thing this method does. For example, for some generic class Foo, this is called when we do Foo[int] - there, with cls=Foo and params=int.

However, note that this method is also called when defining generic classes in the first place with class Foo[T]: ….

__init_subclass__(): Function to initialize subclasses.

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.

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.

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.

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.

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.

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)) – 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.

__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='o-- ', bypassMarker='| ')[source]

Render the tree as ASCII art.

Parameters:

prefix (str) – A string printed in front of every line, e.g. for indentation. Default: "".
lineend (str) – A string printed at the end of every line. Default: "\n".
nodeMarker (str) – A string printed before every tree node. Default: "o-- ".
bypassMarker (str) – A string printed when there are further nodes in the parent level. Default: "| ".

Return type:

str

Returns:

A rendered tree as multiline string.