Coverage for pyTooling/Tree/__init__.py: 90%
366 statements
« prev ^ index » next coverage.py v7.8.0, created at 2025-04-25 22:22 +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(f"Parameter 'parent' is not of type 'Node'.")
201 if version_info >= (3, 11): # pragma: no cover
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
222 if nodeID is None:
223 self._root._nodesWithoutID.append(self)
224 elif nodeID in self._root._nodesWithID:
225 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
226 else:
227 self._root._nodesWithID[nodeID] = self
229 parent._children.append(self)
231 self._children = []
232 if children is not None:
233 if not isinstance(children, Iterable):
234 ex = TypeError(f"Parameter 'children' is not iterable.")
235 if version_info >= (3, 11): # pragma: no cover
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 if version_info >= (3, 11): # pragma: no cover
243 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
244 raise ex
246 child.Parent = self
248 @readonly
249 def ID(self) -> Nullable[IDType]:
250 """
251 Read-only property to access the unique ID of a node (:attr:`_id`).
253 If no ID was given at node construction time, ID return None.
255 :returns: Unique ID of a node, if ID was given at node creation time, else None.
256 """
257 return self._id
259 @property
260 def Value(self) -> Nullable[ValueType]:
261 """
262 Property to get and set the value (:attr:`_value`) of a node.
264 :returns: The value of a node.
265 """
266 return self._value
268 @Value.setter
269 def Value(self, value: Nullable[ValueType]) -> None:
270 self._value = value
272 def __getitem__(self, key: DictKeyType) -> DictValueType:
273 """
274 Read a node's attached attributes (key-value-pairs) by key.
276 :param key: The key to look for.
277 :returns: The value associated to the given key.
278 """
279 return self._dict[key]
281 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
282 """
283 Create or update a node's attached attributes (key-value-pairs) by key.
285 If a key doesn't exist yet, a new key-value-pair is created.
287 :param key: The key to create or update.
288 :param value: The value to associate to the given key.
289 """
290 self._dict[key] = value
292 def __delitem__(self, key: DictKeyType) -> None:
293 """
294 .. todo:: TREE::Node::__delitem__ Needs documentation.
296 """
297 del self._dict[key]
299 def __contains__(self, key: DictKeyType) -> bool:
300 """
301 .. todo:: TREE::Node::__contains__ Needs documentation.
303 """
304 return key in self._dict
306 def __len__(self) -> int:
307 """
308 Returns the number of attached attributes (key-value-pairs) on this node.
310 :returns: Number of attached attributes.
311 """
312 return len(self._dict)
314 @readonly
315 def Root(self) -> 'Node':
316 """
317 Read-only property to access the tree's root node (:attr:`_root`).
319 :returns: The root node (representative node) of a tree.
320 """
321 return self._root
323 @property
324 def Parent(self) -> Nullable['Node']:
325 """
326 Property to get and set the parent (:attr:`_parent`) of a node.
328 .. note::
330 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and
331 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`.
333 :returns: The parent of a node.
334 :raises TypeError: If parameter ``parent`` is not a :class:`Node`
335 :raises AlreadyInTreeError: Parent is already a child node in this tree.
336 """
337 return self._parent
339 @Parent.setter
340 def Parent(self, parent: Nullable['Node']) -> None:
341 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root
343 if parent is None:
344 self._nodesWithID = {}
345 self._nodesWithoutID = []
346 self._level = 0
348 if self._id is None:
349 self._nodesWithoutID.append(self)
350 self._root._nodesWithoutID.remove(self)
351 else:
352 self._nodesWithID[self._id] = self
353 del self._nodesWithID[self._id]
355 for sibling in self.GetDescendants():
356 sibling._root = self
357 sibling._level = sibling._parent._level + 1
358 if sibling._id is None:
359 self._nodesWithoutID.append(sibling)
360 self._root._nodesWithoutID.remove(sibling)
361 else:
362 self._nodesWithID[sibling._id] = sibling
363 del self._nodesWithID[sibling._id]
365 self._parent._children.remove(self)
367 self._root = self
368 self._parent = None
369 elif not isinstance(parent, Node):
370 ex = TypeError(f"Parameter 'parent' is not of type 'Node'.")
371 if version_info >= (3, 11): # pragma: no cover
372 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
373 raise ex
374 else:
375 if parent._root is self._root:
376 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.")
378 self._root = parent._root
379 self._parent = parent
380 self._level = parent._level + 1
381 for node in self.GetDescendants():
382 node._level = node._parent._level + 1
383 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID)
384 self._nodesWithID = self._nodesWithoutID = None
385 parent._children.append(self)
387 @readonly
388 def Siblings(self) -> Tuple['Node', ...]:
389 """
390 A read-only property to return a tuple of all siblings from the current node.
392 If the current node is the only child, the tuple is empty.
394 Siblings are child nodes of the current node's parent node, without the current node itself.
396 :returns: A tuple of all siblings of the current node.
397 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
398 """
399 if self._parent is None:
400 raise NoSiblingsError(f"Root node has no siblings.")
402 return tuple([node for node in self._parent if node is not self])
404 @readonly
405 def LeftSiblings(self) -> Tuple['Node', ...]:
406 """
407 A read-only property to return a tuple of all siblings left from the current node.
409 If the current node is the only child, the tuple is empty.
411 Siblings are child nodes of the current node's parent node, without the current node itself.
413 :returns: A tuple of all siblings left of the current node.
414 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
415 """
416 if self._parent is None:
417 raise NoSiblingsError(f"Root node has no siblings.")
419 result = []
420 for node in self._parent:
421 if node is not self:
422 result.append(node)
423 else:
424 break
425 else:
426 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
428 return tuple(result)
430 @readonly
431 def RightSiblings(self) -> Tuple['Node', ...]:
432 """
433 A read-only property to return a tuple of all siblings right from the current node.
435 If the current node is the only child, the tuple is empty.
437 Siblings are child nodes of the current node's parent node, without the current node itself.
439 :returns: A tuple of all siblings right of the current node.
440 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
441 """
442 if self._parent is None:
443 raise NoSiblingsError(f"Root node has no siblings.")
445 result = []
446 iterator = iter(self._parent)
447 for node in iterator:
448 if node is self:
449 break
450 else:
451 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
453 for node in iterator:
454 result.append(node)
456 return tuple(result)
458 def _GetPathAsLinkedList(self) -> Deque["Node"]:
459 """
460 Compute the path from current node to root node by using a linked list (:class:`deque`).
462 :meta private:
463 :returns: Path from node to root node as double-ended queue (deque).
464 """
465 path: Deque['Node'] = deque()
467 node = self
468 while node is not None:
469 path.appendleft(node)
470 node = node._parent
472 return path
474 @readonly
475 def Path(self) -> Tuple['Node']:
476 """
477 Read-only property to return the path from root node to the node as a tuple of nodes.
479 :returns: A tuple of nodes describing the path from root node to the node.
480 """
481 return tuple(self._GetPathAsLinkedList())
483 @readonly
484 def Level(self) -> int:
485 """
486 Read-only property to return a node's level in the tree.
488 The level is the distance to the root node.
490 :returns: The node's level.
491 """
492 return self._level
494 @readonly
495 def Size(self) -> int:
496 """
497 Read-only property to return the size of the tree.
499 :returns: Count of all nodes in the tree structure.
500 """
501 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID)
503 @readonly
504 def IsRoot(self) -> bool:
505 """
506 Returns true, if the node is the root node (representative node of the tree).
508 :returns: ``True``, if node is the root node.
509 """
510 return self._parent is None
512 @readonly
513 def IsLeaf(self) -> bool:
514 """
515 Returns true, if the node is a leaf node (has no children).
517 :returns: ``True``, if node has no children.
518 """
519 return len(self._children) == 0
521 @readonly
522 def HasChildren(self) -> bool:
523 """
524 Returns true, if the node has child nodes.
526 :returns: ``True``, if node has children.
527 """
528 return len(self._children) > 0
530 def _SetNewRoot(self, nodesWithIDs: Dict['Node', 'Node'], nodesWithoutIDs: List['Node']) -> None:
531 for nodeID, node in nodesWithIDs.items():
532 if nodeID in self._root._nodesWithID:
533 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
534 else:
535 self._root._nodesWithID[nodeID] = node
536 node._root = self._root
538 for node in nodesWithoutIDs:
539 self._root._nodesWithoutID.append(node)
540 node._root = self._root
542 def AddChild(self, child: 'Node'):
543 """
544 Add a child node to the current node of the tree.
546 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and
547 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`).
549 :param child: The child node to be added to the tree.
550 :raises TypeError: If parameter ``child`` is not a :class:`Node`.
551 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree.
553 .. seealso::
555 :attr:`Parent` |br|
556 |rarr| Set the parent of a node.
557 :meth:`AddChildren` |br|
558 |rarr| Add multiple children at once.
559 """
560 if not isinstance(child, Node):
561 ex = TypeError(f"Parameter 'child' is not of type 'Node'.")
562 if version_info >= (3, 11): # pragma: no cover
563 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
564 raise ex
566 if child._root is self._root:
567 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
569 child._root = self._root
570 child._parent = self
571 child._level = self._level + 1
572 for node in child.GetDescendants():
573 node._level = node._parent._level + 1
574 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
575 child._nodesWithID = child._nodesWithoutID = None
576 self._children.append(child)
578 def AddChildren(self, children: Iterable['Node']):
579 """
580 Add multiple children nodes to the current node of the tree.
582 :param children: The list of children nodes to be added to the tree.
583 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`.
584 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree.
586 .. seealso::
588 :attr:`Parent` |br|
589 |rarr| Set the parent of a node.
590 :meth:`AddChild` |br|
591 |rarr| Add a child node to the tree.
592 """
593 for child in children:
594 if not isinstance(child, Node):
595 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
596 if version_info >= (3, 11): # pragma: no cover
597 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
598 raise ex
600 if child._root is self._root:
601 # TODO: create a more specific exception
602 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
604 child._root = self._root
605 child._parent = self
606 child._level = self._level + 1
607 for node in child.GetDescendants():
608 node._level = node._parent._level + 1
609 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
610 child._nodesWithID = child._nodesWithoutID = None
611 self._children.append(child)
613 def GetPath(self) -> Generator['Node', None, None]:
614 """
615 .. todo:: TREE::Node::GetPAth Needs documentation.
617 """
618 for node in self._GetPathAsLinkedList():
619 yield node
621 def GetAncestors(self) -> Generator['Node', None, None]:
622 """
623 .. todo:: TREE::Node::GetAncestors Needs documentation.
625 """
626 node = self._parent
627 while node is not None:
628 yield node
629 node = node._parent
631 def GetCommonAncestors(self, others: Union['Node', Iterable['Node']]) -> Generator['Node', None, None]:
632 """
633 .. todo:: TREE::Node::GetCommonAncestors Needs documentation.
635 """
636 if isinstance(others, Node):
637 # Check for trivial case
638 if others is self:
639 for node in self._GetPathAsLinkedList():
640 yield node
641 return
643 # Check if both are in the same tree.
644 if self._root is not others._root:
645 raise NotInSameTreeError(f"Node 'others' is not in the same tree.")
647 # Compute paths top-down and walk both paths until they deviate
648 for left, right in zip(self.Path, others.Path):
649 if left is right:
650 yield left
651 else:
652 return
653 elif isinstance(others, Iterable):
654 raise NotImplementedError(f"Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.")
656 def GetChildren(self) -> Generator['Node', None, None]:
657 """
658 A generator to iterate all direct children of the current node.
660 :returns: A generator to iterate all children.
662 .. seealso::
664 :meth:`GetDescendants` |br|
665 |rarr| Iterate all descendants.
666 :meth:`IterateLevelOrder` |br|
667 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
668 :meth:`IteratePreOrder` |br|
669 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
670 :meth:`IteratePostOrder` |br|
671 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
672 """
673 for child in self._children:
674 yield child
676 def GetSiblings(self) -> Generator['Node', None, None]:
677 """
678 A generator to iterate all siblings.
680 Siblings are child nodes of the current node's parent node, without the current node itself.
682 :returns: A generator to iterate all siblings of the current node.
683 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
684 """
685 if self._parent is None:
686 raise NoSiblingsError(f"Root node has no siblings.")
688 for node in self._parent:
689 if node is self:
690 continue
692 yield node
694 def GetLeftSiblings(self) -> Generator['Node', None, None]:
695 """
696 A generator to iterate all siblings left from the current node.
698 Siblings are child nodes of the current node's parent node, without the current node itself.
700 :returns: A generator to iterate all siblings left of the current node.
701 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
702 """
703 if self._parent is None:
704 raise NoSiblingsError(f"Root node has no siblings.")
706 for node in self._parent:
707 if node is self:
708 break
710 yield node
711 else:
712 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
714 def GetRightSiblings(self) -> Generator['Node', None, None]:
715 """
716 A generator to iterate all siblings right from the current node.
718 Siblings are child nodes of the current node's parent node, without the current node itself.
720 :returns: A generator to iterate all siblings right of the current node.
721 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
722 """
723 if self._parent is None:
724 raise NoSiblingsError(f"Root node has no siblings.")
726 iterator = iter(self._parent)
727 for node in iterator:
728 if node is self:
729 break
730 else:
731 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
733 for node in iterator:
734 yield node
736 def GetDescendants(self) -> Generator['Node', None, None]:
737 """
738 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder`
739 it doesn't include the node itself.
741 :returns: A generator to iterate all descendants.
743 .. seealso::
745 :meth:`GetChildren` |br|
746 |rarr| Iterate all children, but no grand-children.
747 :meth:`IterateLevelOrder` |br|
748 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
749 :meth:`IteratePreOrder` |br|
750 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
751 :meth:`IteratePostOrder` |br|
752 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
753 """
754 for child in self._children:
755 yield child
756 yield from child.GetDescendants()
758 def GetRelatives(self):
759 """
760 A generator to iterate all relatives (all siblings and all their descendants) of the current node.
762 :returns: A generator to iterate all relatives.
763 """
764 for node in self.GetSiblings():
765 yield node
766 yield from node.GetDescendants()
768 def GetLeftRelatives(self):
769 """
770 A generator to iterate all left relatives (left siblings and all their descendants) of the current node.
772 :returns: A generator to iterate all left relatives.
773 """
774 for node in self.GetLeftSiblings():
775 yield node
776 yield from node.GetDescendants()
778 def GetRightRelatives(self):
779 """
780 A generator to iterate all right relatives (right siblings and all their descendants) of the current node.
782 :returns: A generator to iterate all right relatives.
783 """
784 for node in self.GetRightSiblings():
785 yield node
786 yield from node.GetDescendants()
788 def IterateLeafs(self) -> Generator['Node', None, None]:
789 """
790 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.
792 :returns: A generator to iterate leaf-nodes reachable from current node.
793 """
794 for child in self._children:
795 if child.IsLeaf:
796 yield child
797 else:
798 yield from child.IterateLeafs()
800 def IterateLevelOrder(self) -> Generator['Node', None, None]:
801 """
802 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`,
803 this includes also the node itself as the first returned node.
805 :returns: A generator to iterate all siblings level-by-level.
807 .. seealso::
809 :meth:`GetChildren` |br|
810 |rarr| Iterate all children, but no grand-children.
811 :meth:`GetDescendants` |br|
812 |rarr| Iterate all descendants.
813 :meth:`IteratePreOrder` |br|
814 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
815 :meth:`IteratePostOrder` |br|
816 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
817 """
818 queue = deque([self])
819 while queue:
820 currentNode = queue.pop()
821 yield currentNode
822 for node in currentNode._children:
823 queue.appendleft(node)
825 def IteratePreOrder(self) -> Generator['Node', None, None]:
826 """
827 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes
828 also the node itself as the first returned node.
830 :returns: A generator to iterate all siblings in pre-order.
832 .. seealso::
834 :meth:`GetChildren` |br|
835 |rarr| Iterate all children, but no grand-children.
836 :meth:`GetDescendants` |br|
837 |rarr| Iterate all descendants.
838 :meth:`IterateLevelOrder` |br|
839 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
840 :meth:`IteratePostOrder` |br|
841 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
842 """
843 yield self
844 for child in self._children:
845 yield from child.IteratePreOrder()
847 def IteratePostOrder(self) -> Generator['Node', None, None]:
848 """
849 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this
850 includes also the node itself as the last returned node.
852 :returns: A generator to iterate all siblings in post-order.
854 .. seealso::
856 :meth:`GetChildren` |br|
857 |rarr| Iterate all children, but no grand-children.
858 :meth:`GetDescendants` |br|
859 |rarr| Iterate all descendants.
860 :meth:`IterateLevelOrder` |br|
861 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
862 :meth:`IteratePreOrder` |br|
863 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
864 """
865 for child in self._children:
866 yield from child.IteratePostOrder()
867 yield self
869 def WalkTo(self, other: 'Node') -> Generator['Node', None, None]:
870 """
871 Returns a generator to iterate the path from node to another node.
873 :param other: Node to walk to.
874 :returns: Generator to iterate the path from node to other node.
875 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree.
876 """
877 # Check for trivial case
878 if other is self:
879 yield from ()
881 # Check if both are in the same tree.
882 if self._root is not other._root:
883 raise NotInSameTreeError(f"Node 'other' is not in the same tree.")
885 # Compute both paths to the root.
886 # 1. Walk from self to root, until a first common ancestor is found.
887 # 2. Walk from there to other (reverse paths)
888 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk.
889 index = len(otherPath)
890 for node in self.GetAncestors():
891 try:
892 index = otherPath.index(node)
893 break
894 except ValueError:
895 yield node
897 for i in range(index, len(otherPath)):
898 yield otherPath[i]
900 def GetNodeByID(self, nodeID: IDType) -> 'Node':
901 """
902 Lookup a node by its unique ID.
904 :param nodeID: ID of a node to lookup in the tree.
905 :returns: Node for the given ID.
906 :raises ValueError: If parameter ``nodeID`` is None.
907 :raises KeyError: If parameter ``nodeID`` is not found in the tree.
908 """
909 if nodeID is None:
910 raise ValueError(f"'None' is not supported as an ID value.")
912 return self._root._nodesWithID[nodeID]
914 def Find(self, predicate: Callable) -> Generator['Node', None, None]:
915 raise NotImplementedError(f"Method 'Find' is not yet implemented.")
917 def __iter__(self) -> Iterator['Node']:
918 """
919 Returns an iterator to iterate all child nodes.
921 :returns: Children iterator.
922 """
923 return iter(self._children)
925 def __len__(self) -> int:
926 """
927 Returns the number of children, but not including grand-children.
929 :returns: Number of child nodes.
930 """
931 return len(self._children)
933 def __repr__(self) -> str:
934 """
935 Returns a detailed string representation of the node.
937 :returns: The detailed string representation of the node.
938 """
939 nodeID = parent = value = ""
940 if self._id is not None:
941 nodeID = f"; nodeID='{self._id}'"
942 if (self._parent is not None) and (self._parent._id is not None):
943 parent = f"; parent='{self._parent._id}'"
944 if self._value is not None:
945 value = f"; value='{self._value}'"
947 return f"<node{nodeID}{parent}{value}>"
949 def __str__(self) -> str:
950 """
951 Return a string representation of the node.
953 Order of resolution:
955 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
956 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
957 3. Else, return :meth:`__repr__`.
959 :returns: The resolved string representation of the node.
960 """
961 if self._value is not None:
962 return str(self._value)
963 elif self._id is not None:
964 return str(self._id)
965 else:
966 return self.__repr__()
968 def Render(
969 self,
970 prefix: str = "",
971 lineend: str = "\n",
972 nodeMarker: str = "├─",
973 lastNodeMarker: str = "└─",
974 bypassMarker: str = "│ "
975 ) -> str:
976 """
977 Render the tree as ASCII art.
979 :param prefix: A string printed in front of every line, e.g. for indentation. Default: ``""``.
980 :param lineend: A string printed at the end of every line. Default: ``"\\n"``.
981 :param nodeMarker: A string printed before every non-last tree node. Default: ``"├─"``.
982 :param lastNodeMarker: A string printed before every last tree node. Default: ``"└─"``.
983 :param bypassMarker: A string printed when there are further nodes in the parent level. Default: ``"│ "``.
984 :return: A rendered tree as multiline string.
985 """
986 emptyMarker = " " * len(bypassMarker)
988 def _render(node: Node, markers: str):
989 result = []
991 if node.HasChildren:
992 for child in node._children[:-1]:
993 nodeRepresentation = child._format(child) if child._format else str(child)
994 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}")
995 result.extend(_render(child, markers + bypassMarker))
997 # last child node
998 child = node._children[-1]
999 nodeRepresentation = child._format(child) if child._format else str(child)
1000 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}")
1001 result.extend(_render(child, markers + emptyMarker))
1003 return result
1005 # Root element
1006 nodeRepresentation = self._format(self) if self._format else str(self)
1007 result = [f"{prefix}{nodeRepresentation}{lineend}"]
1008 result.extend(_render(self, ""))
1010 return "".join(result)