Package logilab-common-0 ::
Package 39 ::
Package 0 ::
Module tree
|
|
1 """Base class to represent a tree structure.
2
3 :copyright: 2000-2008 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
4 :contact: http://www.logilab.fr/ -- mailto:contact@logilab.fr
5 :license: General Public License version 2 - http://www.gnu.org/licenses
6 """
7 __docformat__ = "restructuredtext en"
8
9 import sys
10
11 from logilab.common import flatten
12 from logilab.common.visitor import VisitedMixIn, FilteredIterator, no_filter
13
14
15
17 """raised when a node has not been found"""
18
19 EX_SIBLING_NOT_FOUND = "No such sibling as '%s'"
20 EX_CHILD_NOT_FOUND = "No such child as '%s'"
21 EX_NODE_NOT_FOUND = "No such node as '%s'"
22
23
24
25
27 """a basic tree node, caracterised by an id"""
28
30 self.id = nid
31
32 self.parent = None
33 self.children = []
34
36 return iter(self.children)
37
39 s = ['%s%s %s' % (' '*indent, self.__class__.__name__, self.id)]
40 indent += 2
41 for child in self.children:
42 try:
43 s.append(child.__str__(indent))
44 except TypeError:
45 s.append(child.__str__())
46 return '\n'.join(s)
47
49 return not self.children
50
52 """add a node to children"""
53 self.children.append(child)
54 child.parent = self
55
57 """remove a child node"""
58 self.children.remove(child)
59 child.parent = None
60
61 - def insert(self, index, child):
62 """insert a child node"""
63 self.children.insert(index, child)
64 child.parent = self
65
66 - def replace(self, old_child, new_child):
67 """replace a child node with another"""
68 i = self.children.index(old_child)
69 self.children.pop(i)
70 self.children.insert(i, new_child)
71 new_child.parent = self
72
79
81 """
82 return the next sibling for this node if any
83 """
84 parent = self.parent
85 if parent is None:
86
87 return None
88 index = parent.children.index(self)
89 try:
90 return parent.children[index+1]
91 except IndexError:
92 return None
93
95 """
96 return the previous sibling for this node if any
97 """
98 parent = self.parent
99 if parent is None:
100
101 return None
102 index = parent.children.index(self)
103 if index > 0:
104 return parent.children[index-1]
105 return None
106
116
118 """
119 return child of given id
120 """
121 if self.id == nid:
122 return self
123 for c in self.children :
124 if recurse:
125 try:
126 return c.get_child_by_id(nid, 1)
127 except NodeNotFound :
128 continue
129 if c.id == nid :
130 return c
131 raise NodeNotFound(EX_CHILD_NOT_FOUND % nid)
132
134 """
135 return child of given path (path is a list of ids)
136 """
137 if len(path) > 0 and path[0] == self.id:
138 if len(path) == 1 :
139 return self
140 else :
141 for c in self.children :
142 try:
143 return c.get_child_by_path(path[1:])
144 except NodeNotFound :
145 pass
146 raise NodeNotFound(EX_CHILD_NOT_FOUND % path)
147
149 """
150 return depth of this node in the tree
151 """
152 if self.parent is not None:
153 return 1 + self.parent.depth()
154 else :
155 return 0
156
158 """
159 return depth of the tree from this node
160 """
161 if self.children:
162 return 1 + max([c.depth_down() for c in self.children])
163 return 1
164
166 """
167 return the width of the tree from this node
168 """
169 return len(self.leaves())
170
172 """
173 return the root node of the tree
174 """
175 if self.parent is not None:
176 return self.parent.root()
177 return self
178
180 """
181 return a list with all the leaves nodes descendant from this node
182 """
183 leaves = []
184 if self.children:
185 for child in self.children:
186 leaves += child.leaves()
187 return leaves
188 else:
189 return [self]
190
192 return iter(self.children)
193
195 """
196 return a list with all the nodes descendant from this node
197 """
198 if _list is None:
199 _list = []
200 _list.append(self)
201 for c in self.children:
202 c.flatten(_list)
203 return _list
204
206 """
207 return list of parents up to root node
208 """
209 lst = [self]
210 if self.parent is not None:
211 lst.extend(self.parent.lineage())
212 return lst
213
214 -class VNode(Node, VisitedMixIn):
215 """a visitable node
216 """
217 pass
218
219
221 """a binary node (ie only two children
222 """
223 - def __init__(self, lhs=None, rhs=None) :
224 VNode.__init__(self)
225 if lhs is not None or rhs is not None:
226 assert lhs and rhs
227 self.append(lhs)
228 self.append(rhs)
229
231 """remove the child and replace this node with the other child
232 """
233 self.children.remove(child)
234 self.parent.replace(self, self.children[0])
235
237 """
238 return the left hand side and the right hand side of this node
239 """
240 return self.children[0], self.children[1]
241
242
243
244 if sys.version_info[0:2] >= (2, 2):
245 list_class = list
246 else:
247 from UserList import UserList
248 list_class = UserList
249
251 """Used to manipulate Nodes as Lists
252 """
257
259 return '%s%s %s' % (indent*' ', self.__class__.__name__,
260 ', '.join([str(v) for v in self]))
261
263 """add a node to children"""
264 list_class.append(self, child)
265 child.parent = self
266
267 - def insert(self, index, child):
268 """add a node to children"""
269 list_class.insert(self, index, child)
270 child.parent = self
271
273 """add a node to children"""
274 list_class.remove(self, child)
275 child.parent = None
276
277 - def pop(self, index):
278 """add a node to children"""
279 child = list_class.pop(self, index)
280 child.parent = None
281
284
285
286
287 -def post_order_list(node, filter_func=no_filter):
288 """
289 create a list with tree nodes for which the <filter> function returned true
290 in a post order fashion
291 """
292 l, stack = [], []
293 poped, index = 0, 0
294 while node:
295 if filter_func(node):
296 if node.children and not poped:
297 stack.append((node, index))
298 index = 0
299 node = node.children[0]
300 else:
301 l.append(node)
302 index += 1
303 try:
304 node = stack[-1][0].children[index]
305 except IndexError:
306 node = None
307 else:
308 node = None
309 poped = 0
310 if node is None and stack:
311 node, index = stack.pop()
312 poped = 1
313 return l
314
316 """
317 create a list with tree nodes for which the <filter> function returned true
318 in a pre order fashion
319 """
320 l, stack = [], []
321 poped, index = 0, 0
322 while node:
323 if filter_func(node):
324 if not poped:
325 l.append(node)
326 if node.children and not poped:
327 stack.append((node, index))
328 index = 0
329 node = node.children[0]
330 else:
331 index += 1
332 try:
333 node = stack[-1][0].children[index]
334 except IndexError:
335 node = None
336 else:
337 node = None
338 poped = 0
339 if node is None and len(stack) > 1:
340 node, index = stack.pop()
341 poped = 1
342 return l
343
344 -class PostfixedDepthFirstIterator(FilteredIterator):
345 """a postfixed depth first iterator, designed to be used with visitors
346 """
347 - def __init__(self, node, filter_func=None):
349
351 """a pretfixed depth first iterator, designed to be used with visitors
352 """
353 - def __init__(self, node, filter_func=None):
355