# 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.