Package logilab :: Package common :: Module tree

[frames] | no frames]

# Source Code for Module logilab.common.tree

      1  # copyright 2003-2011 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