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 """
210 return a list with all the nodes descendant from this node
211 """
212 if _list is None:
213 _list = []
214 _list.append(self)
215 for c in self.children:
216 c.flatten(_list)
217 return _list
218
220 """
221 return list of parents up to root node
222 """
223 lst = [self]
224 if self.parent is not None:
225 lst.extend(self.parent.lineage())
226 return lst
227
228 -class VNode(Node, VisitedMixIn):
229 """a visitable node
230 """
231 pass
232
233
235 """a binary node (i.e. only two children
236 """
237 - def __init__(self, lhs=None, rhs=None) :
238 VNode.__init__(self)
239 if lhs is not None or rhs is not None:
240 assert lhs and rhs
241 self.append(lhs)
242 self.append(rhs)
243
245 """remove the child and replace this node with the other child
246 """
247 self.children.remove(child)
248 self.parent.replace(self, self.children[0])
249
251 """
252 return the left hand side and the right hand side of this node
253 """
254 return self.children[0], self.children[1]
255
256
257
258 if sys.version_info[0:2] >= (2, 2):
259 list_class = list
260 else:
261 from UserList import UserList
262 list_class = UserList
263
265 """Used to manipulate Nodes as Lists
266 """
271
273 return '%s%s %s' % (indent*' ', self.__class__.__name__,
274 ', '.join([str(v) for v in self]))
275
277 """add a node to children"""
278 list_class.append(self, child)
279 child.parent = self
280
281 - def insert(self, index, child):
282 """add a node to children"""
283 list_class.insert(self, index, child)
284 child.parent = self
285
287 """add a node to children"""
288 list_class.remove(self, child)
289 child.parent = None
290
291 - def pop(self, index):
292 """add a node to children"""
293 child = list_class.pop(self, index)
294 child.parent = None
295
298
299
300
301 -def post_order_list(node, filter_func=no_filter):
302 """
303 create a list with tree nodes for which the <filter> function returned true
304 in a post order fashion
305 """
306 l, stack = [], []
307 poped, index = 0, 0
308 while node:
309 if filter_func(node):
310 if node.children and not poped:
311 stack.append((node, index))
312 index = 0
313 node = node.children[0]
314 else:
315 l.append(node)
316 index += 1
317 try:
318 node = stack[-1][0].children[index]
319 except IndexError:
320 node = None
321 else:
322 node = None
323 poped = 0
324 if node is None and stack:
325 node, index = stack.pop()
326 poped = 1
327 return l
328
330 """
331 create a list with tree nodes for which the <filter> function returned true
332 in a pre order fashion
333 """
334 l, stack = [], []
335 poped, index = 0, 0
336 while node:
337 if filter_func(node):
338 if not poped:
339 l.append(node)
340 if node.children and not poped:
341 stack.append((node, index))
342 index = 0
343 node = node.children[0]
344 else:
345 index += 1
346 try:
347 node = stack[-1][0].children[index]
348 except IndexError:
349 node = None
350 else:
351 node = None
352 poped = 0
353 if node is None and len(stack) > 1:
354 node, index = stack.pop()
355 poped = 1
356 return l
357
358 -class PostfixedDepthFirstIterator(FilteredIterator):
359 """a postfixed depth first iterator, designed to be used with visitors
360 """
361 - def __init__(self, node, filter_func=None):
363
365 """a prefixed depth first iterator, designed to be used with visitors
366 """
367 - def __init__(self, node, filter_func=None):
369