Coverage for pyTooling/Tree/__init__.py: 90%
371 statements
« prev ^ index » next coverage.py v7.11.3, created at 2025-11-16 09:59 +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 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:: The top-down construction should be preferred, because it's slightly faster.
123 Each tree uses the **root** node (a.k.a. tree-representative) to store some per-tree data structures. E.g. a list of
124 all IDs in a tree. For easy and quick access to such data structures, each sibling node contains a reference to the
125 root node (:attr:`_root`). In case of adding a tree to an existing tree, such data structures get merged and all added
126 nodes get assigned with new root references. Use the read-only property :attr:`Root` to access the root reference.
128 The reference to the parent node (:attr:`_parent`) can be access via property :attr:`Parent`. If the property's setter
129 is used, a node and all its siblings are added to another tree or to a new position in the same tree.
131 The references to all node's children is stored in a list (:attr:`_children`). Children, siblings, ancestors, can be
132 accessed via various generators:
134 * :meth:`GetAncestors` |rarr| iterate all ancestors bottom-up.
135 * :meth:`GetChildren` |rarr| iterate all direct children.
136 * :meth:`GetDescendants` |rarr| iterate all descendants.
137 * :meth:`IterateLevelOrder` |rarr| IterateLevelOrder.
138 * :meth:`IteratePreOrder` |rarr| iterate siblings in pre-order.
139 * :meth:`IteratePostOrder` |rarr| iterate siblings in post-order.
141 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
142 dictionary (:attr:`_nodesWithID`). In case no ID is given, all such ID-less nodes are collected in a single bin and store as a
143 list of nodes. An ID can be modified after the Node was created. Use the read-only property :attr:`ID` to access
144 the ID.
146 Each node can have a **value** (:attr:`_value`), which can be given at node creation time, or it can be assigned and/or
147 modified later. Use the property :attr:`Value` to get or set the value.
149 Moreover, each node can store various key-value-pairs (:attr:`_dict`). Use the dictionary syntax to get and set
150 key-value-pairs.
151 """
153 _id: Nullable[IDType] #: Unique identifier of a node. ``None`` if not used.
154 _nodesWithID: Nullable[Dict[IDType, 'Node']] #: Dictionary of all IDs in the tree. ``None`` if it's not the root node.
155 _nodesWithoutID: Nullable[List['Node']] #: List of all nodes without an ID in the tree. ``None`` if it's not the root node.
156 _root: 'Node' #: Reference to the root of a tree. ``self`` if it's the root node.
157 _parent: Nullable['Node'] #: Reference to the parent node. ``None`` if it's the root node.
158 _children: List['Node'] #: List of all children
159# _links: List['Node']
161 _level: int #: Level of the node (distance to the root).
162 _value: Nullable[ValueType] #: Field to store the node's value.
163 _dict: Dict[DictKeyType, DictValueType] #: Dictionary to store key-value-pairs attached to the node.
165 _format: Nullable[Callable[["Node"], str]] #: A node formatting function returning a one-line representation for tree-rendering.
167 def __init__(
168 self,
169 nodeID: Nullable[IDType] = None,
170 value: Nullable[ValueType] = None,
171 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
172 parent: 'Node' = None,
173 children: Nullable[Iterable['Node']] = None,
174 format: Nullable[Callable[["Node"], str]] = None
175 ) -> None:
176 """
177 .. todo:: TREE::Node::init Needs documentation.
179 :param nodeID: The optional unique ID of a node within the whole tree data structure.
180 :param value: The optional value of the node.
181 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
182 :param parent: The optional parent node in the tree.
183 :param children: The optional list of child nodes.
184 :param format: The optional node formatting function returning a one-line representation for tree-rendering.
186 :raises TypeError: If parameter parent is not an instance of Node.
187 :raises ValueError: If nodeID already exists in the tree.
188 :raises TypeError: If parameter children is not iterable.
189 :raises ValueError: If an element of children is not an instance of Node.
190 """
192 self._id = nodeID
193 self._value = value
194 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
196 self._format = format
198 if parent is not None and not isinstance(parent, Node):
199 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
200 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
201 raise ex
203 if parent is None:
204 self._root = self
205 self._parent = None
206 self._level = 0
208 self._nodesWithID = {}
209 self._nodesWithoutID = []
210 if nodeID is None:
211 self._nodesWithoutID.append(self)
212 else:
213 self._nodesWithID[nodeID] = self
214 else:
215 self._root = parent._root
216 self._parent = parent
217 self._level = parent._level + 1
218 self._nodesWithID = None
220 if nodeID is None:
221 self._root._nodesWithoutID.append(self)
222 elif nodeID in self._root._nodesWithID:
223 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
224 else:
225 self._root._nodesWithID[nodeID] = self
227 parent._children.append(self)
229 self._children = []
230 if children is not None:
231 if not isinstance(children, Iterable):
232 ex = TypeError("Parameter 'children' is not iterable.")
233 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.")
234 raise ex
236 for child in children:
237 if not isinstance(child, Node):
238 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
239 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
240 raise ex
242 child.Parent = self
244 @readonly
245 def ID(self) -> Nullable[IDType]:
246 """
247 Read-only property to access the unique ID of a node (:attr:`_id`).
249 If no ID was given at node construction time, ID return None.
251 :returns: Unique ID of a node, if ID was given at node creation time, else None.
252 """
253 return self._id
255 @property
256 def Value(self) -> Nullable[ValueType]:
257 """
258 Property to get and set the value (:attr:`_value`) of a node.
260 :returns: The value of a node.
261 """
262 return self._value
264 @Value.setter
265 def Value(self, value: Nullable[ValueType]) -> None:
266 self._value = value
268 def __getitem__(self, key: DictKeyType) -> DictValueType:
269 """
270 Read a node's attached attributes (key-value-pairs) by key.
272 :param key: The key to look for.
273 :returns: The value associated to the given key.
274 """
275 return self._dict[key]
277 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
278 """
279 Create or update a node's attached attributes (key-value-pairs) by key.
281 If a key doesn't exist yet, a new key-value-pair is created.
283 :param key: The key to create or update.
284 :param value: The value to associate to the given key.
285 """
286 self._dict[key] = value
288 def __delitem__(self, key: DictKeyType) -> None:
289 """
290 .. todo:: TREE::Node::__delitem__ Needs documentation.
292 """
293 del self._dict[key]
295 def __contains__(self, key: DictKeyType) -> bool:
296 """
297 .. todo:: TREE::Node::__contains__ Needs documentation.
299 """
300 return key in self._dict
302 def __len__(self) -> int:
303 """
304 Returns the number of attached attributes (key-value-pairs) on this node.
306 :returns: Number of attached attributes.
307 """
308 return len(self._dict)
310 @readonly
311 def Root(self) -> 'Node':
312 """
313 Read-only property to access the tree's root node (:attr:`_root`).
315 :returns: The root node (representative node) of a tree.
316 """
317 return self._root
319 @property
320 def Parent(self) -> Nullable['Node']:
321 """
322 Property to get and set the parent (:attr:`_parent`) of a node.
324 .. note::
326 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and
327 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`.
329 :returns: The parent of a node.
330 :raises TypeError: If parameter ``parent`` is not a :class:`Node`
331 :raises AlreadyInTreeError: Parent is already a child node in this tree.
332 """
333 return self._parent
335 @Parent.setter
336 def Parent(self, parent: Nullable['Node']) -> None:
337 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root
339 if parent is None:
340 self._nodesWithID = {}
341 self._nodesWithoutID = []
342 self._level = 0
344 if self._id is None:
345 self._nodesWithoutID.append(self)
346 self._root._nodesWithoutID.remove(self)
347 else:
348 self._nodesWithID[self._id] = self
349 del self._nodesWithID[self._id]
351 for sibling in self.GetDescendants():
352 sibling._root = self
353 sibling._level = sibling._parent._level + 1
354 if sibling._id is None:
355 self._nodesWithoutID.append(sibling)
356 self._root._nodesWithoutID.remove(sibling)
357 else:
358 self._nodesWithID[sibling._id] = sibling
359 del self._nodesWithID[sibling._id]
361 self._parent._children.remove(self)
363 self._root = self
364 self._parent = None
365 elif not isinstance(parent, Node):
366 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
367 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
368 raise ex
369 else:
370 if parent._root is self._root:
371 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.")
373 self._root = parent._root
374 self._parent = parent
375 self._level = parent._level + 1
376 for node in self.GetDescendants():
377 node._level = node._parent._level + 1
378 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID)
379 self._nodesWithID = self._nodesWithoutID = None
380 parent._children.append(self)
382 @readonly
383 def Siblings(self) -> Tuple['Node', ...]:
384 """
385 A read-only property to return a tuple of all siblings from the current node.
387 If the current node is the only child, the tuple is empty.
389 Siblings are child nodes of the current node's parent node, without the current node itself.
391 :returns: A tuple of all siblings of the current node.
392 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
393 """
394 if self._parent is None:
395 raise NoSiblingsError(f"Root node has no siblings.")
397 return tuple([node for node in self._parent if node is not self])
399 @readonly
400 def LeftSiblings(self) -> Tuple['Node', ...]:
401 """
402 A read-only property to return a tuple of all siblings left from the current node.
404 If the current node is the only child, the tuple is empty.
406 Siblings are child nodes of the current node's parent node, without the current node itself.
408 :returns: A tuple of all siblings left of the current node.
409 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
410 """
411 if self._parent is None:
412 raise NoSiblingsError(f"Root node has no siblings.")
414 result = []
415 for node in self._parent:
416 if node is not self:
417 result.append(node)
418 else:
419 break
420 else:
421 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
423 return tuple(result)
425 @readonly
426 def RightSiblings(self) -> Tuple['Node', ...]:
427 """
428 A read-only property to return a tuple of all siblings right from the current node.
430 If the current node is the only child, the tuple is empty.
432 Siblings are child nodes of the current node's parent node, without the current node itself.
434 :returns: A tuple of all siblings right of the current node.
435 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
436 """
437 if self._parent is None:
438 raise NoSiblingsError(f"Root node has no siblings.")
440 result = []
441 iterator = iter(self._parent)
442 for node in iterator:
443 if node is self:
444 break
445 else:
446 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
448 for node in iterator:
449 result.append(node)
451 return tuple(result)
453 def _GetPathAsLinkedList(self) -> Deque["Node"]:
454 """
455 Compute the path from current node to root node by using a linked list (:class:`deque`).
457 :meta private:
458 :returns: Path from node to root node as double-ended queue (deque).
459 """
460 path: Deque['Node'] = deque()
462 node = self
463 while node is not None:
464 path.appendleft(node)
465 node = node._parent
467 return path
469 @readonly
470 def Path(self) -> Tuple['Node']:
471 """
472 Read-only property to return the path from root node to the node as a tuple of nodes.
474 :returns: A tuple of nodes describing the path from root node to the node.
475 """
476 return tuple(self._GetPathAsLinkedList())
478 @readonly
479 def Level(self) -> int:
480 """
481 Read-only property to return a node's level in the tree.
483 The level is the distance to the root node.
485 :returns: The node's level.
486 """
487 return self._level
489 @readonly
490 def Size(self) -> int:
491 """
492 Read-only property to return the size of the tree.
494 :returns: Count of all nodes in the tree structure.
495 """
496 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID)
498 @readonly
499 def IsRoot(self) -> bool:
500 """
501 Returns true, if the node is the root node (representative node of the tree).
503 :returns: ``True``, if node is the root node.
504 """
505 return self._parent is None
507 @readonly
508 def IsLeaf(self) -> bool:
509 """
510 Returns true, if the node is a leaf node (has no children).
512 :returns: ``True``, if node has no children.
513 """
514 return len(self._children) == 0
516 @readonly
517 def HasChildren(self) -> bool:
518 """
519 Returns true, if the node has child nodes.
521 :returns: ``True``, if node has children.
522 """
523 return len(self._children) > 0
525 def _SetNewRoot(self, nodesWithIDs: Dict['Node', 'Node'], nodesWithoutIDs: List['Node']) -> None:
526 for nodeID, node in nodesWithIDs.items():
527 if nodeID in self._root._nodesWithID:
528 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
529 else:
530 self._root._nodesWithID[nodeID] = node
531 node._root = self._root
533 for node in nodesWithoutIDs:
534 self._root._nodesWithoutID.append(node)
535 node._root = self._root
537 def AddChild(self, child: 'Node'):
538 """
539 Add a child node to the current node of the tree.
541 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and
542 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`).
544 :param child: The child node to be added to the tree.
545 :raises TypeError: If parameter ``child`` is not a :class:`Node`.
546 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree.
548 .. seealso::
550 :attr:`Parent` |br|
551 |rarr| Set the parent of a node.
552 :meth:`AddChildren` |br|
553 |rarr| Add multiple children at once.
554 """
555 if not isinstance(child, Node):
556 ex = TypeError(f"Parameter 'child' is not of type 'Node'.")
557 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
558 raise ex
560 if child._root is self._root:
561 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
563 child._root = self._root
564 child._parent = self
565 child._level = self._level + 1
566 for node in child.GetDescendants():
567 node._level = node._parent._level + 1
568 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
569 child._nodesWithID = child._nodesWithoutID = None
570 self._children.append(child)
572 def AddChildren(self, children: Iterable['Node']):
573 """
574 Add multiple children nodes to the current node of the tree.
576 :param children: The list of children nodes to be added to the tree.
577 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`.
578 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree.
580 .. seealso::
582 :attr:`Parent` |br|
583 |rarr| Set the parent of a node.
584 :meth:`AddChild` |br|
585 |rarr| Add a child node to the tree.
586 """
587 for child in children:
588 if not isinstance(child, Node):
589 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
590 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
591 raise ex
593 if child._root is self._root:
594 # TODO: create a more specific exception
595 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
597 child._root = self._root
598 child._parent = self
599 child._level = self._level + 1
600 for node in child.GetDescendants():
601 node._level = node._parent._level + 1
602 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
603 child._nodesWithID = child._nodesWithoutID = None
604 self._children.append(child)
606 def GetPath(self) -> Generator['Node', None, None]:
607 """
608 .. todo:: TREE::Node::GetPAth Needs documentation.
610 """
611 for node in self._GetPathAsLinkedList():
612 yield node
614 def GetAncestors(self) -> Generator['Node', None, None]:
615 """
616 .. todo:: TREE::Node::GetAncestors Needs documentation.
618 """
619 node = self._parent
620 while node is not None:
621 yield node
622 node = node._parent
624 def GetCommonAncestors(self, others: Union['Node', Iterable['Node']]) -> Generator['Node', None, None]:
625 """
626 .. todo:: TREE::Node::GetCommonAncestors Needs documentation.
628 """
629 if isinstance(others, Node):
630 # Check for trivial case
631 if others is self:
632 for node in self._GetPathAsLinkedList():
633 yield node
634 return
636 # Check if both are in the same tree.
637 if self._root is not others._root:
638 raise NotInSameTreeError(f"Node 'others' is not in the same tree.")
640 # Compute paths top-down and walk both paths until they deviate
641 for left, right in zip(self.Path, others.Path):
642 if left is right:
643 yield left
644 else:
645 return
646 elif isinstance(others, Iterable):
647 raise NotImplementedError(f"Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.")
649 def GetChildren(self) -> Generator['Node', None, None]:
650 """
651 A generator to iterate all direct children of the current node.
653 :returns: A generator to iterate all children.
655 .. seealso::
657 :meth:`GetDescendants` |br|
658 |rarr| Iterate all descendants.
659 :meth:`IterateLevelOrder` |br|
660 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
661 :meth:`IteratePreOrder` |br|
662 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
663 :meth:`IteratePostOrder` |br|
664 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
665 """
666 for child in self._children:
667 yield child
669 def GetSiblings(self) -> Generator['Node', None, None]:
670 """
671 A generator to iterate all siblings.
673 Siblings are child nodes of the current node's parent node, without the current node itself.
675 :returns: A generator to iterate all siblings of the current node.
676 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
677 """
678 if self._parent is None:
679 raise NoSiblingsError(f"Root node has no siblings.")
681 for node in self._parent:
682 if node is self:
683 continue
685 yield node
687 def GetLeftSiblings(self) -> Generator['Node', None, None]:
688 """
689 A generator to iterate all siblings left from the current node.
691 Siblings are child nodes of the current node's parent node, without the current node itself.
693 :returns: A generator to iterate all siblings left of the current node.
694 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
695 """
696 if self._parent is None:
697 raise NoSiblingsError(f"Root node has no siblings.")
699 for node in self._parent:
700 if node is self:
701 break
703 yield node
704 else:
705 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
707 def GetRightSiblings(self) -> Generator['Node', None, None]:
708 """
709 A generator to iterate all siblings right from the current node.
711 Siblings are child nodes of the current node's parent node, without the current node itself.
713 :returns: A generator to iterate all siblings right of the current node.
714 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
715 """
716 if self._parent is None:
717 raise NoSiblingsError(f"Root node has no siblings.")
719 iterator = iter(self._parent)
720 for node in iterator:
721 if node is self:
722 break
723 else:
724 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover
726 for node in iterator:
727 yield node
729 def GetDescendants(self) -> Generator['Node', None, None]:
730 """
731 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder`
732 it doesn't include the node itself.
734 :returns: A generator to iterate all descendants.
736 .. seealso::
738 :meth:`GetChildren` |br|
739 |rarr| Iterate all children, but no grand-children.
740 :meth:`IterateLevelOrder` |br|
741 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
742 :meth:`IteratePreOrder` |br|
743 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
744 :meth:`IteratePostOrder` |br|
745 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
746 """
747 for child in self._children:
748 yield child
749 yield from child.GetDescendants()
751 def GetRelatives(self):
752 """
753 A generator to iterate all relatives (all siblings and all their descendants) of the current node.
755 :returns: A generator to iterate all relatives.
756 """
757 for node in self.GetSiblings():
758 yield node
759 yield from node.GetDescendants()
761 def GetLeftRelatives(self):
762 """
763 A generator to iterate all left relatives (left siblings and all their descendants) of the current node.
765 :returns: A generator to iterate all left relatives.
766 """
767 for node in self.GetLeftSiblings():
768 yield node
769 yield from node.GetDescendants()
771 def GetRightRelatives(self):
772 """
773 A generator to iterate all right relatives (right siblings and all their descendants) of the current node.
775 :returns: A generator to iterate all right relatives.
776 """
777 for node in self.GetRightSiblings():
778 yield node
779 yield from node.GetDescendants()
781 def IterateLeafs(self) -> Generator['Node', None, None]:
782 """
783 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.
785 :returns: A generator to iterate leaf-nodes reachable from current node.
786 """
787 for child in self._children:
788 if child.IsLeaf:
789 yield child
790 else:
791 yield from child.IterateLeafs()
793 def IterateLevelOrder(self) -> Generator['Node', None, None]:
794 """
795 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`,
796 this includes also the node itself as the first returned node.
798 :returns: A generator to iterate all siblings level-by-level.
800 .. seealso::
802 :meth:`GetChildren` |br|
803 |rarr| Iterate all children, but no grand-children.
804 :meth:`GetDescendants` |br|
805 |rarr| Iterate all descendants.
806 :meth:`IteratePreOrder` |br|
807 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
808 :meth:`IteratePostOrder` |br|
809 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
810 """
811 queue = deque([self])
812 while queue:
813 currentNode = queue.pop()
814 yield currentNode
815 for node in currentNode._children:
816 queue.appendleft(node)
818 def IteratePreOrder(self) -> Generator['Node', None, None]:
819 """
820 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes
821 also the node itself as the first returned node.
823 :returns: A generator to iterate all siblings in pre-order.
825 .. seealso::
827 :meth:`GetChildren` |br|
828 |rarr| Iterate all children, but no grand-children.
829 :meth:`GetDescendants` |br|
830 |rarr| Iterate all descendants.
831 :meth:`IterateLevelOrder` |br|
832 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
833 :meth:`IteratePostOrder` |br|
834 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
835 """
836 yield self
837 for child in self._children:
838 yield from child.IteratePreOrder()
840 def IteratePostOrder(self) -> Generator['Node', None, None]:
841 """
842 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this
843 includes also the node itself as the last returned node.
845 :returns: A generator to iterate all siblings in post-order.
847 .. seealso::
849 :meth:`GetChildren` |br|
850 |rarr| Iterate all children, but no grand-children.
851 :meth:`GetDescendants` |br|
852 |rarr| Iterate all descendants.
853 :meth:`IterateLevelOrder` |br|
854 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
855 :meth:`IteratePreOrder` |br|
856 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
857 """
858 for child in self._children:
859 yield from child.IteratePostOrder()
860 yield self
862 def WalkTo(self, other: 'Node') -> Generator['Node', None, None]:
863 """
864 Returns a generator to iterate the path from node to another node.
866 :param other: Node to walk to.
867 :returns: Generator to iterate the path from node to other node.
868 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree.
869 """
870 # Check for trivial case
871 if other is self:
872 yield from ()
874 # Check if both are in the same tree.
875 if self._root is not other._root:
876 raise NotInSameTreeError(f"Node 'other' is not in the same tree.")
878 # Compute both paths to the root.
879 # 1. Walk from self to root, until a first common ancestor is found.
880 # 2. Walk from there to other (reverse paths)
881 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk.
882 index = len(otherPath)
883 for node in self.GetAncestors():
884 try:
885 index = otherPath.index(node)
886 break
887 except ValueError:
888 yield node
890 for i in range(index, len(otherPath)):
891 yield otherPath[i]
893 def GetNodeByID(self, nodeID: IDType) -> 'Node':
894 """
895 Lookup a node by its unique ID.
897 :param nodeID: ID of a node to lookup in the tree.
898 :returns: Node for the given ID.
899 :raises ValueError: If parameter ``nodeID`` is None.
900 :raises KeyError: If parameter ``nodeID`` is not found in the tree.
901 """
902 if nodeID is None:
903 raise ValueError(f"'None' is not supported as an ID value.")
905 return self._root._nodesWithID[nodeID]
907 def Find(self, predicate: Callable) -> Generator['Node', None, None]:
908 raise NotImplementedError(f"Method 'Find' is not yet implemented.")
910 def __iter__(self) -> Iterator['Node']:
911 """
912 Returns an iterator to iterate all child nodes.
914 :returns: Children iterator.
915 """
916 return iter(self._children)
918 def __len__(self) -> int:
919 """
920 Returns the number of children, but not including grand-children.
922 :returns: Number of child nodes.
923 """
924 return len(self._children)
926 def __repr__(self) -> str:
927 """
928 Returns a detailed string representation of the node.
930 :returns: The detailed string representation of the node.
931 """
932 nodeID = parent = value = ""
933 if self._id is not None:
934 nodeID = f"; nodeID='{self._id}'"
935 if (self._parent is not None) and (self._parent._id is not None):
936 parent = f"; parent='{self._parent._id}'"
937 if self._value is not None:
938 value = f"; value='{self._value}'"
940 return f"<node{nodeID}{parent}{value}>"
942 def __str__(self) -> str:
943 """
944 Return a string representation of the node.
946 Order of resolution:
948 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
949 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
950 3. Else, return :meth:`__repr__`.
952 :returns: The resolved string representation of the node.
953 """
954 if self._value is not None:
955 return str(self._value)
956 elif self._id is not None:
957 return str(self._id)
958 else:
959 return self.__repr__()
961 def Render(
962 self,
963 prefix: str = "",
964 lineend: str = "\n",
965 nodeMarker: str = "├─",
966 lastNodeMarker: str = "└─",
967 bypassMarker: str = "│ "
968 ) -> str:
969 """
970 Render the tree as ASCII art.
972 :param prefix: A string printed in front of every line, e.g. for indentation. Default: ``""``.
973 :param lineend: A string printed at the end of every line. Default: ``"\\n"``.
974 :param nodeMarker: A string printed before every non-last tree node. Default: ``"├─"``.
975 :param lastNodeMarker: A string printed before every last tree node. Default: ``"└─"``.
976 :param bypassMarker: A string printed when there are further nodes in the parent level. Default: ``"│ "``.
977 :return: A rendered tree as multiline string.
978 """
979 emptyMarker = " " * len(bypassMarker)
981 def _render(node: Node, markers: str):
982 result = []
984 if node.HasChildren:
985 for child in node._children[:-1]:
986 nodeRepresentation = child._format(child) if child._format else str(child)
987 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}")
988 result.extend(_render(child, markers + bypassMarker))
990 # last child node
991 child = node._children[-1]
992 nodeRepresentation = child._format(child) if child._format else str(child)
993 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}")
994 result.extend(_render(child, markers + emptyMarker))
996 return result
998 # Root element
999 nodeRepresentation = self._format(self) if self._format else str(self)
1000 result = [f"{prefix}{nodeRepresentation}{lineend}"]
1001 result.extend(_render(self, ""))
1003 return "".join(result)