Coverage for pyTooling/Tree/__init__.py: 90%
372 statements
« prev ^ index » next coverage.py v7.16.2, created at 2026-10-03 23:02 +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"""
32A powerful tree data structure for Python.
34.. seealso::
36 :mod:`pyTooling.Graph`
37 |rarr| A graph, of which a tree is the acyclic single-rooted case.
38 :mod:`pyTooling.Graph.GraphML`
39 |rarr| Writing a tree as a GraphML document.
40 :mod:`pyTooling.LinkedList`
41 |rarr| An object-oriented doubly linked-list data structure.
42"""
43from __future__ import annotations
45from collections import deque
46from typing import TypeVar, Generic, Deque, Union, Optional as Nullable
47from typing import Any, Callable, Iterator, Generator, Iterable, Mapping, Hashable
49from pyTooling.Decorators import export, readonly
50from pyTooling.MetaClasses import ExtendedType
51from pyTooling.Exceptions import ToolingException
52from pyTooling.Common import getFullyQualifiedName
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 TreeError(ToolingException):
70 """Base exception of all exceptions raised by :mod:`pyTooling.Tree`."""
73@export
74class InternalError(TreeError):
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(TreeError):
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(TreeError):
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(TreeError):
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::
124 The top-down construction should be preferred, because it's slightly faster.
126 Each tree uses the **root** node (a.k.a. tree-representative) to store some per-tree data structures. E.g. a list of
127 all IDs in a tree. For easy and quick access to such data structures, each sibling node contains a reference to the
128 root node (:attr:`_root`). In case of adding a tree to an existing tree, such data structures get merged and all added
129 nodes get assigned with new root references. Use the read-only property :attr:`Root` to access the root reference.
131 The reference to the parent node (:attr:`_parent`) can be access via property :attr:`Parent`. If the property's setter
132 is used, a node and all its siblings are added to another tree or to a new position in the same tree.
134 The references to all node's children is stored in a list (:attr:`_children`). Children, siblings, ancestors, can be
135 accessed via various generators:
137 * :meth:`GetAncestors` |rarr| iterate all ancestors bottom-up.
138 * :meth:`GetChildren` |rarr| iterate all direct children.
139 * :meth:`GetDescendants` |rarr| iterate all descendants.
140 * :meth:`IterateLevelOrder` |rarr| IterateLevelOrder.
141 * :meth:`IteratePreOrder` |rarr| iterate siblings in pre-order.
142 * :meth:`IteratePostOrder` |rarr| iterate siblings in post-order.
144 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
145 dictionary (:attr:`_nodesWithID`). In case no ID is given, all such ID-less nodes are collected in a single bin and store as a
146 list of nodes. An ID can be modified after the Node was created. Use the read-only property :attr:`ID` to access
147 the ID.
149 Each node can have a **value** (:attr:`_value`), which can be given at node creation time, or it can be assigned and/or
150 modified later. Use the property :attr:`Value` to get or set the value.
152 Moreover, each node can store various key-value-pairs (:attr:`_dict`). Use the dictionary syntax to get and set
153 key-value-pairs.
154 """
156 _id: Nullable[IDType] #: Unique identifier of a node. ``None`` if not used.
157 _nodesWithID: Nullable[dict[IDType, Node]] #: Dictionary of all IDs in the tree. ``None`` if it's not the root node.
158 _nodesWithoutID: Nullable[list[Node]] #: List of all nodes without an ID in the tree. ``None`` if it's not the root node.
159 _root: Node #: Reference to the root of a tree. ``self`` if it's the root node.
160 _parent: Nullable[Node] #: Reference to the parent node. ``None`` if it's the root node.
161 _children: list[Node] #: List of all children
162# _links: list['Node']
164 _level: int #: Level of the node (distance to the root).
165 _value: Nullable[ValueType] #: Field to store the node's value.
166 _dict: dict[DictKeyType, DictValueType] #: Dictionary to store key-value-pairs attached to the node.
168 _format: Nullable[Callable[[Node], str]] #: A node formatting function returning a one-line representation for tree-rendering.
170 def __init__(
171 self,
172 nodeID: Nullable[IDType] = None,
173 value: Nullable[ValueType] = None,
174 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
175 parent: Nullable[Node] = None,
176 children: Nullable[Iterable[Node]] = None,
177 format: Nullable[Callable[[Node], str]] = None
178 ) -> None:
179 """
180 .. todo:: TREE::Node::init Needs documentation.
182 :param nodeID: Optional, unique ID of a node within the whole tree data structure.
183 :param value: Optional, value of the node.
184 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
185 :param parent: Optional, parent node in the tree.
186 :param children: Optional, list of child nodes.
187 :param format: Optional, node formatting function returning a one-line representation for
188 tree-rendering.
190 :raises TypeError: If parameter parent is not an instance of Node.
191 :raises ValueError: If nodeID already exists in the tree.
192 :raises TypeError: If parameter children is not iterable.
193 :raises ValueError: If an element of children is not an instance of Node.
194 """
196 self._id = nodeID
197 self._value = value
198 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
200 self._format = format
202 if parent is not None and not isinstance(parent, Node):
203 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
204 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
205 raise ex
207 if parent is None:
208 self._root = self
209 self._parent = None
210 self._level = 0
212 self._nodesWithID = {}
213 self._nodesWithoutID = []
214 if nodeID is None:
215 self._nodesWithoutID.append(self)
216 else:
217 self._nodesWithID[nodeID] = self
218 else:
219 self._root = parent._root
220 self._parent = parent
221 self._level = parent._level + 1
222 self._nodesWithID = None
223 self._nodesWithoutID = None
225 if nodeID is None:
226 self._root._nodesWithoutID.append(self)
227 elif nodeID in self._root._nodesWithID:
228 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
229 else:
230 self._root._nodesWithID[nodeID] = self
232 parent._children.append(self)
234 self._children = []
235 if children is not None:
236 if not isinstance(children, Iterable):
237 ex = TypeError("Parameter 'children' is not iterable.")
238 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.")
239 raise ex
241 for child in children:
242 if not isinstance(child, Node):
243 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
244 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
245 raise ex
247 child.Parent = self
249 @readonly
250 def ID(self) -> Nullable[IDType]:
251 """
252 Read-only property to access the unique ID of a node (:attr:`_id`).
254 If no ID was given at node construction time, ID return None.
256 :returns: Unique ID of a node, if ID was given at node creation time, else None.
257 """
258 return self._id
260 @property
261 def Value(self) -> Nullable[ValueType]:
262 """
263 Property to get and set the value (:attr:`_value`) of a node.
265 :returns: The value of a node.
266 """
267 return self._value
269 @Value.setter
270 def Value(self, value: Nullable[ValueType]) -> None:
271 self._value = value
273 def __getitem__(self, key: DictKeyType) -> DictValueType:
274 """
275 Read a node's attached attributes (key-value-pairs) by key.
277 :param key: The key to look for.
278 :returns: The value associated to the given key.
279 """
280 return self._dict[key]
282 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
283 """
284 Create or update a node's attached attributes (key-value-pairs) by key.
286 If a key doesn't exist yet, a new key-value-pair is created.
288 :param key: The key to create or update.
289 :param value: Optional, the value to associate to the given key.
290 """
291 self._dict[key] = value
293 def __delitem__(self, key: DictKeyType) -> None:
294 """
295 Remove an attached attribute (key-value-pair) from the node by key.
297 :param key: The key to remove.
298 :raises KeyError: If the key does not exist.
299 """
300 del self._dict[key]
302 def __contains__(self, key: DictKeyType) -> bool:
303 """
304 Check if a key exists in the node's attached attributes.
306 :param key: The key to look for.
307 :returns: ``True``, if the key exists.
308 """
309 return key in self._dict
311 def __len__(self) -> int:
312 """
313 Returns the number of attached attributes (key-value-pairs) on this node.
315 :returns: Number of attached attributes.
316 """
317 return len(self._dict)
319 @readonly
320 def Root(self) -> Node:
321 """
322 Read-only property to access the tree's root node (:attr:`_root`).
324 :returns: The root node (representative node) of a tree.
325 """
326 return self._root
328 @property
329 def Parent(self) -> Nullable[Node]:
330 """
331 Property to access the parent (:attr:`_parent`) of a node.
333 Assigning ``None`` detaches the node from its tree, which makes it the root node of the subtree it carries.
334 Assigning a node appends this node - and everything below it - to that node's tree.
336 .. note::
338 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and
339 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`.
341 :returns: The parent of a node, or ``None`` if the node is a root node.
342 :raises TypeError: If a node that is not a :class:`Node` is assigned.
343 :raises AlreadyInTreeError: If the assigned parent is already a child node in this tree.
344 """
345 return self._parent
347 @Parent.setter
348 def Parent(self, parent: Nullable[Node]) -> None:
349 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root
351 if parent is None:
352 self._nodesWithID = {}
353 self._nodesWithoutID = []
354 self._level = 0
356 if self._id is None:
357 self._nodesWithoutID.append(self)
358 self._root._nodesWithoutID.remove(self)
359 else:
360 self._nodesWithID[self._id] = self
361 del self._nodesWithID[self._id]
363 for sibling in self.GetDescendants():
364 sibling._root = self
365 sibling._level = sibling._parent._level + 1
366 if sibling._id is None:
367 self._nodesWithoutID.append(sibling)
368 self._root._nodesWithoutID.remove(sibling)
369 else:
370 self._nodesWithID[sibling._id] = sibling
371 del self._nodesWithID[sibling._id]
373 self._parent._children.remove(self)
375 self._root = self
376 self._parent = None
377 elif not isinstance(parent, Node):
378 ex = TypeError("Parameter 'parent' is not of type 'Node'.")
379 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.")
380 raise ex
381 else:
382 if parent._root is self._root:
383 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.")
385 self._root = parent._root
386 self._parent = parent
387 self._level = parent._level + 1
388 for node in self.GetDescendants():
389 node._level = node._parent._level + 1
390 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID)
391 self._nodesWithID = self._nodesWithoutID = None
392 parent._children.append(self)
394 @readonly
395 def Siblings(self) -> tuple[Node, ...]:
396 """
397 A read-only property to return a tuple of all siblings from the current node.
399 If the current node is the only child, the tuple is empty.
401 Siblings are child nodes of the current node's parent node, without the current node itself.
403 :returns: A tuple of all siblings of the current node.
404 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
405 """
406 if self._parent is None:
407 raise NoSiblingsError("Root node has no siblings.")
409 return tuple([node for node in self._parent if node is not self])
411 @readonly
412 def LeftSiblings(self) -> tuple[Node, ...]:
413 """
414 A read-only property to return a tuple of all siblings left from the current node.
416 If the current node is the only child, the tuple is empty.
418 Siblings are child nodes of the current node's parent node, without the current node itself.
420 :returns: A tuple of all siblings left of the current node.
421 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
422 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its parent's
423 children.
424 """
425 if self._parent is None:
426 raise NoSiblingsError("Root node has no siblings.")
428 result = []
429 for node in self._parent:
430 if node is not self:
431 result.append(node)
432 else:
433 break
434 else:
435 raise InternalError("Data structure corruption: Self is not part of parent's children.") # pragma: no cover
437 return tuple(result)
439 @readonly
440 def RightSiblings(self) -> tuple[Node, ...]:
441 """
442 A read-only property to return a tuple of all siblings right from the current node.
444 If the current node is the only child, the tuple is empty.
446 Siblings are child nodes of the current node's parent node, without the current node itself.
448 :returns: A tuple of all siblings right of the current node.
449 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
450 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its parent's
451 children.
452 """
453 if self._parent is None:
454 raise NoSiblingsError("Root node has no siblings.")
456 result = []
457 iterator = iter(self._parent)
458 for node in iterator:
459 if node is self:
460 break
461 else:
462 raise InternalError("Data structure corruption: Self is not part of parent's children.") # pragma: no cover
464 for node in iterator:
465 result.append(node)
467 return tuple(result)
469 def _GetPathAsLinkedList(self) -> Deque[Node]:
470 """
471 Compute the path from current node to root node by using a linked list (:class:`deque`).
473 :meta private:
474 :returns: Path from node to root node as double-ended queue (deque).
475 """
476 path: Deque[Node] = deque()
478 node = self
479 while node is not None:
480 path.appendleft(node)
481 node = node._parent
483 return path
485 @readonly
486 def Path(self) -> tuple[Node]:
487 """
488 Read-only property to return the path from root node to the node as a tuple of nodes.
490 :returns: A tuple of nodes describing the path from root node to the node.
491 """
492 return tuple(self._GetPathAsLinkedList())
494 @readonly
495 def Level(self) -> int:
496 """
497 Read-only property to access a node's level in the tree.
499 The level is the distance to the root node.
501 :returns: The node's level.
502 """
503 return self._level
505 @readonly
506 def Size(self) -> int:
507 """
508 Read-only property to return the size of the tree.
510 :returns: Count of all nodes in the tree structure.
511 """
512 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID)
514 @readonly
515 def IsRoot(self) -> bool:
516 """
517 Returns true, if the node is the root node (representative node of the tree).
519 :returns: ``True``, if node is the root node.
520 """
521 return self._parent is None
523 @readonly
524 def IsLeaf(self) -> bool:
525 """
526 Returns true, if the node is a leaf node (has no children).
528 :returns: ``True``, if node has no children.
529 """
530 return len(self._children) == 0
532 @readonly
533 def HasChildren(self) -> bool:
534 """
535 Returns true, if the node has child nodes.
537 :returns: ``True``, if node has children.
538 """
539 return len(self._children) > 0
541 def _SetNewRoot(self, nodesWithIDs: dict[Node, Node], nodesWithoutIDs: list[Node]) -> None:
542 """
543 Move the given nodes into this node's tree.
545 :param nodesWithIDs: Nodes with an ID, which have to stay unique within the tree.
546 :param nodesWithoutIDs: Nodes without an ID.
547 :raises ValueError: If one of the IDs already exists in this tree.
548 """
549 for nodeID, node in nodesWithIDs.items():
550 if nodeID in self._root._nodesWithID:
551 raise ValueError(f"ID '{nodeID}' already exists in this tree.")
552 else:
553 self._root._nodesWithID[nodeID] = node
554 node._root = self._root
556 for node in nodesWithoutIDs:
557 self._root._nodesWithoutID.append(node)
558 node._root = self._root
560 def AddChild(self, child: Node) -> None:
561 """
562 Add a child node to the current node of the tree.
564 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and
565 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`).
567 :param child: The child node to be added to the tree.
568 :raises TypeError: If parameter ``child`` is not a :class:`Node`.
569 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree.
571 .. seealso::
573 :attr:`Parent`
574 |rarr| Set the parent of a node.
575 :meth:`AddChildren`
576 |rarr| Add multiple children at once.
577 """
578 if not isinstance(child, Node):
579 ex = TypeError("Parameter 'child' is not of type 'Node'.")
580 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
581 raise ex
583 if child._root is self._root:
584 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
586 child._root = self._root
587 child._parent = self
588 child._level = self._level + 1
589 for node in child.GetDescendants():
590 node._level = node._parent._level + 1
591 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
592 child._nodesWithID = child._nodesWithoutID = None
593 self._children.append(child)
595 def AddChildren(self, children: Iterable[Node]) -> None:
596 """
597 Add multiple children nodes to the current node of the tree.
599 :param children: Optional, the list of children nodes to be added to the tree.
600 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`.
601 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree.
603 .. seealso::
605 :attr:`Parent`
606 |rarr| Set the parent of a node.
607 :meth:`AddChild`
608 |rarr| Add a child node to the tree.
609 """
610 for child in children:
611 if not isinstance(child, Node):
612 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.")
613 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.")
614 raise ex
616 if child._root is self._root:
617 # TODO: create a more specific exception
618 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.")
620 child._root = self._root
621 child._parent = self
622 child._level = self._level + 1
623 for node in child.GetDescendants():
624 node._level = node._parent._level + 1
625 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID)
626 child._nodesWithID = child._nodesWithoutID = None
627 self._children.append(child)
629 def GetPath(self) -> Generator[Node, None, None]:
630 """
631 Compute the path from the root node to this node.
633 :returns: A generator yielding the nodes from the root down to this node.
634 """
635 for node in self._GetPathAsLinkedList():
636 yield node
638 def GetAncestors(self) -> Generator[Node, None, None]:
639 """
640 Iterate the ancestors of this node.
642 :returns: A generator yielding the parent, its parent, and so on up to the root node.
643 """
644 node = self._parent
645 while node is not None:
646 yield node
647 node = node._parent
649 def GetCommonAncestors(self, others: Union[Node, Iterable[Node]]) -> Generator[Node, None, None]:
650 """
651 Compute the common ancestors of this node and one or more other nodes.
653 The nodes' paths from the root are walked in parallel and yielded as long as they are identical, so the last
654 yielded node is the nearest common ancestor.
656 :param others: Another node, or an iterable of nodes, to compute the common ancestors with.
657 :returns: A generator yielding the common ancestors, starting at the root node.
658 :raises NotInSameTreeError: If one of the given nodes is not in the same tree.
659 :raises NotImplementedError: If more than one other node is given; the common ancestors of a set of nodes are
660 not computed yet.
661 """
662 if isinstance(others, Node):
663 # Check for trivial case
664 if others is self:
665 for node in self._GetPathAsLinkedList():
666 yield node
667 return
669 # Check if both are in the same tree.
670 if self._root is not others._root:
671 raise NotInSameTreeError("Node 'others' is not in the same tree.")
673 # Compute paths top-down and walk both paths until they deviate
674 for left, right in zip(self.Path, others.Path):
675 if left is right:
676 yield left
677 else:
678 return
679 elif isinstance(others, Iterable):
680 raise NotImplementedError("Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.")
682 def GetChildren(self) -> Generator[Node, None, None]:
683 """
684 A generator to iterate all direct children of the current node.
686 :returns: A generator to iterate all children.
688 .. seealso::
690 :meth:`GetDescendants`
691 |rarr| Iterate all descendants.
692 :meth:`IterateLevelOrder`
693 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
694 :meth:`IteratePreOrder`
695 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
696 :meth:`IteratePostOrder`
697 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
698 """
699 for child in self._children:
700 yield child
702 def GetSiblings(self) -> Generator[Node, None, None]:
703 """
704 A generator to iterate all siblings.
706 Siblings are child nodes of the current node's parent node, without the current node itself.
708 :returns: A generator to iterate all siblings of the current node.
709 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
710 """
711 if self._parent is None:
712 raise NoSiblingsError("Root node has no siblings.")
714 for node in self._parent:
715 if node is self:
716 continue
718 yield node
720 def GetLeftSiblings(self) -> Generator[Node, None, None]:
721 """
722 A generator to iterate all siblings left from the current node.
724 Siblings are child nodes of the current node's parent node, without the current node itself.
726 :returns: A generator to iterate all siblings left of the current node.
727 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
728 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its
729 parent's children.
730 """
731 if self._parent is None:
732 raise NoSiblingsError("Root node has no siblings.")
734 for node in self._parent:
735 if node is self:
736 break
738 yield node
739 else:
740 raise InternalError("Data structure corruption: Self is not part of parent's children.") # pragma: no cover
742 def GetRightSiblings(self) -> Generator[Node, None, None]:
743 """
744 A generator to iterate all siblings right from the current node.
746 Siblings are child nodes of the current node's parent node, without the current node itself.
748 :returns: A generator to iterate all siblings right of the current node.
749 :raises NoSiblingsError: If the current node has no parent node and thus no siblings.
750 :raises InternalError: If the tree's data structure is corrupted, because this node is not one of its
751 parent's children.
752 """
753 if self._parent is None:
754 raise NoSiblingsError("Root node has no siblings.")
756 iterator = iter(self._parent)
757 for node in iterator:
758 if node is self:
759 break
760 else:
761 raise InternalError("Data structure corruption: Self is not part of parent's children.") # pragma: no cover
763 for node in iterator:
764 yield node
766 def GetDescendants(self) -> Generator[Node, None, None]:
767 """
768 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder`
769 it doesn't include the node itself.
771 :returns: A generator to iterate all descendants.
773 .. seealso::
775 :meth:`GetChildren`
776 |rarr| Iterate all children, but no grand-children.
777 :meth:`IterateLevelOrder`
778 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
779 :meth:`IteratePreOrder`
780 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
781 :meth:`IteratePostOrder`
782 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
783 """
784 for child in self._children:
785 yield child
786 yield from child.GetDescendants()
788 def GetRelatives(self) -> Generator[Node, None, None]:
789 """
790 A generator to iterate all relatives (all siblings and all their descendants) of the current node.
792 :returns: A generator to iterate all relatives.
793 """
794 for node in self.GetSiblings():
795 yield node
796 yield from node.GetDescendants()
798 def GetLeftRelatives(self) -> Generator[Node, None, None]:
799 """
800 A generator to iterate all left relatives (left siblings and all their descendants) of the current node.
802 :returns: A generator to iterate all left relatives.
803 """
804 for node in self.GetLeftSiblings():
805 yield node
806 yield from node.GetDescendants()
808 def GetRightRelatives(self) -> Generator[Node, None, None]:
809 """
810 A generator to iterate all right relatives (right siblings and all their descendants) of the current node.
812 :returns: A generator to iterate all right relatives.
813 """
814 for node in self.GetRightSiblings():
815 yield node
816 yield from node.GetDescendants()
818 def IterateLeafs(self) -> Generator[Node, None, None]:
819 """
820 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node.
822 :returns: A generator to iterate leaf-nodes reachable from current node.
823 """
824 for child in self._children:
825 if child.IsLeaf:
826 yield child
827 else:
828 yield from child.IterateLeafs()
830 def IterateLevelOrder(self) -> Generator[Node, None, None]:
831 """
832 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`,
833 this includes also the node itself as the first returned node.
835 :returns: A generator to iterate all siblings level-by-level.
837 .. seealso::
839 :meth:`GetChildren`
840 |rarr| Iterate all children, but no grand-children.
841 :meth:`GetDescendants`
842 |rarr| Iterate all descendants.
843 :meth:`IteratePreOrder`
844 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
845 :meth:`IteratePostOrder`
846 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
847 """
848 queue = deque([self])
849 while queue:
850 currentNode = queue.pop()
851 yield currentNode
852 for node in currentNode._children:
853 queue.appendleft(node)
855 def IteratePreOrder(self) -> Generator[Node, None, None]:
856 """
857 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes
858 also the node itself as the first returned node.
860 :returns: A generator to iterate all siblings in pre-order.
862 .. seealso::
864 :meth:`GetChildren`
865 |rarr| Iterate all children, but no grand-children.
866 :meth:`GetDescendants`
867 |rarr| Iterate all descendants.
868 :meth:`IterateLevelOrder`
869 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
870 :meth:`IteratePostOrder`
871 |rarr| Iterate items in post-order, which includes the node itself as a last returned node.
872 """
873 yield self
874 for child in self._children:
875 yield from child.IteratePreOrder()
877 def IteratePostOrder(self) -> Generator[Node, None, None]:
878 """
879 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this
880 includes also the node itself as the last returned node.
882 :returns: A generator to iterate all siblings in post-order.
884 .. seealso::
886 :meth:`GetChildren`
887 |rarr| Iterate all children, but no grand-children.
888 :meth:`GetDescendants`
889 |rarr| Iterate all descendants.
890 :meth:`IterateLevelOrder`
891 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node.
892 :meth:`IteratePreOrder`
893 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node.
894 """
895 for child in self._children:
896 yield from child.IteratePostOrder()
897 yield self
899 def WalkTo(self, other: Node) -> Generator[Node, None, None]:
900 """
901 Returns a generator to iterate the path from node to another node.
903 :param other: Node to walk to.
904 :returns: Generator to iterate the path from node to other node.
905 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree.
906 """
907 # Check for trivial case
908 if other is self:
909 yield from ()
911 # Check if both are in the same tree.
912 if self._root is not other._root:
913 raise NotInSameTreeError("Node 'other' is not in the same tree.")
915 # Compute both paths to the root.
916 # 1. Walk from self to root, until a first common ancestor is found.
917 # 2. Walk from there to other (reverse paths)
918 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk.
919 index = len(otherPath)
920 for node in self.GetAncestors():
921 try:
922 index = otherPath.index(node)
923 break
924 except ValueError:
925 yield node
927 for i in range(index, len(otherPath)):
928 yield otherPath[i]
930 def GetNodeByID(self, nodeID: IDType) -> Node:
931 """
932 Lookup a node by its unique ID.
934 :param nodeID: Optional, ID of a node to lookup in the tree.
935 :returns: Node for the given ID.
936 :raises ValueError: If parameter ``nodeID`` is None.
937 :raises KeyError: If parameter ``nodeID`` is not found in the tree.
938 """
939 if nodeID is None:
940 raise ValueError("'None' is not supported as an ID value.")
942 return self._root._nodesWithID[nodeID]
944 def Find(self, predicate: Callable[[Node], bool]) -> Generator[Node, None, None]:
945 """
946 Search the tree for nodes matching a predicate.
948 :param predicate: Filter function accepting a node and returning a boolean.
949 :returns: A generator yielding the matching nodes.
950 :raises NotImplementedError: Searching a tree is not implemented yet.
951 """
952 raise NotImplementedError("Method 'Find' is not yet implemented.")
954 def __iter__(self) -> Iterator[Node]:
955 """
956 Returns an iterator to iterate all child nodes.
958 :returns: Children iterator.
959 """
960 return iter(self._children)
962 def __len__(self) -> int:
963 """
964 Returns the number of children, but not including grand-children.
966 :returns: Number of child nodes.
967 """
968 return len(self._children)
970 def __repr__(self) -> str:
971 """
972 Returns a detailed string representation of the node.
974 :returns: The detailed string representation of the node.
975 """
976 nodeID = parent = value = ""
977 if self._id is not None:
978 nodeID = f"; nodeID='{self._id}'"
980 if (self._parent is not None) and (self._parent._id is not None):
981 parent = f"; parent='{self._parent._id}'"
983 if self._value is not None:
984 value = f"; value='{self._value}'"
986 return f"<node{nodeID}{parent}{value}>"
988 def __str__(self) -> str:
989 """
990 Return a string representation of the node.
992 Order of resolution:
994 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
995 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
996 3. Else, return :meth:`__repr__`.
998 :returns: The resolved string representation of the node.
999 """
1000 if self._value is not None:
1001 return str(self._value)
1002 elif self._id is not None:
1003 return str(self._id)
1004 else:
1005 return self.__repr__()
1007 def Render(
1008 self,
1009 prefix: str = "",
1010 lineend: str = "\n",
1011 nodeMarker: str = "├─",
1012 lastNodeMarker: str = "└─",
1013 bypassMarker: str = "│ "
1014 ) -> str:
1015 """
1016 Render the tree as ASCII art.
1018 :param prefix: Optional, a string printed in front of every line, e.g. for indentation. Default: ``""``.
1019 :param lineend: Optional, a string printed at the end of every line. Default: ``"\\n"``.
1020 :param nodeMarker: Optional, a string printed before every non-last tree node. Default: ``"├─"``.
1021 :param lastNodeMarker: Optional, a string printed before every last tree node. Default: ``"└─"``.
1022 :param bypassMarker: Optional, a string printed when there are further nodes in the parent level. Default: ``"│
1023 "``.
1024 :returns: A rendered tree as multiline string.
1025 """
1026 emptyMarker = " " * len(bypassMarker)
1028 def _render(node: Node, markers: str):
1029 """
1030 Nested function for recursion.
1032 :param node: The node whose children are rendered.
1033 :param markers: The prefix of the current level, assembled from the join and bypass markers.
1034 :returns: The rendered lines of that subtree.
1035 """
1036 result = []
1038 if node.HasChildren:
1039 for child in node._children[:-1]:
1040 nodeRepresentation = child._format(child) if child._format else str(child)
1041 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}")
1042 result.extend(_render(child, markers + bypassMarker))
1044 # last child node
1045 child = node._children[-1]
1046 nodeRepresentation = child._format(child) if child._format else str(child)
1047 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}")
1048 result.extend(_render(child, markers + emptyMarker))
1050 return result
1052 # Root element
1053 nodeRepresentation = self._format(self) if self._format else str(self)
1054 result = [f"{prefix}{nodeRepresentation}{lineend}"]
1055 result.extend(_render(self, ""))
1057 return "".join(result)