Coverage for pyTooling / Tree / __init__.py: 90%
371 statements
« prev ^ index » next coverage.py v7.13.3, created at 2026-02-07 17:18 +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"""A powerful tree data structure for Python."""
32from collections import deque
33from typing import TypeVar, Generic, List, Tuple, Dict, Deque, Union, Optional as Nullable
34from typing import Callable, Iterator, Generator, Iterable, Mapping, Hashable
36from pyTooling.Decorators import export, readonly
37from pyTooling.MetaClasses import ExtendedType
38from pyTooling.Exceptions import ToolingException
39from pyTooling.Common import getFullyQualifiedName
42IDType = TypeVar("IDType", bound=Hashable)
43"""A type variable for a tree's ID."""
45ValueType = TypeVar("ValueType")
46"""A type variable for a tree's value."""
48DictKeyType = TypeVar("DictKeyType")
49"""A type variable for a tree's dictionary keys."""
51DictValueType = TypeVar("DictValueType")
52"""A type variable for a tree's dictionary values."""
55@export
56class TreeException(ToolingException):
57 """Base exception of all exceptions raised by :mod:`pyTooling.Tree`."""
60@export
61class InternalError(TreeException):
62 """
63 The exception is raised when a data structure corruption is detected.
65 .. danger::
67 This exception should never be raised.
69 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|
70 `⇒ Bug Tracker at GitHub <https://github.com/pyTooling/pyTooling/issues>`__
71 """
74@export
75class NoSiblingsError(TreeException):
76 """
77 The exception is raised when a node has no parent and thus has no siblings.
79 .. hint::
81 A node with no parent is the root node of the tree.
82 """
85@export
86class AlreadyInTreeError(TreeException):
87 """
88 The exception is raised when the current node and the other node are already in the same tree.
90 .. hint::
92 A tree a an acyclic graph without cross-edges. Thus backward edges and cross edges are permitted.
93 """
96@export
97class NotInSameTreeError(TreeException):
98 """The exception is raised when the current node and the other node are not in the same tree."""
101@export
102class Node(Generic[IDType, ValueType, DictKeyType, DictValueType], metaclass=ExtendedType, slots=True):
103 """
104 A **tree** data structure can be constructed of ``Node`` instances.
106 Therefore, nodes can be connected to parent nodes or a parent node can add child nodes. This allows to construct a
107 tree top-down or bottom-up.
109 .. hint::
111 The top-down construction should be preferred, because it's slightly faster.
113 Each tree uses the **root** node (a.k.a. tree-representative) to store some per-tree data structures. E.g. a list of
114 all IDs in a tree. For easy and quick access to such data structures, each sibling node contains a reference to the
115 root node (:attr:`_root`). In case of adding a tree to an existing tree, such data structures get merged and all added
116 nodes get assigned with new root references. Use the read-only property :attr:`Root` to access the root reference.
118 The reference to the parent node (:attr:`_parent`) can be access via property :attr:`Parent`. If the property's setter
119 is used, a node and all its siblings are added to another tree or to a new position in the same tree.
121 The references to all node's children is stored in a list (:attr:`_children`). Children, siblings, ancestors, can be
122 accessed via various generators:
124 * :meth:`GetAncestors` |rarr| iterate all ancestors bottom-up.
125 * :meth:`GetChildren` |rarr| iterate all direct children.
126 * :meth:`GetDescendants` |rarr| iterate all descendants.
127 * :meth:`IterateLevelOrder` |rarr| IterateLevelOrder.
128 * :meth:`IteratePreOrder` |rarr| iterate siblings in pre-order.
129 * :meth:`IteratePostOrder` |rarr| iterate siblings in post-order.
131 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
132 dictionary (:attr:`_nodesWithID`). In case no ID is given, all such ID-less nodes are collected in a single bin and store as a
133 list of nodes. An ID can be modified after the Node was created. Use the read-only property :attr:`ID` to access
134 the ID.
136 Each node can have a **value** (:attr:`_value`), which can be given at node creation time, or it can be assigned and/or
137 modified later. Use the property :attr:`Value` to get or set the value.
139 Moreover, each node can store various key-value-pairs (:attr:`_dict`). Use the dictionary syntax to get and set
140 key-value-pairs.
141 """
143 _id: Nullable[IDType] #: Unique identifier of a node. ``None`` if not used.
144 _nodesWithID: Nullable[Dict[IDType, 'Node']] #: Dictionary of all IDs in the tree. ``None`` if it's not the root node.
145 _nodesWithoutID: Nullable[List['Node']] #: List of all nodes without an ID in the tree. ``None`` if it's not the root node.
146 _root: 'Node' #: Reference to the root of a tree. ``self`` if it's the root node.
147 _parent: Nullable['Node'] #: Reference to the parent node. ``None`` if it's the root node.
148 _children: List['Node'] #: List of all children
149# _links: List['Node']
151 _level: int #: Level of the node (distance to the root).
152 _value: Nullable[ValueType] #: Field to store the node's value.
153 _dict: Dict[DictKeyType, DictValueType] #: Dictionary to store key-value-pairs attached to the node.
155 _format: Nullable[Callable[["Node"], str]] #: A node formatting function returning a one-line representation for tree-rendering.
157 def __init__(
158 self,
159 nodeID: Nullable[IDType] = None,
160 value: Nullable[ValueType] = None,
161 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
162 parent: 'Node' = None,
163 children: Nullable[Iterable['Node']] = None,
164 format: Nullable[Callable[["Node"], str]] = None
165 ) -> None:
166 """
167 .. todo:: TREE::Node::init Needs documentation.
169 :param nodeID: The optional unique ID of a node within the whole tree data structure.
170 :param value: The optional value of the node.
171 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
172 :param parent: The optional parent node in the tree.
173 :param children: The optional list of child nodes.
174 :param format: The optional node formatting function returning a one-line representation for tree-rendering.
176 :raises TypeError: If parameter parent is not an instance of Node.
177 :raises ValueError: If nodeID already exists in the tree.
178 :raises TypeError: If parameter children is not iterable.
179 :raises ValueError: If an element of children is not an instance of Node.
180 """
182 self._id = nodeID
183 self._value = value
184 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
186 self._format = format
188 if parent is not None and not isinstance(parent, Node):
189 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
190 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
191 raise ex
193 if parent is None:
194 self._root = self
195 self._parent = None
196 self._level = 0
198 self._nodesWithID = {}
199 self._nodesWithoutID = []
200 if nodeID is None:
201 self._nodesWithoutID.append(self)
202 else:
203 self._nodesWithID[nodeID] = self
204 else:
205 self._root = parent._root
206 self._parent = parent
207 self._level = parent._level + 1
208 self._nodesWithID = None
209 self._nodesWithoutID = None
211 if nodeID is None:
212 self._root._nodesWithoutID.append(self)
213 elif nodeID in self._root._nodesWithID:
214 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
215 else:
216 self._root._nodesWithID[nodeID] = self
218 parent._children.append(self)
220 self._children = []
221 if children is not None:
222 if not isinstance(children, Iterable):
223 ex = TypeError("Parameter 'children' is not iterable.")
224 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.")
225 raise ex
227 for child in children:
228 if not isinstance(child, Node):
229 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
230 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
231 raise ex
233 child.Parent = self
235 @readonly
236 def ID(self) -> Nullable[IDType]:
237 """
238 Read-only property to access the unique ID of a node (:attr:`_id`).
240 If no ID was given at node construction time, ID return None.
242 :returns: Unique ID of a node, if ID was given at node creation time, else None.
243 """
244 return self._id
246 @property
247 def Value(self) -> Nullable[ValueType]:
248 """
249 Property to get and set the value (:attr:`_value`) of a node.
251 :returns: The value of a node.
252 """
253 return self._value
255 @Value.setter
256 def Value(self, value: Nullable[ValueType]) -> None:
257 self._value = value
259 def __getitem__(self, key: DictKeyType) -> DictValueType:
260 """
261 Read a node's attached attributes (key-value-pairs) by key.
263 :param key: The key to look for.
264 :returns: The value associated to the given key.
265 """
266 return self._dict[key]
268 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
269 """
270 Create or update a node's attached attributes (key-value-pairs) by key.
272 If a key doesn't exist yet, a new key-value-pair is created.
274 :param key: The key to create or update.
275 :param value: The value to associate to the given key.
276 """
277 self._dict[key] = value
279 def __delitem__(self, key: DictKeyType) -> None:
280 """
281 .. todo:: TREE::Node::__delitem__ Needs documentation.
283 """
284 del self._dict[key]
286 def __contains__(self, key: DictKeyType) -> bool:
287 """
288 .. todo:: TREE::Node::__contains__ Needs documentation.
290 """
291 return key in self._dict
293 def __len__(self) -> int:
294 """
295 Returns the number of attached attributes (key-value-pairs) on this node.
297 :returns: Number of attached attributes.
298 """
299 return len(self._dict)
301 @readonly
302 def Root(self) -> 'Node':
303 """
304 Read-only property to access the tree's root node (:attr:`_root`).
306 :returns: The root node (representative node) of a tree.
307 """
308 return self._root
310 @property
311 def Parent(self) -> Nullable['Node']:
312 """
313 Property to get and set the parent (:attr:`_parent`) of a node.
315 .. note::
317 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and
318 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`.
320 :returns: The parent of a node.
321 :raises TypeError: If parameter ``parent`` is not a :class:`Node`
322 :raises AlreadyInTreeError: Parent is already a child node in this tree.
323 """
324 return self._parent
326 @Parent.setter
327 def Parent(self, parent: Nullable['Node']) -> None:
328 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root
330 if parent is None:
331 self._nodesWithID = {}
332 self._nodesWithoutID = []
333 self._level = 0
335 if self._id is None:
336 self._nodesWithoutID.append(self)
337 self._root._nodesWithoutID.remove(self)
338 else:
339 self._nodesWithID[self._id] = self
340 del self._nodesWithID[self._id]
342 for sibling in self.GetDescendants():
343 sibling._root = self
344 sibling._level = sibling._parent._level + 1
345 if sibling._id is None:
346 self._nodesWithoutID.append(sibling)
347 self._root._nodesWithoutID.remove(sibling)
348 else:
349 self._nodesWithID[sibling._id] = sibling
350 del self._nodesWithID[sibling._id]
352 self._parent._children.remove(self)
354 self._root = self
355 self._parent = None
356 elif not isinstance(parent, Node):
357 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
358 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
359 raise ex
360 else:
361 if parent._root is self._root:
362 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.")
364 self._root = parent._root
365 self._parent = parent
366 self._level = parent._level + 1
367 for node in self.GetDescendants():
368 node._level = node._parent._level + 1
369 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID)
370 self._nodesWithID = self._nodesWithoutID = None
371 parent._children.append(self)
373 @readonly
374 def Siblings(self) -> Tuple['Node', ...]:
375 """
376 A read-only property to return a tuple of all siblings from the current node.
378 If the current node is the only child, the tuple is empty.
380 Siblings are child nodes of the current node's parent node, without the current node itself.
382 :returns: A tuple of all siblings of the current node.
383 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
384 """
385 if self._parent is None:
386 raise NoSiblingsError(f"Root node has no siblings.")
388 return tuple([node for node in self._parent if node is not self])
390 @readonly
391 def LeftSiblings(self) -> Tuple['Node', ...]:
392 """
393 A read-only property to return a tuple of all siblings left from the current node.
395 If the current node is the only child, the tuple is empty.
397 Siblings are child nodes of the current node's parent node, without the current node itself.
399 :returns: A tuple of all siblings left of the current node.
400 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
401 """
402 if self._parent is None:
403 raise NoSiblingsError(f"Root node has no siblings.")
405 result = []
406 for node in self._parent:
407 if node is not self:
408 result.append(node)
409 else:
410 break
411 else:
412 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
414 return tuple(result)
416 @readonly
417 def RightSiblings(self) -> Tuple['Node', ...]:
418 """
419 A read-only property to return a tuple of all siblings right from the current node.
421 If the current node is the only child, the tuple is empty.
423 Siblings are child nodes of the current node's parent node, without the current node itself.
425 :returns: A tuple of all siblings right of the current node.
426 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
427 """
428 if self._parent is None:
429 raise NoSiblingsError(f"Root node has no siblings.")
431 result = []
432 iterator = iter(self._parent)
433 for node in iterator:
434 if node is self:
435 break
436 else:
437 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
439 for node in iterator:
440 result.append(node)
442 return tuple(result)
444 def _GetPathAsLinkedList(self) -> Deque["Node"]:
445 """
446 Compute the path from current node to root node by using a linked list (:class:`deque`).
448 :meta private:
449 :returns: Path from node to root node as double-ended queue (deque).
450 """
451 path: Deque['Node'] = deque()
453 node = self
454 while node is not None:
455 path.appendleft(node)
456 node = node._parent
458 return path
460 @readonly
461 def Path(self) -> Tuple['Node']:
462 """
463 Read-only property to return the path from root node to the node as a tuple of nodes.
465 :returns: A tuple of nodes describing the path from root node to the node.
466 """
467 return tuple(self._GetPathAsLinkedList())
469 @readonly
470 def Level(self) -> int:
471 """
472 Read-only property to return a node's level in the tree.
474 The level is the distance to the root node.
476 :returns: The node's level.
477 """
478 return self._level
480 @readonly
481 def Size(self) -> int:
482 """
483 Read-only property to return the size of the tree.
485 :returns: Count of all nodes in the tree structure.
486 """
487 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID)
489 @readonly
490 def IsRoot(self) -> bool:
491 """
492 Returns true, if the node is the root node (representative node of the tree).
494 :returns: ``True``, if node is the root node.
495 """
496 return self._parent is None
498 @readonly
499 def IsLeaf(self) -> bool:
500 """
501 Returns true, if the node is a leaf node (has no children).
503 :returns: ``True``, if node has no children.
504 """
505 return len(self._children) == 0
507 @readonly
508 def HasChildren(self) -> bool:
509 """
510 Returns true, if the node has child nodes.
512 :returns: ``True``, if node has children.
513 """
514 return len(self._children) > 0
516 def _SetNewRoot(self, nodesWithIDs: Dict['Node', 'Node'], nodesWithoutIDs: List['Node']) -> None:
517 for nodeID, node in nodesWithIDs.items():
518 if nodeID in self._root._nodesWithID:
519 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
520 else:
521 self._root._nodesWithID[nodeID] = node
522 node._root = self._root
524 for node in nodesWithoutIDs:
525 self._root._nodesWithoutID.append(node)
526 node._root = self._root
528 def AddChild(self, child: 'Node') -> None:
529 """
530 Add a child node to the current node of the tree.
532 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and
533 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`).
535 :param child: The child node to be added to the tree.
536 :raises TypeError: If parameter ``child`` is not a :class:`Node`.
537 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree.
539 .. seealso::
541 :attr:`Parent` |br|
542 |rarr| Set the parent of a node.
543 :meth:`AddChildren` |br|
544 |rarr| Add multiple children at once.
545 """
546 if not isinstance(child, Node):
547 ex = TypeError(f"Parameter 'child' is not of type 'Node'.")
548 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
549 raise ex
551 if child._root is self._root:
552 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
554 child._root = self._root
555 child._parent = self
556 child._level = self._level + 1
557 for node in child.GetDescendants():
558 node._level = node._parent._level + 1
559 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
560 child._nodesWithID = child._nodesWithoutID = None
561 self._children.append(child)
563 def AddChildren(self, children: Iterable['Node']) -> None:
564 """
565 Add multiple children nodes to the current node of the tree.
567 :param children: The list of children nodes to be added to the tree.
568 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`.
569 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree.
571 .. seealso::
573 :attr:`Parent` |br|
574 |rarr| Set the parent of a node.
575 :meth:`AddChild` |br|
576 |rarr| Add a child node to the tree.
577 """
578 for child in children:
579 if not isinstance(child, Node):
580 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
581 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
582 raise ex
584 if child._root is self._root:
585 # TODO: create a more specific exception
586 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
588 child._root = self._root
589 child._parent = self
590 child._level = self._level + 1
591 for node in child.GetDescendants():
592 node._level = node._parent._level + 1
593 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
594 child._nodesWithID = child._nodesWithoutID = None
595 self._children.append(child)
597 def GetPath(self) -> Generator['Node', None, None]:
598 """
599 .. todo:: TREE::Node::GetPAth Needs documentation.
601 """
602 for node in self._GetPathAsLinkedList():
603 yield node
605 def GetAncestors(self) -> Generator['Node', None, None]:
606 """
607 .. todo:: TREE::Node::GetAncestors Needs documentation.
609 """
610 node = self._parent
611 while node is not None:
612 yield node
613 node = node._parent
615 def GetCommonAncestors(self, others: Union['Node', Iterable['Node']]) -> Generator['Node', None, None]:
616 """
617 .. todo:: TREE::Node::GetCommonAncestors Needs documentation.
619 """
620 if isinstance(others, Node):
621 # Check for trivial case
622 if others is self:
623 for node in self._GetPathAsLinkedList():
624 yield node
625 return
627 # Check if both are in the same tree.
628 if self._root is not others._root:
629 raise NotInSameTreeError(f"Node 'others' is not in the same tree.")
631 # Compute paths top-down and walk both paths until they deviate
632 for left, right in zip(self.Path, others.Path):
633 if left is right:
634 yield left
635 else:
636 return
637 elif isinstance(others, Iterable):
638 raise NotImplementedError(f"Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.")
640 def GetChildren(self) -> Generator['Node', None, None]:
641 """
642 A generator to iterate all direct children of the current node.
644 :returns: A generator to iterate all children.
646 .. seealso::
648 :meth:`GetDescendants` |br|
649 |rarr| Iterate all descendants.
650 :meth:`IterateLevelOrder` |br|
651 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
652 :meth:`IteratePreOrder` |br|
653 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
654 :meth:`IteratePostOrder` |br|
655 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
656 """
657 for child in self._children:
658 yield child
660 def GetSiblings(self) -> Generator['Node', None, None]:
661 """
662 A generator to iterate all siblings.
664 Siblings are child nodes of the current node's parent node, without the current node itself.
666 :returns: A generator to iterate all siblings of the current node.
667 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
668 """
669 if self._parent is None:
670 raise NoSiblingsError(f"Root node has no siblings.")
672 for node in self._parent:
673 if node is self:
674 continue
676 yield node
678 def GetLeftSiblings(self) -> Generator['Node', None, None]:
679 """
680 A generator to iterate all siblings left from the current node.
682 Siblings are child nodes of the current node's parent node, without the current node itself.
684 :returns: A generator to iterate all siblings left of the current node.
685 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
686 """
687 if self._parent is None:
688 raise NoSiblingsError(f"Root node has no siblings.")
690 for node in self._parent:
691 if node is self:
692 break
694 yield node
695 else:
696 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
698 def GetRightSiblings(self) -> Generator['Node', None, None]:
699 """
700 A generator to iterate all siblings right from the current node.
702 Siblings are child nodes of the current node's parent node, without the current node itself.
704 :returns: A generator to iterate all siblings right of the current node.
705 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
706 """
707 if self._parent is None:
708 raise NoSiblingsError(f"Root node has no siblings.")
710 iterator = iter(self._parent)
711 for node in iterator:
712 if node is self:
713 break
714 else:
715 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
717 for node in iterator:
718 yield node
720 def GetDescendants(self) -> Generator['Node', None, None]:
721 """
722 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder`
723 it doesn't include the node itself.
725 :returns: A generator to iterate all descendants.
727 .. seealso::
729 :meth:`GetChildren` |br|
730 |rarr| Iterate all children, but no grand-children.
731 :meth:`IterateLevelOrder` |br|
732 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
733 :meth:`IteratePreOrder` |br|
734 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
735 :meth:`IteratePostOrder` |br|
736 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
737 """
738 for child in self._children:
739 yield child
740 yield from child.GetDescendants()
742 def GetRelatives(self) -> Generator['Node', None, None]:
743 """
744 A generator to iterate all relatives (all siblings and all their descendants) of the current node.
746 :returns: A generator to iterate all relatives.
747 """
748 for node in self.GetSiblings():
749 yield node
750 yield from node.GetDescendants()
752 def GetLeftRelatives(self) -> Generator['Node', None, None]:
753 """
754 A generator to iterate all left relatives (left siblings and all their descendants) of the current node.
756 :returns: A generator to iterate all left relatives.
757 """
758 for node in self.GetLeftSiblings():
759 yield node
760 yield from node.GetDescendants()
762 def GetRightRelatives(self) -> Generator['Node', None, None]:
763 """
764 A generator to iterate all right relatives (right siblings and all their descendants) of the current node.
766 :returns: A generator to iterate all right relatives.
767 """
768 for node in self.GetRightSiblings():
769 yield node
770 yield from node.GetDescendants()
772 def IterateLeafs(self) -> Generator['Node', None, None]:
773 """
774 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.
776 :returns: A generator to iterate leaf-nodes reachable from current node.
777 """
778 for child in self._children:
779 if child.IsLeaf:
780 yield child
781 else:
782 yield from child.IterateLeafs()
784 def IterateLevelOrder(self) -> Generator['Node', None, None]:
785 """
786 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`,
787 this includes also the node itself as the first returned node.
789 :returns: A generator to iterate all siblings level-by-level.
791 .. seealso::
793 :meth:`GetChildren` |br|
794 |rarr| Iterate all children, but no grand-children.
795 :meth:`GetDescendants` |br|
796 |rarr| Iterate all descendants.
797 :meth:`IteratePreOrder` |br|
798 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
799 :meth:`IteratePostOrder` |br|
800 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
801 """
802 queue = deque([self])
803 while queue:
804 currentNode = queue.pop()
805 yield currentNode
806 for node in currentNode._children:
807 queue.appendleft(node)
809 def IteratePreOrder(self) -> Generator['Node', None, None]:
810 """
811 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes
812 also the node itself as the first returned node.
814 :returns: A generator to iterate all siblings in pre-order.
816 .. seealso::
818 :meth:`GetChildren` |br|
819 |rarr| Iterate all children, but no grand-children.
820 :meth:`GetDescendants` |br|
821 |rarr| Iterate all descendants.
822 :meth:`IterateLevelOrder` |br|
823 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
824 :meth:`IteratePostOrder` |br|
825 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
826 """
827 yield self
828 for child in self._children:
829 yield from child.IteratePreOrder()
831 def IteratePostOrder(self) -> Generator['Node', None, None]:
832 """
833 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this
834 includes also the node itself as the last returned node.
836 :returns: A generator to iterate all siblings in post-order.
838 .. seealso::
840 :meth:`GetChildren` |br|
841 |rarr| Iterate all children, but no grand-children.
842 :meth:`GetDescendants` |br|
843 |rarr| Iterate all descendants.
844 :meth:`IterateLevelOrder` |br|
845 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
846 :meth:`IteratePreOrder` |br|
847 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
848 """
849 for child in self._children:
850 yield from child.IteratePostOrder()
851 yield self
853 def WalkTo(self, other: 'Node') -> Generator['Node', None, None]:
854 """
855 Returns a generator to iterate the path from node to another node.
857 :param other: Node to walk to.
858 :returns: Generator to iterate the path from node to other node.
859 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree.
860 """
861 # Check for trivial case
862 if other is self:
863 yield from ()
865 # Check if both are in the same tree.
866 if self._root is not other._root:
867 raise NotInSameTreeError(f"Node 'other' is not in the same tree.")
869 # Compute both paths to the root.
870 # 1. Walk from self to root, until a first common ancestor is found.
871 # 2. Walk from there to other (reverse paths)
872 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk.
873 index = len(otherPath)
874 for node in self.GetAncestors():
875 try:
876 index = otherPath.index(node)
877 break
878 except ValueError:
879 yield node
881 for i in range(index, len(otherPath)):
882 yield otherPath[i]
884 def GetNodeByID(self, nodeID: IDType) -> 'Node':
885 """
886 Lookup a node by its unique ID.
888 :param nodeID: ID of a node to lookup in the tree.
889 :returns: Node for the given ID.
890 :raises ValueError: If parameter ``nodeID`` is None.
891 :raises KeyError: If parameter ``nodeID`` is not found in the tree.
892 """
893 if nodeID is None:
894 raise ValueError(f"'None' is not supported as an ID value.")
896 return self._root._nodesWithID[nodeID]
898 def Find(self, predicate: Callable) -> Generator['Node', None, None]:
899 raise NotImplementedError(f"Method 'Find' is not yet implemented.")
901 def __iter__(self) -> Iterator['Node']:
902 """
903 Returns an iterator to iterate all child nodes.
905 :returns: Children iterator.
906 """
907 return iter(self._children)
909 def __len__(self) -> int:
910 """
911 Returns the number of children, but not including grand-children.
913 :returns: Number of child nodes.
914 """
915 return len(self._children)
917 def __repr__(self) -> str:
918 """
919 Returns a detailed string representation of the node.
921 :returns: The detailed string representation of the node.
922 """
923 nodeID = parent = value = ""
924 if self._id is not None:
925 nodeID = f"; nodeID='{self._id}'"
926 if (self._parent is not None) and (self._parent._id is not None):
927 parent = f"; parent='{self._parent._id}'"
928 if self._value is not None:
929 value = f"; value='{self._value}'"
931 return f"<node{nodeID}{parent}{value}>"
933 def __str__(self) -> str:
934 """
935 Return a string representation of the node.
937 Order of resolution:
939 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
940 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
941 3. Else, return :meth:`__repr__`.
943 :returns: The resolved string representation of the node.
944 """
945 if self._value is not None:
946 return str(self._value)
947 elif self._id is not None:
948 return str(self._id)
949 else:
950 return self.__repr__()
952 def Render(
953 self,
954 prefix: str = "",
955 lineend: str = "\n",
956 nodeMarker: str = "├─",
957 lastNodeMarker: str = "└─",
958 bypassMarker: str = "│ "
959 ) -> str:
960 """
961 Render the tree as ASCII art.
963 :param prefix: A string printed in front of every line, e.g. for indentation. Default: ``""``.
964 :param lineend: A string printed at the end of every line. Default: ``"\\n"``.
965 :param nodeMarker: A string printed before every non-last tree node. Default: ``"├─"``.
966 :param lastNodeMarker: A string printed before every last tree node. Default: ``"└─"``.
967 :param bypassMarker: A string printed when there are further nodes in the parent level. Default: ``"│ "``.
968 :return: A rendered tree as multiline string.
969 """
970 emptyMarker = " " * len(bypassMarker)
972 def _render(node: Node, markers: str):
973 result = []
975 if node.HasChildren:
976 for child in node._children[:-1]:
977 nodeRepresentation = child._format(child) if child._format else str(child)
978 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}")
979 result.extend(_render(child, markers + bypassMarker))
981 # last child node
982 child = node._children[-1]
983 nodeRepresentation = child._format(child) if child._format else str(child)
984 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}")
985 result.extend(_render(child, markers + emptyMarker))
987 return result
989 # Root element
990 nodeRepresentation = self._format(self) if self._format else str(self)
991 result = [f"{prefix}{nodeRepresentation}{lineend}"]
992 result.extend(_render(self, ""))
994 return "".join(result)