/usr/lib/python3/dist-packages/urwidtrees/tree.py is in python3-urwidtrees 1.0.1.1-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 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 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 | # Copyright (C) 2013 Patrick Totzke <patricktotzke@gmail.com>
# This file is released under the GNU GPL, version 3 or a later revision.
import logging
class Tree(object):
"""
Base class for a tree strucures that can be displayed by :class:`TreeBox`
widgets. An instance defines a structure by defining local transformations
on positions. That is, by overwriting
* `next_sibling_position`
* `prev_sibling_position`
* `parent_position`
* `first_child_position`
* `last_child_position`
that compute the next position in the respective direction. Also, they need
to implement method `__getitem__` that returns a :class:`Widget` for a
given position.
The type of objects used as positions may vary in subclasses and is
deliberately unspecified for the base class.
This base class already implements methods based on the local
transformations above. These include :meth:`depth`, :meth:`last_decendant`
and :meth:`[next|prev]_position <next_position>` that computes
next/previous positions in depth-first order.
"""
root = None
# local helper
def _get(self, pos):
"""loads widget at given position; handling invalid arguments"""
res = None, None
if pos is not None:
try:
res = self[pos], pos
except (IndexError, KeyError):
pass
return res
def _next_of_kin(self, pos):
"""
looks up the next sibling of the closest ancestor with not-None next
siblings.
"""
candidate = None
parent = self.parent_position(pos)
if parent is not None:
candidate = self.next_sibling_position(parent)
if candidate is None:
candidate = self._next_of_kin(parent)
return candidate
def _last_in_direction(self, starting_pos, direction):
"""
move in the tree in given direction and return the last position.
:param starting_pos: position to start at
:param direction: callable that transforms a position into a position.
"""
cur_pos = None
next_pos = starting_pos
while next_pos is not None:
cur_pos = next_pos
next_pos = direction(cur_pos)
return cur_pos
def depth(self, pos):
"""determine depth of node at pos"""
parent = self.parent_position(pos)
if parent is None:
return 0
else:
return self.depth(parent) + 1
def is_leaf(self, pos):
"""checks if given position has no children"""
return self.first_child_position(pos) is None
def first_ancestor(self, pos):
"""
position of pos's ancestor with depth 0. Usually, this should return
the root node, but a :class:`Tree` might represent a forrest - have
multiple nodes without parent.
"""
return self._last_in_direction(pos, self.parent_position)
def last_decendant(self, pos):
"""position of last (in DFO) decendant of pos"""
return self._last_in_direction(pos, self.last_child_position)
def last_sibling_position(self, pos):
"""position of last sibling of pos"""
return self._last_in_direction(pos, self.next_sibling_position)
def first_sibling_position(self, pos):
"""position of first sibling of pos"""
return self._last_in_direction(pos, self.prev_sibling_position)
def next_position(self, pos):
"""returns the next position in depth-first order"""
candidate = None
if pos is not None:
candidate = self.first_child_position(pos)
if candidate is None:
candidate = self.next_sibling_position(pos)
if candidate is None:
candidate = self._next_of_kin(pos)
return candidate
def prev_position(self, pos):
"""returns the previous position in depth-first order"""
candidate = None
if pos is not None:
prevsib = self.prev_sibling_position(pos) # is None if first
if prevsib is not None:
candidate = self.last_decendant(prevsib)
else:
parent = self.parent_position(pos)
if parent is not None:
candidate = parent
return candidate
def positions(self, reverse=False):
"""returns a generator that walks the positions of this tree in DFO"""
def Posgen(reverse):
if reverse:
lastrootsib = self.last_sibling_position(self.root)
current = self.last_decendant(lastrootsib)
while current is not None:
yield current
current = self.prev_position(current)
else:
current = self.root
while current is not None:
yield current
current = self.next_position(current)
return Posgen(reverse)
####################################################################
# End of high-level helper implementation. The following need to be
# overwritten by subclasses
####################################################################
def parent_position(self, pos):
"""returns the position of the parent node of the node at `pos`
or `None` if none exists."""
return None
def first_child_position(self, pos):
"""returns the position of the first child of the node at `pos`,
or `None` if none exists."""
return None
def last_child_position(self, pos):
"""returns the position of the last child of the node at `pos`,
or `None` if none exists."""
return None
def next_sibling_position(self, pos):
"""returns the position of the next sibling of the node at `pos`,
or `None` if none exists."""
return None
def prev_sibling_position(self, pos):
"""returns the position of the previous sibling of the node at `pos`,
or `None` if none exists."""
return None
class SimpleTree(Tree):
"""
Walks on a given fixed acyclic structure given as a list of nodes; every
node is a tuple `(content, children)`, where `content` is a `urwid.Widget`
to be displayed at that position and `children` is either `None` or a list
of nodes.
Positions are lists of integers determining a path from the root node with
position `(0,)`.
"""
def __init__(self, treelist):
self._treelist = treelist
self.root = (0,) if treelist else None
Tree.__init__(self)
# a few local helper methods
def _get_substructure(self, treelist, pos):
"""recursive helper to look up node-tuple for `pos` in `treelist`"""
subtree = None
if len(pos) > 1:
subtree = self._get_substructure(treelist[pos[0]][1], pos[1:])
else:
try:
subtree = treelist[pos[0]]
except (IndexError, TypeError):
pass
return subtree
def _get_node(self, treelist, pos):
"""
look up widget at `pos` of `treelist`; default to None if
nonexistent.
"""
node = None
if pos is not None:
subtree = self._get_substructure(treelist, pos)
if subtree is not None:
node = subtree[0]
return node
def _confirm_pos(self, pos):
"""look up widget for pos and default to None"""
candidate = None
if self._get_node(self._treelist, pos) is not None:
candidate = pos
return candidate
# Tree API
def __getitem__(self, pos):
return self._get_node(self._treelist, pos)
def parent_position(self, pos):
parent = None
if pos is not None:
if len(pos) > 1:
parent = pos[:-1]
return parent
def first_child_position(self, pos):
return self._confirm_pos(pos + (0,))
def last_child_position(self, pos):
candidate = None
subtree = self._get_substructure(self._treelist, pos)
if subtree is not None:
children = subtree[1]
if children is not None:
candidate = pos + (len(children) - 1,)
return candidate
def next_sibling_position(self, pos):
return self._confirm_pos(pos[:-1] + (pos[-1] + 1,))
def prev_sibling_position(self, pos):
return pos[:-1] + (pos[-1] - 1,) if (pos[-1] > 0) else None
# optimizations
def depth(self, pos):
"""more performant implementation due to specific structure of pos"""
return len(pos) - 1
|