# copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
# contact http://www.logilab.fr/ -- mailto:contact@logilab.fr
#
# This file is part of logilab-common.
#
# logilab-common is free software: you can redistribute it and/or modify it under
# the terms of the GNU Lesser General Public License as published by the Free
# Software Foundation, either version 2.1 of the License, or (at your option) any
# later version.
#
# logilab-common 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 Lesser General Public License for more
# details.
#
# You should have received a copy of the GNU Lesser General Public License along
# with logilab-common. If not, see <http://www.gnu.org/licenses/>.
"""Base class to represent a tree structure.
"""
__docformat__ = "restructuredtext en"
import sys
from logilab.common.visitor import VisitedMixIn, FilteredIterator, no_filter
from typing import Optional, Any, List, Callable
# Exceptions #################################################################
[docs]class NodeNotFound(Exception):
"""raised when a node has not been found"""
EX_SIBLING_NOT_FOUND: str = "No such sibling as '%s'"
EX_CHILD_NOT_FOUND: str = "No such child as '%s'"
EX_NODE_NOT_FOUND: str = "No such node as '%s'"
# Base node ###################################################################
# describe node of current class
NodeType = Any
[docs]class Node:
"""a basic tree node, characterized by an id"""
def __init__(self, nid: Optional[str] = None) -> None:
self.id = nid
# navigation
# should be something like Optional[type(self)] for subclasses but that's not possible?
self.parent: Optional[NodeType] = None
# should be something like List[type(self)] for subclasses but that's not possible?
self.children: List[NodeType] = []
def __iter__(self):
return iter(self.children)
def __str__(self, indent=0):
s = [f"{' ' * 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)
[docs] def is_leaf(self):
return not self.children
[docs] def append(self, child: NodeType) -> None:
# should be child: type(self) but that's not possible
"""add a node to children"""
self.children.append(child)
child.parent = self
[docs] def remove(self, child: NodeType) -> None:
# should be child: type(self) but that's not possible
"""remove a child node"""
self.children.remove(child)
child.parent = None
[docs] def insert(self, index: int, child: NodeType) -> None:
# should be child: type(self) but that's not possible
"""insert a child node"""
self.children.insert(index, child)
child.parent = self
[docs] def replace(self, old_child: NodeType, new_child: NodeType) -> None:
"""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
[docs] def get_sibling(self, nid: str) -> NodeType:
"""return the sibling node that has given id"""
try:
assert self.parent is not None
return self.parent.get_child_by_id(nid)
except NodeNotFound:
raise NodeNotFound(EX_SIBLING_NOT_FOUND % nid)
[docs] 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
[docs] 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
[docs] def get_node_by_id(self, nid: str) -> NodeType:
"""
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)
[docs] def get_child_by_id(self, nid: str, recurse: Optional[bool] = None) -> NodeType:
"""
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)
[docs] def get_child_by_path(self, path: List[str]) -> NodeType:
"""
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)
[docs] def depth(self) -> int:
"""
return depth of this node in the tree
"""
if self.parent is not None:
return 1 + self.parent.depth()
else:
return 0
[docs] def depth_down(self) -> int:
"""
return depth of the tree from this node
"""
if self.children:
return 1 + max([c.depth_down() for c in self.children])
return 1
[docs] def width(self) -> int:
"""
return the width of the tree from this node
"""
return len(self.leaves())
[docs] def root(self) -> NodeType:
"""
return the root node of the tree
"""
if self.parent is not None:
return self.parent.root()
return self
[docs] def leaves(self) -> List[NodeType]:
"""
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]
[docs] def flatten(self, _list: Optional[List[NodeType]] = None) -> List[NodeType]:
"""
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
[docs] def lineage(self) -> List[NodeType]:
"""
return list of parents up to root node
"""
lst = [self]
if self.parent is not None:
lst.extend(self.parent.lineage())
return lst
[docs]class VNode(Node, VisitedMixIn):
# we should probably merge this VisitedMixIn here because it's only used here
"""a visitable node"""
[docs]class BinaryNode(VNode):
"""a binary node (i.e. 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)
[docs] 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])
[docs] 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
[docs]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]),
)
[docs] def append(self, child):
"""add a node to children"""
list_class.append(self, child)
child.parent = self
[docs] def insert(self, index, child):
"""add a node to children"""
list_class.insert(self, index, child)
child.parent = self
[docs] def remove(self, child):
"""add a node to children"""
list_class.remove(self, child)
child.parent = None
[docs] def pop(self, index):
"""add a node to children"""
child = list_class.pop(self, index)
child.parent = None
def __iter__(self):
return list_class.__iter__(self)
# construct list from tree ####################################################
[docs]def post_order_list(node: Optional[Node], filter_func: Callable = no_filter) -> List[Node]:
"""
create a list with tree nodes for which the <filter> function returned true
in a post order fashion
"""
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
[docs]def pre_order_list(node: Optional[Node], filter_func: Callable = no_filter) -> List[Node]:
"""
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
[docs]class PostfixedDepthFirstIterator(FilteredIterator):
"""a postfixed depth first iterator, designed to be used with visitors"""
def __init__(self, node: Node, filter_func: Optional[Any] = None) -> None:
FilteredIterator.__init__(self, node, post_order_list, filter_func)
[docs]class PrefixedDepthFirstIterator(FilteredIterator):
"""a prefixed depth first iterator, designed to be used with visitors"""
def __init__(self, node: Node, filter_func: Optional[Any] = None) -> None:
FilteredIterator.__init__(self, node, pre_order_list, filter_func)