#!/usr/bin/python

import subprocess

class Node:
    # Class used to represent binary trees
    
    def __init__(self, data):
        self.right = None
        self.left  = None
        self.data  = data
        self.label = 0

    def __repr__(self):
        return self.data

    # labels the current node and all his children. In order to work
    # properly it must be called with an initial value of occ =
    # {}. The labelling assigns to each node a number, such that the
    # combination self.data + self.label is unique throughout the
    # whole tree.
    def labelNodes(self, occ):
        if not self.data in occ:
            occ[self.data] = 0

        self.label = occ[self.data]
        occ[self.data] += 1

        if self.left:
            self.left.labelNodes(occ)
            
        if self.right:
            self.right.labelNodes(occ)
            
    # return the string representation of the node u and all of its
    # children
    def printNodes(self):
        if self.left is None and self.right is None:
            return self.data
        elif self.left is None:
            return self.data + "(" + "()" + self.right.printNodes() + ")"
        elif self.right is None:
            return self.data + "(" + self.left.printNodes() + "()" + ")"            
        else:
            return self.data + "(" + self.left.printNodes() + self.right.printNodes() + ")"

    # dotfile representation of node's content and node's children
    # content.    
    def writeNodeDotfile(self, f):
        node_id = self.data + str(self.label)
        f.write("\"" + node_id + "\"" + " [label=" + "\"" + self.data + "\"" + "] \n")
        
        if f and self.left:
            left_node_id = self.left.data + str(self.left.label)
            f.write("\"" + node_id + "\"" + " -> " + "\"" + left_node_id + "\"" + "\n")
            self.left.writeNodeDotfile(f)
            
        if f and self.right:
            right_node_id = self.right.data + str(self.right.label)
            f.write("\"" + node_id + "\"" + " -> " + "\"" + right_node_id + "\"" + "\n")
            self.right.writeNodeDotfile(f)
            
# -------------------------

class ParseTree:
    
    def __init__(self, root):
        self.root = root
        self.isLabeled = False

    def __repr__(self):
        return self.root.printNodes()

    def labelTree(self):
        occ = {}
        self.isLabeled = True
        return self.root.labelNodes(occ)
    
    def writeTreeDotfile(self, filename):
        # if we have not labeled the tree yet, do it, otherwise some
        # visualization problems may arise when generating the graph
        # image using grapvhiz.
        if not self.isLabeled:
            self.labelTree()
            
        f = open(filename + ".dot", "w+")

        f.write("digraph tree{\n")
        self.root.writeNodeDotfile(f)
        f.write("}\n")
        f.close()

        # generates the image using the dot file
        graphviz_command = "/usr/bin/dot " + filename + ".dot" + " -Tpng -o " + filename + ".png"
        process = subprocess.Popen(graphviz_command, shell=True, stdout=subprocess.PIPE)
        process.wait()