import java.util.Iterator;

/*
 * YOU MUST FILL IN THE CODE FOR THE FOLLOWING FOUR METHODS:
 * - addPresidentIteratively
 * - calculateAverageYearsIteratively
 * - removeRootIteratively
 * - removeRootRecursively
 */
public class PresidentBinarySearchTree {
	// ROOT FOR OUR TREE
	public TreeNode root = null;

	// TOTAL NUMBER OF NODES IN THE TREE
	public int size = 0;

	/*
	 * Default constructor, it does nothing
	 */
	public PresidentBinarySearchTree() {
	}

	// ACCESSOR METHOD
	public int size() {
		return size;
	}

	/*
	 * YOU MUST DEFINE THIS METHOD
	 * 
	 * This method adds a the president argument to the correct sorted location
	 * in the BST using iteration, not recursion.
	 */
	public void addPresidentIteratively(President president) {
		// CASE: EMPTY TREE
		if (root == null) {
			// MAKE IT THE ROOT, THE ONE AND ONLY NODE
			root = new TreeNode(president, null, null, null);
			size++;
		} else {
			TreeNode node = root;
			boolean nodeAdded = false;
			while (!nodeAdded) {
				// NOW WE NEED TO FIND THE RIGHT PLACE
				// TO PUT IT, STARTING WITH THE ROOT
				int comparison = president.compareTo(node.data);

				// NO DUPLICATES
				if (comparison == 0)
					return;

				// ADD TO LEFT SUBTREE
				if (comparison < 0) {
					if (node.leftNode == null) {
						node.leftNode = new TreeNode(president, node, null,
								null);
						nodeAdded = true;
						size++;
					} else
						node = node.leftNode;
				}
				// ADD TO RIGHT SUBTREE
				else {
					if (node.rightNode == null) {
						node.rightNode = new TreeNode(president, node, null,
								null);
						nodeAdded = true;
						size++;
					} else
						node = node.rightNode;
				}
			}
		}
	}

	/*
	 * YOU MUST DEFINE THIS METHOD
	 * 
	 * This method should go through the tree and calculate and return the
	 * average number of years in office for each presidency. This method must
	 * do so iteratively.
	 */
	public double calculateAverageYearsIteratively() {
		if (size == 0)
			return 0.0;

		TreeNode node = root;
		double sum = 0;
		int maxIndex = -1;
		int count = 0;

		while (count < size) {
			if (node.data.getNumber() > maxIndex) {
				if (node.leftNode == null) {
					sum += node.data.calculateYearsInOffice();
					maxIndex = node.data.getNumber();
					count++;
				} else if (node.leftNode.data.getNumber() <= maxIndex) {
					sum += node.data.calculateYearsInOffice();
					maxIndex = node.data.getNumber();
					count++;
				} else {
					node = node.leftNode;
				}
			} else {
				if (node.rightNode != null) {
					if (node.rightNode.data.getNumber() > maxIndex)
						node = node.rightNode;
					else if (node == root) {
						if (node.rightNode != null)
							node = node.rightNode;
					} else
						node = node.parentNode;
				} else if (node == root) {
					if (node.rightNode != null)
						node = node.rightNode;
				} else
					node = node.parentNode;
			}
		}
		return sum / size;
	}

	/*
	 * YOU MUST DEFINE THIS METHOD
	 * 
	 * This method should remove the root node from the tree. To do this you'll
	 * have to promote one of the root node's descendants. If the root has 1
	 * child, promote that child, else promote the right most node on the root
	 * node's left subtree.
	 * 
	 * For this method you must do this promotion iteratively.
	 */
	public President removeRootIteratively() {
		if (size == 0)
			return null;
		President pToReturn = root.data;
		if (size == 1) {
			root = null;
		}
		// PROMOTE RIGHT NODE TO ROOT
		else if (root.leftNode == null) {
			root = root.rightNode;
			root.parentNode = null;
		}
		// PROMOTE LEFT NODE TO ROOT
		else if (root.rightNode == null) {
			root = root.leftNode;
			root.parentNode = null;
		}
		// GET THE RIGHT MOST NODE ON THE LEFT
		else {
			TreeNode node = root.leftNode;
			// PROMOTE LEFT NODE
			if (node.rightNode == null) {
				node.rightNode = root.rightNode;
				node.parentNode = null;
				root = node;
				node.rightNode.parentNode = node;
			} else {
				while (node.rightNode != null) {
					node = node.rightNode;
				}
				// PROMOTE THIS TO THE HEAD
				root.data = node.data;
				if (node.leftNode == null) {
					node.parentNode.rightNode = null;
				} else {
					node.parentNode.rightNode = node.leftNode;
					node.leftNode.parentNode = node.parentNode;
				}
			}
		}
		size--;
		return pToReturn;
	}

	/*
	 * YOU MUST DEFINE THIS METHOD
	 * 
	 * This method should remove the root node from the tree. To do this you'll
	 * have to promote one of the root node's descendants. If the root has 1
	 * child, promote that child, else promote the right most node on the root
	 * node's left subtree.
	 * 
	 * For this method you must do this promotion iteratively.
	 */
	public President removeRootRecursively() {
		if (size == 0)
			return null;
		President pToReturn = root.data;
		if (size == 1) {
			root = null;
		}
		// PROMOTE RIGHT NODE TO ROOT
		else if (root.leftNode == null) {
			root = root.rightNode;
			root.parentNode = null;
		}
		// PROMOTE LEFT NODE TO ROOT
		else if (root.rightNode == null) {
			root = root.leftNode;
			root.parentNode = null;
		} else {
			// RECURSIVELY FIND LEFTMOST ON RIGHT
			pToReturn = getLeftmostPresident(root.rightNode);
		}
		size--;
		return pToReturn;
	}

	/*
	 * A helper method for removeRootRecursively, this method gets the left most
	 * node on the right.
	 */
	public President getLeftmostPresident(TreeNode node) {
		if (node.leftNode != null) {
			return getLeftmostPresident(node.leftNode);
		} else {
			// GET THAT DATA TO RETURN
			President p = node.data;

			// NOW REMOVE THIS NODE FROM THE TREE
			// BUT WHAT KIND OF NODE IS IT?

			// IF IT'S A CHILD NODE OF THE ROOT,
			if (node.parentNode.rightNode == node) {
				node.parentNode.rightNode = node.rightNode;
			}
			// ELSE IT'S PARENT IS NOT THE ROOT
			else {
				node.parentNode.leftNode = node.rightNode;
			}
			if (node.rightNode != null)
				node.rightNode.parentNode = node.parentNode;
			return p;
		}
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method demonstrates how to add a node into a BST using a recursive
	 * solution.
	 */
	public void addPresidentRecursively(President presidentToAdd) {
		if (root == null) {
			root = new TreeNode(presidentToAdd, null, null, null);
			size++;
		} else
			addPresidentToNode(root, presidentToAdd);
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This is the recursive helper method for adding a node to the tree.
	 */
	void addPresidentToNode(TreeNode node, President presidentToAdd) {
		if (node.data.equals(presidentToAdd))
			return;
		if (node.data.compareTo(presidentToAdd) > 0) {
			if (node.leftNode == null) {
				node.leftNode = new TreeNode(presidentToAdd, node, null, null);
				size++;
			} else
				addPresidentToNode(node.leftNode, presidentToAdd);
		} else {
			if (node.rightNode == null) {
				node.rightNode = new TreeNode(presidentToAdd, node, null, null);
				size++;
			} else
				addPresidentToNode(node.rightNode, presidentToAdd);
		}
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method calculates the average number of years in office for all the
	 * presidents currently in the tree.
	 */
	public double calculateAverageYearsRecursively() {
		if (root == null)
			return 0;
		else
			return sumPre(root) / size;
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This is a recursive helper method for the calculateAverageRecursively
	 * method.
	 */
	public double sumPre(TreeNode node) {
		double sum = node.data.calculateYearsInOffice();
		if (node.leftNode != null)
			sum += sumPre(node.leftNode);
		if (node.rightNode != null)
			sum += sumPre(node.rightNode);
		return sum;
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method rearranges the nodes so as to minimize the height of the tree
	 * and to balance the tree on right and left sides. Again, might want to
	 * think about using a recursive helper method.
	 */
	public void rebalance() {
		if (size > 0) {
			SortedIterator it = (SortedIterator) treeIterator();
			int min = 0;
			int max = it.elements.length - 1;
			root = rebalanceNode(it.elements, null, min, max);
		}
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This is a recursive helper method for the rebalance method.
	 */
	private TreeNode rebalanceNode(President[] elements, TreeNode parent,
			int min, int max) {
		if (min == max)
			return new TreeNode(elements[min], parent, null, null);
		else {
			int middle = (int) Math.ceil(((double) min + (double) max) / 2.0);
			TreeNode node = new TreeNode(elements[middle], parent, null, null);
			if (min < middle) {
				node.leftNode = rebalanceNode(elements, node, min, middle - 1);
			}
			if (max > middle) {
				node.rightNode = rebalanceNode(elements, node, middle + 1, max);
			}
			return node;
		}
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method empties the tree of all nodes.
	 */
	public void clear() {
		root = null;
		size = 0;
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method produces an iterator that produces elements in sorted order.
	 */
	public Iterator treeIterator() {
		return new SortedIterator();
	}

	/*
	 * DO NOT CHANGE THIS CLASS
	 * 
	 * This iterator produces data from the tree in sorted order.
	 */
	class SortedIterator implements Iterator {
		protected President[] elements = new President[size];
		protected int currentElement = 0;

		public SortedIterator() {
			if (root != null) {
				fillIteratorElements(root);
				currentElement = 0;
			}
		}

		private void fillIteratorElements(TreeNode node) {
			if (node.leftNode != null)
				fillIteratorElements(node.leftNode);
			elements[currentElement] = node.data;
			currentElement++;
			if (node.rightNode != null)
				fillIteratorElements(node.rightNode);
		}

		public boolean hasNext() {
			if ((size > 0) && (currentElement < size))
				return true;
			else
				return false;
		}

		public Object next() {
			if ((size > 0) && (currentElement < size))
				return elements[currentElement++];
			else
				return null;
		}

		public void remove() {
		}
	}

}

/*
 * DO NOT CHANGE THIS CLASS
 * 
 * This will be used to represent all nodes in our tree.
 */
class TreeNode {
	protected President data;
	protected TreeNode parentNode;
	protected TreeNode leftNode;
	protected TreeNode rightNode;

	public TreeNode(President initData, TreeNode initParent,
			TreeNode initLeftNode, TreeNode initRightNode) {
		data = initData;
		parentNode = initParent;
		leftNode = initLeftNode;
		rightNode = initRightNode;
	}
}