forget the past.

forget the past.

1 files changed, 350 insertions, 0 deletions

diff --git a/tree.py b/tree.py
new file mode 100644
index 0000000..00be29a
--- /dev/null
+++ b/tree.py
@@ -0,0 +1,350 @@
+# Copyright (c) 2000-2003 LOGILAB S.A. (Paris, FRANCE).
+# http://www.logilab.fr/ -- mailto:contact@logilab.fr
+#
+# This program is free software; you can redistribute it and/or modify it under
+# the terms of the GNU General Public License as published by the Free Software
+# Foundation; either version 2 of the License, or (at your option) any later
+# version.
+#
+# This program is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License along with
+# this program; if not, write to the Free Software Foundation, Inc.,
+# 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+"""
+ base class to represent tree structure
+"""
+
+__revision__ = "$Id: tree.py,v 1.24 2006-02-24 10:40:21 nico Exp $"
+
+import sys
+from warnings import warn
+
+from logilab.common import deprecated_function
+from logilab.common.visitor import VisitedMixIn, FilteredIterator, no_filter
+
+## Exceptions #################################################################
+
+class NodeNotFound(Exception):
+    """raised when a node has not been found"""
+
+EX_SIBLING_NOT_FOUND = "No such sibling as '%s'"
+EX_CHILD_NOT_FOUND = "No such child as '%s'"
+EX_NODE_NOT_FOUND = "No such node as '%s'"
+
+
+# Base node ###################################################################
+
+class Node :
+    """a basic tree node, caracterised by an id"""
+
+    def __init__(self, nid=None) :
+        self.id = nid
+        # navigation
+        self.parent = None
+        self.children = []
+
+    def __str__(self, indent=0):
+        s = ['%s%s %s' % (' '*indent, self.__class__.__name__, self.id)]
+        indent += 2
+        for child in self.children:
+            try:
+                s.append(child.__str__(indent))
+            except TypeError:
+                s.append(child.__str__())
+        return '\n'.join(s)
+
+
+    def is_leaf(self):
+        return not self.children
+    
+    def append(self, child):
+        """add a node to children"""
+        self.children.append(child)
+        child.parent = self
+
+    def remove(self, child):
+        """remove a child node"""
+        self.children.remove(child)
+        child.parent = None
+
+    def insert(self, index, child):
+        """insert a child node"""
+        self.children.insert(index, child)
+        child.parent = self
+        
+    def replace(self, old_child, new_child):
+        """replace a child node with another"""
+        i = self.children.index(old_child)
+        self.children.pop(i)
+        self.children.insert(i, new_child)
+        new_child.parent = self
+
+    def get_sibling(self, nid):
+        """return the sibling node that has given id"""
+        try:
+            return self.parent.get_child_by_id(nid)
+        except NodeNotFound :
+            raise NodeNotFound(EX_SIBLING_NOT_FOUND % nid)
+
+    def next_sibling(self):
+        """
+        return the next sibling for this node if any
+        """
+        parent = self.parent
+        if parent is None:
+            # root node has no sibling
+            return None
+        index = parent.children.index(self)
+        try:
+            return parent.children[index+1]
+        except IndexError:
+            return None
+        
+    def previous_sibling(self):
+        """
+        return the previous sibling for this node if any
+        """
+        parent = self.parent
+        if parent is None:
+            # root node has no sibling
+            return None
+        index = parent.children.index(self)
+        if index > 0:
+            return parent.children[index-1]
+        return None
+
+    def get_node_by_id(self, nid):
+        """
+        return node in whole hierarchy that has given id
+        """
+        root = self.root()
+        try:
+            return root.get_child_by_id(nid, 1)
+        except NodeNotFound :
+            raise NodeNotFound(EX_NODE_NOT_FOUND % nid)
+        
+    def get_child_by_id(self, nid, recurse=None):
+        """
+        return child of given id
+        """
+        if self.id == nid:
+            return self
+        for c in self.children :
+            if recurse:
+                try:
+                    return c.get_child_by_id(nid, 1)
+                except NodeNotFound :
+                    continue
+            if c.id == nid :
+                return c
+        raise NodeNotFound(EX_CHILD_NOT_FOUND % nid)
+
+    def get_child_by_path(self, path):
+        """
+        return child of given path (path is a list of ids)
+        """
+        if len(path) > 0 and path[0] == self.id:
+            if len(path) == 1 :
+                return self
+            else :
+                for c in self.children :
+                    try:
+                        return c.get_child_by_path(path[1:])
+                    except NodeNotFound :
+                        pass
+        raise NodeNotFound(EX_CHILD_NOT_FOUND % path)
+
+    def depth(self):
+        """
+        return depth of this node in the tree
+        """
+        if self.parent is not None:
+            return 1 + self.parent.depth()
+        else :
+            return 0
+
+    def root(self):
+        """
+        return the root node of the tree
+        """
+        if self.parent is not None:
+            return self.parent.root()
+        return self
+
+    def leaves(self):
+        """
+        return a list with all the leaves nodes descendant from this node
+        """
+        leaves = []
+        if self.children:
+            for child in self.children:
+                leaves += child.leaves()
+            return leaves
+        else:
+            return [self]
+
+    leafs = deprecated_function(leaves) # backward compatibility
+    
+    def flatten(self, _list=None):
+        """
+        return a list with all the nodes descendant from this node
+        """
+        if _list is None:
+            _list = []
+        _list.append(self)
+        for c in self.children:
+            c.flatten(_list)
+        return _list
+
+    def lineage(self):
+        """
+        return list of parents up to root node
+        """
+        lst = [self]
+        if self.parent is not None:
+            lst.extend(self.parent.lineage())
+        return lst
+    
+class VNode(Node, VisitedMixIn):
+    """a visitable node
+    """
+    pass
+
+            
+class BinaryNode(VNode):
+    """a binary node (ie only two children
+    """
+    def __init__(self, lhs=None, rhs=None) :
+        VNode.__init__(self)
+        if lhs is not None or rhs is not None:
+            assert lhs and rhs
+            self.append(lhs)
+            self.append(rhs)
+            
+    def remove(self, child):
+        """remove the child and replace this node with the other child
+        """
+        self.children.remove(child)
+        self.parent.replace(self, self.children[0])
+        
+    def get_parts(self):
+        """
+        return the left hand side and the right hand side of this node
+        """
+        return self.children[0], self.children[1]
+        
+
+
+if sys.version_info[0:2] >= (2, 2):
+    list_class = list
+else:
+    from UserList import UserList
+    list_class = UserList
+    
+class ListNode(VNode, list_class):
+    """Used to manipulate Nodes as Lists
+    """
+    def __init__(self):
+        list_class.__init__(self)
+        VNode.__init__(self)
+        self.children = self
+        
+    def __str__(self, indent=0):
+        return '%s%s %s' % (indent*' ', self.__class__.__name__,
+                            ', '.join([str(v) for v in self]))
+
+    def append(self, child):
+        """add a node to children"""
+        list_class.append(self, child)
+        child.parent = self
+ 
+    def insert(self, index, child):
+        """add a node to children"""
+        list_class.insert(self, index, child)
+        child.parent = self
+    
+    def remove(self, child):
+        """add a node to children"""
+        list_class.remove(self, child)
+        child.parent = None
+ 
+    def pop(self, index):
+        """add a node to children"""
+        child = list_class.pop(self, index)
+        child.parent = None
+        
+
+# construct list from tree ####################################################
+
+def post_order_list(node, filter_func=no_filter):
+    """ 
+    create a list with tree nodes for which the <filter> function returned true
+    in a post order foashion
+    """
+    l, stack = [], []
+    poped, index = 0, 0
+    while node:
+        if filter_func(node):
+            if node.children and not poped:
+                stack.append((node, index))
+                index = 0
+                node = node.children[0]
+            else:
+                l.append(node)
+                index += 1
+                try:
+                    node = stack[-1][0].children[index]
+                except IndexError:
+                    node = None
+        else:
+            node = None
+        poped = 0
+        if node is None and stack:
+            node, index = stack.pop()
+            poped = 1
+    return l
+
+def pre_order_list(node, filter_func=no_filter):
+    """ 
+    create a list with tree nodes for which the <filter> function returned true
+    in a pre order fashion
+    """
+    l, stack = [], []
+    poped, index = 0, 0
+    while node:
+        if filter_func(node):
+            if not poped:
+                l.append(node)
+            if node.children and not poped:
+                stack.append((node, index))
+                index = 0
+                node = node.children[0]
+            else:
+                index += 1
+                try:
+                    node = stack[-1][0].children[index]
+                except IndexError:
+                    node = None
+        else:
+            node = None
+        poped = 0
+        if node is None and len(stack) > 1:
+            node, index = stack.pop()
+            poped = 1
+    return l
+
+class PostfixedDepthFirstIterator(FilteredIterator):
+    """a postfixed depth first iterator, designed to be used with visitors
+    """
+    def __init__(self, node, filter_func=None):
+        FilteredIterator.__init__(self, node, post_order_list, filter_func)
+
+class PrefixedDepthFirstIterator(FilteredIterator):
+    """a pretfixed depth first iterator, designed to be used with visitors
+    """
+    def __init__(self, node, filter_func=None):
+        FilteredIterator.__init__(self, node, pre_order_list, filter_func)
+