import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;

/**
 * VisualBinaryTreeApplet.java,  Version April-15-2011.
 * Starter code for CSE 332 Project 2, Univ. of Wash., Spring, 2011.
 * This applet provides very basic binary tree functionality. It is NOT an
 * implementation of the Binary Search Tree data structure. Rather, it supports 
 * a strange and unusual INSERT method, and an inefficient FIND method.
 * Its main contribution, therefore, is providing a starting point for more 
 * useful implementations such as real binary search trees.
 * It includes a straightforward means of drawing a binary tree on the applet's
 * drawing area, and it displays the node properties that assist in the display:
 * "inorder number", for the x coordinate, and depth, for the y coordinate.
 * The height of each node is also shown.
 * 
 * Status as of April 15. Working.
 * 
 * @author Steve Tanimoto
 * @version April-15-2011
 */
public class VisualBinaryTreeApplet extends VisualDataStructureApplet {
	/**
	 * Here we provide methods that override those of VisualDataStructureApplet.
	 */
	private static final long serialVersionUID = 1L;
	VisibleBinaryTree vbt;

	public void initDataStructure() {
		vbt = new VisibleBinaryTree();
		vbt.theTree = null;
		myDataStructure = vbt;
	}

	@Override
	public void init() {
		super.init(); // Creates the user interface.
		// Now we put some sample commands into the command area
		// as a convenience for testing:
		userInputText.append("IS_EMPTY\n");
		userInputText.append("INSERT penguin\n");
		userInputText.append("INSERT aardvark\n");
		userInputText.append("INSERT tiger\n");
		userInputText.append("INSERT cougar\n");
		userInputText.append("IS_EMPTY\n");
		userInputText.append("CONTAINS aardvark\n");
		userInputText.append("INSERT bear\n");
		userInputText.append("INSERT canary\n");
		userInputText.append("WAIT\n");
		userInputText.append("INSERT leopard\n");
	}


	public boolean process(String command) {
		if (super.process(command)) {
			return true;
		}
		;
		return processDSCommands(command);
	}

	public void report(String msg) {
		statusLine.setText(msg);
		history.append(msg + "\n");
	}
	
	public boolean processDSCommands(String command) {
		vbt.changed = false;
		if (firstToken.equals("NEW")) {
			myDataStructure = null;
			vbt.updateProperties();
			updateDisplay();
			checkScrolledPanelSize();
			return true;
		}
		if (firstToken.equals("INSERT")) {
			arg = "UNDEFINED ELEMENT";
			if (st.hasMoreTokens()) {
				arg = st.nextToken();
			}
			vbt.insert(arg);
			if (vbt.changed) {
				vbt.updateProperties();
				updateDisplay();
				checkScrolledPanelSize();
			}
			return true;
		}
		if (firstToken.equals("FIND")) {
			arg = "UNDEFINED ELEMENT";
			if (st.hasMoreTokens()) {
				arg = st.nextToken();
			}
			String result = vbt.findAndReport(arg);
			report("FIND returns " + result);
			return true;
		}
		if (firstToken.equals("IS_EMPTY")) {
			boolean result = vbt.isEmpty();
			report("IS_EMPTY returns " + result);
			return true;
		}
		if (firstToken.equals("CONTAINS")) {
			arg = "UNDEFINED ELEMENT";
			if (st.hasMoreTokens()) {
				arg = st.nextToken();
			}
			String result = vbt.findAndReport(arg);
			boolean bresult = true;
			if (result == null)
				bresult = false;
			report("CONTAINS returns " + bresult);
			return true;
		}
		return false;
	}

	/*
	 * The VisibleBinaryTree inner class implements the display methods required 
	 * for a visible data structure. It has data members for things like the colors
	 * used to paint the nodes and arcs. The actual tree data structure itself
	 * is in the data member named theTree.
	 */
	class VisibleBinaryTree extends VisibleDataStructure {
		BinaryTreeNode theTree;
		int treeSize = 0;
		Color myNodeColor;
		Color myNodeBorderColor;
		Color nodeLabelColor;
		Color arcColor;
		Font nodeLabelFont;
		FontMetrics nodeFontMetrics;
		Graphics g;
		BinaryTreeNode lastParent, parentOfSmallest;
		boolean isLeftChild;
		boolean changed;
		int inorderCounter;
		int maxDepth;
		int nodeWidth = 110;
		int nodeHeight = 60;
		int hoffset = nodeWidth / 2;
		int voffset = 100;
		int horizontalSpacing = 100;
		int verticalSpacing = 75;
		int xstart;


		boolean isEmpty() {
			if (theTree == null) {
				return true;
			} else {
				return false;
			}
		}

		// Special, unusual FIND method, to be replaced in Phase A.
		BinaryTreeNode find(String key) {
			boolean found = false;
			return preOrderFind(key, theTree); // call helper from root 
		}
		BinaryTreeNode preOrderFind(String key, BinaryTreeNode currentNode) {
			if (currentNode==null) { return null; }
			if (currentNode.key.equals(key)) return currentNode;
			BinaryTreeNode tempResult = preOrderFind(key, currentNode.leftSubtree);
			if (tempResult!=null) { return tempResult; }
			tempResult = preOrderFind(key, currentNode.rightSubtree);
			return tempResult;
		}
		
		String findAndReport(String key) {
			return find(key).toString();
		}
			
		// Unusual insert method, to be replaced in Phase A of project.
		// Chooses an insertion location in the tree by steering a strange path
		// from the root, according to the parity of the ASCII values of successive characters
		// in the key.
		void insert(String key) {
			BinaryTreeNode loc = find(key);
			if (loc != null)
				return;
			BinaryTreeNode newNode = new BinaryTreeNode(key);
			changed = true;
			if (isEmpty()) {
				theTree = newNode;
				treeSize = 1;
				return;
			}
			BinaryTreeNode parent = theTree;
			boolean side = false;
			boolean found = false;
			int step = 0;
			int n = key.length();
			int direction = 0;
			// Loop through path until a good parent and side is found.
			// If parent is a leaf, it's good and we'll go to its left side.
			// If parent's left side is taken but right is free, go to its right.
			// If parent has two children, find parity of next char in key, and go
			// that way.
			while (! found) {
				direction = ((int)key.charAt(step % n)) % 2;
				if (parent.leftSubtree==null) {
					found = true;
					break;
				}
				if (parent.rightSubtree==null) {
					side = true;
					found = true;
					break; 
				}
				if (direction==0) {
					parent = parent.leftSubtree;
				} else {
					parent = parent.rightSubtree;
				}
			}
			if (! side) {
				parent.leftSubtree = newNode;
			}
			else {
				parent.rightSubtree = newNode;
			}
			
			treeSize++;
		}

		void inorderTraversal() {
			if (theTree != null)
				theTree.inorderTraversal();
		}

		void computeDepths() {
			if (theTree != null)
				theTree.computeDepths();
		}

		void computeHeights() {
			if (theTree != null)
				theTree.computeHeights();
		}

		@Override
		public Dimension getDisplayRegion() {
			int maxX = hoffset + (int) (scale * (xstart + inorderCounter
					* horizontalSpacing));
			int maxY = (int) (scale * (50 + voffset + maxDepth
					* verticalSpacing));
			return new Dimension(maxX, maxY);
		}

		@Override
		public void renderDS(Graphics g) {
			xstart = hoffset;
			renderDictionary(g); // generalized in anticipation of having multiple dictionaries.
		}
		public void renderDictionary(Graphics g) {
			renderBinaryTree(g);
		}
		public void renderBinaryTree(Graphics g) {
			if (theTree == null)
				return;
			this.g = g; // cache the graphics context so it
			// can be used easily in drawTree and drawNode.
			inorderCounter = 0; // initialize count to find x coords of each
			// node.
			theTree.inorderTraversal(); // numbers the nodes left-to-right.
			theTree.depth = 0; // get ready to find y coords (depth).
			maxDepth = 0;
			theTree.computeDepths(); // figure out and store depths of each
			// node.
			// Here are some arbitrary color choices.
			// There should be enough difference in colors so everything is
			// legible. Trial and error is one way to achieve this.
			myNodeColor = new Color(0, 192, 255); // indigo
			myNodeBorderColor = new Color(255, 0, 0); // red
			nodeLabelColor = new Color(230, 230, 255); // light blue
			arcColor = new Color(127, 0, 0); // dark red
			int fontSize = (int) (scale * initialFontSize);
			// note that initialFontSize is inherited from
			// VisualDataStructureApplet.
			nodeLabelFont = new Font("Helvetica", Font.BOLD, fontSize);
			g.setFont(nodeLabelFont);
			nodeFontMetrics = g.getFontMetrics();
			drawTree(theTree);
		}

		void drawTree(BinaryTreeNode node) {
			if (node == null)
				return;
			// Note that drawing is done in a sort of postorder traversal,
			// so that the nodes will be drawn OVER the arcs,
			// rather than vice-versa.
			if (node.leftSubtree != null) {
				g.setColor(arcColor);
				g.drawLine(node.xcenter, node.ycenter,
						node.leftSubtree.xcenter, node.leftSubtree.ycenter);
				drawTree(node.leftSubtree);
			}
			if (node.rightSubtree != null) {
				g.setColor(arcColor);
				g.drawLine(node.xcenter, node.ycenter,
						node.rightSubtree.xcenter, node.rightSubtree.ycenter);
				drawTree(node.rightSubtree);
			}
			drawNode(node);
		}

		void drawNode(BinaryTreeNode node) {
			// Draw the box or oval for the node.
			g.setColor(myNodeBorderColor);
			int pad = 10;
			g.fillRect(node.xcenter - (int) (scale * (nodeWidth + pad) / 2),
					node.ycenter - (int) (scale * (nodeHeight + pad) / 2),
					(int) (scale * (nodeWidth + pad)),
					(int) (scale * (nodeHeight + pad)));
			g.setColor(myNodeColor);
			g.fillRect(node.xcenter - (int) (scale * nodeWidth / 2),
					node.ycenter - (int) (scale * nodeHeight / 2),
					(int) (scale * nodeWidth), (int) (scale * nodeHeight));
			g.setColor(myNodeBorderColor);
			g.drawRect(node.xcenter - (int) (scale * nodeWidth / 2),
					node.ycenter - (int) (scale * nodeHeight / 2),
					(int) (scale * nodeWidth), (int) (scale * nodeHeight));
			// g.fillOval(node.xcenter - (int)(scale*nodeWidth/2),
			// node.ycenter - (int)(scale*nodeHeight/2),
			// (int)(scale*nodeWidth), (int)(scale*nodeHeight));
			// Now draw the node's label, scaled and centered.
			String label = node.key.toString();
			int labelWidth = nodeFontMetrics.stringWidth(label);
			int labelHeight = nodeFontMetrics.getHeight();
			g.setColor(nodeLabelColor);
			g.drawString(node.key, node.xcenter - labelWidth / 2, node.ycenter
					+ (int) (0.25 * labelHeight));
			String info = "d=" + node.depth + "; h=" + node.height + "; i="
					+ node.inorderIndex;
			int infoWidth = nodeFontMetrics.stringWidth(info);
			int infoHeight = nodeFontMetrics.getHeight();
			g.drawString(info, node.xcenter - infoWidth / 2, node.ycenter
					+ (int) (1.25 * labelHeight));
		}

		void updateProperties() {
			vbt.inorderTraversal();
			vbt.computeDepths();
			vbt.computeHeights();
		}
		/*
		 * This inner class represents the actual binary tree, by representing its
		 * root, and recursively, its subtrees. It also provides data members for
		 * storing some display information particular to each node, such as
		 * coordinates on the screen.
		 */
		class BinaryTreeNode {
			String key;
			BinaryTreeNode leftSubtree;
			BinaryTreeNode rightSubtree;
			int inorderIndex;
			int depth = 0;
			int height = 0;
			int xcenter;
			int ycenter;

			BinaryTreeNode(String s) {
				key = s;
			}

			void inorderTraversal() {
				if (leftSubtree != null) {
					leftSubtree.inorderTraversal();
				}
				inorderIndex = inorderCounter++;
				xcenter = (int) (scale * (xstart + 
						(horizontalSpacing * (inorderIndex+0.3))));
				if (rightSubtree != null) {
					rightSubtree.inorderTraversal();
				}
			}

			void computeDepths() {
				ycenter = (int) (scale * (voffset + verticalSpacing * depth));
				if (leftSubtree != null) {
					leftSubtree.depth = depth + 1;
					leftSubtree.computeDepths();
				}
				if (rightSubtree != null) {
					rightSubtree.depth = depth + 1;
					rightSubtree.computeDepths();
				}
				maxDepth = Math.max(maxDepth, depth);
			}

			int computeHeights() {
				if (leftSubtree == null && rightSubtree == null) {
					height = 0;
					return height;
				}
				if (leftSubtree == null) {
					height = 1 + rightSubtree.computeHeights();
					return height;
				}
				if (rightSubtree == null) {
					height = 1 + leftSubtree.computeHeights();
					return height;
				}
				height = 1 + Math.max(leftSubtree.computeHeights(), rightSubtree
						.computeHeights());
				return height;
			}
		}
	}

}