Package logilab :: Package common :: Module tree
[frames] | no frames]

Source Code for Module logilab.common.tree

  1  # copyright 2003-2010 LOGILAB S.A. (Paris, FRANCE), all rights reserved. 
  2  # contact http://www.logilab.fr/ -- mailto:contact@logilab.fr 
  3  # 
  4  # This file is part of logilab-common. 
  5  # 
  6  # logilab-common is free software: you can redistribute it and/or modify it under 
  7  # the terms of the GNU Lesser General Public License as published by the Free 
  8  # Software Foundation, either version 2.1 of the License, or (at your option) any 
  9  # later version. 
 10  # 
 11  # logilab-common is distributed in the hope that it will be useful, but WITHOUT 
 12  # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 
 13  # FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more 
 14  # details. 
 15  # 
 16  # You should have received a copy of the GNU Lesser General Public License along 
 17  # with logilab-common.  If not, see <http://www.gnu.org/licenses/>. 
 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  ## Exceptions ################################################################# 
 32   
33 -class NodeNotFound(Exception):
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 # Base node ################################################################### 42
43 -class Node(object):
44 """a basic tree node, characterized by an id""" 45
46 - def __init__(self, nid=None) :
47 self.id = nid 48 # navigation 49 self.parent = None 50 self.children = []
51
52 - def __iter__(self):
53 return iter(self.children)
54
55 - def __str__(self, indent=0):
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
65 - def is_leaf(self):
66 return not self.children
67
68 - def append(self, child):
69 """add a node to children""" 70 self.children.append(child) 71 child.parent = self
72
73 - def remove(self, child):
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
90 - def get_sibling(self, nid):
91 """return the sibling node that has given id""" 92 try: 93 return self.parent.get_child_by_id(nid) 94 except NodeNotFound : 95 raise NodeNotFound(EX_SIBLING_NOT_FOUND % nid)
96
97 - def next_sibling(self):
98 """ 99 return the next sibling for this node if any 100 """ 101 parent = self.parent 102 if parent is None: 103 # root node has no sibling 104 return None 105 index = parent.children.index(self) 106 try: 107 return parent.children[index+1] 108 except IndexError: 109 return None
110
111 - def previous_sibling(self):
112 """ 113 return the previous sibling for this node if any 114 """ 115 parent = self.parent 116 if parent is None: 117 # root node has no sibling 118 return None 119 index = parent.children.index(self) 120 if index > 0: 121 return parent.children[index-1] 122 return None
123
124 - def get_node_by_id(self, nid):
125 """ 126 return node in whole hierarchy that has given id 127 """ 128 root = self.root() 129 try: 130 return root.get_child_by_id(nid, 1) 131 except NodeNotFound : 132 raise NodeNotFound(EX_NODE_NOT_FOUND % nid)
133
134 - def get_child_by_id(self, nid, recurse=None):
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
150 - def get_child_by_path(self, path):
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
165 - def depth(self):
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
174 - def depth_down(self):
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
182 - def width(self):
183 """ 184 return the width of the tree from this node 185 """ 186 return len(self.leaves())
187
188 - def root(self):
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
196 - def leaves(self):
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
208 - def flatten(self, _list=None):
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
219 - def lineage(self):
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
234 -class BinaryNode(VNode):
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
244 - def remove(self, child):
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
250 - def get_parts(self):
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
264 -class ListNode(VNode, list_class):
265 """Used to manipulate Nodes as Lists 266 """
267 - def __init__(self):
268 list_class.__init__(self) 269 VNode.__init__(self) 270 self.children = self
271
272 - def __str__(self, indent=0):
273 return '%s%s %s' % (indent*' ', self.__class__.__name__, 274 ', '.join([str(v) for v in self]))
275
276 - def append(self, child):
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
286 - def remove(self, child):
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
296 - def __iter__(self):
297 return list_class.__iter__(self)
298 299 # construct list from tree #################################################### 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
329 -def pre_order_list(node, filter_func=no_filter):
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):
362 FilteredIterator.__init__(self, node, post_order_list, filter_func)
363
364 -class PrefixedDepthFirstIterator(FilteredIterator):
365 """a prefixed depth first iterator, designed to be used with visitors 366 """
367 - def __init__(self, node, filter_func=None):
368 FilteredIterator.__init__(self, node, pre_order_list, filter_func)
369