// STATUS: might need to revise this and make it non-static,
// and add a subclass to handle RedBlack trees???

// File: BinaryTreeViewer.java
// generates dot code for visualizing binary trees
// Copyright (C) 2006, 2008 Gregory D. Weber
// Revised 2008 Nov 1

public class BinaryTreeViewer
{

    /** view tree (graphically) */

    public static void view (BinaryTree tree) {
	GraphViewer.view(toDot(tree));
    }

    /** show tree -- display both textually and graphically */

    public static void show (String name, BinaryTree tree) {
	System.out.println("\nHere is " + name + ":\n");
	System.out.println(tree);
	System.out.println("\nHere is a better view; " +
			   "type q or Esc to quit viewer:\n");
	BinaryTreeViewer.view(tree);
    }

    /** Return a DOT language representation of this binary tree */

    public static String toDot (BinaryTree tree) {
	if (tree == null)
	    return ("digraph javatree { /* empty */ }\n");
	else {
	    String rootId = nodeId(tree);
	    return ("digraph javatree {\n" +
		    "  ordering = out;\n" +
		    "  root = " + rootId + ";\n" +
		    toDot("", tree) +
		    "}\n");
	}
    }

    protected static String toDot (String parentside, BinaryTree tree) {
	// Preorder transformation to DOT node and edge statements.
	// parentside is "" if we're at the root of the whole tree;
	// otherwise parentside is parentId:sw if tree is a left subtree,
	// or parentId:se if tree is a right subtree.
	if (tree == null)
	    return "";
	else {
	    String nid = nodeId(tree);
	    return 
		// edge leading into tree, if any
		edgeDecl(parentside, tree) +
		// node declaration
		"  " + nid + " [label = " + nodeLabel(tree) + 
		nodeColorDecl(tree) +
		"];" + "\n" +
		// subtree declarations
		toDot(nid + ":sw", tree.left()) +
		toDot(nid + ":se", tree.right());
	}
    }

    protected static String nodeColorDecl (BinaryTree tree) {
	if (tree instanceof RedBlack) // awkward!!!
	    return ", color = " +
		(((RedBlack)tree).color() == RedBlack.Color.RED ?
		 "red" :
		 "black");
	else
	    return "";
    }
			
    protected static String edgeDecl (String parentside, BinaryTree tree) {
	// DOT declaration for the edge (if any) into the (sub)tree
	// from its parent.  The argument parentside is like in toDot.
	if (parentside == "")
	    return "";
	else 
	    return "  " + parentside + " -> " + nodeId(tree) + ":n;";
    }

    protected static String nodeId (BinaryTree tree) {
	// Precondition: t is a non-empty binary tree
	// (and therefore not null)
	// Returns unique ID for the root node,
	// for use in DOT node declaration;
	// at least we hope the hash code is unique!
	return "n" + tree.hashCode();
    }

    protected static String nodeLabel (BinaryTree tree) {
	// Precondition: tree is non-empty.
	// Return the string that should be displayed for the
	// root node of this tree.
	String quote = "\"";
	return quote + tree.root().toString() + quote;
    }

}