1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 """Base class to represent a tree structure.
19
20
21
22
23 """
24 __docformat__ = "restructuredtext en"
25
26 import sys
27
28 from logilab.common import flatten
29 from logilab.common.visitor import VisitedMixIn, FilteredIterator, no_filter
30
31
32
34 """raised when a node has not been found"""
35
36 EX_SIBLING_NOT_FOUND = "No such sibling as '%s'"
37 EX_CHILD_NOT_FOUND = "No such child as '%s'"
38 EX_NODE_NOT_FOUND = "No such node as '%s'"
39
40
41
42
44 """a basic tree node, characterized by an id"""
45
47 self.id = nid
48
49 self.parent = None
50 self.children = []
51
53 return iter(self.children)
54
56 s = ['%s%s %s' % (' '*indent, self.__class__.__name__, self.id)]
57 indent += 2
58 for child in self.children:
59 try:
60 s.append(child.__str__(indent))
61 except TypeError:
62 s.append(child.__str__())
63 return '\n'.join(s)
64
66 return not self.children
67
69 """add a node to children"""
70 self.children.append(child)
71 child.parent = self
72
74 """remove a child node"""
75 self.children.remove(child)
76 child.parent = None
77
78 - def insert(self, index, child):
79 """insert a child node"""
80 self.children.insert(index, child)
81 child.parent = self
82
83 - def replace(self, old_child, new_child):
84 """replace a child node with another"""
85 i = self.children.index(old_child)
86 self.children.pop(i)
87 self.children.insert(i, new_child)
88 new_child.parent = self
89
96
98 """
99 return the next sibling for this node if any
100 """
101 parent = self.parent
102 if parent is None:
103
104 return None
105 index = parent.children.index(self)
106 try:
107 return parent.children[index+1]
108 except IndexError:
109 return None
110
112 """
113 return the previous sibling for this node if any
114 """
115 parent = self.parent
116 if parent is None:
117
118 return None
119 index = parent.children.index(self)
120 if index > 0:
121 return parent.children[index-1]
122 return None
123
133
135 """
136 return child of given id
137 """
138 if self.id == nid:
139 return self
140 for c in self.children :
141 if recurse:
142 try:
143 return c.get_child_by_id(nid, 1)
144 except NodeNotFound :
145 continue
146 if c.id == nid :
147 return c
148 raise NodeNotFound(EX_CHILD_NOT_FOUND % nid)
149
151 """
152 return child of given path (path is a list of ids)
153 """
154 if len(path) > 0 and path[0] == self.id:
155 if len(path) == 1 :
156 return self
157 else :
158 for c in self.children :
159 try:
160 return c.get_child_by_path(path[1:])
161 except NodeNotFound :
162 pass
163 raise NodeNotFound(EX_CHILD_NOT_FOUND % path)
164
166 """
167 return depth of this node in the tree
168 """
169 if self.parent is not None:
170 return 1 + self.parent.depth()
171 else :
172 return 0
173
175 """
176 return depth of the tree from this node
177 """
178 if self.children:
179 return 1 + max([c.depth_down() for c in self.children])
180 return 1
181
183 """
184 return the width of the tree from this node
185 """
186 return len(self.leaves())
187
189 """
190 return the root node of the tree
191 """
192 if self.parent is not None:
193 return self.parent.root()
194 return self
195
197 """
198 return a list with all the leaves nodes descendant from this node
199 """
200 leaves = []
201 if self.children:
202 for child in self.children:
203 leaves += child.leaves()
204 return leaves
205 else:
206 return [self]
207
209 return iter(self.children)
210
212 """
213 return a list with all the nodes descendant from this node
214 """
215 if _list is None:
216 _list = []
217 _list.append(self)
218 for c in self.children:
219 c.flatten(_list)
220 return _list
221
223 """
224 return list of parents up to root node
225 """
226 lst = [self]
227 if self.parent is not None:
228 lst.extend(self.parent.lineage())
229 return lst
230
231 -class VNode(Node, VisitedMixIn):
232 """a visitable node
233 """
234 pass
235
236
238 """a binary node (i.e. only two children
239 """
240 - def __init__(self, lhs=None, rhs=None) :
241 VNode.__init__(self)
242 if lhs is not None or rhs is not None:
243 assert lhs and rhs
244 self.append(lhs)
245 self.append(rhs)
246
248 """remove the child and replace this node with the other child
249 """
250 self.children.remove(child)
251 self.parent.replace(self, self.children[0])
252
254 """
255 return the left hand side and the right hand side of this node
256 """
257 return self.children[0], self.children[1]
258
259
260
261 if sys.version_info[0:2] >= (2, 2):
262 list_class = list
263 else:
264 from UserList import UserList
265 list_class = UserList
266
268 """Used to manipulate Nodes as Lists
269 """
274
276 return '%s%s %s' % (indent*' ', self.__class__.__name__,
277 ', '.join([str(v) for v in self]))
278
280 """add a node to children"""
281 list_class.append(self, child)
282 child.parent = self
283
284 - def insert(self, index, child):
285 """add a node to children"""
286 list_class.insert(self, index, child)
287 child.parent = self
288
290 """add a node to children"""
291 list_class.remove(self, child)
292 child.parent = None
293
294 - def pop(self, index):
295 """add a node to children"""
296 child = list_class.pop(self, index)
297 child.parent = None
298
301
302
303
304 -def post_order_list(node, filter_func=no_filter):
305 """
306 create a list with tree nodes for which the <filter> function returned true
307 in a post order fashion
308 """
309 l, stack = [], []
310 poped, index = 0, 0
311 while node:
312 if filter_func(node):
313 if node.children and not poped:
314 stack.append((node, index))
315 index = 0
316 node = node.children[0]
317 else:
318 l.append(node)
319 index += 1
320 try:
321 node = stack[-1][0].children[index]
322 except IndexError:
323 node = None
324 else:
325 node = None
326 poped = 0
327 if node is None and stack:
328 node, index = stack.pop()
329 poped = 1
330 return l
331
333 """
334 create a list with tree nodes for which the <filter> function returned true
335 in a pre order fashion
336 """
337 l, stack = [], []
338 poped, index = 0, 0
339 while node:
340 if filter_func(node):
341 if not poped:
342 l.append(node)
343 if node.children and not poped:
344 stack.append((node, index))
345 index = 0
346 node = node.children[0]
347 else:
348 index += 1
349 try:
350 node = stack[-1][0].children[index]
351 except IndexError:
352 node = None
353 else:
354 node = None
355 poped = 0
356 if node is None and len(stack) > 1:
357 node, index = stack.pop()
358 poped = 1
359 return l
360
361 -class PostfixedDepthFirstIterator(FilteredIterator):
362 """a postfixed depth first iterator, designed to be used with visitors
363 """
364 - def __init__(self, node, filter_func=None):
366
368 """a prefixed depth first iterator, designed to be used with visitors
369 """
370 - def __init__(self, node, filter_func=None):
372