Skip to content

mode.utils.trees

Data structure: Trees.

Node

Bases: NodeT[T]

Tree node.

Notes

Nodes have a link to

- the ``.root`` node (or None if this is the top-most node)
- the ``.parent`` node (if this is a child node).
- a list of children

A Node may have arbitrary .data associated with it, and arbitrary data may also be stored in .children.

Parameters:

Name Type Description Default
data Any

Data to associate with node.

 required

Other Parameters:

Name Type Description
root NodeT

Root node.
parent NodeT

Parent node.
children List[NodeT]

List of child nodes.
Source code in mode/utils/trees.py 
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
class Node(NodeT[T]):
    """Tree node.

    Notes:
        Nodes have a link to

            - the ``.root`` node (or None if this is the top-most node)
            - the ``.parent`` node (if this is a child node).
            - a list of children

        A Node may have arbitrary ``.data`` associated with it, and arbitrary
        data may also be stored in ``.children``.

    Arguments:
        data (Any): Data to associate with node.

    Keyword Arguments:
        root (NodeT): Root node.
        parent (NodeT): Parent node.
        children (List[NodeT]): List of child nodes.
    """

    _root: Optional[NodeT[T]] = None
    _parent: Optional[NodeT[T]] = None

    @classmethod
    def _new_node(cls, data: T, **kwargs: Any) -> NodeT[T]:
        return cls(data, **kwargs)

    def __init__(
        self,
        data: T,
        *,
        root: NodeT = None,
        parent: NodeT = None,
        children: Optional[List[NodeT[T]]] = None,
    ) -> None:
        self.data = data
        if root is not None:
            self.root = root
        if parent is not None:
            self.parent = parent
        self.children = children or []

    def new(self, data: T) -> NodeT:
        """Create new node from this node."""
        node = self._new_node(
            data,
            root=self.root if self.root is not None else self,
            parent=self,
        )
        self.children.append(node)
        return node

    def reattach(self, parent: NodeT[T]) -> NodeT[T]:
        """Attach this node to `parent` node."""
        self.root = parent.root if parent.root is not None else parent
        self.parent = parent
        parent.add_deduplicate(self)
        return self

    def detach(self, parent: NodeT[T]) -> NodeT[T]:
        """Detach this node from `parent` node."""
        if self.parent is not None:
            self.parent.discard(self)
        self._parent = None
        self._root = None
        return self

    def add_deduplicate(self, data: Union[T, NodeT[T]]) -> None:
        if data not in self.children:
            self.children.append(data)

    def add(self, data: Union[T, NodeT[T]]) -> None:
        """Add node as a child node."""
        self.children.append(data)

    def discard(self, data: T) -> None:
        """Remove node so it's no longer a child of this node."""
        # XXX slow
        with suppress(ValueError):
            self.children.remove(data)

    def traverse(self) -> Iterator[NodeT[T]]:
        """Iterate over the tree in BFS order."""
        stack: Deque[NodeT[T]] = Deque([self])
        while stack:
            node = stack.popleft()
            yield node
            for child in node.children:
                if isinstance(child, NodeT):
                    stack.append(child)
                else:
                    yield child

    def walk(self) -> Iterator[NodeT[T]]:
        """Iterate over hierarchy backwards.

        This will yield parent nodes all the way up to the root.
        """
        node: Optional[NodeT[T]] = self
        while node:
            yield node
            node = node.parent

    def as_graph(self) -> DependencyGraphT:
        """Convert to `~mode.utils.graphs.DependencyGraph`."""
        graph = DependencyGraph()
        stack: Deque[NodeT] = Deque([self])
        while stack:
            node = stack.popleft()
            for child in node.children:
                graph.add_arc(node.data)
                if isinstance(child, NodeT):
                    stack.append(cast(Node, child))
                    graph.add_edge(node.data, child.data)
                else:
                    graph.add_edge(node.data, child)
        return graph

    def __repr__(self) -> str:
        return f"{type(self).__name__}: {self.path}"

    @property
    def depth(self) -> int:
        return self._find_depth()

    def _find_depth(self) -> int:
        return sum(1 for _ in enumerate(self.walk()))

    @property
    def path(self) -> str:
        return "/".join(
            reversed([shortlabel(node.data) for node in self.walk()])
        )

    @property
    def parent(self) -> Optional[NodeT]:
        return self._parent

    @parent.setter
    def parent(self, node: NodeT) -> None:
        if node is self:
            raise ValueError("Parent node cannot be itself.")
        self._parent = node

    @property
    def root(self) -> Optional[NodeT]:
        return self._root

    @root.setter
    def root(self, node: NodeT) -> None:
        if node is self:
            raise ValueError("Root node cannot be itself.")
        self._root = node

add(data)

Add node as a child node.

Source code in mode/utils/trees.py 
89
90
91
def add(self, data: Union[T, NodeT[T]]) -> None:
    """Add node as a child node."""
    self.children.append(data)

as_graph()

Convert to ~mode.utils.graphs.DependencyGraph.

Source code in mode/utils/trees.py 
121
122
123
124
125
126
127
128
129
130
131
132
133
134
def as_graph(self) -> DependencyGraphT:
    """Convert to `~mode.utils.graphs.DependencyGraph`."""
    graph = DependencyGraph()
    stack: Deque[NodeT] = Deque([self])
    while stack:
        node = stack.popleft()
        for child in node.children:
            graph.add_arc(node.data)
            if isinstance(child, NodeT):
                stack.append(cast(Node, child))
                graph.add_edge(node.data, child.data)
            else:
                graph.add_edge(node.data, child)
    return graph

detach(parent)

Detach this node from parent node.

Source code in mode/utils/trees.py 
77
78
79
80
81
82
83
def detach(self, parent: NodeT[T]) -> NodeT[T]:
    """Detach this node from `parent` node."""
    if self.parent is not None:
        self.parent.discard(self)
    self._parent = None
    self._root = None
    return self

discard(data)

Remove node so it's no longer a child of this node.

Source code in mode/utils/trees.py 
93
94
95
96
97
def discard(self, data: T) -> None:
    """Remove node so it's no longer a child of this node."""
    # XXX slow
    with suppress(ValueError):
        self.children.remove(data)

new(data)

Create new node from this node.

Source code in mode/utils/trees.py 
60
61
62
63
64
65
66
67
68
def new(self, data: T) -> NodeT:
    """Create new node from this node."""
    node = self._new_node(
        data,
        root=self.root if self.root is not None else self,
        parent=self,
    )
    self.children.append(node)
    return node

reattach(parent)

Attach this node to parent node.

Source code in mode/utils/trees.py 
70
71
72
73
74
75
def reattach(self, parent: NodeT[T]) -> NodeT[T]:
    """Attach this node to `parent` node."""
    self.root = parent.root if parent.root is not None else parent
    self.parent = parent
    parent.add_deduplicate(self)
    return self

traverse()

Iterate over the tree in BFS order.

Source code in mode/utils/trees.py 
 99
100
101
102
103
104
105
106
107
108
109
def traverse(self) -> Iterator[NodeT[T]]:
    """Iterate over the tree in BFS order."""
    stack: Deque[NodeT[T]] = Deque([self])
    while stack:
        node = stack.popleft()
        yield node
        for child in node.children:
            if isinstance(child, NodeT):
                stack.append(child)
            else:
                yield child

walk()

Iterate over hierarchy backwards.

This will yield parent nodes all the way up to the root.

Source code in mode/utils/trees.py 
111
112
113
114
115
116
117
118
119
def walk(self) -> Iterator[NodeT[T]]:
    """Iterate over hierarchy backwards.

    This will yield parent nodes all the way up to the root.
    """
    node: Optional[NodeT[T]] = self
    while node:
        yield node
        node = node.parent