Coverage for pyTooling / Tree / __init__.py: 90%
372 statements
« prev ^ index » next coverage.py v7.13.1, created at 2026-01-08 23:46 +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
36try:
37 from pyTooling.Decorators import export, readonly
38 from pyTooling.MetaClasses import ExtendedType
39 from pyTooling.Exceptions import ToolingException
40 from pyTooling.Common import getFullyQualifiedName
41except (ImportError, ModuleNotFoundError): # pragma: no cover
42 print("[pyTooling.Tree] Could not import from 'pyTooling.*'!")
44 try:
45 from Decorators import export, readonly
46 from MetaClasses import ExtendedType, mixin
47 from Exceptions import ToolingException
48 from Common import getFullyQualifiedName
49 except (ImportError, ModuleNotFoundError) as ex: # pragma: no cover
50 print("[pyTooling.Tree] Could not import directly!")
51 raise ex
54IDType = TypeVar("IDType", bound=Hashable)
55"""A type variable for a tree's ID."""
57ValueType = TypeVar("ValueType")
58"""A type variable for a tree's value."""
60DictKeyType = TypeVar("DictKeyType")
61"""A type variable for a tree's dictionary keys."""
63DictValueType = TypeVar("DictValueType")
64"""A type variable for a tree's dictionary values."""
67@export
68class TreeException(ToolingException):
69 """Base exception of all exceptions raised by :mod:`pyTooling.Tree`."""
72@export
73class InternalError(TreeException):
74 """
75 The exception is raised when a data structure corruption is detected.
77 .. danger::
79 This exception should never be raised.
81 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|
82 `⇒ Bug Tracker at GitHub <https://github.com/pyTooling/pyTooling/issues>`__
83 """
86@export
87class NoSiblingsError(TreeException):
88 """
89 The exception is raised when a node has no parent and thus has no siblings.
91 .. hint::
93 A node with no parent is the root node of the tree.
94 """
97@export
98class AlreadyInTreeError(TreeException):
99 """
100 The exception is raised when the current node and the other node are already in the same tree.
102 .. hint::
104 A tree a an acyclic graph without cross-edges. Thus backward edges and cross edges are permitted.
105 """
108@export
109class NotInSameTreeError(TreeException):
110 """The exception is raised when the current node and the other node are not in the same tree."""
113@export
114class Node(Generic[IDType, ValueType, DictKeyType, DictValueType], metaclass=ExtendedType, slots=True):
115 """
116 A **tree** data structure can be constructed of ``Node`` instances.
118 Therefore, nodes can be connected to parent nodes or a parent node can add child nodes. This allows to construct a
119 tree top-down or bottom-up.
121 .. hint::
123 The top-down construction should be preferred, because it's slightly faster.
125 Each tree uses the **root** node (a.k.a. tree-representative) to store some per-tree data structures. E.g. a list of
126 all IDs in a tree. For easy and quick access to such data structures, each sibling node contains a reference to the
127 root node (:attr:`_root`). In case of adding a tree to an existing tree, such data structures get merged and all added
128 nodes get assigned with new root references. Use the read-only property :attr:`Root` to access the root reference.
130 The reference to the parent node (:attr:`_parent`) can be access via property :attr:`Parent`. If the property's setter
131 is used, a node and all its siblings are added to another tree or to a new position in the same tree.
133 The references to all node's children is stored in a list (:attr:`_children`). Children, siblings, ancestors, can be
134 accessed via various generators:
136 * :meth:`GetAncestors` |rarr| iterate all ancestors bottom-up.
137 * :meth:`GetChildren` |rarr| iterate all direct children.
138 * :meth:`GetDescendants` |rarr| iterate all descendants.
139 * :meth:`IterateLevelOrder` |rarr| IterateLevelOrder.
140 * :meth:`IteratePreOrder` |rarr| iterate siblings in pre-order.
141 * :meth:`IteratePostOrder` |rarr| iterate siblings in post-order.
143 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
144 dictionary (:attr:`_nodesWithID`). In case no ID is given, all such ID-less nodes are collected in a single bin and store as a
145 list of nodes. An ID can be modified after the Node was created. Use the read-only property :attr:`ID` to access
146 the ID.
148 Each node can have a **value** (:attr:`_value`), which can be given at node creation time, or it can be assigned and/or
149 modified later. Use the property :attr:`Value` to get or set the value.
151 Moreover, each node can store various key-value-pairs (:attr:`_dict`). Use the dictionary syntax to get and set
152 key-value-pairs.
153 """
155 _id: Nullable[IDType] #: Unique identifier of a node. ``None`` if not used.
156 _nodesWithID: Nullable[Dict[IDType, 'Node']] #: Dictionary of all IDs in the tree. ``None`` if it's not the root node.
157 _nodesWithoutID: Nullable[List['Node']] #: List of all nodes without an ID in the tree. ``None`` if it's not the root node.
158 _root: 'Node' #: Reference to the root of a tree. ``self`` if it's the root node.
159 _parent: Nullable['Node'] #: Reference to the parent node. ``None`` if it's the root node.
160 _children: List['Node'] #: List of all children
161# _links: List['Node']
163 _level: int #: Level of the node (distance to the root).
164 _value: Nullable[ValueType] #: Field to store the node's value.
165 _dict: Dict[DictKeyType, DictValueType] #: Dictionary to store key-value-pairs attached to the node.
167 _format: Nullable[Callable[["Node"], str]] #: A node formatting function returning a one-line representation for tree-rendering.
169 def __init__(
170 self,
171 nodeID: Nullable[IDType] = None,
172 value: Nullable[ValueType] = None,
173 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
174 parent: 'Node' = None,
175 children: Nullable[Iterable['Node']] = None,
176 format: Nullable[Callable[["Node"], str]] = None
177 ) -> None:
178 """
179 .. todo:: TREE::Node::init Needs documentation.
181 :param nodeID: The optional unique ID of a node within the whole tree data structure.
182 :param value: The optional value of the node.
183 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
184 :param parent: The optional parent node in the tree.
185 :param children: The optional list of child nodes.
186 :param format: The optional node formatting function returning a one-line representation for tree-rendering.
188 :raises TypeError: If parameter parent is not an instance of Node.
189 :raises ValueError: If nodeID already exists in the tree.
190 :raises TypeError: If parameter children is not iterable.
191 :raises ValueError: If an element of children is not an instance of Node.
192 """
194 self._id = nodeID
195 self._value = value
196 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
198 self._format = format
200 if parent is not None and not isinstance(parent, Node):
201 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
202 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
203 raise ex
205 if parent is None:
206 self._root = self
207 self._parent = None
208 self._level = 0
210 self._nodesWithID = {}
211 self._nodesWithoutID = []
212 if nodeID is None:
213 self._nodesWithoutID.append(self)
214 else:
215 self._nodesWithID[nodeID] = self
216 else:
217 self._root = parent._root
218 self._parent = parent
219 self._level = parent._level + 1
220 self._nodesWithID = None
221 self._nodesWithoutID = None
223 if nodeID is None:
224 self._root._nodesWithoutID.append(self)
225 elif nodeID in self._root._nodesWithID:
226 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
227 else:
228 self._root._nodesWithID[nodeID] = self
230 parent._children.append(self)
232 self._children = []
233 if children is not None:
234 if not isinstance(children, Iterable):
235 ex = TypeError("Parameter 'children' is not iterable.")
236 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.")
237 raise ex
239 for child in children:
240 if not isinstance(child, Node):
241 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
242 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
243 raise ex
245 child.Parent = self
247 @readonly
248 def ID(self) -> Nullable[IDType]:
249 """
250 Read-only property to access the unique ID of a node (:attr:`_id`).
252 If no ID was given at node construction time, ID return None.
254 :returns: Unique ID of a node, if ID was given at node creation time, else None.
255 """
256 return self._id
258 @property
259 def Value(self) -> Nullable[ValueType]:
260 """
261 Property to get and set the value (:attr:`_value`) of a node.
263 :returns: The value of a node.
264 """
265 return self._value
267 @Value.setter
268 def Value(self, value: Nullable[ValueType]) -> None:
269 self._value = value
271 def __getitem__(self, key: DictKeyType) -> DictValueType:
272 """
273 Read a node's attached attributes (key-value-pairs) by key.
275 :param key: The key to look for.
276 :returns: The value associated to the given key.
277 """
278 return self._dict[key]
280 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
281 """
282 Create or update a node's attached attributes (key-value-pairs) by key.
284 If a key doesn't exist yet, a new key-value-pair is created.
286 :param key: The key to create or update.
287 :param value: The value to associate to the given key.
288 """
289 self._dict[key] = value
291 def __delitem__(self, key: DictKeyType) -> None:
292 """
293 .. todo:: TREE::Node::__delitem__ Needs documentation.
295 """
296 del self._dict[key]
298 def __contains__(self, key: DictKeyType) -> bool:
299 """
300 .. todo:: TREE::Node::__contains__ Needs documentation.
302 """
303 return key in self._dict
305 def __len__(self) -> int:
306 """
307 Returns the number of attached attributes (key-value-pairs) on this node.
309 :returns: Number of attached attributes.
310 """
311 return len(self._dict)
313 @readonly
314 def Root(self) -> 'Node':
315 """
316 Read-only property to access the tree's root node (:attr:`_root`).
318 :returns: The root node (representative node) of a tree.
319 """
320 return self._root
322 @property
323 def Parent(self) -> Nullable['Node']:
324 """
325 Property to get and set the parent (:attr:`_parent`) of a node.
327 .. note::
329 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and
330 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`.
332 :returns: The parent of a node.
333 :raises TypeError: If parameter ``parent`` is not a :class:`Node`
334 :raises AlreadyInTreeError: Parent is already a child node in this tree.
335 """
336 return self._parent
338 @Parent.setter
339 def Parent(self, parent: Nullable['Node']) -> None:
340 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root
342 if parent is None:
343 self._nodesWithID = {}
344 self._nodesWithoutID = []
345 self._level = 0
347 if self._id is None:
348 self._nodesWithoutID.append(self)
349 self._root._nodesWithoutID.remove(self)
350 else:
351 self._nodesWithID[self._id] = self
352 del self._nodesWithID[self._id]
354 for sibling in self.GetDescendants():
355 sibling._root = self
356 sibling._level = sibling._parent._level + 1
357 if sibling._id is None:
358 self._nodesWithoutID.append(sibling)
359 self._root._nodesWithoutID.remove(sibling)
360 else:
361 self._nodesWithID[sibling._id] = sibling
362 del self._nodesWithID[sibling._id]
364 self._parent._children.remove(self)
366 self._root = self
367 self._parent = None
368 elif not isinstance(parent, Node):
369 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
370 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
371 raise ex
372 else:
373 if parent._root is self._root:
374 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.")
376 self._root = parent._root
377 self._parent = parent
378 self._level = parent._level + 1
379 for node in self.GetDescendants():
380 node._level = node._parent._level + 1
381 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID)
382 self._nodesWithID = self._nodesWithoutID = None
383 parent._children.append(self)
385 @readonly
386 def Siblings(self) -> Tuple['Node', ...]:
387 """
388 A read-only property to return a tuple of all siblings from the current node.
390 If the current node is the only child, the tuple is empty.
392 Siblings are child nodes of the current node's parent node, without the current node itself.
394 :returns: A tuple of all siblings of the current node.
395 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
396 """
397 if self._parent is None:
398 raise NoSiblingsError(f"Root node has no siblings.")
400 return tuple([node for node in self._parent if node is not self])
402 @readonly
403 def LeftSiblings(self) -> Tuple['Node', ...]:
404 """
405 A read-only property to return a tuple of all siblings left from the current node.
407 If the current node is the only child, the tuple is empty.
409 Siblings are child nodes of the current node's parent node, without the current node itself.
411 :returns: A tuple of all siblings left of the current node.
412 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
413 """
414 if self._parent is None:
415 raise NoSiblingsError(f"Root node has no siblings.")
417 result = []
418 for node in self._parent:
419 if node is not self:
420 result.append(node)
421 else:
422 break
423 else:
424 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
426 return tuple(result)
428 @readonly
429 def RightSiblings(self) -> Tuple['Node', ...]:
430 """
431 A read-only property to return a tuple of all siblings right from the current node.
433 If the current node is the only child, the tuple is empty.
435 Siblings are child nodes of the current node's parent node, without the current node itself.
437 :returns: A tuple of all siblings right of the current node.
438 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
439 """
440 if self._parent is None:
441 raise NoSiblingsError(f"Root node has no siblings.")
443 result = []
444 iterator = iter(self._parent)
445 for node in iterator:
446 if node is self:
447 break
448 else:
449 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
451 for node in iterator:
452 result.append(node)
454 return tuple(result)
456 def _GetPathAsLinkedList(self) -> Deque["Node"]:
457 """
458 Compute the path from current node to root node by using a linked list (:class:`deque`).
460 :meta private:
461 :returns: Path from node to root node as double-ended queue (deque).
462 """
463 path: Deque['Node'] = deque()
465 node = self
466 while node is not None:
467 path.appendleft(node)
468 node = node._parent
470 return path
472 @readonly
473 def Path(self) -> Tuple['Node']:
474 """
475 Read-only property to return the path from root node to the node as a tuple of nodes.
477 :returns: A tuple of nodes describing the path from root node to the node.
478 """
479 return tuple(self._GetPathAsLinkedList())
481 @readonly
482 def Level(self) -> int:
483 """
484 Read-only property to return a node's level in the tree.
486 The level is the distance to the root node.
488 :returns: The node's level.
489 """
490 return self._level
492 @readonly
493 def Size(self) -> int:
494 """
495 Read-only property to return the size of the tree.
497 :returns: Count of all nodes in the tree structure.
498 """
499 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID)
501 @readonly
502 def IsRoot(self) -> bool:
503 """
504 Returns true, if the node is the root node (representative node of the tree).
506 :returns: ``True``, if node is the root node.
507 """
508 return self._parent is None
510 @readonly
511 def IsLeaf(self) -> bool:
512 """
513 Returns true, if the node is a leaf node (has no children).
515 :returns: ``True``, if node has no children.
516 """
517 return len(self._children) == 0
519 @readonly
520 def HasChildren(self) -> bool:
521 """
522 Returns true, if the node has child nodes.
524 :returns: ``True``, if node has children.
525 """
526 return len(self._children) > 0
528 def _SetNewRoot(self, nodesWithIDs: Dict['Node', 'Node'], nodesWithoutIDs: List['Node']) -> None:
529 for nodeID, node in nodesWithIDs.items():
530 if nodeID in self._root._nodesWithID:
531 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
532 else:
533 self._root._nodesWithID[nodeID] = node
534 node._root = self._root
536 for node in nodesWithoutIDs:
537 self._root._nodesWithoutID.append(node)
538 node._root = self._root
540 def AddChild(self, child: 'Node') -> None:
541 """
542 Add a child node to the current node of the tree.
544 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and
545 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`).
547 :param child: The child node to be added to the tree.
548 :raises TypeError: If parameter ``child`` is not a :class:`Node`.
549 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree.
551 .. seealso::
553 :attr:`Parent` |br|
554 |rarr| Set the parent of a node.
555 :meth:`AddChildren` |br|
556 |rarr| Add multiple children at once.
557 """
558 if not isinstance(child, Node):
559 ex = TypeError(f"Parameter 'child' is not of type 'Node'.")
560 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
561 raise ex
563 if child._root is self._root:
564 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
566 child._root = self._root
567 child._parent = self
568 child._level = self._level + 1
569 for node in child.GetDescendants():
570 node._level = node._parent._level + 1
571 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
572 child._nodesWithID = child._nodesWithoutID = None
573 self._children.append(child)
575 def AddChildren(self, children: Iterable['Node']) -> None:
576 """
577 Add multiple children nodes to the current node of the tree.
579 :param children: The list of children nodes to be added to the tree.
580 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`.
581 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree.
583 .. seealso::
585 :attr:`Parent` |br|
586 |rarr| Set the parent of a node.
587 :meth:`AddChild` |br|
588 |rarr| Add a child node to the tree.
589 """
590 for child in children:
591 if not isinstance(child, Node):
592 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
593 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
594 raise ex
596 if child._root is self._root:
597 # TODO: create a more specific exception
598 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
600 child._root = self._root
601 child._parent = self
602 child._level = self._level + 1
603 for node in child.GetDescendants():
604 node._level = node._parent._level + 1
605 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
606 child._nodesWithID = child._nodesWithoutID = None
607 self._children.append(child)
609 def GetPath(self) -> Generator['Node', None, None]:
610 """
611 .. todo:: TREE::Node::GetPAth Needs documentation.
613 """
614 for node in self._GetPathAsLinkedList():
615 yield node
617 def GetAncestors(self) -> Generator['Node', None, None]:
618 """
619 .. todo:: TREE::Node::GetAncestors Needs documentation.
621 """
622 node = self._parent
623 while node is not None:
624 yield node
625 node = node._parent
627 def GetCommonAncestors(self, others: Union['Node', Iterable['Node']]) -> Generator['Node', None, None]:
628 """
629 .. todo:: TREE::Node::GetCommonAncestors Needs documentation.
631 """
632 if isinstance(others, Node):
633 # Check for trivial case
634 if others is self:
635 for node in self._GetPathAsLinkedList():
636 yield node
637 return
639 # Check if both are in the same tree.
640 if self._root is not others._root:
641 raise NotInSameTreeError(f"Node 'others' is not in the same tree.")
643 # Compute paths top-down and walk both paths until they deviate
644 for left, right in zip(self.Path, others.Path):
645 if left is right:
646 yield left
647 else:
648 return
649 elif isinstance(others, Iterable):
650 raise NotImplementedError(f"Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.")
652 def GetChildren(self) -> Generator['Node', None, None]:
653 """
654 A generator to iterate all direct children of the current node.
656 :returns: A generator to iterate all children.
658 .. seealso::
660 :meth:`GetDescendants` |br|
661 |rarr| Iterate all descendants.
662 :meth:`IterateLevelOrder` |br|
663 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
664 :meth:`IteratePreOrder` |br|
665 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
666 :meth:`IteratePostOrder` |br|
667 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
668 """
669 for child in self._children:
670 yield child
672 def GetSiblings(self) -> Generator['Node', None, None]:
673 """
674 A generator to iterate all siblings.
676 Siblings are child nodes of the current node's parent node, without the current node itself.
678 :returns: A generator to iterate all siblings of the current node.
679 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
680 """
681 if self._parent is None:
682 raise NoSiblingsError(f"Root node has no siblings.")
684 for node in self._parent:
685 if node is self:
686 continue
688 yield node
690 def GetLeftSiblings(self) -> Generator['Node', None, None]:
691 """
692 A generator to iterate all siblings left from the current node.
694 Siblings are child nodes of the current node's parent node, without the current node itself.
696 :returns: A generator to iterate all siblings left of the current node.
697 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
698 """
699 if self._parent is None:
700 raise NoSiblingsError(f"Root node has no siblings.")
702 for node in self._parent:
703 if node is self:
704 break
706 yield node
707 else:
708 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
710 def GetRightSiblings(self) -> Generator['Node', None, None]:
711 """
712 A generator to iterate all siblings right from the current node.
714 Siblings are child nodes of the current node's parent node, without the current node itself.
716 :returns: A generator to iterate all siblings right of the current node.
717 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
718 """
719 if self._parent is None:
720 raise NoSiblingsError(f"Root node has no siblings.")
722 iterator = iter(self._parent)
723 for node in iterator:
724 if node is self:
725 break
726 else:
727 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
729 for node in iterator:
730 yield node
732 def GetDescendants(self) -> Generator['Node', None, None]:
733 """
734 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder`
735 it doesn't include the node itself.
737 :returns: A generator to iterate all descendants.
739 .. seealso::
741 :meth:`GetChildren` |br|
742 |rarr| Iterate all children, but no grand-children.
743 :meth:`IterateLevelOrder` |br|
744 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
745 :meth:`IteratePreOrder` |br|
746 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
747 :meth:`IteratePostOrder` |br|
748 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
749 """
750 for child in self._children:
751 yield child
752 yield from child.GetDescendants()
754 def GetRelatives(self) -> Generator['Node', None, None]:
755 """
756 A generator to iterate all relatives (all siblings and all their descendants) of the current node.
758 :returns: A generator to iterate all relatives.
759 """
760 for node in self.GetSiblings():
761 yield node
762 yield from node.GetDescendants()
764 def GetLeftRelatives(self) -> Generator['Node', None, None]:
765 """
766 A generator to iterate all left relatives (left siblings and all their descendants) of the current node.
768 :returns: A generator to iterate all left relatives.
769 """
770 for node in self.GetLeftSiblings():
771 yield node
772 yield from node.GetDescendants()
774 def GetRightRelatives(self) -> Generator['Node', None, None]:
775 """
776 A generator to iterate all right relatives (right siblings and all their descendants) of the current node.
778 :returns: A generator to iterate all right relatives.
779 """
780 for node in self.GetRightSiblings():
781 yield node
782 yield from node.GetDescendants()
784 def IterateLeafs(self) -> Generator['Node', None, None]:
785 """
786 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.
788 :returns: A generator to iterate leaf-nodes reachable from current node.
789 """
790 for child in self._children:
791 if child.IsLeaf:
792 yield child
793 else:
794 yield from child.IterateLeafs()
796 def IterateLevelOrder(self) -> Generator['Node', None, None]:
797 """
798 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`,
799 this includes also the node itself as the first returned node.
801 :returns: A generator to iterate all siblings level-by-level.
803 .. seealso::
805 :meth:`GetChildren` |br|
806 |rarr| Iterate all children, but no grand-children.
807 :meth:`GetDescendants` |br|
808 |rarr| Iterate all descendants.
809 :meth:`IteratePreOrder` |br|
810 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
811 :meth:`IteratePostOrder` |br|
812 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
813 """
814 queue = deque([self])
815 while queue:
816 currentNode = queue.pop()
817 yield currentNode
818 for node in currentNode._children:
819 queue.appendleft(node)
821 def IteratePreOrder(self) -> Generator['Node', None, None]:
822 """
823 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes
824 also the node itself as the first returned node.
826 :returns: A generator to iterate all siblings in pre-order.
828 .. seealso::
830 :meth:`GetChildren` |br|
831 |rarr| Iterate all children, but no grand-children.
832 :meth:`GetDescendants` |br|
833 |rarr| Iterate all descendants.
834 :meth:`IterateLevelOrder` |br|
835 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
836 :meth:`IteratePostOrder` |br|
837 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
838 """
839 yield self
840 for child in self._children:
841 yield from child.IteratePreOrder()
843 def IteratePostOrder(self) -> Generator['Node', None, None]:
844 """
845 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this
846 includes also the node itself as the last returned node.
848 :returns: A generator to iterate all siblings in post-order.
850 .. seealso::
852 :meth:`GetChildren` |br|
853 |rarr| Iterate all children, but no grand-children.
854 :meth:`GetDescendants` |br|
855 |rarr| Iterate all descendants.
856 :meth:`IterateLevelOrder` |br|
857 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
858 :meth:`IteratePreOrder` |br|
859 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
860 """
861 for child in self._children:
862 yield from child.IteratePostOrder()
863 yield self
865 def WalkTo(self, other: 'Node') -> Generator['Node', None, None]:
866 """
867 Returns a generator to iterate the path from node to another node.
869 :param other: Node to walk to.
870 :returns: Generator to iterate the path from node to other node.
871 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree.
872 """
873 # Check for trivial case
874 if other is self:
875 yield from ()
877 # Check if both are in the same tree.
878 if self._root is not other._root:
879 raise NotInSameTreeError(f"Node 'other' is not in the same tree.")
881 # Compute both paths to the root.
882 # 1. Walk from self to root, until a first common ancestor is found.
883 # 2. Walk from there to other (reverse paths)
884 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk.
885 index = len(otherPath)
886 for node in self.GetAncestors():
887 try:
888 index = otherPath.index(node)
889 break
890 except ValueError:
891 yield node
893 for i in range(index, len(otherPath)):
894 yield otherPath[i]
896 def GetNodeByID(self, nodeID: IDType) -> 'Node':
897 """
898 Lookup a node by its unique ID.
900 :param nodeID: ID of a node to lookup in the tree.
901 :returns: Node for the given ID.
902 :raises ValueError: If parameter ``nodeID`` is None.
903 :raises KeyError: If parameter ``nodeID`` is not found in the tree.
904 """
905 if nodeID is None:
906 raise ValueError(f"'None' is not supported as an ID value.")
908 return self._root._nodesWithID[nodeID]
910 def Find(self, predicate: Callable) -> Generator['Node', None, None]:
911 raise NotImplementedError(f"Method 'Find' is not yet implemented.")
913 def __iter__(self) -> Iterator['Node']:
914 """
915 Returns an iterator to iterate all child nodes.
917 :returns: Children iterator.
918 """
919 return iter(self._children)
921 def __len__(self) -> int:
922 """
923 Returns the number of children, but not including grand-children.
925 :returns: Number of child nodes.
926 """
927 return len(self._children)
929 def __repr__(self) -> str:
930 """
931 Returns a detailed string representation of the node.
933 :returns: The detailed string representation of the node.
934 """
935 nodeID = parent = value = ""
936 if self._id is not None:
937 nodeID = f"; nodeID='{self._id}'"
938 if (self._parent is not None) and (self._parent._id is not None):
939 parent = f"; parent='{self._parent._id}'"
940 if self._value is not None:
941 value = f"; value='{self._value}'"
943 return f"<node{nodeID}{parent}{value}>"
945 def __str__(self) -> str:
946 """
947 Return a string representation of the node.
949 Order of resolution:
951 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
952 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
953 3. Else, return :meth:`__repr__`.
955 :returns: The resolved string representation of the node.
956 """
957 if self._value is not None:
958 return str(self._value)
959 elif self._id is not None:
960 return str(self._id)
961 else:
962 return self.__repr__()
964 def Render(
965 self,
966 prefix: str = "",
967 lineend: str = "\n",
968 nodeMarker: str = "├─",
969 lastNodeMarker: str = "└─",
970 bypassMarker: str = "│ "
971 ) -> str:
972 """
973 Render the tree as ASCII art.
975 :param prefix: A string printed in front of every line, e.g. for indentation. Default: ``""``.
976 :param lineend: A string printed at the end of every line. Default: ``"\\n"``.
977 :param nodeMarker: A string printed before every non-last tree node. Default: ``"├─"``.
978 :param lastNodeMarker: A string printed before every last tree node. Default: ``"└─"``.
979 :param bypassMarker: A string printed when there are further nodes in the parent level. Default: ``"│ "``.
980 :return: A rendered tree as multiline string.
981 """
982 emptyMarker = " " * len(bypassMarker)
984 def _render(node: Node, markers: str):
985 result = []
987 if node.HasChildren:
988 for child in node._children[:-1]:
989 nodeRepresentation = child._format(child) if child._format else str(child)
990 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}")
991 result.extend(_render(child, markers + bypassMarker))
993 # last child node
994 child = node._children[-1]
995 nodeRepresentation = child._format(child) if child._format else str(child)
996 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}")
997 result.extend(_render(child, markers + emptyMarker))
999 return result
1001 # Root element
1002 nodeRepresentation = self._format(self) if self._format else str(self)
1003 result = [f"{prefix}{nodeRepresentation}{lineend}"]
1004 result.extend(_render(self, ""))
1006 return "".join(result)