Package logilab-common-0 :: Package 39 :: Package 0 :: Module tree
[frames] | no frames]

Source Code for Module logilab-common-0.39.0.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  ## Exceptions ################################################################# 
 15   
16 -class NodeNotFound(Exception):
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 # Base node ################################################################### 25
26 -class Node(object):
27 """a basic tree node, caracterised by an id""" 28
29 - def __init__(self, nid=None) :
30 self.id = nid 31 # navigation 32 self.parent = None 33 self.children = []
34
35 - def __iter__(self):
36 return iter(self.children)
37
38 - def __str__(self, indent=0):
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
48 - def is_leaf(self):
49 return not self.children
50
51 - def append(self, child):
52 """add a node to children""" 53 self.children.append(child) 54 child.parent = self
55
56 - def remove(self, child):
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
73 - def get_sibling(self, nid):
74 """return the sibling node that has given id""" 75 try: 76 return self.parent.get_child_by_id(nid) 77 except NodeNotFound : 78 raise NodeNotFound(EX_SIBLING_NOT_FOUND % nid)
79
80 - def next_sibling(self):
81 """ 82 return the next sibling for this node if any 83 """ 84 parent = self.parent 85 if parent is None: 86 # root node has no sibling 87 return None 88 index = parent.children.index(self) 89 try: 90 return parent.children[index+1] 91 except IndexError: 92 return None
93
94 - def previous_sibling(self):
95 """ 96 return the previous sibling for this node if any 97 """ 98 parent = self.parent 99 if parent is None: 100 # root node has no sibling 101 return None 102 index = parent.children.index(self) 103 if index > 0: 104 return parent.children[index-1] 105 return None
106
107 - def get_node_by_id(self, nid):
108 """ 109 return node in whole hierarchy that has given id 110 """ 111 root = self.root() 112 try: 113 return root.get_child_by_id(nid, 1) 114 except NodeNotFound : 115 raise NodeNotFound(EX_NODE_NOT_FOUND % nid)
116
117 - def get_child_by_id(self, nid, recurse=None):
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
133 - def get_child_by_path(self, path):
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
148 - def depth(self):
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
157 - def depth_down(self):
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
165 - def width(self):
166 """ 167 return the width of the tree from this node 168 """ 169 return len(self.leaves())
170
171 - def root(self):
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
179 - def leaves(self):
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
191 - def __iter__(self):
192 return iter(self.children)
193
194 - def flatten(self, _list=None):
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
205 - def lineage(self):
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
220 -class BinaryNode(VNode):
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
230 - def remove(self, child):
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
236 - def get_parts(self):
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
250 -class ListNode(VNode, list_class):
251 """Used to manipulate Nodes as Lists 252 """
253 - def __init__(self):
254 list_class.__init__(self) 255 VNode.__init__(self) 256 self.children = self
257
258 - def __str__(self, indent=0):
259 return '%s%s %s' % (indent*' ', self.__class__.__name__, 260 ', '.join([str(v) for v in self]))
261
262 - def append(self, child):
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
272 - def remove(self, child):
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
282 - def __iter__(self):
283 return list_class.__iter__(self)
284 285 # construct list from tree #################################################### 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
315 -def pre_order_list(node, filter_func=no_filter):
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):
348 FilteredIterator.__init__(self, node, post_order_list, filter_func)
349
350 -class PrefixedDepthFirstIterator(FilteredIterator):
351 """a pretfixed depth first iterator, designed to be used with visitors 352 """
353 - def __init__(self, node, filter_func=None):
354 FilteredIterator.__init__(self, node, pre_order_list, filter_func)
355