source: branches/numpy/anuga/utilities/treenode.py @ 6415

Last change on this file since 6415 was 3566, checked in by ole, 18 years ago

Moved quad and friends to utilities

File size: 3.7 KB
Line 
1
2import string
3import exceptions
4import types
5
6
7class 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        if not hasattr(self,'ClearLeafNode'):
29            self.ClearLeafNode = None
30        if not hasattr(self,'ClearInternalNode'):
31            self.ClearInternalNode = None
32
33        # when not already set by derived class, set unique instance name
34        if not hasattr(self,"name"):
35            if name:
36                self.name = name
37            else:
38                self.name = id(self)
39
40
41    #Make treenode elements appear as sequences such thta on
42    #can iterate over them             
43    def __iter__(self):
44        self.index = -1   # incremented on first call to next()
45        return self
46
47    def next(self):
48        try:
49            self.index += 1
50            return self.children[self.index]
51        except IndexError:
52            self.index = -1
53            raise StopIteration
54
55
56
57    #---- public methods ------------------------------------
58
59    def GetChildren(self):
60        return self.children
61
62
63    def GetParent(self):
64        return self.parent
65
66
67    def AddChild(self,child):
68        child.parent = self
69        if hasattr(self,'storage'):
70            child.storage = self.storage
71        if self.children is None:
72            self.children = []
73        self.children.append(child)
74
75
76    def DeleteChild(self,child):
77        try:
78            index = self.children.index(child)
79            child.Prune()
80            del self.children[index]
81            if self.children == []:
82                self.children = None
83        except ValueError:
84            raise TreeNodeError
85
86
87    def Prune(self):
88        if self.children is None:                  # Leaf node
89            if callable(self.clear_leaf_node):
90                self.clear_leaf_node()
91            else:
92                msg = 'Node must have a method named "clear_leaf_node"' 
93                raise msg       
94        else:
95            if callable(self.clear_internal_node):   # Internal node
96                self.clear_internal_node()
97            else:
98                msg = 'Node must have a method named "clear_internal_node"' 
99                raise msg       
100                               
101            for child in self.children:
102                child.Prune()
103            self.children = None
104
105
106    #FIXME: I think this one is redundant and should could be removed (OMN)
107    # Really?  Where is the equivalent method? (DEE)
108    # OK - I reliased that we can use it for testing and statistics (OMN)
109    def GetLeaves(self):
110        if self.children is None:
111            myleaves = [self]
112        else:
113            myleaves = []
114            for child in self.children:
115                myleaves += child.GetLeaves()
116
117        return myleaves
118
119
120    def CountLeaves(self):
121        if self.children is None:
122            count = 1
123        else:
124            count = 0
125            for child in self.children:
126                count += child.CountLeaves()
127
128        return count
129
130
131    def Show(self,depth=0):
132        """Traverse tree and print node names.
133        """       
134        print "%s%s" % ('  '*depth, self.name)
135        if self.children:
136            for child in self.children:
137                child.Show(depth+1)
138        else:
139            print ': %d' %self.Count()
140
141         
142#----------------------------------------------------------------
143class TreeNodeError(exceptions.Exception):
144    pass
145 
Note: See TracBrowser for help on using the repository browser.