1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
"""
:copyright: Copyright since 2006 by Oliver Schoenborn, all rights reserved.
:license: BSD, see LICENSE_BSD_Simple.txt for details.
"""
class TopicTreeTraverser:
"""
Supports taking action on every topic in the topic tree. The traverse() method
traverses a topic tree and calls visitor._onTopic() for each topic in the tree
that satisfies visitor._accept(). Additionally it calls visitor._startChildren()
whenever it starts traversing the subtopics of a topic, and
visitor._endChildren() when it is done with the subtopics. Finally, it calls
visitor._doneTraversal() when traversal has been completed. The visitor must
therefore adhere to the ITopicTreeVisitor interface.
"""
DEPTH = 'Depth first through topic tree'
BREADTH = 'Breadth first through topic tree'
MAP = 'Sequential through topic manager\'s topics map'
def __init__(self, visitor = None):
"""The visitor, if given, must adhere to API of
ITopicTreeVisitor. The visitor can be changed or
set via setVisitor(visitor) before calling traverse()."""
self.__handler = visitor
def setVisitor(self, visitor):
"""The visitor must adhere to API of ITopicTreeVisitor. """
self.__handler = visitor
def traverse(self, topicObj, how=DEPTH, onlyFiltered=True):
"""Start traversing tree at topicObj. Note that topicObj is a
Topic object, not a topic name. The how defines if tree should
be traversed breadth or depth first. If onlyFiltered is
False, then all nodes are accepted (_accept(node) not called).
This method can be called multiple times.
"""
if how == self.MAP:
raise NotImplementedError('not yet available')
self.__handler._startTraversal()
if how == self.BREADTH:
self.__traverseBreadth(topicObj, onlyFiltered)
else:
assert how == self.DEPTH
self.__traverseDepth(topicObj, onlyFiltered)
self.__handler._doneTraversal()
def __traverseBreadth(self, topicObj, onlyFiltered):
visitor = self.__handler
def extendQueue(subtopics):
topics.append(visitor._startChildren)
topics.extend(subtopics)
topics.append(visitor._endChildren)
topics = [topicObj]
while topics:
topicObj = topics.pop(0)
if topicObj in (visitor._startChildren, visitor._endChildren):
topicObj()
continue
if onlyFiltered:
if visitor._accept(topicObj):
extendQueue( topicObj.getSubtopics() )
visitor._onTopic(topicObj)
else:
extendQueue( topicObj.getSubtopics() )
visitor._onTopic(topicObj)
def __traverseDepth(self, topicObj, onlyFiltered):
visitor = self.__handler
def extendStack(topicTreeStack, subtopics):
topicTreeStack.insert(0, visitor._endChildren) # marker functor
# put subtopics in list in alphabetical order
subtopicsTmp = subtopics
subtopicsTmp.sort(reverse=True, key=topicObj.__class__.getName)
for sub in subtopicsTmp:
topicTreeStack.insert(0, sub) # this puts them in reverse order
topicTreeStack.insert(0, visitor._startChildren) # marker functor
topics = [topicObj]
while topics:
topicObj = topics.pop(0)
if topicObj in (visitor._startChildren, visitor._endChildren):
topicObj()
continue
if onlyFiltered:
if visitor._accept(topicObj):
extendStack( topics, topicObj.getSubtopics() )
visitor._onTopic(topicObj)
else:
extendStack( topics, topicObj.getSubtopics() )
visitor._onTopic(topicObj)
class ITopicTreeVisitor:
"""
Derive from ITopicTreeVisitor and override one or more of the
self._*() methods. Give an instance to an instance of
TopicTreeTraverser.
"""
def _accept(self, topicObj):
"""Override this to filter nodes of topic tree. Must return
True (accept node) of False (reject node). Note that rejected
nodes cause traversal to move to next branch (no children
traversed)."""
return True
def _startTraversal(self):
"""Override this to define what to do when traversal() starts."""
pass
def _onTopic(self, topicObj):
"""Override this to define what to do for each node."""
pass
def _startChildren(self):
"""Override this to take special action whenever a
new level of the topic hierarchy is started (e.g., indent
some output). """
pass
def _endChildren(self):
"""Override this to take special action whenever a
level of the topic hierarchy is completed (e.g., dedent
some output). """
pass
def _doneTraversal(self):
"""Override this to take special action when traversal done."""
pass
|
