#
# Tree implementation for Python >= 2.3
#
""" General Tree class for trees of n-th order"""

class TreeNodeException (Exception):
    def __init__(self, node, msg):
        self.node = node
        self.value = msg

    def __str__(self):
        return repr(self.value)

class TreeNode:
    def __init__ (self, data):
        # data carried by the node
        self.data = data
        # child node list
        self.children = []

class Tree:
    def __init__ (self):
        # root node
        self.root = None
        # node count of the tree
        self.count = 0

    def insert_node (self, parent, node):
        if self.root == None:
            self.root = node
            self.count += 1
            return
        if parent == None:
            parent = self.root
        parent.children.append (node)
        self.count += 1
        return

    def delete_node (self, parent, node):
        # deletion of nodes is only possible, if they have no children
        # anything else has to be implemented somewhere!
        if node is parent:
            if len (parent.children) > 0:
                raise TreeNodeException (node, "Node has children")
            if parent is self.root:
                self.root = None
                return

        if node not in parent:
            raise TreeNodeException (node, "Node not found in parent")

        parent.children.delete (node)
        return

    def search_node (self, parent, node):
        if parent == None:
            parent = self.root

        if parent is node:
            return parent

        if len(parent.children) <= 0:
            return None
        
        for item in parent.children:
            item = self.search_node (item, node)
            if item != None:
                return item
        return None
        
    def print_tree (self, node, indentation):
        output = indentation * "  "

        if len (node.children) > 0:
            output += node.data + " ("
        else:
            output += node.data
        print output
        for child in node.children:
            self.print_tree (child, indentation + 1)
        if len (node.children) > 0:
            print indentation * "  " + ")"

# test section starts here

def __test_tree ():
    tree = Tree ()
    tree.insert_node (None, TreeNode ("root node here"))
    tree.insert_node (None, TreeNode ("this"))
    tree.insert_node (None, TreeNode ("is"))
    nd = TreeNode ("a")
    tree.insert_node (None, nd)
    tree.insert_node (nd, TreeNode ("tree"))
    search = TreeNode ("node")
    tree.insert_node (nd, search)

    tree.insert_node (None, TreeNode ("test"))

    tree.print_tree (tree.root, 0)
    #print "======================================"
    #print tree.search_node (None, nd)
    #tree.print_sub_tree (tree.search_node (None, nd))
    return

if __name__ == '__main__':
    __test_tree ()