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
|
'''
:copyright: Copyright 2006-2009 by Oliver Schoenborn, all rights reserved.
:license: BSD, see LICENSE.txt for details.
'''
class TopicTreeTraverser:
'''
Topic tree traverser. Provides the traverse() method
which traverses a topic tree and calls self._onTopic() for
each topic in the tree that satisfies self._accept().
Additionally it calls self._startChildren() whenever it
starts traversing the subtopics of a topic, and
self._endChildren() when it is done with the subtopics.
Finally, it calls self._doneTraversal() when traversal
has been completed.'''
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
pubsub.utils.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 pubsub.utils.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)
|
