Coverage for pyTooling/Tree/__init__.py: 90%

372 statements  

« prev     ^ index     » next       coverage.py v7.11.0, created at 2025-10-19 06:41 +0000

1# ==================================================================================================================== # 

2# _____ _ _ _____ # 

3# _ __ _ |_ _|__ ___ | (_)_ __ __ _|_ _| __ ___ ___ # 

4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` | | || '__/ _ \/ _ \ # 

5# | |_) | |_| || | (_) | (_) | | | | | | (_| |_| || | | __/ __/ # 

6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)_||_| \___|\___| # 

7# |_| |___/ |___/ # 

8# ==================================================================================================================== # 

9# Authors: # 

10# Patrick Lehmann # 

11# # 

12# License: # 

13# ==================================================================================================================== # 

14# Copyright 2017-2025 Patrick Lehmann - Bötzingen, Germany # 

15# # 

16# Licensed under the Apache License, Version 2.0 (the "License"); # 

17# you may not use this file except in compliance with the License. # 

18# You may obtain a copy of the License at # 

19# # 

20# http://www.apache.org/licenses/LICENSE-2.0 # 

21# # 

22# Unless required by applicable law or agreed to in writing, software # 

23# distributed under the License is distributed on an "AS IS" BASIS, # 

24# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # 

25# See the License for the specific language governing permissions and # 

26# limitations under the License. # 

27# # 

28# SPDX-License-Identifier: Apache-2.0 # 

29# ==================================================================================================================== # 

30# 

31"""A powerful tree data structure for Python.""" 

32from collections import deque 

33from sys import version_info # needed for versions before Python 3.11 

34from typing import TypeVar, Generic, List, Tuple, Dict, Deque, Union, Optional as Nullable 

35from typing import Callable, Iterator, Generator, Iterable, Mapping, Hashable 

36 

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.*'!") 

44 

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 

53 

54 

55IDType = TypeVar("IDType", bound=Hashable) 

56"""A type variable for a tree's ID.""" 

57 

58ValueType = TypeVar("ValueType") 

59"""A type variable for a tree's value.""" 

60 

61DictKeyType = TypeVar("DictKeyType") 

62"""A type variable for a tree's dictionary keys.""" 

63 

64DictValueType = TypeVar("DictValueType") 

65"""A type variable for a tree's dictionary values.""" 

66 

67 

68@export 

69class TreeException(ToolingException): 

70 """Base exception of all exceptions raised by :mod:`pyTooling.Tree`.""" 

71 

72 

73@export 

74class InternalError(TreeException): 

75 """ 

76 The exception is raised when a data structure corruption is detected. 

77 

78 .. danger:: 

79 

80 This exception should never be raised. 

81 

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 """ 

85 

86 

87@export 

88class NoSiblingsError(TreeException): 

89 """ 

90 The exception is raised when a node has no parent and thus has no siblings. 

91 

92 .. hint:: 

93 

94 A node with no parent is the root node of the tree. 

95 """ 

96 

97 

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. 

102 

103 .. hint:: 

104 

105 A tree a an acyclic graph without cross-edges. Thus backward edges and cross edges are permitted. 

106 """ 

107 

108 

109@export 

110class NotInSameTreeError(TreeException): 

111 """The exception is raised when the current node and the other node are not in the same tree.""" 

112 

113 

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. 

118 

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. 

121 

122 .. hint:: The top-down construction should be preferred, because it's slightly faster. 

123 

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. 

128 

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. 

131 

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: 

134 

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. 

141 

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. 

146 

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. 

149 

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 """ 

153 

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'] 

161 

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. 

165 

166 _format: Nullable[Callable[["Node"], str]] #: A node formatting function returning a one-line representation for tree-rendering. 

167 

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. 

179 

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. 

186 

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 """ 

192 

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 {} 

196 

197 self._format = format 

198 

199 if parent is not None and not isinstance(parent, Node): 

200 ex = TypeError("Parameter 'parent' is not of type 'Node'.") 

201 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.") 

202 raise ex 

203 

204 if parent is None: 

205 self._root = self 

206 self._parent = None 

207 self._level = 0 

208 

209 self._nodesWithID = {} 

210 self._nodesWithoutID = [] 

211 if nodeID is None: 

212 self._nodesWithoutID.append(self) 

213 else: 

214 self._nodesWithID[nodeID] = self 

215 else: 

216 self._root = parent._root 

217 self._parent = parent 

218 self._level = parent._level + 1 

219 self._nodesWithID = None 

220 

221 if nodeID is None: 

222 self._root._nodesWithoutID.append(self) 

223 elif nodeID in self._root._nodesWithID: 

224 raise ValueError(f"ID '{nodeID}' already exists in this tree.") 

225 else: 

226 self._root._nodesWithID[nodeID] = self 

227 

228 parent._children.append(self) 

229 

230 self._children = [] 

231 if children is not None: 

232 if not isinstance(children, Iterable): 

233 ex = TypeError("Parameter 'children' is not iterable.") 

234 ex.add_note(f"Got type '{getFullyQualifiedName(children)}'.") 

235 raise ex 

236 

237 for child in children: 

238 if not isinstance(child, Node): 

239 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.") 

240 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.") 

241 raise ex 

242 

243 child.Parent = self 

244 

245 @readonly 

246 def ID(self) -> Nullable[IDType]: 

247 """ 

248 Read-only property to access the unique ID of a node (:attr:`_id`). 

249 

250 If no ID was given at node construction time, ID return None. 

251 

252 :returns: Unique ID of a node, if ID was given at node creation time, else None. 

253 """ 

254 return self._id 

255 

256 @property 

257 def Value(self) -> Nullable[ValueType]: 

258 """ 

259 Property to get and set the value (:attr:`_value`) of a node. 

260 

261 :returns: The value of a node. 

262 """ 

263 return self._value 

264 

265 @Value.setter 

266 def Value(self, value: Nullable[ValueType]) -> None: 

267 self._value = value 

268 

269 def __getitem__(self, key: DictKeyType) -> DictValueType: 

270 """ 

271 Read a node's attached attributes (key-value-pairs) by key. 

272 

273 :param key: The key to look for. 

274 :returns: The value associated to the given key. 

275 """ 

276 return self._dict[key] 

277 

278 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None: 

279 """ 

280 Create or update a node's attached attributes (key-value-pairs) by key. 

281 

282 If a key doesn't exist yet, a new key-value-pair is created. 

283 

284 :param key: The key to create or update. 

285 :param value: The value to associate to the given key. 

286 """ 

287 self._dict[key] = value 

288 

289 def __delitem__(self, key: DictKeyType) -> None: 

290 """ 

291 .. todo:: TREE::Node::__delitem__ Needs documentation. 

292 

293 """ 

294 del self._dict[key] 

295 

296 def __contains__(self, key: DictKeyType) -> bool: 

297 """ 

298 .. todo:: TREE::Node::__contains__ Needs documentation. 

299 

300 """ 

301 return key in self._dict 

302 

303 def __len__(self) -> int: 

304 """ 

305 Returns the number of attached attributes (key-value-pairs) on this node. 

306 

307 :returns: Number of attached attributes. 

308 """ 

309 return len(self._dict) 

310 

311 @readonly 

312 def Root(self) -> 'Node': 

313 """ 

314 Read-only property to access the tree's root node (:attr:`_root`). 

315 

316 :returns: The root node (representative node) of a tree. 

317 """ 

318 return self._root 

319 

320 @property 

321 def Parent(self) -> Nullable['Node']: 

322 """ 

323 Property to get and set the parent (:attr:`_parent`) of a node. 

324 

325 .. note:: 

326 

327 As the current node might be a tree itself, appending this node to a tree can lead to a merge of trees and 

328 especially to a merge of IDs. As IDs are unique, it might raise an :exc:`Exception`. 

329 

330 :returns: The parent of a node. 

331 :raises TypeError: If parameter ``parent`` is not a :class:`Node` 

332 :raises AlreadyInTreeError: Parent is already a child node in this tree. 

333 """ 

334 return self._parent 

335 

336 @Parent.setter 

337 def Parent(self, parent: Nullable['Node']) -> None: 

338 # TODO: is moved inside the same tree, don't move nodes in _nodesWithID and don't change _root 

339 

340 if parent is None: 

341 self._nodesWithID = {} 

342 self._nodesWithoutID = [] 

343 self._level = 0 

344 

345 if self._id is None: 

346 self._nodesWithoutID.append(self) 

347 self._root._nodesWithoutID.remove(self) 

348 else: 

349 self._nodesWithID[self._id] = self 

350 del self._nodesWithID[self._id] 

351 

352 for sibling in self.GetDescendants(): 

353 sibling._root = self 

354 sibling._level = sibling._parent._level + 1 

355 if sibling._id is None: 

356 self._nodesWithoutID.append(sibling) 

357 self._root._nodesWithoutID.remove(sibling) 

358 else: 

359 self._nodesWithID[sibling._id] = sibling 

360 del self._nodesWithID[sibling._id] 

361 

362 self._parent._children.remove(self) 

363 

364 self._root = self 

365 self._parent = None 

366 elif not isinstance(parent, Node): 

367 ex = TypeError("Parameter 'parent' is not of type 'Node'.") 

368 ex.add_note(f"Got type '{getFullyQualifiedName(parent)}'.") 

369 raise ex 

370 else: 

371 if parent._root is self._root: 

372 raise AlreadyInTreeError(f"Parent '{parent}' is already a child node in this tree.") 

373 

374 self._root = parent._root 

375 self._parent = parent 

376 self._level = parent._level + 1 

377 for node in self.GetDescendants(): 

378 node._level = node._parent._level + 1 

379 self._SetNewRoot(self._nodesWithID, self._nodesWithoutID) 

380 self._nodesWithID = self._nodesWithoutID = None 

381 parent._children.append(self) 

382 

383 @readonly 

384 def Siblings(self) -> Tuple['Node', ...]: 

385 """ 

386 A read-only property to return a tuple of all siblings from the current node. 

387 

388 If the current node is the only child, the tuple is empty. 

389 

390 Siblings are child nodes of the current node's parent node, without the current node itself. 

391 

392 :returns: A tuple of all siblings of the current node. 

393 :raises NoSiblingsError: If the current node has no parent node and thus no siblings. 

394 """ 

395 if self._parent is None: 

396 raise NoSiblingsError(f"Root node has no siblings.") 

397 

398 return tuple([node for node in self._parent if node is not self]) 

399 

400 @readonly 

401 def LeftSiblings(self) -> Tuple['Node', ...]: 

402 """ 

403 A read-only property to return a tuple of all siblings left from the current node. 

404 

405 If the current node is the only child, the tuple is empty. 

406 

407 Siblings are child nodes of the current node's parent node, without the current node itself. 

408 

409 :returns: A tuple of all siblings left of the current node. 

410 :raises NoSiblingsError: If the current node has no parent node and thus no siblings. 

411 """ 

412 if self._parent is None: 

413 raise NoSiblingsError(f"Root node has no siblings.") 

414 

415 result = [] 

416 for node in self._parent: 

417 if node is not self: 

418 result.append(node) 

419 else: 

420 break 

421 else: 

422 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover 

423 

424 return tuple(result) 

425 

426 @readonly 

427 def RightSiblings(self) -> Tuple['Node', ...]: 

428 """ 

429 A read-only property to return a tuple of all siblings right from the current node. 

430 

431 If the current node is the only child, the tuple is empty. 

432 

433 Siblings are child nodes of the current node's parent node, without the current node itself. 

434 

435 :returns: A tuple of all siblings right of the current node. 

436 :raises NoSiblingsError: If the current node has no parent node and thus no siblings. 

437 """ 

438 if self._parent is None: 

439 raise NoSiblingsError(f"Root node has no siblings.") 

440 

441 result = [] 

442 iterator = iter(self._parent) 

443 for node in iterator: 

444 if node is self: 

445 break 

446 else: 

447 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover 

448 

449 for node in iterator: 

450 result.append(node) 

451 

452 return tuple(result) 

453 

454 def _GetPathAsLinkedList(self) -> Deque["Node"]: 

455 """ 

456 Compute the path from current node to root node by using a linked list (:class:`deque`). 

457 

458 :meta private: 

459 :returns: Path from node to root node as double-ended queue (deque). 

460 """ 

461 path: Deque['Node'] = deque() 

462 

463 node = self 

464 while node is not None: 

465 path.appendleft(node) 

466 node = node._parent 

467 

468 return path 

469 

470 @readonly 

471 def Path(self) -> Tuple['Node']: 

472 """ 

473 Read-only property to return the path from root node to the node as a tuple of nodes. 

474 

475 :returns: A tuple of nodes describing the path from root node to the node. 

476 """ 

477 return tuple(self._GetPathAsLinkedList()) 

478 

479 @readonly 

480 def Level(self) -> int: 

481 """ 

482 Read-only property to return a node's level in the tree. 

483 

484 The level is the distance to the root node. 

485 

486 :returns: The node's level. 

487 """ 

488 return self._level 

489 

490 @readonly 

491 def Size(self) -> int: 

492 """ 

493 Read-only property to return the size of the tree. 

494 

495 :returns: Count of all nodes in the tree structure. 

496 """ 

497 return len(self._root._nodesWithID) + len(self._root._nodesWithoutID) 

498 

499 @readonly 

500 def IsRoot(self) -> bool: 

501 """ 

502 Returns true, if the node is the root node (representative node of the tree). 

503 

504 :returns: ``True``, if node is the root node. 

505 """ 

506 return self._parent is None 

507 

508 @readonly 

509 def IsLeaf(self) -> bool: 

510 """ 

511 Returns true, if the node is a leaf node (has no children). 

512 

513 :returns: ``True``, if node has no children. 

514 """ 

515 return len(self._children) == 0 

516 

517 @readonly 

518 def HasChildren(self) -> bool: 

519 """ 

520 Returns true, if the node has child nodes. 

521 

522 :returns: ``True``, if node has children. 

523 """ 

524 return len(self._children) > 0 

525 

526 def _SetNewRoot(self, nodesWithIDs: Dict['Node', 'Node'], nodesWithoutIDs: List['Node']) -> None: 

527 for nodeID, node in nodesWithIDs.items(): 

528 if nodeID in self._root._nodesWithID: 

529 raise ValueError(f"ID '{nodeID}' already exists in this tree.") 

530 else: 

531 self._root._nodesWithID[nodeID] = node 

532 node._root = self._root 

533 

534 for node in nodesWithoutIDs: 

535 self._root._nodesWithoutID.append(node) 

536 node._root = self._root 

537 

538 def AddChild(self, child: 'Node'): 

539 """ 

540 Add a child node to the current node of the tree. 

541 

542 If ``child`` is a subtree, both trees get merged. So all nodes in ``child`` get a new :attr:`_root` assigned and 

543 all IDs are merged into the node's root's ID lists (:attr:`_nodesWithID`). 

544 

545 :param child: The child node to be added to the tree. 

546 :raises TypeError: If parameter ``child`` is not a :class:`Node`. 

547 :raises AlreadyInTreeError: If parameter ``child`` is already a node in the tree. 

548 

549 .. seealso:: 

550 

551 :attr:`Parent` |br| 

552 |rarr| Set the parent of a node. 

553 :meth:`AddChildren` |br| 

554 |rarr| Add multiple children at once. 

555 """ 

556 if not isinstance(child, Node): 

557 ex = TypeError(f"Parameter 'child' is not of type 'Node'.") 

558 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.") 

559 raise ex 

560 

561 if child._root is self._root: 

562 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.") 

563 

564 child._root = self._root 

565 child._parent = self 

566 child._level = self._level + 1 

567 for node in child.GetDescendants(): 

568 node._level = node._parent._level + 1 

569 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID) 

570 child._nodesWithID = child._nodesWithoutID = None 

571 self._children.append(child) 

572 

573 def AddChildren(self, children: Iterable['Node']): 

574 """ 

575 Add multiple children nodes to the current node of the tree. 

576 

577 :param children: The list of children nodes to be added to the tree. 

578 :raises TypeError: If parameter ``children`` contains an item, which is not a :class:`Node`. 

579 :raises AlreadyInTreeError: If parameter ``children`` contains an item, which is already a node in the tree. 

580 

581 .. seealso:: 

582 

583 :attr:`Parent` |br| 

584 |rarr| Set the parent of a node. 

585 :meth:`AddChild` |br| 

586 |rarr| Add a child node to the tree. 

587 """ 

588 for child in children: 

589 if not isinstance(child, Node): 

590 ex = TypeError(f"Item '{child}' in parameter 'children' is not of type 'Node'.") 

591 ex.add_note(f"Got type '{getFullyQualifiedName(child)}'.") 

592 raise ex 

593 

594 if child._root is self._root: 

595 # TODO: create a more specific exception 

596 raise AlreadyInTreeError(f"Child '{child}' is already a node in this tree.") 

597 

598 child._root = self._root 

599 child._parent = self 

600 child._level = self._level + 1 

601 for node in child.GetDescendants(): 

602 node._level = node._parent._level + 1 

603 self._SetNewRoot(child._nodesWithID, child._nodesWithoutID) 

604 child._nodesWithID = child._nodesWithoutID = None 

605 self._children.append(child) 

606 

607 def GetPath(self) -> Generator['Node', None, None]: 

608 """ 

609 .. todo:: TREE::Node::GetPAth Needs documentation. 

610 

611 """ 

612 for node in self._GetPathAsLinkedList(): 

613 yield node 

614 

615 def GetAncestors(self) -> Generator['Node', None, None]: 

616 """ 

617 .. todo:: TREE::Node::GetAncestors Needs documentation. 

618 

619 """ 

620 node = self._parent 

621 while node is not None: 

622 yield node 

623 node = node._parent 

624 

625 def GetCommonAncestors(self, others: Union['Node', Iterable['Node']]) -> Generator['Node', None, None]: 

626 """ 

627 .. todo:: TREE::Node::GetCommonAncestors Needs documentation. 

628 

629 """ 

630 if isinstance(others, Node): 

631 # Check for trivial case 

632 if others is self: 

633 for node in self._GetPathAsLinkedList(): 

634 yield node 

635 return 

636 

637 # Check if both are in the same tree. 

638 if self._root is not others._root: 

639 raise NotInSameTreeError(f"Node 'others' is not in the same tree.") 

640 

641 # Compute paths top-down and walk both paths until they deviate 

642 for left, right in zip(self.Path, others.Path): 

643 if left is right: 

644 yield left 

645 else: 

646 return 

647 elif isinstance(others, Iterable): 

648 raise NotImplementedError(f"Generator 'GetCommonAncestors' does not yet support an iterable of siblings to compute the common ancestors.") 

649 

650 def GetChildren(self) -> Generator['Node', None, None]: 

651 """ 

652 A generator to iterate all direct children of the current node. 

653 

654 :returns: A generator to iterate all children. 

655 

656 .. seealso:: 

657 

658 :meth:`GetDescendants` |br| 

659 |rarr| Iterate all descendants. 

660 :meth:`IterateLevelOrder` |br| 

661 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node. 

662 :meth:`IteratePreOrder` |br| 

663 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node. 

664 :meth:`IteratePostOrder` |br| 

665 |rarr| Iterate items in post-order, which includes the node itself as a last returned node. 

666 """ 

667 for child in self._children: 

668 yield child 

669 

670 def GetSiblings(self) -> Generator['Node', None, None]: 

671 """ 

672 A generator to iterate all siblings. 

673 

674 Siblings are child nodes of the current node's parent node, without the current node itself. 

675 

676 :returns: A generator to iterate all siblings of the current node. 

677 :raises NoSiblingsError: If the current node has no parent node and thus no siblings. 

678 """ 

679 if self._parent is None: 

680 raise NoSiblingsError(f"Root node has no siblings.") 

681 

682 for node in self._parent: 

683 if node is self: 

684 continue 

685 

686 yield node 

687 

688 def GetLeftSiblings(self) -> Generator['Node', None, None]: 

689 """ 

690 A generator to iterate all siblings left from the current node. 

691 

692 Siblings are child nodes of the current node's parent node, without the current node itself. 

693 

694 :returns: A generator to iterate all siblings left of the current node. 

695 :raises NoSiblingsError: If the current node has no parent node and thus no siblings. 

696 """ 

697 if self._parent is None: 

698 raise NoSiblingsError(f"Root node has no siblings.") 

699 

700 for node in self._parent: 

701 if node is self: 

702 break 

703 

704 yield node 

705 else: 

706 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover 

707 

708 def GetRightSiblings(self) -> Generator['Node', None, None]: 

709 """ 

710 A generator to iterate all siblings right from the current node. 

711 

712 Siblings are child nodes of the current node's parent node, without the current node itself. 

713 

714 :returns: A generator to iterate all siblings right of the current node. 

715 :raises NoSiblingsError: If the current node has no parent node and thus no siblings. 

716 """ 

717 if self._parent is None: 

718 raise NoSiblingsError(f"Root node has no siblings.") 

719 

720 iterator = iter(self._parent) 

721 for node in iterator: 

722 if node is self: 

723 break 

724 else: 

725 raise InternalError(f"Data structure corruption: Self is not part of parent's children.") # pragma: no cover 

726 

727 for node in iterator: 

728 yield node 

729 

730 def GetDescendants(self) -> Generator['Node', None, None]: 

731 """ 

732 A generator to iterate all descendants of the current node. In contrast to `IteratePreOrder` and `IteratePostOrder` 

733 it doesn't include the node itself. 

734 

735 :returns: A generator to iterate all descendants. 

736 

737 .. seealso:: 

738 

739 :meth:`GetChildren` |br| 

740 |rarr| Iterate all children, but no grand-children. 

741 :meth:`IterateLevelOrder` |br| 

742 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node. 

743 :meth:`IteratePreOrder` |br| 

744 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node. 

745 :meth:`IteratePostOrder` |br| 

746 |rarr| Iterate items in post-order, which includes the node itself as a last returned node. 

747 """ 

748 for child in self._children: 

749 yield child 

750 yield from child.GetDescendants() 

751 

752 def GetRelatives(self): 

753 """ 

754 A generator to iterate all relatives (all siblings and all their descendants) of the current node. 

755 

756 :returns: A generator to iterate all relatives. 

757 """ 

758 for node in self.GetSiblings(): 

759 yield node 

760 yield from node.GetDescendants() 

761 

762 def GetLeftRelatives(self): 

763 """ 

764 A generator to iterate all left relatives (left siblings and all their descendants) of the current node. 

765 

766 :returns: A generator to iterate all left relatives. 

767 """ 

768 for node in self.GetLeftSiblings(): 

769 yield node 

770 yield from node.GetDescendants() 

771 

772 def GetRightRelatives(self): 

773 """ 

774 A generator to iterate all right relatives (right siblings and all their descendants) of the current node. 

775 

776 :returns: A generator to iterate all right relatives. 

777 """ 

778 for node in self.GetRightSiblings(): 

779 yield node 

780 yield from node.GetDescendants() 

781 

782 def IterateLeafs(self) -> Generator['Node', None, None]: 

783 """ 

784 A generator to iterate all leaf-nodes in a subtree, which subtree root is the current node. 

785 

786 :returns: A generator to iterate leaf-nodes reachable from current node. 

787 """ 

788 for child in self._children: 

789 if child.IsLeaf: 

790 yield child 

791 else: 

792 yield from child.IterateLeafs() 

793 

794 def IterateLevelOrder(self) -> Generator['Node', None, None]: 

795 """ 

796 A generator to iterate all siblings of the current node level-by-level top-down. In contrast to `GetDescendants`, 

797 this includes also the node itself as the first returned node. 

798 

799 :returns: A generator to iterate all siblings level-by-level. 

800 

801 .. seealso:: 

802 

803 :meth:`GetChildren` |br| 

804 |rarr| Iterate all children, but no grand-children. 

805 :meth:`GetDescendants` |br| 

806 |rarr| Iterate all descendants. 

807 :meth:`IteratePreOrder` |br| 

808 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node. 

809 :meth:`IteratePostOrder` |br| 

810 |rarr| Iterate items in post-order, which includes the node itself as a last returned node. 

811 """ 

812 queue = deque([self]) 

813 while queue: 

814 currentNode = queue.pop() 

815 yield currentNode 

816 for node in currentNode._children: 

817 queue.appendleft(node) 

818 

819 def IteratePreOrder(self) -> Generator['Node', None, None]: 

820 """ 

821 A generator to iterate all siblings of the current node in pre-order. In contrast to `GetDescendants`, this includes 

822 also the node itself as the first returned node. 

823 

824 :returns: A generator to iterate all siblings in pre-order. 

825 

826 .. seealso:: 

827 

828 :meth:`GetChildren` |br| 

829 |rarr| Iterate all children, but no grand-children. 

830 :meth:`GetDescendants` |br| 

831 |rarr| Iterate all descendants. 

832 :meth:`IterateLevelOrder` |br| 

833 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node. 

834 :meth:`IteratePostOrder` |br| 

835 |rarr| Iterate items in post-order, which includes the node itself as a last returned node. 

836 """ 

837 yield self 

838 for child in self._children: 

839 yield from child.IteratePreOrder() 

840 

841 def IteratePostOrder(self) -> Generator['Node', None, None]: 

842 """ 

843 A generator to iterate all siblings of the current node in post-order. In contrast to `GetDescendants`, this 

844 includes also the node itself as the last returned node. 

845 

846 :returns: A generator to iterate all siblings in post-order. 

847 

848 .. seealso:: 

849 

850 :meth:`GetChildren` |br| 

851 |rarr| Iterate all children, but no grand-children. 

852 :meth:`GetDescendants` |br| 

853 |rarr| Iterate all descendants. 

854 :meth:`IterateLevelOrder` |br| 

855 |rarr| Iterate items level-by-level, which includes the node itself as a first returned node. 

856 :meth:`IteratePreOrder` |br| 

857 |rarr| Iterate items in pre-order, which includes the node itself as a first returned node. 

858 """ 

859 for child in self._children: 

860 yield from child.IteratePostOrder() 

861 yield self 

862 

863 def WalkTo(self, other: 'Node') -> Generator['Node', None, None]: 

864 """ 

865 Returns a generator to iterate the path from node to another node. 

866 

867 :param other: Node to walk to. 

868 :returns: Generator to iterate the path from node to other node. 

869 :raises NotInSameTreeError: If parameter ``other`` is not part of the same tree. 

870 """ 

871 # Check for trivial case 

872 if other is self: 

873 yield from () 

874 

875 # Check if both are in the same tree. 

876 if self._root is not other._root: 

877 raise NotInSameTreeError(f"Node 'other' is not in the same tree.") 

878 

879 # Compute both paths to the root. 

880 # 1. Walk from self to root, until a first common ancestor is found. 

881 # 2. Walk from there to other (reverse paths) 

882 otherPath = other.Path # TODO: Path generates a list and a tuple. Provide a generator for such a walk. 

883 index = len(otherPath) 

884 for node in self.GetAncestors(): 

885 try: 

886 index = otherPath.index(node) 

887 break 

888 except ValueError: 

889 yield node 

890 

891 for i in range(index, len(otherPath)): 

892 yield otherPath[i] 

893 

894 def GetNodeByID(self, nodeID: IDType) -> 'Node': 

895 """ 

896 Lookup a node by its unique ID. 

897 

898 :param nodeID: ID of a node to lookup in the tree. 

899 :returns: Node for the given ID. 

900 :raises ValueError: If parameter ``nodeID`` is None. 

901 :raises KeyError: If parameter ``nodeID`` is not found in the tree. 

902 """ 

903 if nodeID is None: 

904 raise ValueError(f"'None' is not supported as an ID value.") 

905 

906 return self._root._nodesWithID[nodeID] 

907 

908 def Find(self, predicate: Callable) -> Generator['Node', None, None]: 

909 raise NotImplementedError(f"Method 'Find' is not yet implemented.") 

910 

911 def __iter__(self) -> Iterator['Node']: 

912 """ 

913 Returns an iterator to iterate all child nodes. 

914 

915 :returns: Children iterator. 

916 """ 

917 return iter(self._children) 

918 

919 def __len__(self) -> int: 

920 """ 

921 Returns the number of children, but not including grand-children. 

922 

923 :returns: Number of child nodes. 

924 """ 

925 return len(self._children) 

926 

927 def __repr__(self) -> str: 

928 """ 

929 Returns a detailed string representation of the node. 

930 

931 :returns: The detailed string representation of the node. 

932 """ 

933 nodeID = parent = value = "" 

934 if self._id is not None: 

935 nodeID = f"; nodeID='{self._id}'" 

936 if (self._parent is not None) and (self._parent._id is not None): 

937 parent = f"; parent='{self._parent._id}'" 

938 if self._value is not None: 

939 value = f"; value='{self._value}'" 

940 

941 return f"<node{nodeID}{parent}{value}>" 

942 

943 def __str__(self) -> str: 

944 """ 

945 Return a string representation of the node. 

946 

947 Order of resolution: 

948 

949 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`. 

950 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`. 

951 3. Else, return :meth:`__repr__`. 

952 

953 :returns: The resolved string representation of the node. 

954 """ 

955 if self._value is not None: 

956 return str(self._value) 

957 elif self._id is not None: 

958 return str(self._id) 

959 else: 

960 return self.__repr__() 

961 

962 def Render( 

963 self, 

964 prefix: str = "", 

965 lineend: str = "\n", 

966 nodeMarker: str = "├─", 

967 lastNodeMarker: str = "└─", 

968 bypassMarker: str = "│ " 

969 ) -> str: 

970 """ 

971 Render the tree as ASCII art. 

972 

973 :param prefix: A string printed in front of every line, e.g. for indentation. Default: ``""``. 

974 :param lineend: A string printed at the end of every line. Default: ``"\\n"``. 

975 :param nodeMarker: A string printed before every non-last tree node. Default: ``"├─"``. 

976 :param lastNodeMarker: A string printed before every last tree node. Default: ``"└─"``. 

977 :param bypassMarker: A string printed when there are further nodes in the parent level. Default: ``"│ "``. 

978 :return: A rendered tree as multiline string. 

979 """ 

980 emptyMarker = " " * len(bypassMarker) 

981 

982 def _render(node: Node, markers: str): 

983 result = [] 

984 

985 if node.HasChildren: 

986 for child in node._children[:-1]: 

987 nodeRepresentation = child._format(child) if child._format else str(child) 

988 result.append(f"{prefix}{markers}{nodeMarker}{nodeRepresentation}{lineend}") 

989 result.extend(_render(child, markers + bypassMarker)) 

990 

991 # last child node 

992 child = node._children[-1] 

993 nodeRepresentation = child._format(child) if child._format else str(child) 

994 result.append(f"{prefix}{markers}{lastNodeMarker}{nodeRepresentation}{lineend}") 

995 result.extend(_render(child, markers + emptyMarker)) 

996 

997 return result 

998 

999 # Root element 

1000 nodeRepresentation = self._format(self) if self._format else str(self) 

1001 result = [f"{prefix}{nodeRepresentation}{lineend}"] 

1002 result.extend(_render(self, "")) 

1003 

1004 return "".join(result)