package algs13;

import java.util.Scanner;
import stdlib.*;

// A Playground for binary trees

public class XBTree {
	static class BNode {
		public BNode (double item, BNode left, BNode right) {
			this.item = item;
			this.left = left;
			this.right = right;
		}
		public double item;
		public BNode left;
		public BNode right;
	}
	BNode root;

	// height/depth of empty tree is -1
	// height/depth of singleton tree is 0
	public int height () {
		//TODO
		return StdRandom.uniform (100);
	}
	public int depth () {
		//TODO
		return StdRandom.uniform (100);
	}	
	public int depthOfShallowestFive () {
		//TODO
		return StdRandom.uniform (100);
	}
	public int heightOfShortestFive () {
		//TODO
		return StdRandom.uniform (100);
	}


	// prefix with parenthesis
	public String toString () {
		StringBuilder sb = new StringBuilder ();
		toString (sb, root);
		return sb.toString ();
	}
	private static void toString (StringBuilder sb, BNode n) {
		if (n == null) {
			sb.append ("X ");			
		} else if (n.left == null && n.right == null) {
			sb.append (n.item);
			sb.append (" ");
		} else {
			sb.append ("( ");
			sb.append (n.item);
			sb.append (" ");
			toString (sb, n.left);			
			toString (sb, n.right);			
			sb.append (") ");
		}
	}
	public void toGraphviz (String filename) {
		GraphvizBuilder gb = new GraphvizBuilder ();
		toGraphviz (gb, null, root);
		gb.toFileUndirected (filename, "ordering=\"out\"");
	}
	private static void toGraphviz (GraphvizBuilder gb, BNode parent, BNode n) {
		if (n == null) {
			gb.addNullEdge (parent);
			return;
		}
		gb.addLabeledNode (n, Double.toString (n.item));
		if (parent != null) gb.addEdge (parent, n);
		toGraphviz (gb, n, n.left);
		toGraphviz (gb, n, n.right);
	}

	public static XBTree randomTree (double chanceOfNull, int maxDepth) {
		XBTree result = new XBTree ();
		result.root = randomTreeHelper (chanceOfNull, maxDepth, 0);
		return result;
	}
	private static BNode randomTreeHelper (double chanceOfNull, int maxDepth, int depth) {
		if (depth > maxDepth || StdRandom.uniform () < chanceOfNull * depth) 
			return null;
		BNode left = randomTreeHelper (chanceOfNull, maxDepth, depth+1);
		BNode right = randomTreeHelper (chanceOfNull, maxDepth, depth+1);
		double val = StdRandom.uniform (10);
		return new BNode (val, left, right);
	}

	// Parses the following kinds of tree "T"
	// T ::= "X" -- empty
	// T ::= num -- a node with no children
	// T ::= ( num T T ) -- a node with children
	// For example: ( 0 ( 01 12 X ) 02 )
	public static XBTree from (String in) {
		Scanner sc = new Scanner (in);
		XBTree result = new XBTree ();
		result.root = ofHelper (sc);
		return result;
	}
	private static BNode ofHelper (Scanner sc) {
		BNode result = null;
		if (sc.hasNext ("X")) {			
			sc.next (); // gobble "X"
		}
		if (sc.hasNextDouble ()) {
			double val = sc.nextDouble ();
			result = new BNode (val, null, null);
		} else if (sc.hasNext ("\\(")) {
			sc.next (); // gobble "("
			double val = sc.nextDouble ();
			result = new BNode (val, null, null);
			result.left = ofHelper (sc);
			result.right = ofHelper (sc);
			sc.next ("\\)"); //gobble ")"
		} 
		return result;
	}
	private static int count = 0;
	private static void testHeightOfShortestFive (XBTree tree, int expected) {
		int actual = tree.heightOfShortestFive ();
		if (!DEBUG && expected != actual) {
			//if (!DEBUG && ((expected >= 0 && expected != actual) || (expected < 0 && actual > 0))) {
			count++;
			tree.toGraphviz ("error" + count + ".png");
			StdOut.format ("error%d.heightOfShortestFive: expected=%d, actual=%d\n", count, expected, actual);
		}
	}
	private static void testDepthOfShallowestFive (XBTree tree, int expected) {
		int actual = tree.depthOfShallowestFive ();
		if (!DEBUG && expected != actual) {
			count++;
			tree.toGraphviz ("error" + count + ".png");
			StdOut.format ("error%d.depthOfShallowestFive: expected=%d, actual=%d\n", count, expected, actual);
		}
	}

	public static boolean DEBUG = false;
	public static XBTree demoTree () {
		String sl = "( 0 ( 0 X ( 0 ( 0 X ( 0 X X ) ) X ) ) ( 0 X ( 0 X X ) ) )";
		String sr = "( 0 ( 0 ( 0 ( 0 X X ) ( 0 X X ) ) ( 0 X ( 0 ( 0 X X ) X ) ) ) ( 0 ( 0 X X ) X ) )";
		String s = "( 0 " + sl + " " + sr + " )";
		return XBTree.from (s);
	}
	public static void main (String[] args) {
		if (DEBUG) {
			Trace.drawStepsOfMethod("main");
			Trace.drawStepsOfMethod("depth");
			Trace.drawStepsOfMethod("height");
			Trace.drawStepsOfMethod("depthOfShallowestFive");
			Trace.drawStepsOfMethod("heightOfShortestFive");
			Trace.run (); 
			XBTree t0 = demoTree();
			t0.root.right.right.item = 5.0;
			testDepthOfShallowestFive(t0, 2);
			return;
		}
		{
			XBTree t0 = demoTree();			
			testDepthOfShallowestFive(t0, -1);
			t0.root.right.left.right.left.left.item = 5.0;
			testDepthOfShallowestFive(t0, 5);
			t0.root.left.left.left.left.left.item = 5.0;
			testDepthOfShallowestFive(t0, 5);
			t0.root.left.left.left.left.item = 5.0;
			testDepthOfShallowestFive(t0, 4);
			t0.root.right.left.right.item = 5.0;
			testDepthOfShallowestFive(t0, 3);
			t0.root.right.right.item = 5.0;
			testDepthOfShallowestFive(t0, 2);
			t0.root.left.item = 5.0;
			testDepthOfShallowestFive(t0, 1);
			t0.root.item = 5.0;
			testDepthOfShallowestFive(t0, 0);
		}
		{
			XBTree t1 = demoTree();			
			testHeightOfShortestFive(t1, -7);
			t1.root.item = 5.0;
			testHeightOfShortestFive(t1, 5);
			t1.root.left.item = 5.0;
			testHeightOfShortestFive(t1, 4);
			t1.root.right.item = 5.0;
			testHeightOfShortestFive(t1, 4);		
			t1.root.right.left.item = 5.0;
			testHeightOfShortestFive(t1, 3);
			t1.root.left.left.left.item = 5.0;
			testHeightOfShortestFive(t1, 2);
			t1.root.left.left.left.left.item = 5.0;
			testHeightOfShortestFive(t1, 1);
			t1.root.right.left.right.left.left.item = 5.0;
			testHeightOfShortestFive(t1, 0);
		}
		{
			XBTree t2 = demoTree();			
			t2.root.left.left.left.left.item = 5.0;
			t2.root.right.right.item = 5.0;
			t2.toGraphviz ("t2.png");		
			StdOut.format ("t2: %s\n", t2);
			StdOut.format ("%d = t2.depth()\n", t2.depth ());
			StdOut.format ("%d = t2.height()\n", t2.height ());
			StdOut.format ("%d = t2.depthOfShallowestFive()\n", t2.depthOfShallowestFive ());
			StdOut.format ("%d = t2.heightOfShortestFive()\n", t2.heightOfShortestFive ());
		}

		int NUM_RANDOM = 10;
		for (int i=0; i<NUM_RANDOM; i++) {
			XBTree t3 = randomTree (0.11, StdRandom.uniform(3, 9));
			t3.toGraphviz ("t3" + i + ".png");
			StdOut.format ("t3: %s\n", t3);			
			StdOut.format ("%d = t3.depth()\n", t3.depth ());
			StdOut.format ("%d = t3.height()\n", t3.height ());
			StdOut.format ("%d = t3.depthOfShallowestFive()\n", t3.depthOfShallowestFive ());
			StdOut.format ("%d = t3.heightOfShortestFive()\n", t3.heightOfShortestFive ());
		}
		StdOut.println ("Finished tests");
	}
}