#!/usr/bin/python3

class Node(object):
    def __init__(self, data, eout=None):
        self.data = data
        self.ein = []
        self.eout = eout if eout else []

    # (Re-)insert a child node [target] to [self] at index [idx] (or as the
    # rightmost child if index is not given). Also append [self] to the list of
    # parents of [target].
    def add_out(self, target, idx=None):
        if target in self.eout:
            self.eout.remove(target)
        if idx is None:
            self.eout.append(target)
        else:
            self.eout.insert(idx, target)
        if self not in target.ein:
            target.ein.append(self)
        return target

    def __repr__(self):
        return str(self.data)

    def __lt__(self, other):
        return self.data < other.data

# Print the edit graph containing [nodes] in graphviz dot format. The [label]
# and [pos] functions determine node labels and coordinates (x,y), and the
# [node_attr] and [edge_attr] functions specify additional attributes for each
# node and edge. To actually use the coordinates returned by [pos], generate
# the image using neato -n1.
def graphviz(nodes, label=str, pos=None, node_attr=None, edge_attr=None):
    # Generate node descriptions.
    node_str = ''
    node_id = {}
    for node in nodes:
        node_id[node] = len(node_id)
        node_str += '\t{} [label="{}"'.format(node_id[node], label(node).replace('"', '\\"'))
        if pos:
            node_str += ', ' + 'pos="{},{}"'.format(*pos(node))
        if node_attr:
            node_str += ', ' + node_attr(node)
        node_str += '];\n'

    # Generate edge descriptions (breadth-first).
    edge_str = ''
    for node in nodes:
        a = node_id[node]
        for child in node.eout:
            b = node_id[child]
            edge_str += '\t{} -> {}'.format(a, b)
            if edge_attr:
                edge_str += ' [' + edge_attr(node, child) + ']'
            edge_str += ';\n'

    output = 'digraph G {\n'
    output += '\tordering="out";\n'
    output += '\tnode [shape="box", margin="0.05,0", fontname="sans", fontsize=13.0];\n'
    output += '\n'
    output += node_str
    output += '\n'
    output += edge_str
    output += '}\n'

    return output