Skip to content

data_structure

Tree and bi-directional list structures used across URes.

Examples:

>>> from ures.data_structure import TreeNode
>>> root = TreeNode("root")
>>> root.value
'root'

TreeNode 

TreeNode(value: Any)

Bases: Generic[_TreeNodeT]

A tree node with parent/child links and path traversal helpers.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> root.add_child(child)
>>> child.parent is root
True

Initialize a TreeNode instance.

Parameters:

  • value (Any) –

    The value to be stored in the node.

Examples:

>>> node = TreeNode("root")
>>> node.value
'root'
Source code in ures/data_structure/tree.py 
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def __init__(self, value: Any):
    """
    Initialize a TreeNode instance.

    Args:
        value (Any): The value to be stored in the node.

    Examples:
        >>> node = TreeNode("root")
        >>> node.value
        'root'
    """
    self._parent: _TreeNodeT | None = None
    self._children: dict[str, _TreeNodeT] = {}
    self._value: Any = value
    self._id = uuid.uuid4().hex

parent property 

parent: _TreeNodeT | None

Get the parent node of this TreeNode.

Returns:

  • _TreeNodeT | None –

    Optional[_TreeNodeT]: The parent node if it exists; otherwise, None.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> child.set_parent(root)
>>> child.parent is root
True

children property 

children: dict[str, _TreeNodeT]

Get the dictionary of child nodes.

Returns:

  • dict[str, _TreeNodeT] –

    dict[str, _TreeNodeT]: A dictionary mapping each child's unique ID to its TreeNode instance.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> root.add_child(child)
>>> list(root.children.values())[0].value
'child'

is_leaf property 

is_leaf: bool

Determine if the node is a leaf (i.e., has no children).

Returns:

  • bool ( bool ) –

    True if the node has no children; otherwise, False.

Examples:

>>> node = TreeNode("leaf")
>>> node.is_leaf
True

value property 

value: Any

Retrieve the value stored in the node.

Returns:

  • Any ( Any ) –

    The value of the node.

Examples:

>>> node = TreeNode(10)
>>> node.value
10

id property 

id: str

Get the unique identifier of the node.

Returns:

  • str ( str ) –

    A unique hexadecimal string identifier for the node.

Examples:

>>> node = TreeNode("example")
>>> isinstance(node.id, str)
True

add_child 

add_child(child: _TreeNodeT)

Add a child node to the current node.

This method adds the given child to the node's children dictionary (using the child's ID as key) and sets the current node as the parent of the child.

Parameters:

  • child (TreeNode) –

    The child node to add.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> root.add_child(child)
>>> child.parent is root
True
Source code in ures/data_structure/tree.py 
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
def add_child(self, child: _TreeNodeT):
    """
    Add a child node to the current node.

    This method adds the given child to the node's children dictionary (using the child's ID as key)
    and sets the current node as the parent of the child.

    Args:
        child (TreeNode): The child node to add.

    Examples:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> root.add_child(child)
        >>> child.parent is root
        True
    """
    if child.id not in self.children:
        self._children[child.id] = child
        child.set_parent(self)

remove_child 

remove_child(child: TreeNode)

Remove a child node from the current node.

This method removes the specified child node from the current node's children and clears the child's parent reference.

Parameters:

  • child (TreeNode) –

    The child node to remove.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> root.add_child(child)
>>> root.remove_child(child)
>>> child.parent is None
True
Source code in ures/data_structure/tree.py 
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
def remove_child(self, child: TreeNode):
    """
    Remove a child node from the current node.

    This method removes the specified child node from the current node's children and clears the
    child's parent reference.

    Args:
        child (TreeNode): The child node to remove.

    Examples:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> root.add_child(child)
        >>> root.remove_child(child)
        >>> child.parent is None
        True
    """
    if child.id in self.children:
        self._children.pop(child.id)
        child.set_parent(None)

set_parent 

set_parent(parent: _TreeNodeT | None)

Set the parent of the current node.

If the node already has a parent, it will be removed from that parent's children before setting the new parent.

Parameters:

  • parent (TreeNode | None) –

    The new parent node. If None, the node will have no parent.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> child.set_parent(root)
>>> child.parent is root
True
Source code in ures/data_structure/tree.py 
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
def set_parent(self, parent: _TreeNodeT | None):
    """
    Set the parent of the current node.

    If the node already has a parent, it will be removed from that parent's children before setting
    the new parent.

    Args:
        parent (TreeNode | None): The new parent node. If None, the node will have no parent.

    Examples:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> child.set_parent(root)
        >>> child.parent is root
        True
    """
    if parent is not None:
        if isinstance(self.parent, TreeNode):
            self.parent.remove_child(self)
    self._parent = parent

backward_stack 

backward_stack() -> Iterator[TreeNode]

Generate an iterator for the path from the current node to the root.

The iterator yields nodes starting with the current node and then each successive parent until no further parent exists.

Returns:

  • Iterator[TreeNode] –

    Iterator[TreeNode]: An iterator over the nodes from the current node up to the root.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> child.set_parent(root)
>>> "/".join(node.value for node in child.backward_stack())
'child/root'
Source code in ures/data_structure/tree.py 
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
def backward_stack(self) -> Iterator[TreeNode]:
    """
    Generate an iterator for the path from the current node to the root.

    The iterator yields nodes starting with the current node and then each successive parent until
    no further parent exists.

    Returns:
        Iterator[TreeNode]: An iterator over the nodes from the current node up to the root.

    Examples:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> child.set_parent(root)
        >>> "/".join(node.value for node in child.backward_stack())
        'child/root'
    """
    current = self
    while current is not None:
        yield current
        current = current.parent

forward_stack 

forward_stack(**kwargs) -> list[list[Any]]

Get all forward paths from the current node to each leaf node.

This method performs a depth-first search (DFS) to compute every possible path from the current node to all leaf nodes. If an optional attribute key is provided via kwargs, the method returns that attribute for each node in the path; otherwise, it returns the node itself.

Other Parameters:

  • attr (str) –

    The attribute name to extract from each node. Defaults to None.

Returns:

  • list[list[Any]] –

    list[list[Any]]: A list of paths, where each path is a list of nodes or attribute values from the current node to a leaf node.

Examples:

>>> root = TreeNode("root")
>>> child1 = TreeNode("child1")
>>> child2 = TreeNode("child2")
>>> root.add_child(child1)
>>> root.add_child(child2)
>>> paths = root.forward_stack(attr="value")
>>> sorted(paths)
[['child1', 'root'], ['child2', 'root']]  # Order may vary
Source code in ures/data_structure/tree.py 
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
def forward_stack(self, **kwargs) -> list[list[Any]]:
    """
    Get all forward paths from the current node to each leaf node.

    This method performs a depth-first search (DFS) to compute every possible path from the current node
    to all leaf nodes. If an optional attribute key is provided via kwargs, the method returns that attribute
    for each node in the path; otherwise, it returns the node itself.

    Keyword Args:
        attr (str, optional): The attribute name to extract from each node. Defaults to None.

    Returns:
        list[list[Any]]: A list of paths, where each path is a list of nodes or attribute values from the
                         current node to a leaf node.

    Examples:
        >>> root = TreeNode("root")
        >>> child1 = TreeNode("child1")
        >>> child2 = TreeNode("child2")
        >>> root.add_child(child1)
        >>> root.add_child(child2)
        >>> paths = root.forward_stack(attr="value")
        >>> sorted(paths)
        [['child1', 'root'], ['child2', 'root']]  # Order may vary
    """
    all_paths = []
    self._dfs(cast(_TreeNodeT, self), [], all_paths, **kwargs)
    return all_paths

BiDirection 

BiDirection(value: Any)

Bases: Generic[_BiDirectionT]

Create a bi-directional linked node.

Initializes a node with the given value and sets its previous and next pointers to itself, forming a circular structure when isolated.

Parameters:

  • value (Any) –

    The value to store in the node.

Examples:

>>> node = BiDirection("A")
>>> node.value
'A'
>>> node.prev is node
True
>>> node.next is node
True
Source code in ures/data_structure/bi_directional_links.py 
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def __init__(self, value: Any):
    """
    Create a bi-directional linked node.

    Initializes a node with the given value and sets its previous and next pointers to itself,
    forming a circular structure when isolated.

    Args:
        value (Any): The value to store in the node.

    Examples:
        >>> node = BiDirection("A")
        >>> node.value
        'A'
        >>> node.prev is node
        True
        >>> node.next is node
        True
    """
    self._prev: _BiDirectionT = cast(_BiDirectionT, self)
    self._next: _BiDirectionT = cast(_BiDirectionT, self)
    self._value: Any = value
    self._id = uuid.uuid4().hex

prev property 

prev: _BiDirectionT

Get the previous node in the linked structure.

Returns:

  • BiDirection ( _BiDirectionT ) –

    The previous node.

Examples:

>>> node = BiDirection("A")
>>> node.prev is node
True

next property 

next: _BiDirectionT

Get the next node in the linked structure.

Returns:

  • BiDirection ( _BiDirectionT ) –

    The next node.

Examples:

>>> node = BiDirection("A")
>>> node.next is node
True

value property 

value: Any

Retrieve the value stored in the node.

Returns:

  • Any ( Any ) –

    The node's value.

Examples:

>>> node = BiDirection(123)
>>> node.value
123

id property 

id: str

Get the unique identifier of the node.

Returns:

  • str ( str ) –

    A hexadecimal string representing the node's unique ID.

Examples:

>>> node = BiDirection("A")
>>> isinstance(node.id, str)
True

insert_after 

insert_after(node: _BiDirectionT) -> None

Insert a node immediately after the current node.

Adjusts pointers so that the new node is placed between the current node and its next node.

Parameters:

  • node (BiDirection) –

    The node to be inserted after the current node.

Examples:

>>> node1 = BiDirection("A")
>>> node2 = BiDirection("B")
>>> node1.insert_after(node2)
>>> node1.next is node2
True
>>> node2.prev is node1
True
Source code in ures/data_structure/bi_directional_links.py 
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
def insert_after(self, node: _BiDirectionT) -> None:
    """
    Insert a node immediately after the current node.

    Adjusts pointers so that the new node is placed between the current node and its next node.

    Args:
        node (BiDirection): The node to be inserted after the current node.

    Examples:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("B")
        >>> node1.insert_after(node2)
        >>> node1.next is node2
        True
        >>> node2.prev is node1
        True
    """
    node._prev = self
    node._next = self._next
    self._next._prev = node
    self._next = node

insert_before 

insert_before(node: _BiDirectionT) -> None

Insert a node immediately before the current node.

Adjusts pointers so that the new node is placed between the current node's previous node and the current node.

Parameters:

  • node (BiDirection) –

    The node to be inserted before the current node.

Examples:

>>> node1 = BiDirection("A")
>>> node2 = BiDirection("B")
>>> node1.insert_before(node2)
>>> node1.prev is node2
True
>>> node2.next is node1
True
Source code in ures/data_structure/bi_directional_links.py 
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
def insert_before(self, node: _BiDirectionT) -> None:
    """
    Insert a node immediately before the current node.

    Adjusts pointers so that the new node is placed between the current node's previous node and the current node.

    Args:
        node (BiDirection): The node to be inserted before the current node.

    Examples:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("B")
        >>> node1.insert_before(node2)
        >>> node1.prev is node2
        True
        >>> node2.next is node1
        True
    """
    node._prev = self._prev
    node._next = self
    self._prev._next = node
    self._prev = node

remove 

remove() -> None

Remove the current node from the linked structure.

Adjusts the previous and next nodes to bypass the current node and resets the current node's pointers to point to itself.

Examples:

>>> node1 = BiDirection("A")
>>> node2 = BiDirection("B")
>>> node1.insert_after(node2)
>>> node2.remove()
>>> node1.next is node1
True
Source code in ures/data_structure/bi_directional_links.py 
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
def remove(self) -> None:
    """
    Remove the current node from the linked structure.

    Adjusts the previous and next nodes to bypass the current node and resets the current node's
    pointers to point to itself.

    Examples:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("B")
        >>> node1.insert_after(node2)
        >>> node2.remove()
        >>> node1.next is node1
        True
    """
    self._prev._next = self._next
    self._next._prev = self._prev
    self._prev = cast(_BiDirectionT, self)
    self._next = cast(_BiDirectionT, self)

search 

search(value: Any) -> Optional[_BiDirectionT]

Search for a node with the specified value in the linked structure.

Starting from the current node, traverse through the chain until the value is found or the search returns to the starting node.

Parameters:

  • value (Any) –

    The value to search for.

Returns:

  • Optional[_BiDirectionT] –

    Optional[BiDirection]: The node with the matching value, or None if not found.

Examples:

>>> node1 = BiDirection("A")
>>> node2 = BiDirection("B")
>>> node3 = BiDirection("C")
>>> node1.insert_after(node2)
>>> node2.insert_after(node3)
>>> found = node1.search("C")
>>> found.value
'C'
>>> not_found = node1.search("D")
>>> not_found is None
True
Source code in ures/data_structure/bi_directional_links.py 
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
def search(self, value: Any) -> Optional[_BiDirectionT]:
    """
    Search for a node with the specified value in the linked structure.

    Starting from the current node, traverse through the chain until the value is found or the search
    returns to the starting node.

    Args:
        value (Any): The value to search for.

    Returns:
        Optional[BiDirection]: The node with the matching value, or None if not found.

    Examples:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("B")
        >>> node3 = BiDirection("C")
        >>> node1.insert_after(node2)
        >>> node2.insert_after(node3)
        >>> found = node1.search("C")
        >>> found.value
        'C'
        >>> not_found = node1.search("D")
        >>> not_found is None
        True
    """
    node: _BiDirectionT = cast(_BiDirectionT, self)
    while node.value != value and node.next != self:
        node = node.next
    return node if node.value == value else None

NonCircularBiLink(value: Any)

Bases: BiDirection['NonCircularBiLink']

Create a non-circular doubly linked list node.

Parameters:

  • value (Any) –

    The value of the node.

Source code in ures/data_structure/bi_directional_links.py 
242
243
244
245
246
247
248
249
250
def __init__(self, value: Any):
    """Create a non-circular doubly linked list node.

    Args:
            value (Any): The value of the node.
    """
    super().__init__(value)
    self._prev: Optional[NonCircularBiLink] = None
    self._next: Optional[NonCircularBiLink] = None

insert_after 

insert_after(node: NonCircularBiLink)

Insert a node after the current node.

Parameters:

  • node (NonCircularDoublyLinkedNode) –

    The node to be inserted.

Source code in ures/data_structure/bi_directional_links.py 
260
261
262
263
264
265
266
267
268
269
270
271
def insert_after(self, node: NonCircularBiLink):
    """Insert a node after the current node.

    Args:
            node (NonCircularDoublyLinkedNode): The node to be inserted.

    """
    node._prev = self
    node._next = self._next
    if self._next:
        self._next._prev = node
    self._next = node

insert_before 

insert_before(node: NonCircularBiLink)

Insert a node before the current node.

Parameters:

  • node (NonCircularDoublyLinkedNode) –

    The node to be inserted.

Source code in ures/data_structure/bi_directional_links.py 
273
274
275
276
277
278
279
280
281
282
283
284
def insert_before(self, node: NonCircularBiLink):
    """Insert a node before the current node.

    Args:
            node (NonCircularDoublyLinkedNode): The node to be inserted.

    """
    node._next = self
    node._prev = self._prev
    if self._prev:
        self._prev._next = node
    self._prev = node

remove 

remove()

Remove the current node from the list.

Source code in ures/data_structure/bi_directional_links.py 
286
287
288
289
290
291
292
293
def remove(self):
    """Remove the current node from the list."""
    if self._prev:
        self._prev._next = self._next
    if self._next:
        self._next._prev = self._prev
    self._prev = None
    self._next = None

get_head 

get_head() -> NonCircularBiLink

Get the head of the list starting from the current node.

Returns:

Source code in ures/data_structure/bi_directional_links.py 
295
296
297
298
299
300
301
302
303
304
def get_head(self) -> NonCircularBiLink:
    """Get the head of the list starting from the current node.

    Returns:
            NonCircularBiLink: The head node of the list.
    """
    node = self
    while node.prev:
        node = node.prev
    return node

search 

search(value: Any) -> Optional[NonCircularBiLink]

Search a node by value starting from the current node.

Parameters:

  • value (Any) –

    The value to be searched.

Returns:

Source code in ures/data_structure/bi_directional_links.py 
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
def search(self, value: Any) -> Optional[NonCircularBiLink]:
    """Search a node by value starting from the current node.

    Args:
            value (Any): The value to be searched.

    Returns:
            Optional[NonCircularDoublyLinkedNode]: The node with the value if found, else None.
    """
    node = self.get_head()
    # traverse the list until the end
    while node:
        if node.value == value:
            return node
        node = node.next
    return None

total_nodes 

total_nodes() -> int

Count the total number of nodes in the list starting from the current node.

Returns:

  • int –

    The number of nodes reachable from this node.

Source code in ures/data_structure/bi_directional_links.py 
323
324
325
326
327
328
329
330
331
332
333
334
def total_nodes(self) -> int:
    """Count the total number of nodes in the list starting from the current node.

    Returns:
        The number of nodes reachable from this node.
    """
    count = 0
    node = self.get_head()
    while node:
        count += 1
        node = node.next
    return count