diff options
Diffstat (limited to 'intern/python/modules/util/tree.py')
-rw-r--r-- | intern/python/modules/util/tree.py | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/intern/python/modules/util/tree.py b/intern/python/modules/util/tree.py new file mode 100644 index 00000000000..313159239c6 --- /dev/null +++ b/intern/python/modules/util/tree.py @@ -0,0 +1,215 @@ +# Basisklasse fuer Baumstruktur +# Object-orientiertes Programmieren Wi/97 +# +# (c) Martin Strubel, Fakultaet fuer Physik, Universitaet Konstanz +# (strubi@gandalf.physik.uni-konstanz.de) + +# updated 08.2001 + +"""Simple binary tree module + + This module demonstrates a binary tree class. + + Example:: + + a = [5, 8, 8, 3, 7, 9] + t1 = Tree() + t1.fromList(a) + + Operations on tree nodes are done by writing a simple operator class:: + + class myOp: + def __init__(self): + ... + def operate(self, node): + do_something(node) + + and calling the recursive application:: + + op = MyOp() + t1.recurse(op) + + Objects inserted into the tree can be of any kind, as long as they define a + comparison operation. +""" + +def recurse(node, do): + if node == None: + return + recurse(node.left, do) + do(node) + recurse(node.right, do) + +class Nullnode: + def __init__(self): + self.left = None + self.right = None + self.depth = 0 + + def recurse(self, do): + if self == Nil: + return + self.left.recurse(do) + do(self) + self.right.recurse(do) + +Nil = Nullnode() + +def nothing(x): + return x + +class Node(Nullnode): + def __init__(self, data = None): + self.left = Nil + self.right = Nil + self.data = data + self.depth = 0 + + def __repr__(self): + return "Node: %s" % self.data + + def insert(self, node): + if node.data < self.data: + if self.left != Nil: + return self.left.insert(node) + else: + node.depth = self.depth + 1 + self.left = node + # print "inserted left" + return self + + elif node.data > self.data: + if self.right != Nil: + return self.right.insert(node) + else: + node.depth = self.depth + 1 + self.right = node + # print "inserted right" + return self + else: + return self.insert_equal(node) + + def find(self, node, do = nothing): + if node.data < self.data: + if self.left != Nil: + return self.left.find(node, do) + else: + return self + elif node.data > self.data: + if self.right != Nil: + return self.right.find(node, do) + else: + return self + else: + return do(self) + + def remove(self, node): + newpar + return self + def insert_equal(self, node): + #print "insert:", + self.equal(node) + return self + def found_equal(self, node): + self.equal(node) + def equal(self, node): + # handle special + print "node (%s) is equal self (%s)" % (node, self) + def copy(self): + n = Node(self.data) + return n + + def recursecopy(self): + n = Node() + n.data = self.data + n.flag = self.flag + if self.left != Nil: + n.left = self.left.recursecopy() + if self.right != Nil: + n.right = self.right.recursecopy() + + return n + +class NodeOp: + def __init__(self): + self.list = [] + def copy(self, node): + self.list.append(node.data) + +class Tree: + def __init__(self, root = None): + self.root = root + self.n = 0 + def __radd__(self, other): + print other + t = self.copy() + t.merge(other) + return t + def __repr__(self): + return "Tree with %d elements" % self.n + def insert(self, node): + if self.root == None: + self.root = node + else: + self.root.insert(node) + self.n += 1 + def recurse(self, do): + if self.root == None: + return + self.root.recurse(do) + def find(self, node): + return self.root.find(node) + def remove(self, node): + self.root.remove(node) + def copy(self): + "make true copy of self" + t = newTree() + c = NodeOp() + self.recurse(c.copy) + t.fromList(c.list) + return t + def asList(self): + c = NodeOp() + self.recurse(c.copy) + return c.list + def fromList(self, list): + for item in list: + n = Node(item) + self.insert(n) + def insertcopy(self, node): + n = node.copy() + self.insert(n) + def merge(self, other): + other.recurse(self.insertcopy) +# EXAMPLE: + +newTree = Tree + +def printnode(x): + print "Element: %s, depth: %s" % (x, x.depth) + +def test(): + a = [5, 8, 8, 3, 7, 9] + t1 = Tree() + t1.fromList(a) + + b = [12, 4, 56, 7, 34] + t2 = Tree() + t2.fromList(b) + + print "tree1:" + print t1.asList() + print "tree2:" + print t2.asList() + print '-----' + print "Trees can be added:" + + + t3 = t1 + t2 + print t3.asList() + print "..or alternatively merged:" + t1.merge(t2) + print t1.asList() + +if __name__ == '__main__': + test() |