Initial revision
[blender.git] / intern / python / modules / util / tree.py
1 # Basisklasse fuer Baumstruktur
2 # Object-orientiertes Programmieren Wi/97
3 #
4 # (c) Martin Strubel, Fakultaet fuer Physik, Universitaet Konstanz
5 # (strubi@gandalf.physik.uni-konstanz.de)
6
7 # updated 08.2001
8
9 """Simple binary tree module
10
11         This module demonstrates a binary tree class.
12
13         Example::
14
15                 a = [5, 8, 8, 3, 7, 9]
16                 t1 = Tree()
17                 t1.fromList(a)
18
19         Operations on tree nodes are done by writing a simple operator class::
20                 
21                 class myOp:
22                         def __init__(self):
23                                 ...
24                         def operate(self, node):
25                                 do_something(node)
26
27         and calling the recursive application::
28
29                 op = MyOp()
30                 t1.recurse(op)
31
32         Objects inserted into the tree can be of any kind, as long as they define a
33         comparison operation.
34 """     
35
36 def recurse(node, do):
37         if node == None:
38                 return
39         recurse(node.left, do)
40         do(node)
41         recurse(node.right, do)
42
43 class Nullnode:
44         def __init__(self):
45                 self.left = None
46                 self.right = None
47                 self.depth = 0
48
49         def recurse(self, do):
50                 if self == Nil:
51                         return
52                 self.left.recurse(do)
53                 do(self)
54                 self.right.recurse(do)
55
56 Nil = Nullnode()
57
58 def nothing(x):
59         return x
60                         
61 class Node(Nullnode):
62         def __init__(self, data = None):
63                 self.left = Nil
64                 self.right = Nil
65                 self.data = data
66                 self.depth = 0
67
68         def __repr__(self):
69                 return "Node: %s" % self.data
70                 
71         def insert(self, node):
72                 if node.data < self.data:
73                         if self.left != Nil: 
74                                 return self.left.insert(node)
75                         else:
76                                 node.depth = self.depth + 1
77                                 self.left = node
78                         #       print "inserted left"
79                                 return self
80
81                 elif node.data > self.data:
82                         if self.right != Nil:
83                                 return self.right.insert(node)
84                         else:
85                                 node.depth = self.depth + 1
86                                 self.right = node
87                         #       print "inserted right"
88                                 return self
89                 else: 
90                         return self.insert_equal(node)
91
92         def find(self, node, do = nothing):
93                 if node.data < self.data:
94                         if self.left != Nil: 
95                                 return self.left.find(node, do)
96                         else:
97                                 return self
98                 elif node.data > self.data:
99                         if self.right != Nil:
100                                 return self.right.find(node, do)
101                         else:
102                                 return self
103                 else: 
104                         return do(self)
105
106         def remove(self, node):
107                 newpar 
108                 return self     
109         def insert_equal(self, node):
110                 #print "insert:",
111                 self.equal(node)
112                 return self
113         def found_equal(self, node):
114                 self.equal(node)
115         def equal(self, node):
116                 # handle special
117                 print "node (%s) is equal self (%s)" % (node, self)
118         def copy(self):
119                 n = Node(self.data)
120                 return n
121
122         def recursecopy(self):
123                 n = Node()
124                 n.data = self.data
125                 n.flag = self.flag
126                 if self.left != Nil:
127                         n.left = self.left.recursecopy()
128                 if self.right != Nil:
129                         n.right = self.right.recursecopy()
130
131                 return n
132
133 class NodeOp:
134         def __init__(self):
135                 self.list = []
136         def copy(self, node):
137                 self.list.append(node.data)
138
139 class Tree:
140         def __init__(self, root = None):
141                 self.root = root
142                 self.n = 0
143         def __radd__(self, other):
144                 print other
145                 t = self.copy()
146                 t.merge(other)
147                 return t
148         def __repr__(self):
149                 return "Tree with %d elements" % self.n
150         def insert(self, node):
151                 if self.root == None:
152                         self.root = node
153                 else:
154                         self.root.insert(node)
155                 self.n += 1     
156         def recurse(self, do):
157                 if self.root == None:
158                         return
159                 self.root.recurse(do)
160         def find(self, node):
161                 return self.root.find(node)
162         def remove(self, node):
163                 self.root.remove(node)
164         def copy(self):
165                 "make true copy of self"
166                 t = newTree()
167                 c = NodeOp()
168                 self.recurse(c.copy)
169                 t.fromList(c.list)
170                 return t
171         def asList(self):
172                 c = NodeOp()
173                 self.recurse(c.copy)
174                 return c.list
175         def fromList(self, list):
176                 for item in list:
177                         n = Node(item)
178                         self.insert(n)
179         def insertcopy(self, node):
180                 n = node.copy()
181                 self.insert(n)
182         def merge(self, other):
183                 other.recurse(self.insertcopy)
184 # EXAMPLE:
185
186 newTree = Tree
187
188 def printnode(x):
189         print "Element: %s, depth: %s" % (x, x.depth)
190
191 def test():
192         a = [5, 8, 8, 3, 7, 9]
193         t1 = Tree()
194         t1.fromList(a)
195
196         b = [12, 4, 56, 7, 34]
197         t2 = Tree()
198         t2.fromList(b)
199
200         print "tree1:"
201         print t1.asList()
202         print "tree2:"
203         print t2.asList()
204         print '-----'
205         print "Trees can be added:"
206
207         
208         t3 = t1 + t2
209         print t3.asList()
210         print "..or alternatively merged:"
211         t1.merge(t2)
212         print t1.asList()
213
214 if __name__ == '__main__':
215         test()