Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/treelib/node.py: 49%
Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1#!/usr/bin/env python
2# Copyright (C) 2011
3# Brett Alistair Kromkamp - brettkromkamp@gmail.com
4# Copyright (C) 2012-2025
5# Xiaming Chen - chenxm35@gmail.com
6# and other contributors.
7# All rights reserved.
8"""
9Node structure in treelib.
11A :class:`Node` object contains basic properties such as node identifier,
12node tag, parent node, children nodes etc., and some operations for a node.
14The Node class is the fundamental building block of a Tree. Each node can store:
15- A unique identifier for tree operations
16- A human-readable tag for display
17- Custom data payload
18- Parent-child relationships within one or more trees
20Note:
21 Nodes are typically created through Tree.create_node() rather than
22 directly instantiated, as the Tree class manages the parent-child
23 relationships automatically.
24"""
25from __future__ import unicode_literals
27import copy
28import sys
29import uuid
30from collections import defaultdict
31from typing import Any, List, Optional, Union, cast
32from warnings import warn
34from .exceptions import NodePropertyError
35from .misc import deprecated
37if sys.version_info >= (3, 9):
38 StrList = list[str]
39else:
40 StrList = List[str] # Python 3.8 and earlier
43class Node(object):
44 """
45 Elementary node object stored in Tree structures.
47 A Node represents a single element in a tree hierarchy. Each node maintains
48 references to its parent and children within specific tree contexts, along
49 with a human-readable tag and optional data payload.
51 Attributes:
52 identifier (str): Unique identifier for this node within a tree.
53 tag (str): Human-readable label for display purposes.
54 expanded (bool): Controls visibility of children in tree displays.
55 data (Any): User-defined payload associated with this node.
57 Example:
58 Creating nodes with different configurations::
60 # Basic node
61 node = Node("Root", "root")
63 # Node with custom data
64 node = Node("File", "file1", data={"size": 1024, "type": "txt"})
66 # Node that starts collapsed
67 node = Node("Folder", "folder1", expanded=False)
69 Warning:
70 While nodes can be created directly, it's recommended to use
71 Tree.create_node() which properly manages tree relationships.
72 """
74 #: Mode constants for routine `update_fpointer()`.
75 (ADD, DELETE, INSERT, REPLACE) = list(range(4))
77 def __init__(
78 self,
79 tag: Optional[str] = None,
80 identifier: Optional[str] = None,
81 expanded: bool = True,
82 data: Any = None,
83 ) -> None:
84 """
85 Create a new Node object to be placed inside a Tree object.
87 Args:
88 tag: Human-readable label for the node. If None, uses identifier.
89 identifier: Unique ID for the node. If None, generates a UUID.
90 expanded: Whether node children are visible in tree displays.
91 data: Optional user data to associate with this node.
93 Example:
94 Creating different types of nodes::
96 # Auto-generated identifier
97 node1 = Node("My Node")
99 # Explicit identifier
100 node2 = Node("Root", "root")
102 # With custom data
103 node3 = Node("User", "user1", data={"name": "Alice", "role": "admin"})
105 # Initially collapsed
106 node4 = Node("Large Folder", "folder", expanded=False)
107 """
109 #: if given as a parameter, must be unique
110 self._identifier: Optional[str] = None
111 self._set_identifier(identifier)
113 #: None or something else
114 #: if None, self._identifier will be set to the identifier's value.
115 if tag is None:
116 self._tag = self._identifier
117 else:
118 self._tag = tag
120 #: boolean
121 self.expanded = expanded
123 #: identifier of the parent's node :
124 self._predecessor: dict = {}
125 #: identifier(s) of the soons' node(s) :
126 self._successors: dict = defaultdict(list)
128 #: User payload associated with this node.
129 self.data = data
131 # for retro-compatibility on bpointer/fpointer
132 self._initial_tree_id: Optional[str] = None
134 def __lt__(self, other) -> bool:
135 """
136 Compare nodes for sorting based on their tags.
138 Enables sorting of Node objects in collections by comparing their tag attributes.
139 This allows natural ordering when displaying or processing collections of nodes.
141 Args:
142 other: Another Node object to compare with.
144 Returns:
145 bool: True if this node's tag is lexicographically less than other's tag.
147 Example:
148 Sorting nodes by tag::
150 nodes = [Node("Charlie", "c"), Node("Alice", "a"), Node("Bob", "b")]
151 sorted_nodes = sorted(nodes) # Alice, Bob, Charlie
152 """
153 return self.tag < other.tag
155 def set_initial_tree_id(self, tree_id: str) -> None:
156 """
157 Set the initial tree identifier for backward compatibility.
159 This method is used internally to maintain compatibility with older
160 node pointer systems. Each node remembers the first tree it was added to
161 for legacy bpointer/fpointer access.
163 Args:
164 tree_id: Unique identifier of the tree this node was first added to.
166 Note:
167 This is an internal method used for legacy compatibility.
168 Modern code should use the tree-specific pointer methods instead.
169 """
170 if self._initial_tree_id is None:
171 self._initial_tree_id = tree_id
173 def _set_identifier(self, nid: Optional[str]) -> None:
174 """
175 Initialize node identifier with given value or auto-generate one.
177 Private method used during node creation to set the unique identifier.
178 If no identifier is provided, generates a UUID automatically to ensure
179 uniqueness within the tree.
181 Args:
182 nid: Desired node identifier, or None to auto-generate.
184 Note:
185 This is an internal method. Use the identifier property for
186 accessing or modifying the identifier after node creation.
187 """
188 if nid is None:
189 self._identifier = str(uuid.uuid1())
190 else:
191 self._identifier = nid
193 @property
194 @deprecated(alias="node.predecessor")
195 def bpointer(self):
196 if self._initial_tree_id not in self._predecessor.keys():
197 return None
198 return self._predecessor[self._initial_tree_id]
200 @bpointer.setter
201 @deprecated(alias="node.set_predecessor")
202 def bpointer(self, value) -> None:
203 self.set_predecessor(value, self._initial_tree_id)
205 @deprecated(alias="node.set_predecessor")
206 def update_bpointer(self, nid) -> None:
207 self.set_predecessor(nid, self._initial_tree_id)
209 @property
210 @deprecated(alias="node.successors")
211 def fpointer(self):
212 if self._initial_tree_id not in self._successors:
213 return []
214 return self._successors[self._initial_tree_id]
216 @fpointer.setter
217 @deprecated(alias="node.update_successors")
218 def fpointer(self, value: Union[None, list, dict, set]) -> None:
219 self.set_successors(value, tree_id=self._initial_tree_id)
221 @deprecated(alias="node.update_successors")
222 def update_fpointer(self, nid, mode=ADD, replace=None):
223 self.update_successors(nid, mode, replace, self._initial_tree_id)
225 def predecessor(self, tree_id):
226 """
227 Get the parent node identifier in the specified tree.
229 Since nodes can exist in multiple trees simultaneously, this method
230 returns the parent identifier for this node within a specific tree context.
232 Args:
233 tree_id: Identifier of the tree to query parent relationship in.
235 Returns:
236 str or None: Parent node identifier, or None if this is a root node.
238 Example:
239 Accessing parent in different trees::
241 # Node can have different parents in different trees
242 parent_id = node.predecessor("tree1")
243 if parent_id:
244 print(f"Parent in tree1: {parent_id}")
245 """
246 return self._predecessor[tree_id]
248 def set_predecessor(self, nid: Optional[str], tree_id: Optional[str]) -> None:
249 """
250 Set the parent node identifier for this node in a specific tree.
252 Establishes or updates the parent-child relationship for this node
253 within the context of a particular tree. Used internally by tree
254 operations to maintain proper hierarchy.
256 Args:
257 nid: Parent node identifier, or None to make this a root node.
258 tree_id: Identifier of the tree to set parent relationship in.
260 Example:
261 Setting parent relationship::
263 node.set_predecessor("parent_id", "tree1")
264 node.set_predecessor(None, "tree1") # Make root
265 """
266 self._predecessor[tree_id] = nid
268 def successors(self, tree_id: Optional[str]) -> StrList:
269 """
270 Get the list of child node identifiers in the specified tree.
272 Returns all direct children of this node within a specific tree context.
273 Children are maintained as an ordered list to preserve insertion order
274 and support custom sorting.
276 Args:
277 tree_id: Identifier of the tree to query children in.
279 Returns:
280 list[str]: List of child node identifiers. Empty list if no children.
282 Example:
283 Accessing children in different trees::
285 children = node.successors("tree1")
286 for child_id in children:
287 print(f"Child: {child_id}")
289 # Node can have different children in different trees
290 tree1_children = node.successors("tree1")
291 tree2_children = node.successors("tree2")
292 """
293 return self._successors[tree_id]
295 def set_successors(self, value: Union[None, list, dict, set], tree_id: Optional[str] = None) -> None:
296 """
297 Set the complete list of child node identifiers for a specific tree.
299 Replaces the entire children list with new values. Accepts multiple
300 input formats for flexibility: list, set, dict (uses keys), or None.
302 Args:
303 value: New children collection. Can be:
304 - list: Used directly as child identifiers
305 - set: Converted to list of identifiers
306 - dict: Uses dictionary keys as identifiers
307 - None: Sets empty children list
308 tree_id: Identifier of the tree to set children in.
310 Raises:
311 NotImplementedError: If value type is not supported.
313 Example:
314 Setting children from different sources::
316 # From list
317 node.set_successors(["child1", "child2"], "tree1")
319 # From set
320 node.set_successors({"child1", "child2"}, "tree1")
322 # From dict (uses keys)
323 node.set_successors({"child1": data1, "child2": data2}, "tree1")
325 # Clear children
326 node.set_successors(None, "tree1")
327 """
328 setter_lookup = {
329 "NoneType": lambda x: list(),
330 "list": lambda x: x,
331 "dict": lambda x: list(x.keys()),
332 "set": lambda x: list(x),
333 }
335 t = value.__class__.__name__
336 if t in setter_lookup:
337 f_setter = setter_lookup[t]
338 self._successors[tree_id] = f_setter(value)
339 else:
340 raise NotImplementedError("Unsupported value type %s" % t)
342 def update_successors(
343 self,
344 nid: Optional[str],
345 mode: int = ADD,
346 replace: Optional[str] = None,
347 tree_id: Optional[str] = None,
348 ) -> None:
349 """
350 Update the children list with different modification modes.
352 Provides granular control over child node list modifications without
353 replacing the entire list. Supports adding, removing, and replacing
354 individual child references.
356 Args:
357 nid: Child node identifier to operate on.
358 mode: Operation type using Node constants:
359 - Node.ADD: Append child to end of list
360 - Node.DELETE: Remove child from list
361 - Node.INSERT: Deprecated, same as ADD
362 - Node.REPLACE: Replace child with another identifier
363 replace: New identifier when mode=REPLACE. Required for replace mode.
364 tree_id: Identifier of the tree to modify children in.
366 Raises:
367 NodePropertyError: If replace is None when mode=REPLACE.
368 NotImplementedError: If mode is not supported.
370 Example:
371 Different update operations::
373 # Add a child
374 node.update_successors("new_child", Node.ADD, tree_id="tree1")
376 # Remove a child
377 node.update_successors("old_child", Node.DELETE, tree_id="tree1")
379 # Replace a child
380 node.update_successors("old_child", Node.REPLACE,
381 replace="new_child", tree_id="tree1")
382 """
383 if nid is None:
384 return
386 def _manipulator_append() -> None:
387 self.successors(tree_id).append(nid)
389 def _manipulator_delete() -> None:
390 if nid in self.successors(tree_id):
391 self.successors(tree_id).remove(nid)
392 else:
393 warn("Nid %s wasn't present in fpointer" % nid)
395 def _manipulator_insert() -> None:
396 warn("WARNING: INSERT is deprecated to ADD mode")
397 self.update_successors(nid, tree_id=tree_id)
399 def _manipulator_replace() -> None:
400 if replace is None:
401 raise NodePropertyError('Argument "replace" should be provided when mode is {}'.format(mode))
402 ind = self.successors(tree_id).index(nid)
403 self.successors(tree_id)[ind] = replace
405 manipulator_lookup = {
406 self.ADD: "_manipulator_append",
407 self.DELETE: "_manipulator_delete",
408 self.INSERT: "_manipulator_insert",
409 self.REPLACE: "_manipulator_replace",
410 }
412 if mode not in manipulator_lookup:
413 raise NotImplementedError("Unsupported node updating mode %s" % str(mode))
415 f_name = cast(str, manipulator_lookup.get(mode))
416 f = locals()[f_name]
417 return f()
419 @property
420 def identifier(self) -> str:
421 """
422 Get the unique identifier of this node.
424 The identifier serves as the primary key for this node within tree structures.
425 It must be unique within each tree that contains this node. Used for all
426 tree operations including lookup, traversal, and relationship management.
428 Returns:
429 str: The unique node identifier.
431 Example:
432 Accessing node identifier::
434 node = Node("My Node", "unique_id")
435 print(node.identifier) # "unique_id"
437 # Use in tree operations
438 tree[node.identifier] # Access via identifier
439 """
440 return cast(str, self._identifier)
442 def clone_pointers(self, former_tree_id: str, new_tree_id: str) -> None:
443 """
444 Clone parent-child relationships from one tree context to another.
446 Copies the complete relationship structure (parent and children) from
447 one tree context to a new tree context. Used when moving or copying
448 nodes between trees while preserving their hierarchical relationships.
450 Args:
451 former_tree_id: Source tree identifier to copy relationships from.
452 new_tree_id: Target tree identifier to copy relationships to.
454 Example:
455 Cloning relationships between trees::
457 # Copy node relationships from tree1 to tree2
458 node.clone_pointers("tree1", "tree2")
460 # Now node has same relationships in both trees
461 assert node.predecessor("tree1") == node.predecessor("tree2")
462 """
463 former_bpointer = self.predecessor(former_tree_id)
464 self.set_predecessor(former_bpointer, new_tree_id)
465 former_fpointer = self.successors(former_tree_id)
466 # fpointer is a list and would be copied by reference without deepcopy
467 self.set_successors(copy.deepcopy(former_fpointer), tree_id=new_tree_id)
469 def reset_pointers(self, tree_id) -> None:
470 """
471 Reset all parent-child relationships for a specific tree context.
473 Clears both parent and children references for this node within the
474 specified tree, effectively making it an isolated node. Used during
475 tree restructuring operations.
477 Args:
478 tree_id: Identifier of the tree to reset relationships in.
480 Example:
481 Resetting node relationships::
483 # Clear all relationships in tree1
484 node.reset_pointers("tree1")
486 # Node now has no parent or children in tree1
487 assert node.predecessor("tree1") is None
488 assert len(node.successors("tree1")) == 0
489 """
490 self.set_predecessor(None, tree_id)
491 self.set_successors([], tree_id=tree_id)
493 @identifier.setter # type: ignore
494 def identifier(self, value: str) -> None:
495 """
496 Set the unique identifier of this node.
498 Updates the node's identifier while maintaining data integrity.
499 The new identifier must be unique within any trees containing this node.
501 Args:
502 value: New unique identifier for this node. Cannot be None.
504 Warning:
505 Changing a node's identifier while it exists in trees can break
506 tree integrity. Use Tree.update_node() for safe identifier changes.
508 Example:
509 Updating node identifier::
511 node.identifier = "new_unique_id"
513 # Better approach when node is in a tree:
514 tree.update_node("old_id", identifier="new_id")
515 """
516 if value is None:
517 print("WARNING: node ID can not be None")
518 else:
519 self._set_identifier(value)
521 def is_leaf(self, tree_id: Optional[str] = None) -> bool:
522 """
523 Check if this node is a leaf (has no children) in the specified tree.
525 A leaf node is one that has no child nodes. This is a fundamental
526 property used in tree algorithms and can vary between different
527 tree contexts if the node exists in multiple trees.
529 Args:
530 tree_id: Identifier of the tree to check leaf status in.
531 If None, uses the initial tree for backward compatibility.
533 Returns:
534 bool: True if node has no children in the specified tree, False otherwise.
536 Example:
537 Checking leaf status::
539 if node.is_leaf("tree1"):
540 print("This is a leaf node")
542 # Different trees may have different leaf status
543 is_leaf_tree1 = node.is_leaf("tree1")
544 is_leaf_tree2 = node.is_leaf("tree2") # May differ
545 """
546 if tree_id is None:
547 # for retro-compatilibity
548 if self._initial_tree_id not in self._successors.keys():
549 return True
550 else:
551 tree_id = self._initial_tree_id
553 if len(self.successors(tree_id)) == 0:
554 return True
555 else:
556 return False
558 def is_root(self, tree_id: Optional[str] = None) -> bool:
559 """
560 Check if this node is a root (has no parent) in the specified tree.
562 A root node is the topmost node in a tree hierarchy with no parent.
563 Every tree has exactly one root node. This status can vary between
564 different tree contexts if the node exists in multiple trees.
566 Args:
567 tree_id: Identifier of the tree to check root status in.
568 If None, uses the initial tree for backward compatibility.
570 Returns:
571 bool: True if node has no parent in the specified tree, False otherwise.
573 Example:
574 Checking root status::
576 if node.is_root("tree1"):
577 print("This is the root node")
579 # Same node might be root in one tree but not another
580 is_root_tree1 = node.is_root("tree1")
581 is_root_tree2 = node.is_root("tree2") # May differ
582 """
583 if tree_id is None:
584 # for retro-compatilibity
585 if self._initial_tree_id not in self._predecessor.keys():
586 return True
587 else:
588 tree_id = self._initial_tree_id
590 return self.predecessor(tree_id) is None
592 @property
593 def tag(self) -> str:
594 """
595 Get the human-readable display name of this node.
597 The tag serves as the display label for this node in tree visualizations,
598 printouts, and user interfaces. Unlike the identifier, the tag doesn't
599 need to be unique and is primarily for human readability.
601 Returns:
602 str: The display name/label for this node.
604 Example:
605 Using node tags for display::
607 node = Node("User Profile", "user123")
608 print(node.tag) # "User Profile"
609 print(node.identifier) # "user123"
611 # Tags are used in tree display
612 tree.show() # Shows "User Profile" not "user123"
613 """
614 return cast(str, self._tag)
616 @tag.setter
617 def tag(self, value: Optional[str]) -> None:
618 """
619 Set the human-readable display name of this node.
621 Updates the display label used in tree visualizations and string
622 representations. The tag can be changed freely without affecting
623 tree structure or node relationships.
625 Args:
626 value: New display name for the node. Can be None.
628 Example:
629 Updating node display name::
631 node.tag = "Updated Profile"
632 print(node.tag) # "Updated Profile"
634 # Useful for dynamic labeling
635 node.tag = f"User: {user.name} (Active)"
636 """
637 self._tag = value if value is not None else None
639 def __repr__(self) -> str:
640 """
641 Return detailed string representation of this node for debugging.
643 Provides a comprehensive view of the node's properties including
644 tag, identifier, and data. Useful for debugging, logging, and
645 development work.
647 Returns:
648 str: Detailed string representation in format:
649 Node(tag=<tag>, identifier=<id>, data=<data>)
651 Example:
652 Node representation output::
654 node = Node("Profile", "user123", data={"age": 30})
655 print(repr(node))
656 # Output: Node(tag=Profile, identifier=user123, data={'age': 30})
658 # Useful in lists and debugging
659 print([node1, node2]) # Shows detailed info for each node
660 """
661 name = self.__class__.__name__
662 kwargs = [
663 "tag={0}".format(self.tag),
664 "identifier={0}".format(self.identifier),
665 "data={0}".format(self.data),
666 ]
667 return "%s(%s)" % (name, ", ".join(kwargs))