1 | |
---|
2 | import string |
---|
3 | import exceptions |
---|
4 | import types |
---|
5 | |
---|
6 | |
---|
7 | class TreeNode: |
---|
8 | """class TreeNode |
---|
9 | |
---|
10 | Base class for nodes in a tree-like structure. |
---|
11 | Public Methods: |
---|
12 | GetChildren() |
---|
13 | GetParent() |
---|
14 | AddChild(child) |
---|
15 | GetLeaves() |
---|
16 | DeleteChild(child) |
---|
17 | Prune(children) |
---|
18 | Show() |
---|
19 | """ |
---|
20 | |
---|
21 | |
---|
22 | def __init__(self,name=None): |
---|
23 | self.children = None |
---|
24 | self.parent = None |
---|
25 | |
---|
26 | # Subclasses can implement these attributes as functions, called |
---|
27 | # when a node (either leaf or internal) is deleted |
---|
28 | |
---|
29 | # FIXME (Ole): The hasattr statements below were commented out on 12 July 2009 by Ole Nielsen due to |
---|
30 | # errors appearing when using Python2.6. Tests pass, so I think this was just superfluous anyway. |
---|
31 | # |
---|
32 | # Excerpt from What's New in Python 2.6 |
---|
33 | # |
---|
34 | #The hasattr() function was catching and ignoring all errors, |
---|
35 | #under the assumption that they meant a __getattr__() method |
---|
36 | #was failing somehow and the return value of hasattr() would |
---|
37 | #therefore be False. This logic shouldn't be applied to |
---|
38 | #KeyboardInterrupt and SystemExit, however; Python 2.6 will no |
---|
39 | #longer discard such exceptions when hasattr() encounters |
---|
40 | #them. (Fixed by Benjamin Peterson; issue 2196.) |
---|
41 | |
---|
42 | #if not hasattr(self,'ClearLeafNode'): |
---|
43 | # self.ClearLeafNode = None |
---|
44 | #if not hasattr(self,'ClearInternalNode'): |
---|
45 | # self.ClearInternalNode = None |
---|
46 | |
---|
47 | # # When not already set by derived class, set unique instance name |
---|
48 | #if not hasattr(self,'name'): |
---|
49 | # if name: |
---|
50 | # self.name = name |
---|
51 | # else: |
---|
52 | # self.name = id(self) |
---|
53 | |
---|
54 | # When not already set by derived class, set unique instance name |
---|
55 | if name: |
---|
56 | self.name = name |
---|
57 | else: |
---|
58 | self.name = id(self) |
---|
59 | |
---|
60 | |
---|
61 | |
---|
62 | |
---|
63 | # Make treenode elements appear as sequences such that one |
---|
64 | # can iterate over them |
---|
65 | def __iter__(self): |
---|
66 | self.index = -1 # incremented on first call to next() |
---|
67 | return self |
---|
68 | |
---|
69 | def next(self): |
---|
70 | try: |
---|
71 | self.index += 1 |
---|
72 | return self.children[self.index] |
---|
73 | except IndexError: |
---|
74 | self.index = -1 |
---|
75 | raise StopIteration |
---|
76 | |
---|
77 | |
---|
78 | |
---|
79 | #---- public methods ------------------------------------ |
---|
80 | |
---|
81 | def GetChildren(self): |
---|
82 | return self.children |
---|
83 | |
---|
84 | |
---|
85 | def GetParent(self): |
---|
86 | return self.parent |
---|
87 | |
---|
88 | |
---|
89 | def AddChild(self,child): |
---|
90 | child.parent = self |
---|
91 | if hasattr(self,'storage'): |
---|
92 | child.storage = self.storage |
---|
93 | if self.children is None: |
---|
94 | self.children = [] |
---|
95 | self.children.append(child) |
---|
96 | |
---|
97 | |
---|
98 | def DeleteChild(self,child): |
---|
99 | try: |
---|
100 | index = self.children.index(child) |
---|
101 | child.Prune() |
---|
102 | del self.children[index] |
---|
103 | if self.children == []: |
---|
104 | self.children = None |
---|
105 | except ValueError: |
---|
106 | raise TreeNodeError |
---|
107 | |
---|
108 | |
---|
109 | def Prune(self): |
---|
110 | if self.children is None: # Leaf node |
---|
111 | if callable(self.clear_leaf_node): |
---|
112 | self.clear_leaf_node() |
---|
113 | else: |
---|
114 | msg = 'Node must have a method named "clear_leaf_node"' |
---|
115 | raise msg |
---|
116 | else: |
---|
117 | if callable(self.clear_internal_node): # Internal node |
---|
118 | self.clear_internal_node() |
---|
119 | else: |
---|
120 | msg = 'Node must have a method named "clear_internal_node"' |
---|
121 | raise msg |
---|
122 | |
---|
123 | for child in self.children: |
---|
124 | child.Prune() |
---|
125 | self.children = None |
---|
126 | |
---|
127 | |
---|
128 | #FIXME: I think this one is redundant and should could be removed (OMN) |
---|
129 | # Really? Where is the equivalent method? (DEE) |
---|
130 | # OK - I reliased that we can use it for testing and statistics (OMN) |
---|
131 | def GetLeaves(self): |
---|
132 | if self.children is None: |
---|
133 | myleaves = [self] |
---|
134 | else: |
---|
135 | myleaves = [] |
---|
136 | for child in self.children: |
---|
137 | myleaves += child.GetLeaves() |
---|
138 | |
---|
139 | return myleaves |
---|
140 | |
---|
141 | |
---|
142 | def CountLeaves(self): |
---|
143 | if self.children is None: |
---|
144 | count = 1 |
---|
145 | else: |
---|
146 | count = 0 |
---|
147 | for child in self.children: |
---|
148 | count += child.CountLeaves() |
---|
149 | |
---|
150 | return count |
---|
151 | |
---|
152 | |
---|
153 | def Show(self,depth=0): |
---|
154 | """Traverse tree and print node names. |
---|
155 | """ |
---|
156 | print "%s%s" % (' '*depth, self.name) |
---|
157 | if self.children: |
---|
158 | for child in self.children: |
---|
159 | child.Show(depth+1) |
---|
160 | else: |
---|
161 | print ': %d' %self.Count() |
---|
162 | |
---|
163 | |
---|
164 | #---------------------------------------------------------------- |
---|
165 | class TreeNodeError(exceptions.Exception): |
---|
166 | pass |
---|
167 | |
---|