Entry

Multi-node tree

Jul 5th, 2000 10:01
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 217, Python Snippet Support Team

"""
Packages: new_datatypes.trees
"""
""" multitree.py
    Defines a tree class. With this tree it's easy to add, change and delete
    multiple elements per node. A node consists of a title (a string) and a
    list, which can be manipulated at will. Printing and foreach-functions
    are available.
    23 Dec 98   Creation.
    25 Dec 98   Added _printtree, elements, nodes.
"""
def _printtree(node, prefix=""):
    """ Helper print routine, called by MultiTreeNode.printtree(). """
    if prefix == "": print "|"
    for i in range(len(node.list)):
        if isinstance(node.list[i], MultiTreeNode):
            if i == len(node.list)-1:
                newprefix = prefix + "     "
            else:
                newprefix = prefix + "|    "
            print "%s+--- %s" % (prefix, str(node.list[i].title))
            if node.list[i].list != []:
                # we don't want a dangling |
                print "%s|" % (newprefix)
                _printtree(node.list[i], newprefix)
            print "%s" % (newprefix)
        else:
            print "%s+--- %s" % (prefix, str(node.list[i]))
class MultiTreeNode:
    class __TreePrintOptions:
        foo = 1
        bar = 2
        # I'll implement this later... maybe... :) User should be able to
        # provide his own print options.
    def __init__(self, title="<>", list=[]):
        self.title = title
        self.list = list
        self.printoptions = self.__class__.__TreePrintOptions()
    def __getitem__(self, index):
        return self.list[index]
    def __setitem__(self, index, value):
        self.list[index] = value
    def __repr__(self):
        str = "MultiTreeNode %s %s" % (self.title, self.list)
        return str
    def printtree(self):
        _printtree(self)
    def foreach(self, f):
        """ Do something with each element in the tree. f is a function that
            takes an element, does something with it, and returns a new value.
        """
        for i in range(len(self.list)):
            if isinstance(self.list[i], MultiTreeNode):
                self.list[i].foreach(f)
            else:
                # do something
                self.list[i] = f(self.list[i])
    def foreachnode(self, f):
        """ Do something with each *Node* we encounter. f is a different
            function than the f in foreach... this one should not return
            anything, rather it should do something with the node. 
        """
        for i in range(len(self.list)):
            if isinstance(self.list[i], MultiTreeNode):
                f(self.list[i])
                self.list[i].foreachnode(f)
            else:
                pass
    def elements(self):
        """ Returns the number of elements, *not* counting nodes. """
        global counter
        counter = 0
        def count(elem):
            global counter
            counter = counter + 1
        self.foreach(count)
        return counter
    def nodes(self):
        """ Returns the number of nodes. Does not count itself. """
        global counter
        counter = 0
        def count(node):
            global counter
            counter = counter + 1
        self.foreachnode(count)
        return counter            
MultiTree = MultiTreeNode   # alias
if __name__ == "__main__":
    MN = MultiTreeNode
    animals = MN("Animals", [
        MN("Mammals", [
            MN("Carnivores", [
                MN("Canines", ["Dog", "Wolf", "Jackal", "Fox"]),
                MN("Felines", ["Lion", "Tiger", "Leopard"]),
            ]),
            MN("Herbivores", ["Sheep", "Goat"]),
        ]),
        MN("Birds", []),
        MN("Reptiles", []),
        MN("Insects", []),
        MN("Amphibians", []),
        MN("Fish", ["Shrimp", "Goldfish", "Shark"]),
    ])
    def _test1():
        print animals[0]    # print Mammals
        animals.printtree()
    def _test2():
        def f(elem):
            return elem + " sucks!"
        print "for‘ach:"
        animals.foreach(f)
        print animals
    def _test3():
        def g(node):
            node.title = node.title + " suck donkey!"
        print "foreachnode:"
        animals.foreachnode(g)
        print animals
    # put test here...
    # _test1()
    print animals.elements(), animals.nodes()