import java.util.Iterator;

/*
 * YOU MUST FILL IN THE CODE FOR THE FOLLOWING TWO METHODS:
 * - calculateTreeLevels 
 * - rebalance
 */

public class DJIABinarySearchTree
{
	// ROOT FOR OUR TREE
	private TreeNode root = null;
	
	// TOTAL NUMBER OF NODES IN THE TREE
	private int size = 0;
	
	/*
	 * Default constructor, it does nothing
	 */
	public DJIABinarySearchTree() {}
	

	// ACCESSOR METHOD
	public int size() { return size; }
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method adds a company to the correct sorted location
	 * in the BST by employing the recursive addCompanyToNode method.
	 */
	public void addCompany(DJIACompany initCompany)
	{
		// CASE: EMPTY TREE
		if (root == null)
		{
			// MAKE IT THE ROOT, THE ONE AND ONLY NODE
			root = new TreeNode(initCompany, null, null);
			size++;
		}
		else
		{
			// addCompanyToNode WILL FIND THE PLACE TO PUT IT,
			// STARTING WITH THE ROOT
			addCompanyToNode(root, initCompany);
		}
	}
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method recursively searches for the appropriate
	 * place in this BST to add the company.
	 */
	private void addCompanyToNode(TreeNode node, DJIACompany initCompany)
	{
		// NO DUPLICATES
		if (node.data.getSymbol().equals(initCompany.getSymbol()))
			return;
		
		// ADD TO LEFT SUBTREE
		if (node.data.getSymbol().compareTo(initCompany.getSymbol()) > 0)
		{
			// ADD IT AS A LEAF, WE CAN'T GO ANY FURTHER LEFT
			if (node.leftNode == null)
			{
				node.leftNode = new TreeNode(initCompany, null, null);
				size++;
			}
			else
			{
				// TRY FURTHER LEFT
				addCompanyToNode(node.leftNode, initCompany);
			}
		}
		// ADD TO RIGHT SUBTREE
		else
		{
			// ADD IT AS A LEAF, WE CAN'T GO ANY FURTHER RIGHT
			if (node.rightNode == null)
			{
				node.rightNode = new TreeNode(initCompany, null, null);
				size++;
			}
			else
			{
				// TRY FURTHER RIGHT
				addCompanyToNode(node.rightNode, initCompany);
			}
		}
	}

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

	/*
	 * YOU MUST DEFINE THIS METHOD
	 * 
	 * It calculates the level of the deepest node in the tree. Note,
	 * if the tree only has a root, then it only has one level.
	 * 
	 * ADVICE: Look at how I recursively defined the addCompanyToNode
	 * method. You might want to try to do something like that for this as well.
	 */
	public int calculateTreeLevels()
	{
// ADD YOUR CODE HERE
	}
	
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method is used for rendering purposes. It's used to calculate
	 * the position of each node such that we get a nice, aligned looking
	 * tree.
	 */
	public int calculateTreeIndex(DJIACompany company)
	{
		return calculateTreeIndex(root, company, 0);
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method is a recursive helper to calculateTreeIndex
	 */
	private int calculateTreeIndex(TreeNode node, DJIACompany company, int index)
	{
		if (node == null)
			return -1;
		int comparison = node.data.getSymbol().compareTo(company.getSymbol());
		if (comparison == 0)
			return index;
		else if (comparison > 0)
		{
			int leftIndex = (2 * index) + 1;
			return calculateTreeIndex(node.leftNode, company, leftIndex); 
		}
		else
		{
			int rightIndex = (2 * index) + 2;
			return calculateTreeIndex(node.rightNode, company, rightIndex);
		}
	}

	/*
	 *	YOU MUST DEFINE THIS METHOD
	 *
	 * 	This method should rearrange the node 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()
	{
// YOUR CODE GOES HERE
	}
	
	
	/*
	 * 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 DJIACompany[] elements = new DJIACompany[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(){}
	}
}

class TreeNode
{
	protected DJIACompany data;
	protected TreeNode leftNode;
	protected TreeNode rightNode;
	
	public TreeNode(DJIACompany initData,
					TreeNode initLeftNode,
					TreeNode initRightNode)
	{
		data = initData;
		leftNode = initLeftNode;
		rightNode = initRightNode;
	}
}