/*
This file is part of the algoviz@vt collection of algorithm
visualizations.

This program is free software: you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation, either version 3
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this distribution. If not, see
<http://www.gnu.org/licenses/>.
*/

import java.awt.Color;
import java.awt.Graphics;
import java.io.IOException;
import java.io.Writer;
import java.util.ArrayList;

/**
 * A Binary Search Tree class. Although this class is heavily modified, the core
 * BST functionality remains intact. Basically, the modifications make tracing
 * each BST operations easy.
 * 
 * @author Andrew Whitaker (aawhitak@vt.edu)
 * 
 * @param <Key>
 *            The data type of the keys for the Binary Search Tree.
 * @param <Elem>
 *            The data type of the values in this BST.
 */
public class BST<Key extends Comparable<Key>, Elem> implements
		DictionaryADT<Key, Elem>
{
	/* The root of this tree */
	private BinNodeADT<Key, Elem> root;
	/* The number of nodes in the tree */
	private int nodeCount;
	/*
	 * A list containing the States that the most recent operation has gone
	 * through.
	 */
	private ArrayList<State> stateList;
	/* The TreePanel that this BST belongs to. */
	private TreePanel treePanel;
	/* The number of levels in this tree. */
	private int levels;

	/**
	 * Creates a new BST.
	 * 
	 * @param p
	 */
	public BST(TreePanel p) {
		this();
		treePanel = p;

	}

	/**
	 * Creates a new BST with a null root.
	 */
	public BST() {
		root = null;
		nodeCount = 0;
		stateList = new ArrayList<State>();
		levels = 0;
	}

	/**
	 * Clears the BST (not implemented)
	 */
	public void clear() {
		// TODO Auto-generated method stub

	}

	/**
	 * Find method.
	 * 
	 * @param k
	 *            The key you're looking for.
	 * @return The element associated with this key.
	 */
	public Elem find(Key k) {
		stateList.clear();
		return findHelper(root, k);
	}

	/**
	 * Find helper method. Works just like a normal BST find method, but tracks
	 * each "State" the BST is in using a list.
	 * 
	 * @param node
	 *            The node to recursively find from.
	 * @param k
	 *            The key to look for.
	 * @return The Element corresponding to the key.
	 */
	private Elem findHelper(BinNodeADT<Key, Elem> node, Key k) {
		if (node == null) {
			return null;
		}
		Elem it = node.val();
		if (k.compareTo(node.key()) < 0) {
			State s = new State((GraphicalNode) node.val(),
					State.OperationType.INSERT, "Went left of " + node.key()
							+ "\n");
			stateList.add(s);
			System.out.println("find left of " + node.key());
			return findHelper(node.left(), k);
		} else if (node.key().equals(k)) {
			State s = new State((GraphicalNode) it, State.OperationType.FIND,
					"Found node successfully\n");
			stateList.add(s);
			System.out.println("find right of " + node.key());
			return it;
		} else {
			State s = new State((GraphicalNode) node.val(),
					State.OperationType.FIND, "Went right of " + node.key()
							+ "\n");
			stateList.add(s);
			return findHelper(node.right(), k);
		}
	}

	/**
	 * Inserts a new node in the Binary Search Tree with the specified Key and
	 * Element.
	 * 
	 * @param k
	 *            The key to put into the new node.
	 * @param e
	 *            The element to put into the new node.
	 */
	public void insert(Key k, Elem e) {
		stateList.clear();
		int tmpLevels = levels;
		levels = 0;
		root = insertHelper(root, k, e);
		if (levels < tmpLevels) {
			levels = tmpLevels;
		}
		treePanel.setLevels(levels);
		nodeCount++;
	}

	/**
	 * Prints the BST to the specified writer.
	 * 
	 * @param w
	 *            The writer to write the BST to.
	 */
	public void print(Writer w) {
		printHelper(root, w);
	}

	/**
	 * @return The list of states that the BST went through to complete the last
	 *         operation.
	 */
	public ArrayList<State> getStateList() {
		return stateList;
	}

	/**
	 * Helper method for insertion. Works just like a regular BST insertion
	 * except "States" are kept track of.
	 * 
	 * @param node
	 *            The node to recursively insert on.
	 * @param k
	 *            The key to insert
	 * @param it
	 *            The element to insert
	 * @return The newly inserted node.
	 */
	private BinNodeADT<Key, Elem> insertHelper(BinNodeADT<Key, Elem> node, Key k,
			Elem it) {
		if (node == null) {
			// feedback.append("Node added successfully\n");
			State s = new State((GraphicalNode) it, State.OperationType.INSERT,
					"Inserted " + k.toString() + " successfully\n");
			stateList.add(s);
			levels++;
			return new BinNode<Key, Elem>(k, it, null, null);
		}
		if (k.compareTo(node.key()) < 0) {
			// feedback.append("Went left of " + root.key() + "\n");
			State s = new State((GraphicalNode) node.val(),
					State.OperationType.INSERT, "Went left of " + node.key()
							+ "\n");
			stateList.add(s);
			levels++;
			node.setLeft(insertHelper(node.left(), k, it));
		} else {
			// feedback.append("Went right of " + node.key() + "\n");

			State s = new State((GraphicalNode) node.val(),
					State.OperationType.INSERT, "Went right of " + node.key()
							+ "\n");
			stateList.add(s);
			levels++;
			node.setRight(insertHelper(node.right(), k, it));
		}
		return node;
	}

	/**
	 * Helper method for printing a BST.
	 * 
	 * @param root
	 *            The node to recursively print.
	 * @param w
	 *            The writer to print to.
	 */
	private void printHelper(BinNodeADT<Key, Elem> root, Writer w) {
		if (root == null) {
			return;
		}
		printHelper(root.left(), w);
		try {
			w.write(root.val() + " ");
		} catch (IOException e) {
			e.printStackTrace();
		}
		printHelper(root.right(), w);
	}

	/**
	 * Removes the node with the specified key from the tree.
	 */
	public Elem remove(Key k) {
		return removeHelper(root, k).val();
	}

	/**
	 * Helper for the remove method. State-tracking has not been implemented for
	 * remove().
	 * 
	 * @param node
	 *            The node to recursively remove on.
	 * @param k
	 *            The key to remove.
	 * @return The node that was removed.
	 */
	public BinNodeADT<Key, Elem> removeHelper(BinNodeADT<Key, Elem> node, Key k) {
		if (node == null)
			return null;
		else if (k.compareTo(node.key()) < 0) {
			node.setLeft(removeHelper(node.left(), k));
		} else if (k.compareTo(node.key()) > 0) {
			node.setRight(removeHelper(node.right(), k));
		} else
		// found it
		{
			if (node.left() == null) {
				node = node.right();
			} else if (root.right() == null) {
				node = node.left();
			} else {
				BinNodeADT<Key, Elem> tmp = getMin(root.right());
				node.setVal(tmp.val());
				node.setRight(deleteMin(node.right()));
			}
		}
		return node;
	}

	/**
	 * Helper method for remove, gets the minimum node in the subtree at root.
	 * 
	 * @param root
	 *            The subtree to search for the minimum node.
	 * @return The minimum node in the subtree.
	 */
	private BinNodeADT<Key, Elem> getMin(BinNodeADT<Key, Elem> root) {
		if (root.left() == null) {
			return root;
		} else {
			return getMin(root.left());
		}
	}

	/**
	 * Helper for the remove method.
	 * 
	 * @param node
	 *            The subtree to remove the minimum from.
	 * @return The node that was removed.
	 */
	private BinNodeADT<Key, Elem> deleteMin(BinNodeADT<Key, Elem> node) {
		if (node.left() == null)
			return node.right();

		else {
			node.setLeft(deleteMin(node.left()));
			return node;
		}
	}

	public Elem removeAny() {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * Returns the size of this tree.
	 */
	public int size() {
		// TODO Auto-generated method stub
		return nodeCount;
	}

	/**
	 * Draws the tree in a post-order traversal. Draws each node at the proper
	 * place, using the BST's TreePanel.
	 * 
	 * @param g	The graphics to draw on.
	 * @param recalc	If the tree should be recalculated.
	 * @param draw		If the tree should be redrawn
	 */
	public void drawPostOrder(Graphics g, boolean recalc, boolean draw) {
		traversePostOrder(root, 0, 0, g, recalc, draw);
	}

	/**
	 * Recursive helper for drawing the tree.
	 * @param node	The node to draw/traverse
	 * @param x		The "abstract x" of the current node.
	 * @param y		The "abstract y" of the current node.
	 * @param g		The graphics to draw on.
	 * @param recalcPos		If the tree should be recalculated
	 * @param draw			If the tree should be drawn.
	 */
	private void traversePostOrder(BinNodeADT<Key, Elem> node, int x, int y,
			Graphics g, boolean recalcPos, boolean draw) {

		if (node == null) {
			return;
		}
		traversePostOrder(node.left(), x * 2, y + 1, g, recalcPos, draw);
		traversePostOrder(node.right(), x * 2 + 1, y + 1, g, recalcPos, draw);
		visit(node, x, y, g, recalcPos, draw);

		if (node.left() != null
				&& !((GraphicalNode) node.left().val()).isHidden()) {
			g.setColor(Color.BLACK);
			GraphicalNode n = (GraphicalNode)node.left().val();
			GraphicalNode parent = (GraphicalNode)node.val();
			g.drawLine(parent.getX() + (GraphicalNode.NODE_WIDTH / 2), parent.getY() + GraphicalNode.NODE_HEIGHT, n.getX() + (GraphicalNode.NODE_WIDTH / 2), n.getY());//, g);
		}
		if (node.right() != null
				&& !((GraphicalNode) node.right().val()).isHidden()) {
			g.setColor(Color.BLACK);
			GraphicalNode n = (GraphicalNode)node.right().val();
			GraphicalNode parent = (GraphicalNode)node.val();
			g.drawLine(parent.getX() + (GraphicalNode.NODE_WIDTH / 2), parent.getY() + GraphicalNode.NODE_HEIGHT, n.getX() + (GraphicalNode.NODE_WIDTH / 2), n.getY());//, g);
		}
		

		
	}

	/**
	 * Visit the specified node.
	 * @param node	The node to visit.
	 * @param x		The x position of the node.
	 * @param y		The y position of the node.
	 * @param g		The graphics to draw on
	 * @param recalcPos	Recalculate the tree?
	 * @param draw		Redraw the tree?
	 */
	private void visit(BinNodeADT<Key, Elem> node, int x, int y, Graphics g,
			boolean recalcPos, boolean draw) {
		// System.out.println("Evaluating node " + node.key());
		GraphicalNode curr = (GraphicalNode) node.val();
		if (recalcPos) {
			System.out.println("Recalculating node positions");
			curr.setXPos(treePanel.getPhysicalX(x, y));
			curr.setYPos(y * TreePanel.NODE_VERTICAL_DISTANCE);

			curr.setAbstractX(x);
			curr.setAbstractY(y);
		}

		if (draw) {
			System.out.println("BST Drawing: " + curr);
			curr.draw(g);
		}
	}


}