# definition of tree structures for fctree
# J. Templon NIKHEF, written May 2001 while at University of Georgia.
TINDENT = 5 # indentation (number of spaces) for nesting of text tree print
# Node: one node per subroutine, main routine, function, or block data
# name: string, name of routine
# children: list of Nodes, routines called by this routine.
class Node:
def __init__(self, nodename,shape=None):
self.name = nodename
self.children = None
self.shape = shape
# apply function to node and all children.
# exception: when during a traversal, it is found that a node is its own
# parent, the traversal does not follow to children. In this way
# infinite recursion is avoided.
def init_traverse(): # prepare for new tree traversal
for i in Lprocessed:
Lprocessed.remove(i)
for j in Lparent:
Lparent.remove(j)
def applyall(node, function):
function(node)
if node.name in Lparent : return # avoid infinite recursion
if not node.children : return # no children to process
Lparent.append(node.name) # push current node onto parent stack
for child in node.children: # process children
applyall(child, function)
junk = Lparent.pop() # pop current node off parent stack
def applyunique(node, function):
function(node)
if node.name in Lprocessed : return # never print subtree more than once
if not node.children : return # no children to process
Lprocessed.append(node.name)
Lparent.append(node.name) # push current node onto parent stack
for child in node.children: # process children
applyunique(child, function)
junk = Lparent.pop() # pop current node off parent stack
def tprint(node): # test: text print
spaces = 5*len(Lparent)*' ' # indentation
print spaces+node.name
class Formathandler: # holds functions for formatted
# traversal of tree
def __init__(self,
Fnode, # for node not yet encountered
Fref, # for already-encountered node
Fb4child, # for b4 application to each child
Fb4nextchild, # called between application to children
Fafterchild, # called after application to each child
Fafterchildren, # called after traversing all children
filename=None) :
self.node = Fnode
self.ref = Fref
self.b4child = Fb4child
self.b4nextchild = Fb4nextchild
self.afterchild = Fafterchild
self.afterchildren = Fafterchildren
if not filename :
self.of = sys.stdout
else:
self.of = open(filename,'w')
def fmt_applyunique(node, fmt):
if node.name in Lprocessed : # never print subtree more than once
fmt.ref(node,fmt)
return
fmt.node(node,fmt)
rfirst = 1
Lprocessed.append(node.name)
Lparent.append(node.name) # push current node onto parent stack
if node.children:
for child in node.children:
if rfirst == 0:
fmt.b4nextchild(fmt)
else:
rfirst = 0
fmt.b4child(child,fmt)
fmt_applyunique(child, fmt)
fmt.afterchild(fmt)
fmt.afterchildren(fmt)
junk = Lparent.pop() # pop current node off parent stack
Ltreenode = [ ] # list of Nodes at root of top-level trees
Dnode = { } # dict mapping names of Node onto Node
Dsubtree = { } # dict mapping keys cID onto subtree objects (list of Node)
# only contains top-level 'continuation trees'
# Node.children = Dsubtree[cID] works.
Lparent = [ ] # stack (implemented as list) keeping track of parents during
# list traversal, to avoid infinite recursion in case of
# cyclical references
Lprocessed = [ ] # list of nodes already processed in applyunique
# if applyunique traversal finds node in this list, its
# children will not be processed.