// file: BinaryTree.java
// Binary Tree
// Copyright (C) 2006 Gregory D. Weber

public class BinaryTree<E> implements Graphable {

    protected Tnode<E> root;

    public BinaryTree () { root = null; }

    public BinaryTree (E item) { root = new Tnode<E>(item, null, null); }

    public BinaryTree (E item, BinaryTree<E> left, BinaryTree<E> right) {
	root = new Tnode<E>(item, left.root, right.root);
    }

    protected BinaryTree (Tnode<E> node) { root = node; }
    
    // Protected accessors (for convenience)

    protected Tnode<E> left (Tnode<E> node) { return node.left; }

    protected Tnode<E> right (Tnode<E> node) { return node.right; }

    // Public methods

    public boolean isEmpty() { return (root == null); }

    public int height () { return height(root); }

    protected int height (Tnode<E> root) {
	if (root == null)
	    return 0;
	else
	    return 1 + Math.max(height(left(root)), height(right(root)));
    }

    // Size = number of elements

    public int size () { return size(root); }

    protected int size (Tnode<E> root) {
	if (root == null)
	    return 0;
	else
	    return 1 + size(left(root)) + size(right(root));
    }

    /** This is not guaranteed to be a binary search tree, so we must
	search exhaustively. */

    public boolean search (E target) { return search(root, target); }

    protected boolean search (Tnode<E> root, E target) {
	/* If we want to return instead an E result:
	if (root == null)
	    return null;
	else if (root.item.equals(target))
	    return root.item;
	else if ((result = (search(left(root), target))) != null)
	    return result;
	else 
	    return search(right(root), target);
	*/
	return (root != null &&
		(root.item.equals(target) ||
		 search(left(root), target) ||
		 search(right(root), target)));
    }

    public void preorder (Visitor<E> vis) { preorder(vis, root); }

    protected void preorder (Visitor<E> vis, Tnode<E> node) {
	if (node == null) 
	    return;
	else {
	    vis.visit(node);
	    preorder(vis, left(node));
	    preorder(vis, right(node));
	}
    }

    public void inorder (Visitor<E> vis) { inorder(vis, root); }

    protected void inorder (Visitor<E> vis, Tnode<E> node) {
	if (node == null)
	    return;
	else {
	    inorder(vis, left(node));
	    vis.visit(node);
	    inorder(vis, right(node));
	}
    }

    public void postorder (Visitor<E> vis) { postorder(vis, root); }

    protected void postorder (Visitor<E> vis, Tnode<E> node) {
	if (node == null)
	    return;
	else {
	    postorder(vis, left(node));
	    postorder(vis, right(node));
	    vis.visit(node);
	}
    }

    public boolean equals (BinaryTree<E> obj) {
	return (this == obj) || equalNodes(root, obj.root);
    }

    protected boolean equalNodes (Tnode<E> a, Tnode<E> b) {
	return (a.item.equals(b.item) &&
		equalNodes(a.left, b.left) &&
		equalNodes(a.right, b.right));
    }
    
	
    /** Stringify the empty tree as "".
	For non-empty trees, something like
	
            / Right
	 Root
	    \ Left
    */

    public String toString () {
	return toString("", "", root);
    }

    protected String toString (String indent, String prefix, Tnode<E> node) {

	if (node == null)
	    return "";
	else {

	    // Increase indentation by string length of root + 3
	    String rootstr1 = node.item.toString();
	    String newindent = indent + spaces(rootstr1.length() + 3);

	    // Reverse inorder traversal
	    String rightstr = toString(newindent, "/ ", right(node));
	    String rootstr = indent + prefix + rootstr1;
	    String leftstr = toString(newindent, "\\ ", left(node));
	    return rightstr + rootstr + "\n" + leftstr;
	}
    }

    protected String spaces (int n) {
	String result = "";
	for (int i = 0; i < n; i++)
	    result += " ";
	return result;
    }

    // For the Graphable interface

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

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

    protected String toDot (String parent, Tnode<E> node) {
	// Preorder transformation to DOT node and edge statements.
	// parent is "" if node is the root;
	// otherwise parent is parentId:sw if node is a left child,
	// or parentId:se if node is a right child.
	if (node == null)
	    return "";
	else {
	    String nid = nodeId(node);
	    return 
		// edge leading into node, if any
		edgeDecl(parent, node) +
		// node declaration
		"  " + nid + " [label = " + nodeLabel(node) + 
		", color = " + node.getColor() +
		"];" + "\n" +
		// subtree declarations
		toDot(nid + ":sw", left(node)) +
		toDot(nid + ":se", right(node));
	}
    }

    protected String edgeDecl (String parentside, Tnode<E> node) {
	// DOT declaration for the edge (if any) into the node
	// from its parent.  If node is the root, then parentside is "";
	// otherwise if node is a left child, then parentside is parentid:sw;
	// otherwise, parentside is parentid:se.
	if (parentside == "")
	    return "";
	else 
	    return "  " + parentside + " -> " + nodeId(node) + ":n;";
    }

    protected String nodeId (Tnode<E> node) {
	// Return unique ID for this node for use in DOT node declaration;
	// at least we hope the hash code is unique!
	return "n" + node.hashCode();
    }

    protected String nodeLabel (Tnode<E> node) {
	// Return the string that should be displayed for this node.
	String quote = "\"";
	return quote + node.item.toString() + quote;
    }

	    
}