diff options
author | root <devnull@localhost> | 2006-04-26 10:48:09 +0000 |
---|---|---|
committer | root <devnull@localhost> | 2006-04-26 10:48:09 +0000 |
commit | 8b1e1c104bdff504b3e775b450432e6462b8d09b (patch) | |
tree | 0367359f6a18f318741f387d82dc3dcfd8139950 /tree.py | |
download | logilab-common-8b1e1c104bdff504b3e775b450432e6462b8d09b.tar.gz |
forget the past.
forget the past.
Diffstat (limited to 'tree.py')
-rw-r--r-- | tree.py | 350 |
1 files changed, 350 insertions, 0 deletions
@@ -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) + |