Coverage for pyTooling/Tree/__init__.py: 93%
419 statements
« prev ^ index » next coverage.py v7.17.0, created at 2026-10-25 12:33 +0000
1# ==================================================================================================================== #
2# _____ _ _ _____ #
3# _ __ _ |_ _|__ ___ | (_)_ __ __ _|_ _| __ ___ ___ #
4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` | | || '__/ _ \/ _ \ #
5# | |_) | |_| || | (_) | (_) | | | | | | (_| |_| || | | __/ __/ #
6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)_||_| \___|\___| #
7# |_| |___/ |___/ #
8# ==================================================================================================================== #
9# Authors: #
10# Patrick Lehmann #
11# #
12# License: #
13# ==================================================================================================================== #
14# Copyright 2017-2026 Patrick Lehmann - Bötzingen, Germany #
15# #
16# Licensed under the Apache License, Version 2.0 (the "License"); #
17# you may not use this file except in compliance with the License. #
18# You may obtain a copy of the License at #
19# #
20# http://www.apache.org/licenses/LICENSE-2.0 #
21# #
22# Unless required by applicable law or agreed to in writing, software #
23# distributed under the License is distributed on an "AS IS" BASIS, #
24# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. #
25# See the License for the specific language governing permissions and #
26# limitations under the License. #
27# #
28# SPDX-License-Identifier: Apache-2.0 #
29# ==================================================================================================================== #
30#
31"""
32A powerful tree data structure for Python.
34.. seealso::
36 :mod:`pyTooling.Graph`
37 |rarr| A graph, of which a tree is the acyclic single-rooted case.
38 :mod:`pyTooling.Graph.GraphML`
39 |rarr| Writing a tree as a GraphML document.
40 :mod:`pyTooling.LinkedList`
41 |rarr| An object-oriented doubly linked-list data structure.
42"""
43from __future__ import annotations
45from collections import deque
46from typing import TypeVar, Generic, Deque, Union, Optional as Nullable, Any, Callable, Generator, \
47 Iterable, Mapping, Hashable
49from pyTooling.Decorators import export, readonly
50from pyTooling.MetaClasses import ExtendedType
51from pyTooling.Exceptions import AlreadyInHierarchyError, NotInSameHierarchyError, ToolingException, \
52 NotAChildError as CommonNotAChildError
53from pyTooling.Common import getFullyQualifiedName
54from pyTooling.DataModel import KeyValuePairsMixin, Predicate
57IDType = TypeVar("IDType", bound=Hashable)
58"""A type variable for a tree's ID."""
60ValueType = TypeVar("ValueType")
61"""A type variable for a tree's value."""
64@export
65class TreeError(ToolingException):
66 """Base exception of all exceptions raised by :mod:`pyTooling.Tree`."""
69@export
70class InternalError(TreeError):
71 """
72 The exception is raised when a data structure corruption is detected.
74 .. danger::
76 This exception should never be raised.
78 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|
79 :gh:`⇒ Bug Tracker at GitHub <pyTooling/pyTooling/issues>`
80 """
83@export
84class NoSiblingsError(TreeError):
85 """
86 The exception is raised when a node has no parent and thus has no siblings.
88 .. hint::
90 A node with no parent is the root node of the tree.
91 """
94@export
95class AlreadyInTreeError(TreeError, AlreadyInHierarchyError):
96 """
97 The exception is raised when the current node and the other node are already in the same tree.
99 .. hint::
101 A tree a an acyclic graph without cross-edges. Thus backward edges and cross edges are permitted.
102 """
104 _otherNode: Nullable[Node] #: Other node, which is in the same tree already.
106 def __init__(self, message: str, /, *, otherNode: Nullable[Node] = None) -> None:
107 """
108 Initializes the exception with the other node, which is in the same tree already.
110 :param message: The exception's message.
111 :param otherNode: Optional, the other node, which is in the same tree already.
112 """
113 super().__init__(message)
114 self._otherNode = otherNode
116 @readonly
117 def OtherNode(self) -> Nullable[Node]:
118 """
119 Read-only property to access the other node, which is in the same tree already (:attr:`_otherNode`).
121 :returns: The other node, or ``None`` if it wasn't recorded.
122 """
123 return self._otherNode
126@export
127class NotInSameTreeError(TreeError, NotInSameHierarchyError):
128 """The exception is raised when the current node and the other node are not in the same tree."""
130 _otherNode: Nullable[Node] #: Other node, which is in another tree.
132 def __init__(self, message: str, /, *, otherNode: Nullable[Node] = None) -> None:
133 """
134 Initializes the exception with the other node, which is in another tree.
136 :param message: The exception's message.
137 :param otherNode: Optional, the other node, which is in another tree.
138 """
139 super().__init__(message)
140 self._otherNode = otherNode
142 @readonly
143 def OtherNode(self) -> Nullable[Node]:
144 """
145 Read-only property to access the other node, which is in another tree (:attr:`_otherNode`).
147 :returns: The other node, or ``None`` if it wasn't recorded.
148 """
149 return self._otherNode
152@export
153class NotAChildError(TreeError, CommonNotAChildError):
154 """
155 The exception is raised when a node is not a direct child of the current node.
157 .. hint::
159 A grandchild is in the same tree, but it's a child of another node.
160 """
162 _child: Nullable[Node] #: Node that isn't a direct child of the current node.
164 def __init__(self, message: str, /, *, child: Nullable[Node] = None) -> None:
165 """
166 Initializes the exception with the node that isn't a direct child of the current node.
168 :param message: The exception's message.
169 :param child: Optional, the node that isn't a direct child of the current node.
170 """
171 super().__init__(message)
172 self._child = child
174 @readonly
175 def Child(self) -> Nullable[Node]:
176 """
177 Read-only property to access the node that isn't a direct child of the current node (:attr:`_child`).
179 :returns: The node, or ``None`` if it wasn't recorded.
180 """
181 return self._child
184@export
185class Node(KeyValuePairsMixin, Generic[IDType, ValueType], metaclass=ExtendedType, slots=True):
186 """
187 A **tree** data structure can be constructed of ``Node`` instances.
189 Therefore, nodes can be connected to parent nodes or a parent node can add child nodes. This allows to construct a
190 tree top-down or bottom-up.
192 .. hint::
194 The top-down construction should be preferred, because it's slightly faster.
196 Each tree uses the **root** node (a.k.a. tree-representative) to store some per-tree data structures. E.g. a list of
197 all IDs in a tree. For easy and quick access to such data structures, each sibling node contains a reference to the
198 root node (:attr:`_root`). In case of adding a tree to an existing tree, such data structures get merged and all added
199 nodes get assigned with new root references. Use the read-only property :attr:`Root` to access the root reference.
201 The reference to the parent node (:attr:`_parent`) can be access via property :attr:`Parent`. If the property's setter
202 is used, a node and all its siblings are added to another tree or to a new position in the same tree.
204 The references to all node's children is stored in a list (:attr:`_children`). Children, siblings, ancestors, can be
205 accessed via various generators:
207 * :meth:`GetAncestors` |rarr| iterate all ancestors bottom-up.
208 * :meth:`GetChildren` |rarr| iterate all direct children.
209 * :meth:`GetDescendants` |rarr| iterate all descendants.
210 * :meth:`IterateLevelOrder` |rarr| IterateLevelOrder.
211 * :meth:`IteratePreOrder` |rarr| iterate siblings in pre-order.
212 * :meth:`IteratePostOrder` |rarr| iterate siblings in post-order.
214 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
215 dictionary (:attr:`_nodesWithID`). In case no ID is given, all such ID-less nodes are collected in a single bin and store as a
216 list of nodes. An ID can be modified after the Node was created. Use the read-only property :attr:`ID` to access
217 the ID.
219 Each node can have a **value** (:attr:`_value`), which can be given at node creation time, or it can be assigned and/or
220 modified later. Use the property :attr:`Value` to get or set the value.
222 Moreover, each node can store arbitrary key-value-pairs (:class:`~pyTooling.DataModel.KeyValuePairsMixin`). Use the
223 dictionary syntax to get and set key-value-pairs: ``in``, :pycode:`len(node)` and iterating a node address the
224 key-value-pairs, not the children.
225 """
227 _id: Nullable[IDType] #: Unique identifier of a node. ``None`` if not used.
228 _nodesWithID: Nullable[dict[IDType, Node]] #: Dictionary of all IDs in the tree. ``None`` if it's not the root node.
229 _nodesWithoutID: Nullable[list[Node]] #: List of all nodes without an ID in the tree. ``None`` if it's not the root node.
230 _root: Nullable[Node] #: Reference to the root of a tree. ``self`` if it's the root node, ``None`` once deleted.
231 _parent: Nullable[Node] #: Reference to the parent node. ``None`` if it's the root node.
232 _children: list[Node] #: List of all children
233# _links: list['Node']
235 _level: int #: Level of the node (distance to the root).
236 _value: Nullable[ValueType] #: Field to store the node's value.
238 _format: Nullable[Callable[[Node], str]] #: A node formatting function returning a one-line representation for tree-rendering.
240 def __init__(
241 self,
242 nodeID: Nullable[IDType] = None,
243 value: Nullable[ValueType] = None,
244 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None,
245 parent: Nullable[Node] = None,
246 children: Nullable[Iterable[Node]] = None,
247 format: Nullable[Callable[[Node], str]] = None
248 ) -> None:
249 """
250 .. todo:: TREE::Node::init Needs documentation.
252 :param nodeID: Optional, unique ID of a node within the whole tree data structure.
253 :param value: Optional, value of the node.
254 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
255 :param parent: Optional, parent node in the tree.
256 :param children: Optional, list of child nodes.
257 :param format: Optional, node formatting function returning a one-line representation for
258 tree-rendering.
260 :raises TypeError: If parameter 'keyValuePairs' is not a mapping.
261 :raises TypeError: If parameter parent is not an instance of Node.
262 :raises ValueError: If nodeID already exists in the tree.
263 :raises TypeError: If parameter children is not iterable.
264 :raises ValueError: If an element of children is not an instance of Node.
265 """
266 super().__init__(keyValuePairs)
268 self._id = nodeID
269 self._value = value
271 self._format = format
273 if parent is not None and not isinstance(parent, Node):
274 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
275 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
276 raise ex
278 if parent is None:
279 self._root = self
280 self._parent = None
281 self._level = 0
283 self._nodesWithID = {}
284 self._nodesWithoutID = []
285 if nodeID is None:
286 self._nodesWithoutID.append(self)
287 else:
288 self._nodesWithID[nodeID] = self
289 else:
290 self._root = parent._root
291 self._parent = parent
292 self._level = parent._level + 1
293 self._nodesWithID = None
294 self._nodesWithoutID = None
296 if nodeID is None:
297 self._root._nodesWithoutID.append(self)
298 elif nodeID in self._root._nodesWithID:
299 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
300 else:
301 self._root._nodesWithID[nodeID] = self
303 parent._children.append(self)
305 self._children = []
306 if children is not None:
307 if not isinstance(children, Iterable):
308 ex = TypeError("Parameter 'children' is not iterable.")
309 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.")
310 raise ex
312 for child in children:
313 if not isinstance(child, Node):
314 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
315 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
316 raise ex
318 child.Parent = self
320 @readonly
321 def ID(self) -> Nullable[IDType]:
322 """
323 Read-only property to access the unique ID of a node (:attr:`_id`).
325 If no ID was given at node construction time, ID return None.
327 :returns: Unique ID of a node, if ID was given at node creation time, else None.
328 """
329 return self._id
331 @property
332 def Value(self) -> Nullable[ValueType]:
333 """
334 Property to get and set the value (:attr:`_value`) of a node.
336 :returns: The value of a node.
337 """
338 return self._value
340 @Value.setter
341 def Value(self, value: Nullable[ValueType]) -> None:
342 self._value = value
344 @readonly
345 def Root(self) -> Node:
346 """
347 Read-only property to access the tree's root node (:attr:`_root`).
349 :returns: The root node (representative node) of a tree.
350 """
351 return self._root
353 @property
354 def Parent(self) -> Nullable[Node]:
355 """
356 Property to access the parent (:attr:`_parent`) of a node.
358 Assigning ``None`` detaches the node from its tree, which makes it the root node of the subtree it carries.
359 Assigning a node appends this node - and everything below it - to that node's tree.
361 .. note::
363 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and
364 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`.
366 :returns: The parent of a node, or ``None`` if the node is a root node.
367 :raises TypeError: If a node that is not a :class:`Node` is assigned.
368 :raises AlreadyInTreeError: If the assigned parent is already a child node in this tree.
369 """
370 return self._parent
372 @Parent.setter
373 def Parent(self, parent: Nullable[Node]) -> None:
374 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root
376 if parent is None:
377 self._nodesWithID = {}
378 self._nodesWithoutID = []
379 self._level = 0
381 if self._id is None:
382 self._nodesWithoutID.append(self)
383 self._root._nodesWithoutID.remove(self)
384 else:
385 self._nodesWithID[self._id] = self
386 del self._root._nodesWithID[self._id]
388 for sibling in self.GetDescendants():
389 sibling._root = self
390 sibling._level = sibling._parent._level + 1
391 if sibling._id is None:
392 self._nodesWithoutID.append(sibling)
393 self._root._nodesWithoutID.remove(sibling)
394 else:
395 self._nodesWithID[sibling._id] = sibling
396 del self._root._nodesWithID[sibling._id]
398 self._parent._children.remove(self)
400 self._root = self
401 self._parent = None
402 elif not isinstance(parent, Node):
403 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
404 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
405 raise ex
406 else:
407 if parent._root is self._root:
408 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.", otherNode=parent)
410 self._root = parent._root
411 self._parent = parent
412 self._level = parent._level + 1
413 for node in self.GetDescendants():
414 node._level = node._parent._level + 1
415 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID)
416 self._nodesWithID = self._nodesWithoutID = None
417 parent._children.append(self)
419 @readonly
420 def Siblings(self) -> tuple[Node, ...]:
421 """
422 A read-only property to return a tuple of all siblings from the current node.
424 If the current node is the only child, the tuple is empty.
426 Siblings are child nodes of the current node's parent node, without the current node itself.
428 :returns: A tuple of all siblings of the current node.
429 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
430 """
431 if self._parent is None:
432 raise NoSiblingsError("Root node has no siblings.")
434 return tuple([node for node in self._parent._children if node is not self])
436 @readonly
437 def LeftSiblings(self) -> tuple[Node, ...]:
438 """
439 A read-only property to return a tuple of all siblings left from the current node.
441 If the current node is the only child, the tuple is empty.
443 Siblings are child nodes of the current node's parent node, without the current node itself.
445 :returns: A tuple of all siblings left of the current node.
446 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
447 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its parent's
448 children.
449 """
450 if self._parent is None:
451 raise NoSiblingsError("Root node has no siblings.")
453 result = []
454 for node in self._parent._children:
455 if node is not self:
456 result.append(node)
457 else:
458 break
459 else:
460 raise InternalError("Data structure corruption: Self is not part of parent's children.") # pragma: no cover
462 return tuple(result)
464 @readonly
465 def RightSiblings(self) -> tuple[Node, ...]:
466 """
467 A read-only property to return a tuple of all siblings right from the current node.
469 If the current node is the only child, the tuple is empty.
471 Siblings are child nodes of the current node's parent node, without the current node itself.
473 :returns: A tuple of all siblings right of the current node.
474 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
475 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its parent's
476 children.
477 """
478 if self._parent is None:
479 raise NoSiblingsError("Root node has no siblings.")
481 result = []
482 iterator = iter(self._parent._children)
483 for node in iterator:
484 if node is self:
485 break
486 else:
487 raise InternalError("Data structure corruption: Self is not part of parent's children.") # pragma: no cover
489 for node in iterator:
490 result.append(node)
492 return tuple(result)
494 def _GetPathAsLinkedList(self) -> Deque[Node]:
495 """
496 Compute the path from current node to root node by using a linked list (:class:`deque`).
498 :meta private:
499 :returns: Path from node to root node as double-ended queue (deque).
500 """
501 path: Deque[Node] = deque()
503 node = self
504 while node is not None:
505 path.appendleft(node)
506 node = node._parent
508 return path
510 @readonly
511 def Path(self) -> tuple[Node]:
512 """
513 Read-only property to return the path from root node to the node as a tuple of nodes.
515 :returns: A tuple of nodes describing the path from root node to the node.
516 """
517 return tuple(self._GetPathAsLinkedList())
519 @readonly
520 def Level(self) -> int:
521 """
522 Read-only property to access a node's level in the tree.
524 The level is the distance to the root node.
526 :returns: The node's level.
527 """
528 return self._level
530 @readonly
531 def Size(self) -> int:
532 """
533 Read-only property to return the size of the tree.
535 :returns: Count of all nodes in the tree structure.
536 """
537 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID)
539 @readonly
540 def IsRoot(self) -> bool:
541 """
542 Returns true, if the node is the root node (representative node of the tree).
544 :returns: ``True``, if node is the root node.
545 """
546 return self._parent is None
548 @readonly
549 def IsLeaf(self) -> bool:
550 """
551 Returns true, if the node is a leaf node (has no children).
553 :returns: ``True``, if node has no children.
554 """
555 return len(self._children) == 0
557 @readonly
558 def Children(self) -> tuple[Node, ...]:
559 """
560 Read-only property to return a tuple of all direct children (:attr:`_children`).
562 :returns: A tuple of all children, in the order they were added.
563 """
564 return tuple(self._children)
566 @readonly
567 def ChildCount(self) -> int:
568 """
569 Read-only property to return the number of direct children, but not including grand-children.
571 :returns: Number of child nodes.
572 """
573 return len(self._children)
575 @readonly
576 def HasChildren(self) -> bool:
577 """
578 Returns true, if the node has child nodes.
580 :returns: ``True``, if node has children.
581 """
582 return len(self._children) > 0
584 def _SetNewRoot(self, nodesWithIDs: dict[Node, Node], nodesWithoutIDs: list[Node]) -> None:
585 """
586 Move the given nodes into this node's tree.
588 :param nodesWithIDs: Nodes with an ID, which have to stay unique within the tree.
589 :param nodesWithoutIDs: Nodes without an ID.
590 :raises ValueError: If one of the IDs already exists in this tree.
591 """
592 for nodeID, node in nodesWithIDs.items():
593 if nodeID in self._root._nodesWithID:
594 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
595 else:
596 self._root._nodesWithID[nodeID] = node
597 node._root = self._root
599 for node in nodesWithoutIDs:
600 self._root._nodesWithoutID.append(node)
601 node._root = self._root
603 def AddChild(self, child: Node) -> None:
604 """
605 Add a child node to the current node of the tree.
607 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and
608 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`).
610 :param child: The child node to be added to the tree.
611 :raises TypeError: If parameter ``child`` is not a :class:`Node`.
612 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree.
614 .. seealso::
616 :attr:`Parent`
617 |rarr| Set the parent of a node.
618 :meth:`AddChildren`
619 |rarr| Add multiple children at once.
620 """
621 if not isinstance(child, Node):
622 ex = TypeError("Parameter 'child' is not of type 'Node'.")
623 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
624 raise ex
626 if child._root is self._root:
627 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.", otherNode=child)
629 child._root = self._root
630 child._parent = self
631 child._level = self._level + 1
632 for node in child.GetDescendants():
633 node._level = node._parent._level + 1
634 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
635 child._nodesWithID = child._nodesWithoutID = None
636 self._children.append(child)
638 def AddChildren(self, children: Iterable[Node]) -> None:
639 """
640 Add multiple children nodes to the current node of the tree.
642 :param children: The list of children nodes to be added to the tree.
643 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`.
644 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree.
646 .. seealso::
648 :attr:`Parent`
649 |rarr| Set the parent of a node.
650 :meth:`AddChild`
651 |rarr| Add a child node to the tree.
652 """
653 for child in children:
654 if not isinstance(child, Node):
655 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
656 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
657 raise ex
659 if child._root is self._root:
660 # TODO: create a more specific exception
661 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.", otherNode=child)
663 child._root = self._root
664 child._parent = self
665 child._level = self._level + 1
666 for node in child.GetDescendants():
667 node._level = node._parent._level + 1
668 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
669 child._nodesWithID = child._nodesWithoutID = None
670 self._children.append(child)
672 def RemoveChild(self, child: Node) -> None:
673 """
674 Remove a child node from the current node of the tree.
676 The child is detached together with its subtree: it becomes the root node of its own tree, like assigning
677 ``None`` to its :attr:`Parent`. All nodes of that subtree get the child as new :attr:`_root` assigned and their
678 IDs are moved from the node's root's ID lists (:attr:`_nodesWithID`) into the child's.
680 :param child: The child node to be removed from the tree.
681 :raises ValueError: If parameter 'child' is ``None``.
682 :raises TypeError: If parameter 'child' is not of type :class:`Node`.
683 :raises NotAChildError: If parameter 'child' is not a direct child of the current node.
685 .. seealso::
687 :attr:`Parent`
688 |rarr| Set the parent of a node.
689 :meth:`RemoveChildren`
690 |rarr| Remove multiple children at once.
691 :meth:`AddChild`
692 |rarr| Add a child node to the tree.
693 """
694 if child is None:
695 raise ValueError("Parameter 'child' is None.")
696 elif not isinstance(child, Node):
697 ex = TypeError("Parameter 'child' is not of type 'Node'.")
698 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
699 raise ex
700 elif child._parent is not self:
701 raise NotAChildError(f"Node '{child}' is not a child of this node.", child=child)
703 child.Parent = None
705 def RemoveChildren(self, children: Iterable[Node]) -> None:
706 """
707 Remove multiple children nodes from the current node of the tree.
709 Each child is detached together with its subtree, like :meth:`RemoveChild` does. The children are collected
710 before the first one is removed, so 'children' may iterate the current node's children, e.g.
711 :meth:`GetChildren`.
713 :param children: The list of children nodes to be removed from the tree.
714 :raises ValueError: If parameter 'children' is ``None``.
715 :raises TypeError: If parameter 'children' is not iterable.
716 :raises ValueError: If parameter 'children' contains ``None``.
717 :raises TypeError: If parameter 'children' contains an item, which is not of type :class:`Node`.
718 :raises NotAChildError: If parameter 'children' contains an item, which is not a direct child of the current
719 node.
721 .. seealso::
723 :attr:`Parent`
724 |rarr| Set the parent of a node.
725 :meth:`RemoveChild`
726 |rarr| Remove a child node from the tree.
727 :meth:`AddChildren`
728 |rarr| Add multiple children at once.
729 """
730 if children is None:
731 raise ValueError("Parameter 'children' is None.")
732 elif not isinstance(children, Iterable):
733 ex = TypeError("Parameter 'children' is not iterable.")
734 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.")
735 raise ex
737 for child in tuple(children):
738 if child is None:
739 raise ValueError("Item in parameter 'children' is None.")
740 elif not isinstance(child, Node):
741 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
742 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
743 raise ex
744 elif child._parent is not self:
745 raise NotAChildError(f"Item '{child}' in parameter 'children' is not a child of this node.", child=child)
747 child.Parent = None
749 def Delete(self) -> None:
750 """
751 Delete this node and its subtree.
753 A node with a parent is removed from it first, like :meth:`RemoveChild` does. Then every node of the subtree is
754 disconnected: it has no root, no parent and no children, and its key-value-pairs are removed. A deleted node
755 belongs to no tree and can't be used any more. Its value is kept.
757 .. seealso::
759 :ref:`Deleting a tree <STRUCT/Tree/Delete>`
760 |rarr| Reference cycles in a tree and Python's garbage collector.
761 :meth:`RemoveChild`
762 |rarr| Remove a child node, which keeps its subtree as a tree of its own.
763 """
764 if self._parent is not None:
765 self.Parent = None
767 for node in (*self._nodesWithoutID, *self._nodesWithID.values()):
768 node._root = None
769 node._parent = None
770 node._children = []
771 node._dict.clear()
773 self._nodesWithID = None
774 self._nodesWithoutID = None
776 def GetPath(self) -> Generator[Node, None, None]:
777 """
778 Compute the path from the root node to this node.
780 :returns: A generator yielding the nodes from the root down to this node.
781 """
782 for node in self._GetPathAsLinkedList():
783 yield node
785 def GetAncestors(self) -> Generator[Node, None, None]:
786 """
787 Iterate the ancestors of this node.
789 :returns: A generator yielding the parent, its parent, and so on up to the root node.
790 """
791 node = self._parent
792 while node is not None:
793 yield node
794 node = node._parent
796 def GetCommonAncestors(self, others: Union[Node, Iterable[Node]]) -> Generator[Node, None, None]:
797 """
798 Compute the common ancestors of this node and one or more other nodes.
800 The nodes' paths from the root are walked in parallel and yielded as long as they are identical, so the last
801 yielded node is the nearest common ancestor.
803 :param others: Another node, or an iterable of nodes, to compute the common ancestors with.
804 :returns: A generator yielding the common ancestors, starting at the root node.
805 :raises NotInSameTreeError: If one of the given nodes is not in the same tree.
806 :raises NotImplementedError: If more than one other node is given; the common ancestors of a set of nodes are
807 not computed yet.
808 """
809 if isinstance(others, Node): 809 ↛ 826line 809 didn't jump to line 826 because the condition on line 809 was always true
810 # Check for trivial case
811 if others is self: 811 ↛ 812line 811 didn't jump to line 812 because the condition on line 811 was never true
812 for node in self._GetPathAsLinkedList():
813 yield node
814 return
816 # Check if both are in the same tree.
817 if self._root is not others._root: 817 ↛ 821line 817 didn't jump to line 821 because the condition on line 817 was always true
818 raise NotInSameTreeError("Node 'others' is not in the same tree.", otherNode=others)
820 # Compute paths top-down and walk both paths until they deviate
821 for left, right in zip(self.Path, others.Path):
822 if left is right:
823 yield left
824 else:
825 return
826 elif isinstance(others, Iterable):
827 raise NotImplementedError("Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.")
829 def GetChildren(self) -> Generator[Node, None, None]:
830 """
831 A generator to iterate all direct children of the current node.
833 :returns: A generator to iterate all children.
835 .. seealso::
837 :meth:`GetDescendants`
838 |rarr| Iterate all descendants.
839 :meth:`IterateLevelOrder`
840 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
841 :meth:`IteratePreOrder`
842 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
843 :meth:`IteratePostOrder`
844 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
845 """
846 for child in self._children:
847 yield child
849 def GetSiblings(self) -> Generator[Node, None, None]:
850 """
851 A generator to iterate all siblings.
853 Siblings are child nodes of the current node's parent node, without the current node itself.
855 :returns: A generator to iterate all siblings of the current node.
856 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
857 """
858 if self._parent is None:
859 raise NoSiblingsError("Root node has no siblings.")
861 for node in self._parent._children:
862 if node is self:
863 continue
865 yield node
867 def GetLeftSiblings(self) -> Generator[Node, None, None]:
868 """
869 A generator to iterate all siblings left from the current node.
871 Siblings are child nodes of the current node's parent node, without the current node itself.
873 :returns: A generator to iterate all siblings left of the current node.
874 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
875 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its
876 parent's children.
877 """
878 if self._parent is None:
879 raise NoSiblingsError("Root node has no siblings.")
881 for node in self._parent._children:
882 if node is self:
883 break
885 yield node
886 else:
887 raise InternalError("Data structure corruption: Self is not part of parent's children.") # pragma: no cover
889 def GetRightSiblings(self) -> Generator[Node, None, None]:
890 """
891 A generator to iterate all siblings right from the current node.
893 Siblings are child nodes of the current node's parent node, without the current node itself.
895 :returns: A generator to iterate all siblings right of the current node.
896 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
897 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its
898 parent's children.
899 """
900 if self._parent is None:
901 raise NoSiblingsError("Root node has no siblings.")
903 iterator = iter(self._parent._children)
904 for node in iterator:
905 if node is self:
906 break
907 else:
908 raise InternalError("Data structure corruption: Self is not part of parent's children.") # pragma: no cover
910 for node in iterator:
911 yield node
913 def GetDescendants(self) -> Generator[Node, None, None]:
914 """
915 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder`
916 it doesn't include the node itself.
918 :returns: A generator to iterate all descendants.
920 .. seealso::
922 :meth:`GetChildren`
923 |rarr| Iterate all children, but no grand-children.
924 :meth:`IterateLevelOrder`
925 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
926 :meth:`IteratePreOrder`
927 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
928 :meth:`IteratePostOrder`
929 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
930 """
931 for child in self._children:
932 yield child
933 yield from child.GetDescendants()
935 def GetRelatives(self) -> Generator[Node, None, None]:
936 """
937 A generator to iterate all relatives (all siblings and all their descendants) of the current node.
939 :returns: A generator to iterate all relatives.
940 """
941 for node in self.GetSiblings():
942 yield node
943 yield from node.GetDescendants()
945 def GetLeftRelatives(self) -> Generator[Node, None, None]:
946 """
947 A generator to iterate all left relatives (left siblings and all their descendants) of the current node.
949 :returns: A generator to iterate all left relatives.
950 """
951 for node in self.GetLeftSiblings():
952 yield node
953 yield from node.GetDescendants()
955 def GetRightRelatives(self) -> Generator[Node, None, None]:
956 """
957 A generator to iterate all right relatives (right siblings and all their descendants) of the current node.
959 :returns: A generator to iterate all right relatives.
960 """
961 for node in self.GetRightSiblings():
962 yield node
963 yield from node.GetDescendants()
965 def IterateLeafs(self) -> Generator[Node, None, None]:
966 """
967 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.
969 :returns: A generator to iterate leaf-nodes reachable from current node.
970 """
971 for child in self._children:
972 if child.IsLeaf:
973 yield child
974 else:
975 yield from child.IterateLeafs()
977 def IterateLevelOrder(self) -> Generator[Node, None, None]:
978 """
979 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`,
980 this includes also the node itself as the first returned node.
982 :returns: A generator to iterate all siblings level-by-level.
984 .. seealso::
986 :meth:`GetChildren`
987 |rarr| Iterate all children, but no grand-children.
988 :meth:`GetDescendants`
989 |rarr| Iterate all descendants.
990 :meth:`IteratePreOrder`
991 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
992 :meth:`IteratePostOrder`
993 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
994 """
995 queue = deque([self])
996 while queue:
997 currentNode = queue.pop()
998 yield currentNode
999 for node in currentNode._children:
1000 queue.appendleft(node)
1002 def IteratePreOrder(self) -> Generator[Node, None, None]:
1003 """
1004 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes
1005 also the node itself as the first returned node.
1007 :returns: A generator to iterate all siblings in pre-order.
1009 .. seealso::
1011 :meth:`GetChildren`
1012 |rarr| Iterate all children, but no grand-children.
1013 :meth:`GetDescendants`
1014 |rarr| Iterate all descendants.
1015 :meth:`IterateLevelOrder`
1016 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
1017 :meth:`IteratePostOrder`
1018 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
1019 """
1020 yield self
1021 for child in self._children:
1022 yield from child.IteratePreOrder()
1024 def IteratePostOrder(self) -> Generator[Node, None, None]:
1025 """
1026 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this
1027 includes also the node itself as the last returned node.
1029 :returns: A generator to iterate all siblings in post-order.
1031 .. seealso::
1033 :meth:`GetChildren`
1034 |rarr| Iterate all children, but no grand-children.
1035 :meth:`GetDescendants`
1036 |rarr| Iterate all descendants.
1037 :meth:`IterateLevelOrder`
1038 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
1039 :meth:`IteratePreOrder`
1040 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
1041 """
1042 for child in self._children:
1043 yield from child.IteratePostOrder()
1044 yield self
1046 def WalkTo(self, other: Node) -> Generator[Node, None, None]:
1047 """
1048 Returns a generator to iterate the path from node to another node.
1050 :param other: Node to walk to.
1051 :returns: Generator to iterate the path from node to other node.
1052 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree.
1053 """
1054 # Check for trivial case
1055 if other is self: 1055 ↛ 1056line 1055 didn't jump to line 1056 because the condition on line 1055 was never true
1056 yield from ()
1058 # Check if both are in the same tree.
1059 if self._root is not other._root: 1059 ↛ 1065line 1059 didn't jump to line 1065 because the condition on line 1059 was always true
1060 raise NotInSameTreeError("Node 'other' is not in the same tree.", otherNode=other)
1062 # Compute both paths to the root.
1063 # 1. Walk from self to root, until a first common ancestor is found.
1064 # 2. Walk from there to other (reverse paths)
1065 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk.
1066 index = len(otherPath)
1067 for node in self.GetAncestors():
1068 try:
1069 index = otherPath.index(node)
1070 break
1071 except ValueError:
1072 yield node
1074 for i in range(index, len(otherPath)):
1075 yield otherPath[i]
1077 def GetNodeByID(self, nodeID: IDType) -> Node:
1078 """
1079 Lookup a node by its unique ID.
1081 :param nodeID: ID of a node to lookup in the tree.
1082 :returns: Node for the given ID.
1083 :raises ValueError: If parameter ``nodeID`` is None.
1084 :raises KeyError: If parameter ``nodeID`` is not found in the tree.
1085 """
1086 if nodeID is None:
1087 raise ValueError("'None' is not supported as an ID value.")
1089 return self._root._nodesWithID[nodeID]
1091 def Find(self, predicate: Predicate[Node]) -> Generator[Node, None, None]:
1092 """
1093 Search the tree for nodes matching a predicate.
1095 :param predicate: Filter function accepting a node and returning a boolean.
1096 :returns: A generator yielding the matching nodes.
1097 :raises NotImplementedError: Searching a tree is not implemented yet.
1098 """
1099 raise NotImplementedError("Method 'Find' is not yet implemented.")
1101 def __repr__(self) -> str:
1102 """
1103 Returns a detailed string representation of the node.
1105 :returns: The detailed string representation of the node.
1106 """
1107 nodeID = parent = value = ""
1108 if self._id is not None:
1109 nodeID = f"; nodeID='{self._id}'"
1111 if (self._parent is not None) and (self._parent._id is not None):
1112 parent = f"; parent='{self._parent._id}'"
1114 if self._value is not None:
1115 value = f"; value='{self._value}'"
1117 return f"<node{nodeID}{parent}{value}>"
1119 def __str__(self) -> str:
1120 """
1121 Return a string representation of the node.
1123 Order of resolution:
1125 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
1126 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
1127 3. Else, return :meth:`__repr__`.
1129 :returns: The resolved string representation of the node.
1130 """
1131 if self._value is not None:
1132 return str(self._value)
1133 elif self._id is not None:
1134 return str(self._id)
1135 else:
1136 return self.__repr__()
1138 def Render(
1139 self,
1140 prefix: str = "",
1141 lineend: str = "\n",
1142 nodeMarker: str = "├─",
1143 lastNodeMarker: str = "└─",
1144 bypassMarker: str = "│ "
1145 ) -> str:
1146 """
1147 Render the tree as ASCII art.
1149 :param prefix: Optional, a string printed in front of every line, e.g. for indentation. Default: ``""``.
1150 :param lineend: Optional, a string printed at the end of every line. Default: ``"\\n"``.
1151 :param nodeMarker: Optional, a string printed before every non-last tree node. Default: ``"├─"``.
1152 :param lastNodeMarker: Optional, a string printed before every last tree node. Default: ``"└─"``.
1153 :param bypassMarker: Optional, a string printed when there are further nodes in the parent level. Default: ``"│
1154 "``.
1155 :returns: A rendered tree as multiline string.
1156 """
1157 emptyMarker = " " * len(bypassMarker)
1159 def _render(node: Node, markers: str):
1160 """
1161 Nested function for recursion.
1163 :param node: The node whose children are rendered.
1164 :param markers: The prefix of the current level, assembled from the join and bypass markers.
1165 :returns: The rendered lines of that subtree.
1166 """
1167 result = []
1169 if node.HasChildren:
1170 for child in node._children[:-1]:
1171 nodeRepresentation = child._format(child) if child._format else str(child)
1172 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}")
1173 result.extend(_render(child, markers + bypassMarker))
1175 # last child node
1176 child = node._children[-1]
1177 nodeRepresentation = child._format(child) if child._format else str(child)
1178 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}")
1179 result.extend(_render(child, markers + emptyMarker))
1181 return result
1183 # Root element
1184 nodeRepresentation = self._format(self) if self._format else str(self)
1185 result = [f"{prefix}{nodeRepresentation}{lineend}"]
1186 result.extend(_render(self, ""))
1188 return "".join(result)