Coverage for pyTooling/Tree/__init__.py: 90%
372 statements
« prev ^ index » next coverage.py v7.15.4, created at 2026-08-22 21:29 +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
47from typing import Any, Callable, Iterator, Generator, Iterable, Mapping, Hashable
49from pyTooling.Decorators import export, readonly
50from pyTooling.MetaClasses import ExtendedType
51from pyTooling.Exceptions import ToolingException
52from pyTooling.Common import getFullyQualifiedName
55IDType = TypeVar("IDType", bound=Hashable)
56"""A type variable for a tree's ID."""
58ValueType = TypeVar("ValueType")
59"""A type variable for a tree's value."""
61DictKeyType = TypeVar("DictKeyType")
62"""A type variable for a tree's dictionary keys."""
64DictValueType = TypeVar("DictValueType")
65"""A type variable for a tree's dictionary values."""
68@export
69class TreeException(ToolingException):
70 """Base exception of all exceptions raised by :mod:`pyTooling.Tree`."""
73@export
74class InternalError(TreeException):
75 """
76 The exception is raised when a data structure corruption is detected.
78 .. danger::
80 This exception should never be raised.
82 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|
83 `⇒ Bug Tracker at GitHub <https://github.com/pyTooling/pyTooling/issues>`__
84 """
87@export
88class NoSiblingsError(TreeException):
89 """
90 The exception is raised when a node has no parent and thus has no siblings.
92 .. hint::
94 A node with no parent is the root node of the tree.
95 """
98@export
99class AlreadyInTreeError(TreeException):
100 """
101 The exception is raised when the current node and the other node are already in the same tree.
103 .. hint::
105 A tree a an acyclic graph without cross-edges. Thus backward edges and cross edges are permitted.
106 """
109@export
110class NotInSameTreeError(TreeException):
111 """The exception is raised when the current node and the other node are not in the same tree."""
114@export
115class Node(Generic[IDType, ValueType, DictKeyType, DictValueType], metaclass=ExtendedType, slots=True):
116 """
117 A **tree** data structure can be constructed of ``Node`` instances.
119 Therefore, nodes can be connected to parent nodes or a parent node can add child nodes. This allows to construct a
120 tree top-down or bottom-up.
122 .. hint::
124 The top-down construction should be preferred, because it's slightly faster.
126 Each tree uses the **root** node (a.k.a. tree-representative) to store some per-tree data structures. E.g. a list of
127 all IDs in a tree. For easy and quick access to such data structures, each sibling node contains a reference to the
128 root node (:attr:`_root`). In case of adding a tree to an existing tree, such data structures get merged and all added
129 nodes get assigned with new root references. Use the read-only property :attr:`Root` to access the root reference.
131 The reference to the parent node (:attr:`_parent`) can be access via property :attr:`Parent`. If the property's setter
132 is used, a node and all its siblings are added to another tree or to a new position in the same tree.
134 The references to all node's children is stored in a list (:attr:`_children`). Children, siblings, ancestors, can be
135 accessed via various generators:
137 * :meth:`GetAncestors` |rarr| iterate all ancestors bottom-up.
138 * :meth:`GetChildren` |rarr| iterate all direct children.
139 * :meth:`GetDescendants` |rarr| iterate all descendants.
140 * :meth:`IterateLevelOrder` |rarr| IterateLevelOrder.
141 * :meth:`IteratePreOrder` |rarr| iterate siblings in pre-order.
142 * :meth:`IteratePostOrder` |rarr| iterate siblings in post-order.
144 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
145 dictionary (:attr:`_nodesWithID`). In case no ID is given, all such ID-less nodes are collected in a single bin and store as a
146 list of nodes. An ID can be modified after the Node was created. Use the read-only property :attr:`ID` to access
147 the ID.
149 Each node can have a **value** (:attr:`_value`), which can be given at node creation time, or it can be assigned and/or
150 modified later. Use the property :attr:`Value` to get or set the value.
152 Moreover, each node can store various key-value-pairs (:attr:`_dict`). Use the dictionary syntax to get and set
153 key-value-pairs.
154 """
156 _id: Nullable[IDType] #: Unique identifier of a node. ``None`` if not used.
157 _nodesWithID: Nullable[dict[IDType, Node]] #: Dictionary of all IDs in the tree. ``None`` if it's not the root node.
158 _nodesWithoutID: Nullable[list[Node]] #: List of all nodes without an ID in the tree. ``None`` if it's not the root node.
159 _root: Node #: Reference to the root of a tree. ``self`` if it's the root node.
160 _parent: Nullable[Node] #: Reference to the parent node. ``None`` if it's the root node.
161 _children: list[Node] #: List of all children
162# _links: list['Node']
164 _level: int #: Level of the node (distance to the root).
165 _value: Nullable[ValueType] #: Field to store the node's value.
166 _dict: dict[DictKeyType, DictValueType] #: Dictionary to store key-value-pairs attached to the node.
168 _format: Nullable[Callable[[Node], str]] #: A node formatting function returning a one-line representation for tree-rendering.
170 def __init__(
171 self,
172 nodeID: Nullable[IDType] = None,
173 value: Nullable[ValueType] = None,
174 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
175 parent: Node = None,
176 children: Nullable[Iterable[Node]] = None,
177 format: Nullable[Callable[[Node], str]] = None
178 ) -> None:
179 """
180 .. todo:: TREE::Node::init Needs documentation.
182 :param nodeID: Optional, unique ID of a node within the whole tree data structure.
183 :param value: Optional, value of the node.
184 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
185 :param parent: Optional, parent node in the tree.
186 :param children: Optional, list of child nodes.
187 :param format: Optional, node formatting function returning a one-line representation for
188 tree-rendering.
190 :raises TypeError: If parameter parent is not an instance of Node.
191 :raises ValueError: If nodeID already exists in the tree.
192 :raises TypeError: If parameter children is not iterable.
193 :raises ValueError: If an element of children is not an instance of Node.
194 """
196 self._id = nodeID
197 self._value = value
198 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
200 self._format = format
202 if parent is not None and not isinstance(parent, Node):
203 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
204 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
205 raise ex
207 if parent is None:
208 self._root = self
209 self._parent = None
210 self._level = 0
212 self._nodesWithID = {}
213 self._nodesWithoutID = []
214 if nodeID is None:
215 self._nodesWithoutID.append(self)
216 else:
217 self._nodesWithID[nodeID] = self
218 else:
219 self._root = parent._root
220 self._parent = parent
221 self._level = parent._level + 1
222 self._nodesWithID = None
223 self._nodesWithoutID = None
225 if nodeID is None:
226 self._root._nodesWithoutID.append(self)
227 elif nodeID in self._root._nodesWithID:
228 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
229 else:
230 self._root._nodesWithID[nodeID] = self
232 parent._children.append(self)
234 self._children = []
235 if children is not None:
236 if not isinstance(children, Iterable):
237 ex = TypeError("Parameter 'children' is not iterable.")
238 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.")
239 raise ex
241 for child in children:
242 if not isinstance(child, Node):
243 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
244 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
245 raise ex
247 child.Parent = self
249 @readonly
250 def ID(self) -> Nullable[IDType]:
251 """
252 Read-only property to access the unique ID of a node (:attr:`_id`).
254 If no ID was given at node construction time, ID return None.
256 :returns: Unique ID of a node, if ID was given at node creation time, else None.
257 """
258 return self._id
260 @property
261 def Value(self) -> Nullable[ValueType]:
262 """
263 Property to get and set the value (:attr:`_value`) of a node.
265 :returns: The value of a node.
266 """
267 return self._value
269 @Value.setter
270 def Value(self, value: Nullable[ValueType]) -> None:
271 self._value = value
273 def __getitem__(self, key: DictKeyType) -> DictValueType:
274 """
275 Read a node's attached attributes (key-value-pairs) by key.
277 :param key: The key to look for.
278 :returns: The value associated to the given key.
279 """
280 return self._dict[key]
282 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
283 """
284 Create or update a node's attached attributes (key-value-pairs) by key.
286 If a key doesn't exist yet, a new key-value-pair is created.
288 :param key: The key to create or update.
289 :param value: Optional, the value to associate to the given key.
290 """
291 self._dict[key] = value
293 def __delitem__(self, key: DictKeyType) -> None:
294 """
295 .. todo:: TREE::Node::__delitem__ Needs documentation.
297 """
298 del self._dict[key]
300 def __contains__(self, key: DictKeyType) -> bool:
301 """
302 Check if a key exists in the node's attached attributes.
304 :param key: The key to look for.
305 :returns: ``True``, if the key exists.
306 """
307 return key in self._dict
309 def __len__(self) -> int:
310 """
311 Returns the number of attached attributes (key-value-pairs) on this node.
313 :returns: Number of attached attributes.
314 """
315 return len(self._dict)
317 @readonly
318 def Root(self) -> Node:
319 """
320 Read-only property to access the tree's root node (:attr:`_root`).
322 :returns: The root node (representative node) of a tree.
323 """
324 return self._root
326 @property
327 def Parent(self) -> Nullable[Node]:
328 """
329 Property to access the parent (:attr:`_parent`) of a node.
331 Assigning ``None`` detaches the node from its tree, which makes it the root node of the subtree it carries.
332 Assigning a node appends this node - and everything below it - to that node's tree.
334 .. note::
336 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and
337 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`.
339 :returns: The parent of a node, or ``None`` if the node is a root node.
340 :raises TypeError: If a node that is not a :class:`Node` is assigned.
341 :raises AlreadyInTreeError: If the assigned parent is already a child node in this tree.
342 """
343 return self._parent
345 @Parent.setter
346 def Parent(self, parent: Nullable[Node]) -> None:
347 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root
349 if parent is None:
350 self._nodesWithID = {}
351 self._nodesWithoutID = []
352 self._level = 0
354 if self._id is None:
355 self._nodesWithoutID.append(self)
356 self._root._nodesWithoutID.remove(self)
357 else:
358 self._nodesWithID[self._id] = self
359 del self._nodesWithID[self._id]
361 for sibling in self.GetDescendants():
362 sibling._root = self
363 sibling._level = sibling._parent._level + 1
364 if sibling._id is None:
365 self._nodesWithoutID.append(sibling)
366 self._root._nodesWithoutID.remove(sibling)
367 else:
368 self._nodesWithID[sibling._id] = sibling
369 del self._nodesWithID[sibling._id]
371 self._parent._children.remove(self)
373 self._root = self
374 self._parent = None
375 elif not isinstance(parent, Node):
376 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
377 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
378 raise ex
379 else:
380 if parent._root is self._root:
381 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.")
383 self._root = parent._root
384 self._parent = parent
385 self._level = parent._level + 1
386 for node in self.GetDescendants():
387 node._level = node._parent._level + 1
388 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID)
389 self._nodesWithID = self._nodesWithoutID = None
390 parent._children.append(self)
392 @readonly
393 def Siblings(self) -> tuple[Node, ...]:
394 """
395 A read-only property to return a tuple of all siblings from the current node.
397 If the current node is the only child, the tuple is empty.
399 Siblings are child nodes of the current node's parent node, without the current node itself.
401 :returns: A tuple of all siblings of the current node.
402 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
403 """
404 if self._parent is None:
405 raise NoSiblingsError(f"Root node has no siblings.")
407 return tuple([node for node in self._parent if node is not self])
409 @readonly
410 def LeftSiblings(self) -> tuple[Node, ...]:
411 """
412 A read-only property to return a tuple of all siblings left from the current node.
414 If the current node is the only child, the tuple is empty.
416 Siblings are child nodes of the current node's parent node, without the current node itself.
418 :returns: A tuple of all siblings left of the current node.
419 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
420 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its parent's
421 children.
422 """
423 if self._parent is None:
424 raise NoSiblingsError(f"Root node has no siblings.")
426 result = []
427 for node in self._parent:
428 if node is not self:
429 result.append(node)
430 else:
431 break
432 else:
433 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
435 return tuple(result)
437 @readonly
438 def RightSiblings(self) -> tuple[Node, ...]:
439 """
440 A read-only property to return a tuple of all siblings right from the current node.
442 If the current node is the only child, the tuple is empty.
444 Siblings are child nodes of the current node's parent node, without the current node itself.
446 :returns: A tuple of all siblings right of the current node.
447 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
448 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its parent's
449 children.
450 """
451 if self._parent is None:
452 raise NoSiblingsError(f"Root node has no siblings.")
454 result = []
455 iterator = iter(self._parent)
456 for node in iterator:
457 if node is self:
458 break
459 else:
460 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
462 for node in iterator:
463 result.append(node)
465 return tuple(result)
467 def _GetPathAsLinkedList(self) -> Deque[Node]:
468 """
469 Compute the path from current node to root node by using a linked list (:class:`deque`).
471 :meta private:
472 :returns: Path from node to root node as double-ended queue (deque).
473 """
474 path: Deque[Node] = deque()
476 node = self
477 while node is not None:
478 path.appendleft(node)
479 node = node._parent
481 return path
483 @readonly
484 def Path(self) -> tuple[Node]:
485 """
486 Read-only property to return the path from root node to the node as a tuple of nodes.
488 :returns: A tuple of nodes describing the path from root node to the node.
489 """
490 return tuple(self._GetPathAsLinkedList())
492 @readonly
493 def Level(self) -> int:
494 """
495 Read-only property to access a node's level in the tree.
497 The level is the distance to the root node.
499 :returns: The node's level.
500 """
501 return self._level
503 @readonly
504 def Size(self) -> int:
505 """
506 Read-only property to return the size of the tree.
508 :returns: Count of all nodes in the tree structure.
509 """
510 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID)
512 @readonly
513 def IsRoot(self) -> bool:
514 """
515 Returns true, if the node is the root node (representative node of the tree).
517 :returns: ``True``, if node is the root node.
518 """
519 return self._parent is None
521 @readonly
522 def IsLeaf(self) -> bool:
523 """
524 Returns true, if the node is a leaf node (has no children).
526 :returns: ``True``, if node has no children.
527 """
528 return len(self._children) == 0
530 @readonly
531 def HasChildren(self) -> bool:
532 """
533 Returns true, if the node has child nodes.
535 :returns: ``True``, if node has children.
536 """
537 return len(self._children) > 0
539 def _SetNewRoot(self, nodesWithIDs: dict[Node, Node], nodesWithoutIDs: list[Node]) -> None:
540 """
541 Move the given nodes into this node's tree.
543 :param nodesWithIDs: Nodes with an ID, which have to stay unique within the tree.
544 :param nodesWithoutIDs: Nodes without an ID.
545 :raises ValueError: If one of the IDs already exists in this tree.
546 """
547 for nodeID, node in nodesWithIDs.items():
548 if nodeID in self._root._nodesWithID:
549 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
550 else:
551 self._root._nodesWithID[nodeID] = node
552 node._root = self._root
554 for node in nodesWithoutIDs:
555 self._root._nodesWithoutID.append(node)
556 node._root = self._root
558 def AddChild(self, child: Node) -> None:
559 """
560 Add a child node to the current node of the tree.
562 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and
563 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`).
565 :param child: The child node to be added to the tree.
566 :raises TypeError: If parameter ``child`` is not a :class:`Node`.
567 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree.
569 .. seealso::
571 :attr:`Parent`
572 |rarr| Set the parent of a node.
573 :meth:`AddChildren`
574 |rarr| Add multiple children at once.
575 """
576 if not isinstance(child, Node):
577 ex = TypeError(f"Parameter 'child' is not of type 'Node'.")
578 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
579 raise ex
581 if child._root is self._root:
582 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
584 child._root = self._root
585 child._parent = self
586 child._level = self._level + 1
587 for node in child.GetDescendants():
588 node._level = node._parent._level + 1
589 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
590 child._nodesWithID = child._nodesWithoutID = None
591 self._children.append(child)
593 def AddChildren(self, children: Iterable[Node]) -> None:
594 """
595 Add multiple children nodes to the current node of the tree.
597 :param children: Optional, the list of children nodes to be added to the tree.
598 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`.
599 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree.
601 .. seealso::
603 :attr:`Parent`
604 |rarr| Set the parent of a node.
605 :meth:`AddChild`
606 |rarr| Add a child node to the tree.
607 """
608 for child in children:
609 if not isinstance(child, Node):
610 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
611 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
612 raise ex
614 if child._root is self._root:
615 # TODO: create a more specific exception
616 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
618 child._root = self._root
619 child._parent = self
620 child._level = self._level + 1
621 for node in child.GetDescendants():
622 node._level = node._parent._level + 1
623 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
624 child._nodesWithID = child._nodesWithoutID = None
625 self._children.append(child)
627 def GetPath(self) -> Generator[Node, None, None]:
628 """
629 Compute the path from the root node to this node.
631 :returns: A generator yielding the nodes from the root down to this node.
632 """
633 for node in self._GetPathAsLinkedList():
634 yield node
636 def GetAncestors(self) -> Generator[Node, None, None]:
637 """
638 Iterate the ancestors of this node.
640 :returns: A generator yielding the parent, its parent, and so on up to the root node.
641 """
642 node = self._parent
643 while node is not None:
644 yield node
645 node = node._parent
647 def GetCommonAncestors(self, others: Union[Node, Iterable[Node]]) -> Generator[Node, None, None]:
648 """
649 Compute the common ancestors of this node and one or more other nodes.
651 The nodes' paths from the root are walked in parallel and yielded as long as they are identical, so the last
652 yielded node is the nearest common ancestor.
654 :param others: Another node, or an iterable of nodes, to compute the common ancestors with.
655 :returns: A generator yielding the common ancestors, starting at the root node.
656 :raises NotInSameTreeError: If one of the given nodes is not in the same tree.
657 :raises NotImplementedError: If more than one other node is given; the common ancestors of a set of nodes are
658 not computed yet.
659 """
660 if isinstance(others, Node):
661 # Check for trivial case
662 if others is self:
663 for node in self._GetPathAsLinkedList():
664 yield node
665 return
667 # Check if both are in the same tree.
668 if self._root is not others._root:
669 raise NotInSameTreeError(f"Node 'others' is not in the same tree.")
671 # Compute paths top-down and walk both paths until they deviate
672 for left, right in zip(self.Path, others.Path):
673 if left is right:
674 yield left
675 else:
676 return
677 elif isinstance(others, Iterable):
678 raise NotImplementedError(f"Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.")
680 def GetChildren(self) -> Generator[Node, None, None]:
681 """
682 A generator to iterate all direct children of the current node.
684 :returns: A generator to iterate all children.
686 .. seealso::
688 :meth:`GetDescendants`
689 |rarr| Iterate all descendants.
690 :meth:`IterateLevelOrder`
691 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
692 :meth:`IteratePreOrder`
693 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
694 :meth:`IteratePostOrder`
695 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
696 """
697 for child in self._children:
698 yield child
700 def GetSiblings(self) -> Generator[Node, None, None]:
701 """
702 A generator to iterate all siblings.
704 Siblings are child nodes of the current node's parent node, without the current node itself.
706 :returns: A generator to iterate all siblings of the current node.
707 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
708 """
709 if self._parent is None:
710 raise NoSiblingsError(f"Root node has no siblings.")
712 for node in self._parent:
713 if node is self:
714 continue
716 yield node
718 def GetLeftSiblings(self) -> Generator[Node, None, None]:
719 """
720 A generator to iterate all siblings left from the current node.
722 Siblings are child nodes of the current node's parent node, without the current node itself.
724 :returns: A generator to iterate all siblings left of the current node.
725 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
726 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its
727 parent's children.
728 """
729 if self._parent is None:
730 raise NoSiblingsError(f"Root node has no siblings.")
732 for node in self._parent:
733 if node is self:
734 break
736 yield node
737 else:
738 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
740 def GetRightSiblings(self) -> Generator[Node, None, None]:
741 """
742 A generator to iterate all siblings right from the current node.
744 Siblings are child nodes of the current node's parent node, without the current node itself.
746 :returns: A generator to iterate all siblings right of the current node.
747 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
748 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its
749 parent's children.
750 """
751 if self._parent is None:
752 raise NoSiblingsError(f"Root node has no siblings.")
754 iterator = iter(self._parent)
755 for node in iterator:
756 if node is self:
757 break
758 else:
759 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
761 for node in iterator:
762 yield node
764 def GetDescendants(self) -> Generator[Node, None, None]:
765 """
766 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder`
767 it doesn't include the node itself.
769 :returns: A generator to iterate all descendants.
771 .. seealso::
773 :meth:`GetChildren`
774 |rarr| Iterate all children, but no grand-children.
775 :meth:`IterateLevelOrder`
776 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
777 :meth:`IteratePreOrder`
778 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
779 :meth:`IteratePostOrder`
780 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
781 """
782 for child in self._children:
783 yield child
784 yield from child.GetDescendants()
786 def GetRelatives(self) -> Generator[Node, None, None]:
787 """
788 A generator to iterate all relatives (all siblings and all their descendants) of the current node.
790 :returns: A generator to iterate all relatives.
791 """
792 for node in self.GetSiblings():
793 yield node
794 yield from node.GetDescendants()
796 def GetLeftRelatives(self) -> Generator[Node, None, None]:
797 """
798 A generator to iterate all left relatives (left siblings and all their descendants) of the current node.
800 :returns: A generator to iterate all left relatives.
801 """
802 for node in self.GetLeftSiblings():
803 yield node
804 yield from node.GetDescendants()
806 def GetRightRelatives(self) -> Generator[Node, None, None]:
807 """
808 A generator to iterate all right relatives (right siblings and all their descendants) of the current node.
810 :returns: A generator to iterate all right relatives.
811 """
812 for node in self.GetRightSiblings():
813 yield node
814 yield from node.GetDescendants()
816 def IterateLeafs(self) -> Generator[Node, None, None]:
817 """
818 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.
820 :returns: A generator to iterate leaf-nodes reachable from current node.
821 """
822 for child in self._children:
823 if child.IsLeaf:
824 yield child
825 else:
826 yield from child.IterateLeafs()
828 def IterateLevelOrder(self) -> Generator[Node, None, None]:
829 """
830 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`,
831 this includes also the node itself as the first returned node.
833 :returns: A generator to iterate all siblings level-by-level.
835 .. seealso::
837 :meth:`GetChildren`
838 |rarr| Iterate all children, but no grand-children.
839 :meth:`GetDescendants`
840 |rarr| Iterate all descendants.
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 queue = deque([self])
847 while queue:
848 currentNode = queue.pop()
849 yield currentNode
850 for node in currentNode._children:
851 queue.appendleft(node)
853 def IteratePreOrder(self) -> Generator[Node, None, None]:
854 """
855 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes
856 also the node itself as the first returned node.
858 :returns: A generator to iterate all siblings in pre-order.
860 .. seealso::
862 :meth:`GetChildren`
863 |rarr| Iterate all children, but no grand-children.
864 :meth:`GetDescendants`
865 |rarr| Iterate all descendants.
866 :meth:`IterateLevelOrder`
867 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
868 :meth:`IteratePostOrder`
869 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
870 """
871 yield self
872 for child in self._children:
873 yield from child.IteratePreOrder()
875 def IteratePostOrder(self) -> Generator[Node, None, None]:
876 """
877 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this
878 includes also the node itself as the last returned node.
880 :returns: A generator to iterate all siblings in post-order.
882 .. seealso::
884 :meth:`GetChildren`
885 |rarr| Iterate all children, but no grand-children.
886 :meth:`GetDescendants`
887 |rarr| Iterate all descendants.
888 :meth:`IterateLevelOrder`
889 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
890 :meth:`IteratePreOrder`
891 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
892 """
893 for child in self._children:
894 yield from child.IteratePostOrder()
895 yield self
897 def WalkTo(self, other: Node) -> Generator[Node, None, None]:
898 """
899 Returns a generator to iterate the path from node to another node.
901 :param other: Node to walk to.
902 :returns: Generator to iterate the path from node to other node.
903 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree.
904 """
905 # Check for trivial case
906 if other is self:
907 yield from ()
909 # Check if both are in the same tree.
910 if self._root is not other._root:
911 raise NotInSameTreeError(f"Node 'other' is not in the same tree.")
913 # Compute both paths to the root.
914 # 1. Walk from self to root, until a first common ancestor is found.
915 # 2. Walk from there to other (reverse paths)
916 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk.
917 index = len(otherPath)
918 for node in self.GetAncestors():
919 try:
920 index = otherPath.index(node)
921 break
922 except ValueError:
923 yield node
925 for i in range(index, len(otherPath)):
926 yield otherPath[i]
928 def GetNodeByID(self, nodeID: IDType) -> Node:
929 """
930 Lookup a node by its unique ID.
932 :param nodeID: Optional, ID of a node to lookup in the tree.
933 :returns: Node for the given ID.
934 :raises ValueError: If parameter ``nodeID`` is None.
935 :raises KeyError: If parameter ``nodeID`` is not found in the tree.
936 """
937 if nodeID is None:
938 raise ValueError(f"'None' is not supported as an ID value.")
940 return self._root._nodesWithID[nodeID]
942 def Find(self, predicate: Callable[[Node], bool]) -> Generator[Node, None, None]:
943 """
944 Search the tree for nodes matching a predicate.
946 :param predicate: Filter function accepting a node and returning a boolean.
947 :returns: A generator yielding the matching nodes.
948 :raises NotImplementedError: Searching a tree is not implemented yet.
949 """
950 raise NotImplementedError(f"Method 'Find' is not yet implemented.")
952 def __iter__(self) -> Iterator[Node]:
953 """
954 Returns an iterator to iterate all child nodes.
956 :returns: Children iterator.
957 """
958 return iter(self._children)
960 def __len__(self) -> int:
961 """
962 Returns the number of children, but not including grand-children.
964 :returns: Number of child nodes.
965 """
966 return len(self._children)
968 def __repr__(self) -> str:
969 """
970 Returns a detailed string representation of the node.
972 :returns: The detailed string representation of the node.
973 """
974 nodeID = parent = value = ""
975 if self._id is not None:
976 nodeID = f"; nodeID='{self._id}'"
977 if (self._parent is not None) and (self._parent._id is not None):
978 parent = f"; parent='{self._parent._id}'"
979 if self._value is not None:
980 value = f"; value='{self._value}'"
982 return f"<node{nodeID}{parent}{value}>"
984 def __str__(self) -> str:
985 """
986 Return a string representation of the node.
988 Order of resolution:
990 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
991 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
992 3. Else, return :meth:`__repr__`.
994 :returns: The resolved string representation of the node.
995 """
996 if self._value is not None:
997 return str(self._value)
998 elif self._id is not None:
999 return str(self._id)
1000 else:
1001 return self.__repr__()
1003 def Render(
1004 self,
1005 prefix: str = "",
1006 lineend: str = "\n",
1007 nodeMarker: str = "├─",
1008 lastNodeMarker: str = "└─",
1009 bypassMarker: str = "│ "
1010 ) -> str:
1011 """
1012 Render the tree as ASCII art.
1014 :param prefix: Optional, a string printed in front of every line, e.g. for indentation. Default: ``""``.
1015 :param lineend: Optional, a string printed at the end of every line. Default: ``"\\n"``.
1016 :param nodeMarker: Optional, a string printed before every non-last tree node. Default: ``"├─"``.
1017 :param lastNodeMarker: Optional, a string printed before every last tree node. Default: ``"└─"``.
1018 :param bypassMarker: Optional, a string printed when there are further nodes in the parent level. Default: ``"│
1019 "``.
1020 :returns: A rendered tree as multiline string.
1021 """
1022 emptyMarker = " " * len(bypassMarker)
1024 def _render(node: Node, markers: str):
1025 """
1026 Nested function for recursion.
1028 :param node: The node whose children are rendered.
1029 :param markers: The prefix of the current level, assembled from the join and bypass markers.
1030 :returns: The rendered lines of that subtree.
1031 """
1032 result = []
1034 if node.HasChildren:
1035 for child in node._children[:-1]:
1036 nodeRepresentation = child._format(child) if child._format else str(child)
1037 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}")
1038 result.extend(_render(child, markers + bypassMarker))
1040 # last child node
1041 child = node._children[-1]
1042 nodeRepresentation = child._format(child) if child._format else str(child)
1043 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}")
1044 result.extend(_render(child, markers + emptyMarker))
1046 return result
1048 # Root element
1049 nodeRepresentation = self._format(self) if self._format else str(self)
1050 result = [f"{prefix}{nodeRepresentation}{lineend}"]
1051 result.extend(_render(self, ""))
1053 return "".join(result)