Coverage for pyTooling/Tree/__init__.py: 90%
372 statements
« prev ^ index » next coverage.py v7.11.0, created at 2025-10-19 06:41 +0000
1# ==================================================================================================================== #
2# _____ _ _ _____ #
3# _ __ _ |_ _|__ ___ | (_)_ __ __ _|_ _| __ ___ ___ #
4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` | | || '__/ _ \/ _ \ #
5# | |_) | |_| || | (_) | (_) | | | | | | (_| |_| || | | __/ __/ #
6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)_||_| \___|\___| #
7# |_| |___/ |___/ #
8# ==================================================================================================================== #
9# Authors: #
10# Patrick Lehmann #
11# #
12# License: #
13# ==================================================================================================================== #
14# Copyright 2017-2025 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 sys import version_info # needed for versions before Python 3.11
34from typing import TypeVar, Generic, List, Tuple, Dict, Deque, Union, Optional as Nullable
35from typing import Callable, Iterator, Generator, Iterable, Mapping, Hashable
37try:
38 from pyTooling.Decorators import export, readonly
39 from pyTooling.MetaClasses import ExtendedType
40 from pyTooling.Exceptions import ToolingException
41 from pyTooling.Common import getFullyQualifiedName
42except (ImportError, ModuleNotFoundError): # pragma: no cover
43 print("[pyTooling.Tree] Could not import from 'pyTooling.*'!")
45 try:
46 from Decorators import export, readonly
47 from MetaClasses import ExtendedType, mixin
48 from Exceptions import ToolingException
49 from Common import getFullyQualifiedName
50 except (ImportError, ModuleNotFoundError) as ex: # pragma: no cover
51 print("[pyTooling.Tree] Could not import directly!")
52 raise ex
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:: The top-down construction should be preferred, because it's slightly faster.
124 Each tree uses the **root** node (a.k.a. tree-representative) to store some per-tree data structures. E.g. a list of
125 all IDs in a tree. For easy and quick access to such data structures, each sibling node contains a reference to the
126 root node (:attr:`_root`). In case of adding a tree to an existing tree, such data structures get merged and all added
127 nodes get assigned with new root references. Use the read-only property :attr:`Root` to access the root reference.
129 The reference to the parent node (:attr:`_parent`) can be access via property :attr:`Parent`. If the property's setter
130 is used, a node and all its siblings are added to another tree or to a new position in the same tree.
132 The references to all node's children is stored in a list (:attr:`_children`). Children, siblings, ancestors, can be
133 accessed via various generators:
135 * :meth:`GetAncestors` |rarr| iterate all ancestors bottom-up.
136 * :meth:`GetChildren` |rarr| iterate all direct children.
137 * :meth:`GetDescendants` |rarr| iterate all descendants.
138 * :meth:`IterateLevelOrder` |rarr| IterateLevelOrder.
139 * :meth:`IteratePreOrder` |rarr| iterate siblings in pre-order.
140 * :meth:`IteratePostOrder` |rarr| iterate siblings in post-order.
142 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
143 dictionary (:attr:`_nodesWithID`). In case no ID is given, all such ID-less nodes are collected in a single bin and store as a
144 list of nodes. An ID can be modified after the Node was created. Use the read-only property :attr:`ID` to access
145 the ID.
147 Each node can have a **value** (:attr:`_value`), which can be given at node creation time, or it can be assigned and/or
148 modified later. Use the property :attr:`Value` to get or set the value.
150 Moreover, each node can store various key-value-pairs (:attr:`_dict`). Use the dictionary syntax to get and set
151 key-value-pairs.
152 """
154 _id: Nullable[IDType] #: Unique identifier of a node. ``None`` if not used.
155 _nodesWithID: Nullable[Dict[IDType, 'Node']] #: Dictionary of all IDs in the tree. ``None`` if it's not the root node.
156 _nodesWithoutID: Nullable[List['Node']] #: List of all nodes without an ID in the tree. ``None`` if it's not the root node.
157 _root: 'Node' #: Reference to the root of a tree. ``self`` if it's the root node.
158 _parent: Nullable['Node'] #: Reference to the parent node. ``None`` if it's the root node.
159 _children: List['Node'] #: List of all children
160# _links: List['Node']
162 _level: int #: Level of the node (distance to the root).
163 _value: Nullable[ValueType] #: Field to store the node's value.
164 _dict: Dict[DictKeyType, DictValueType] #: Dictionary to store key-value-pairs attached to the node.
166 _format: Nullable[Callable[["Node"], str]] #: A node formatting function returning a one-line representation for tree-rendering.
168 def __init__(
169 self,
170 nodeID: Nullable[IDType] = None,
171 value: Nullable[ValueType] = None,
172 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
173 parent: 'Node' = None,
174 children: Nullable[Iterable['Node']] = None,
175 format: Nullable[Callable[["Node"], str]] = None
176 ) -> None:
177 """
178 .. todo:: TREE::Node::init Needs documentation.
180 :param nodeID: The optional unique ID of a node within the whole tree data structure.
181 :param value: The optional value of the node.
182 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
183 :param parent: The optional parent node in the tree.
184 :param children: The optional list of child nodes.
185 :param format: The optional node formatting function returning a one-line representation for tree-rendering.
187 :raises TypeError: If parameter parent is not an instance of Node.
188 :raises ValueError: If nodeID already exists in the tree.
189 :raises TypeError: If parameter children is not iterable.
190 :raises ValueError: If an element of children is not an instance of Node.
191 """
193 self._id = nodeID
194 self._value = value
195 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
197 self._format = format
199 if parent is not None and not isinstance(parent, Node):
200 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
201 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
202 raise ex
204 if parent is None:
205 self._root = self
206 self._parent = None
207 self._level = 0
209 self._nodesWithID = {}
210 self._nodesWithoutID = []
211 if nodeID is None:
212 self._nodesWithoutID.append(self)
213 else:
214 self._nodesWithID[nodeID] = self
215 else:
216 self._root = parent._root
217 self._parent = parent
218 self._level = parent._level + 1
219 self._nodesWithID = None
221 if nodeID is None:
222 self._root._nodesWithoutID.append(self)
223 elif nodeID in self._root._nodesWithID:
224 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
225 else:
226 self._root._nodesWithID[nodeID] = self
228 parent._children.append(self)
230 self._children = []
231 if children is not None:
232 if not isinstance(children, Iterable):
233 ex = TypeError("Parameter 'children' is not iterable.")
234 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.")
235 raise ex
237 for child in children:
238 if not isinstance(child, Node):
239 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
240 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
241 raise ex
243 child.Parent = self
245 @readonly
246 def ID(self) -> Nullable[IDType]:
247 """
248 Read-only property to access the unique ID of a node (:attr:`_id`).
250 If no ID was given at node construction time, ID return None.
252 :returns: Unique ID of a node, if ID was given at node creation time, else None.
253 """
254 return self._id
256 @property
257 def Value(self) -> Nullable[ValueType]:
258 """
259 Property to get and set the value (:attr:`_value`) of a node.
261 :returns: The value of a node.
262 """
263 return self._value
265 @Value.setter
266 def Value(self, value: Nullable[ValueType]) -> None:
267 self._value = value
269 def __getitem__(self, key: DictKeyType) -> DictValueType:
270 """
271 Read a node's attached attributes (key-value-pairs) by key.
273 :param key: The key to look for.
274 :returns: The value associated to the given key.
275 """
276 return self._dict[key]
278 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
279 """
280 Create or update a node's attached attributes (key-value-pairs) by key.
282 If a key doesn't exist yet, a new key-value-pair is created.
284 :param key: The key to create or update.
285 :param value: The value to associate to the given key.
286 """
287 self._dict[key] = value
289 def __delitem__(self, key: DictKeyType) -> None:
290 """
291 .. todo:: TREE::Node::__delitem__ Needs documentation.
293 """
294 del self._dict[key]
296 def __contains__(self, key: DictKeyType) -> bool:
297 """
298 .. todo:: TREE::Node::__contains__ Needs documentation.
300 """
301 return key in self._dict
303 def __len__(self) -> int:
304 """
305 Returns the number of attached attributes (key-value-pairs) on this node.
307 :returns: Number of attached attributes.
308 """
309 return len(self._dict)
311 @readonly
312 def Root(self) -> 'Node':
313 """
314 Read-only property to access the tree's root node (:attr:`_root`).
316 :returns: The root node (representative node) of a tree.
317 """
318 return self._root
320 @property
321 def Parent(self) -> Nullable['Node']:
322 """
323 Property to get and set the parent (:attr:`_parent`) of a node.
325 .. note::
327 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and
328 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`.
330 :returns: The parent of a node.
331 :raises TypeError: If parameter ``parent`` is not a :class:`Node`
332 :raises AlreadyInTreeError: Parent is already a child node in this tree.
333 """
334 return self._parent
336 @Parent.setter
337 def Parent(self, parent: Nullable['Node']) -> None:
338 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root
340 if parent is None:
341 self._nodesWithID = {}
342 self._nodesWithoutID = []
343 self._level = 0
345 if self._id is None:
346 self._nodesWithoutID.append(self)
347 self._root._nodesWithoutID.remove(self)
348 else:
349 self._nodesWithID[self._id] = self
350 del self._nodesWithID[self._id]
352 for sibling in self.GetDescendants():
353 sibling._root = self
354 sibling._level = sibling._parent._level + 1
355 if sibling._id is None:
356 self._nodesWithoutID.append(sibling)
357 self._root._nodesWithoutID.remove(sibling)
358 else:
359 self._nodesWithID[sibling._id] = sibling
360 del self._nodesWithID[sibling._id]
362 self._parent._children.remove(self)
364 self._root = self
365 self._parent = None
366 elif not isinstance(parent, Node):
367 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
368 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
369 raise ex
370 else:
371 if parent._root is self._root:
372 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.")
374 self._root = parent._root
375 self._parent = parent
376 self._level = parent._level + 1
377 for node in self.GetDescendants():
378 node._level = node._parent._level + 1
379 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID)
380 self._nodesWithID = self._nodesWithoutID = None
381 parent._children.append(self)
383 @readonly
384 def Siblings(self) -> Tuple['Node', ...]:
385 """
386 A read-only property to return a tuple of all siblings from the current node.
388 If the current node is the only child, the tuple is empty.
390 Siblings are child nodes of the current node's parent node, without the current node itself.
392 :returns: A tuple of all siblings of the current node.
393 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
394 """
395 if self._parent is None:
396 raise NoSiblingsError(f"Root node has no siblings.")
398 return tuple([node for node in self._parent if node is not self])
400 @readonly
401 def LeftSiblings(self) -> Tuple['Node', ...]:
402 """
403 A read-only property to return a tuple of all siblings left from the current node.
405 If the current node is the only child, the tuple is empty.
407 Siblings are child nodes of the current node's parent node, without the current node itself.
409 :returns: A tuple of all siblings left of the current node.
410 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
411 """
412 if self._parent is None:
413 raise NoSiblingsError(f"Root node has no siblings.")
415 result = []
416 for node in self._parent:
417 if node is not self:
418 result.append(node)
419 else:
420 break
421 else:
422 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
424 return tuple(result)
426 @readonly
427 def RightSiblings(self) -> Tuple['Node', ...]:
428 """
429 A read-only property to return a tuple of all siblings right from the current node.
431 If the current node is the only child, the tuple is empty.
433 Siblings are child nodes of the current node's parent node, without the current node itself.
435 :returns: A tuple of all siblings right of the current node.
436 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
437 """
438 if self._parent is None:
439 raise NoSiblingsError(f"Root node has no siblings.")
441 result = []
442 iterator = iter(self._parent)
443 for node in iterator:
444 if node is self:
445 break
446 else:
447 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
449 for node in iterator:
450 result.append(node)
452 return tuple(result)
454 def _GetPathAsLinkedList(self) -> Deque["Node"]:
455 """
456 Compute the path from current node to root node by using a linked list (:class:`deque`).
458 :meta private:
459 :returns: Path from node to root node as double-ended queue (deque).
460 """
461 path: Deque['Node'] = deque()
463 node = self
464 while node is not None:
465 path.appendleft(node)
466 node = node._parent
468 return path
470 @readonly
471 def Path(self) -> Tuple['Node']:
472 """
473 Read-only property to return the path from root node to the node as a tuple of nodes.
475 :returns: A tuple of nodes describing the path from root node to the node.
476 """
477 return tuple(self._GetPathAsLinkedList())
479 @readonly
480 def Level(self) -> int:
481 """
482 Read-only property to return a node's level in the tree.
484 The level is the distance to the root node.
486 :returns: The node's level.
487 """
488 return self._level
490 @readonly
491 def Size(self) -> int:
492 """
493 Read-only property to return the size of the tree.
495 :returns: Count of all nodes in the tree structure.
496 """
497 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID)
499 @readonly
500 def IsRoot(self) -> bool:
501 """
502 Returns true, if the node is the root node (representative node of the tree).
504 :returns: ``True``, if node is the root node.
505 """
506 return self._parent is None
508 @readonly
509 def IsLeaf(self) -> bool:
510 """
511 Returns true, if the node is a leaf node (has no children).
513 :returns: ``True``, if node has no children.
514 """
515 return len(self._children) == 0
517 @readonly
518 def HasChildren(self) -> bool:
519 """
520 Returns true, if the node has child nodes.
522 :returns: ``True``, if node has children.
523 """
524 return len(self._children) > 0
526 def _SetNewRoot(self, nodesWithIDs: Dict['Node', 'Node'], nodesWithoutIDs: List['Node']) -> None:
527 for nodeID, node in nodesWithIDs.items():
528 if nodeID in self._root._nodesWithID:
529 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
530 else:
531 self._root._nodesWithID[nodeID] = node
532 node._root = self._root
534 for node in nodesWithoutIDs:
535 self._root._nodesWithoutID.append(node)
536 node._root = self._root
538 def AddChild(self, child: 'Node'):
539 """
540 Add a child node to the current node of the tree.
542 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and
543 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`).
545 :param child: The child node to be added to the tree.
546 :raises TypeError: If parameter ``child`` is not a :class:`Node`.
547 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree.
549 .. seealso::
551 :attr:`Parent` |br|
552 |rarr| Set the parent of a node.
553 :meth:`AddChildren` |br|
554 |rarr| Add multiple children at once.
555 """
556 if not isinstance(child, Node):
557 ex = TypeError(f"Parameter 'child' is not of type 'Node'.")
558 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
559 raise ex
561 if child._root is self._root:
562 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
564 child._root = self._root
565 child._parent = self
566 child._level = self._level + 1
567 for node in child.GetDescendants():
568 node._level = node._parent._level + 1
569 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
570 child._nodesWithID = child._nodesWithoutID = None
571 self._children.append(child)
573 def AddChildren(self, children: Iterable['Node']):
574 """
575 Add multiple children nodes to the current node of the tree.
577 :param children: The list of children nodes to be added to the tree.
578 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`.
579 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree.
581 .. seealso::
583 :attr:`Parent` |br|
584 |rarr| Set the parent of a node.
585 :meth:`AddChild` |br|
586 |rarr| Add a child node to the tree.
587 """
588 for child in children:
589 if not isinstance(child, Node):
590 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
591 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
592 raise ex
594 if child._root is self._root:
595 # TODO: create a more specific exception
596 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
598 child._root = self._root
599 child._parent = self
600 child._level = self._level + 1
601 for node in child.GetDescendants():
602 node._level = node._parent._level + 1
603 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
604 child._nodesWithID = child._nodesWithoutID = None
605 self._children.append(child)
607 def GetPath(self) -> Generator['Node', None, None]:
608 """
609 .. todo:: TREE::Node::GetPAth Needs documentation.
611 """
612 for node in self._GetPathAsLinkedList():
613 yield node
615 def GetAncestors(self) -> Generator['Node', None, None]:
616 """
617 .. todo:: TREE::Node::GetAncestors Needs documentation.
619 """
620 node = self._parent
621 while node is not None:
622 yield node
623 node = node._parent
625 def GetCommonAncestors(self, others: Union['Node', Iterable['Node']]) -> Generator['Node', None, None]:
626 """
627 .. todo:: TREE::Node::GetCommonAncestors Needs documentation.
629 """
630 if isinstance(others, Node):
631 # Check for trivial case
632 if others is self:
633 for node in self._GetPathAsLinkedList():
634 yield node
635 return
637 # Check if both are in the same tree.
638 if self._root is not others._root:
639 raise NotInSameTreeError(f"Node 'others' is not in the same tree.")
641 # Compute paths top-down and walk both paths until they deviate
642 for left, right in zip(self.Path, others.Path):
643 if left is right:
644 yield left
645 else:
646 return
647 elif isinstance(others, Iterable):
648 raise NotImplementedError(f"Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.")
650 def GetChildren(self) -> Generator['Node', None, None]:
651 """
652 A generator to iterate all direct children of the current node.
654 :returns: A generator to iterate all children.
656 .. seealso::
658 :meth:`GetDescendants` |br|
659 |rarr| Iterate all descendants.
660 :meth:`IterateLevelOrder` |br|
661 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
662 :meth:`IteratePreOrder` |br|
663 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
664 :meth:`IteratePostOrder` |br|
665 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
666 """
667 for child in self._children:
668 yield child
670 def GetSiblings(self) -> Generator['Node', None, None]:
671 """
672 A generator to iterate all siblings.
674 Siblings are child nodes of the current node's parent node, without the current node itself.
676 :returns: A generator to iterate all siblings of the current node.
677 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
678 """
679 if self._parent is None:
680 raise NoSiblingsError(f"Root node has no siblings.")
682 for node in self._parent:
683 if node is self:
684 continue
686 yield node
688 def GetLeftSiblings(self) -> Generator['Node', None, None]:
689 """
690 A generator to iterate all siblings left from the current node.
692 Siblings are child nodes of the current node's parent node, without the current node itself.
694 :returns: A generator to iterate all siblings left of the current node.
695 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
696 """
697 if self._parent is None:
698 raise NoSiblingsError(f"Root node has no siblings.")
700 for node in self._parent:
701 if node is self:
702 break
704 yield node
705 else:
706 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
708 def GetRightSiblings(self) -> Generator['Node', None, None]:
709 """
710 A generator to iterate all siblings right from the current node.
712 Siblings are child nodes of the current node's parent node, without the current node itself.
714 :returns: A generator to iterate all siblings right of the current node.
715 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
716 """
717 if self._parent is None:
718 raise NoSiblingsError(f"Root node has no siblings.")
720 iterator = iter(self._parent)
721 for node in iterator:
722 if node is self:
723 break
724 else:
725 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
727 for node in iterator:
728 yield node
730 def GetDescendants(self) -> Generator['Node', None, None]:
731 """
732 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder`
733 it doesn't include the node itself.
735 :returns: A generator to iterate all descendants.
737 .. seealso::
739 :meth:`GetChildren` |br|
740 |rarr| Iterate all children, but no grand-children.
741 :meth:`IterateLevelOrder` |br|
742 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
743 :meth:`IteratePreOrder` |br|
744 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
745 :meth:`IteratePostOrder` |br|
746 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
747 """
748 for child in self._children:
749 yield child
750 yield from child.GetDescendants()
752 def GetRelatives(self):
753 """
754 A generator to iterate all relatives (all siblings and all their descendants) of the current node.
756 :returns: A generator to iterate all relatives.
757 """
758 for node in self.GetSiblings():
759 yield node
760 yield from node.GetDescendants()
762 def GetLeftRelatives(self):
763 """
764 A generator to iterate all left relatives (left siblings and all their descendants) of the current node.
766 :returns: A generator to iterate all left relatives.
767 """
768 for node in self.GetLeftSiblings():
769 yield node
770 yield from node.GetDescendants()
772 def GetRightRelatives(self):
773 """
774 A generator to iterate all right relatives (right siblings and all their descendants) of the current node.
776 :returns: A generator to iterate all right relatives.
777 """
778 for node in self.GetRightSiblings():
779 yield node
780 yield from node.GetDescendants()
782 def IterateLeafs(self) -> Generator['Node', None, None]:
783 """
784 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.
786 :returns: A generator to iterate leaf-nodes reachable from current node.
787 """
788 for child in self._children:
789 if child.IsLeaf:
790 yield child
791 else:
792 yield from child.IterateLeafs()
794 def IterateLevelOrder(self) -> Generator['Node', None, None]:
795 """
796 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`,
797 this includes also the node itself as the first returned node.
799 :returns: A generator to iterate all siblings level-by-level.
801 .. seealso::
803 :meth:`GetChildren` |br|
804 |rarr| Iterate all children, but no grand-children.
805 :meth:`GetDescendants` |br|
806 |rarr| Iterate all descendants.
807 :meth:`IteratePreOrder` |br|
808 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
809 :meth:`IteratePostOrder` |br|
810 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
811 """
812 queue = deque([self])
813 while queue:
814 currentNode = queue.pop()
815 yield currentNode
816 for node in currentNode._children:
817 queue.appendleft(node)
819 def IteratePreOrder(self) -> Generator['Node', None, None]:
820 """
821 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes
822 also the node itself as the first returned node.
824 :returns: A generator to iterate all siblings in pre-order.
826 .. seealso::
828 :meth:`GetChildren` |br|
829 |rarr| Iterate all children, but no grand-children.
830 :meth:`GetDescendants` |br|
831 |rarr| Iterate all descendants.
832 :meth:`IterateLevelOrder` |br|
833 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
834 :meth:`IteratePostOrder` |br|
835 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
836 """
837 yield self
838 for child in self._children:
839 yield from child.IteratePreOrder()
841 def IteratePostOrder(self) -> Generator['Node', None, None]:
842 """
843 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this
844 includes also the node itself as the last returned node.
846 :returns: A generator to iterate all siblings in post-order.
848 .. seealso::
850 :meth:`GetChildren` |br|
851 |rarr| Iterate all children, but no grand-children.
852 :meth:`GetDescendants` |br|
853 |rarr| Iterate all descendants.
854 :meth:`IterateLevelOrder` |br|
855 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
856 :meth:`IteratePreOrder` |br|
857 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
858 """
859 for child in self._children:
860 yield from child.IteratePostOrder()
861 yield self
863 def WalkTo(self, other: 'Node') -> Generator['Node', None, None]:
864 """
865 Returns a generator to iterate the path from node to another node.
867 :param other: Node to walk to.
868 :returns: Generator to iterate the path from node to other node.
869 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree.
870 """
871 # Check for trivial case
872 if other is self:
873 yield from ()
875 # Check if both are in the same tree.
876 if self._root is not other._root:
877 raise NotInSameTreeError(f"Node 'other' is not in the same tree.")
879 # Compute both paths to the root.
880 # 1. Walk from self to root, until a first common ancestor is found.
881 # 2. Walk from there to other (reverse paths)
882 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk.
883 index = len(otherPath)
884 for node in self.GetAncestors():
885 try:
886 index = otherPath.index(node)
887 break
888 except ValueError:
889 yield node
891 for i in range(index, len(otherPath)):
892 yield otherPath[i]
894 def GetNodeByID(self, nodeID: IDType) -> 'Node':
895 """
896 Lookup a node by its unique ID.
898 :param nodeID: ID of a node to lookup in the tree.
899 :returns: Node for the given ID.
900 :raises ValueError: If parameter ``nodeID`` is None.
901 :raises KeyError: If parameter ``nodeID`` is not found in the tree.
902 """
903 if nodeID is None:
904 raise ValueError(f"'None' is not supported as an ID value.")
906 return self._root._nodesWithID[nodeID]
908 def Find(self, predicate: Callable) -> Generator['Node', None, None]:
909 raise NotImplementedError(f"Method 'Find' is not yet implemented.")
911 def __iter__(self) -> Iterator['Node']:
912 """
913 Returns an iterator to iterate all child nodes.
915 :returns: Children iterator.
916 """
917 return iter(self._children)
919 def __len__(self) -> int:
920 """
921 Returns the number of children, but not including grand-children.
923 :returns: Number of child nodes.
924 """
925 return len(self._children)
927 def __repr__(self) -> str:
928 """
929 Returns a detailed string representation of the node.
931 :returns: The detailed string representation of the node.
932 """
933 nodeID = parent = value = ""
934 if self._id is not None:
935 nodeID = f"; nodeID='{self._id}'"
936 if (self._parent is not None) and (self._parent._id is not None):
937 parent = f"; parent='{self._parent._id}'"
938 if self._value is not None:
939 value = f"; value='{self._value}'"
941 return f"<node{nodeID}{parent}{value}>"
943 def __str__(self) -> str:
944 """
945 Return a string representation of the node.
947 Order of resolution:
949 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
950 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
951 3. Else, return :meth:`__repr__`.
953 :returns: The resolved string representation of the node.
954 """
955 if self._value is not None:
956 return str(self._value)
957 elif self._id is not None:
958 return str(self._id)
959 else:
960 return self.__repr__()
962 def Render(
963 self,
964 prefix: str = "",
965 lineend: str = "\n",
966 nodeMarker: str = "├─",
967 lastNodeMarker: str = "└─",
968 bypassMarker: str = "│ "
969 ) -> str:
970 """
971 Render the tree as ASCII art.
973 :param prefix: A string printed in front of every line, e.g. for indentation. Default: ``""``.
974 :param lineend: A string printed at the end of every line. Default: ``"\\n"``.
975 :param nodeMarker: A string printed before every non-last tree node. Default: ``"├─"``.
976 :param lastNodeMarker: A string printed before every last tree node. Default: ``"└─"``.
977 :param bypassMarker: A string printed when there are further nodes in the parent level. Default: ``"│ "``.
978 :return: A rendered tree as multiline string.
979 """
980 emptyMarker = " " * len(bypassMarker)
982 def _render(node: Node, markers: str):
983 result = []
985 if node.HasChildren:
986 for child in node._children[:-1]:
987 nodeRepresentation = child._format(child) if child._format else str(child)
988 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}")
989 result.extend(_render(child, markers + bypassMarker))
991 # last child node
992 child = node._children[-1]
993 nodeRepresentation = child._format(child) if child._format else str(child)
994 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}")
995 result.extend(_render(child, markers + emptyMarker))
997 return result
999 # Root element
1000 nodeRepresentation = self._format(self) if self._format else str(self)
1001 result = [f"{prefix}{nodeRepresentation}{lineend}"]
1002 result.extend(_render(self, ""))
1004 return "".join(result)