/**
 ******************************************************************************
 *                    HOMEWORK:  15-121
 ******************************************************************************
 *                    Text concordance program
 ******************************************************************************
 *
 * This is a general binary search tree that can store any comparable objects.
 *
 * Your implementaion must be as general as possible and should not have any
 * references to the Word objects.
 *
 * @author
 * @date
 *****************************************************************************/
 /*****************************************************************************

                         IMPLEMENT THIS CLASS

 *****************************************************************************/

import java.util.*;


public class BSTConcordance<AnyType extends Comparable<AnyType>> implements Iterable<AnyType>
{
	private Comparator<AnyType> comparator;
   private BSTNode<AnyType> root;

 /* additional field variables are NOT allowed   */


 /**
	* Creates a BST that orders its elements according
	* to their natural ordering (using Comparable).
	*/
   public BSTConcordance()
   {
      this(null);
   }

 /**
	* Creates a BST that orders its elements according to
	* the specified comparator.
	*
	* The comparator used to order this tree.
	* If it's null, then the order depends on the elements'
	* natural ordering.
	*/
	public BSTConcordance(Comparator<AnyType> comparator)
	{
		this.comparator = comparator;
		root = null;
	}

 /**
	* Returns the comparator used to order this collection.
	*
	*/
	public Comparator<AnyType> comparator()
	{
		return comparator;
	}

 /**
	* Returns the root of this tree.
	*
	*/
	public BSTNode<AnyType> getRoot()
	{
		return root;
	}

 /**
	* Returns the height of this tree
	*
	*/
	public int getHeight()
	{
		throw new RuntimeException ("You need to implement this method");
	}

 /**
	* Returns the number of nodes in this tree.
	*
	*/
	public int getNumberOfNodes()
	{
		throw new RuntimeException ("You need to implement this method");
	}

 /**
	* Searches for the specified word
	*
	*/
   public AnyType search(AnyType toSearch)
   {
		throw new RuntimeException ("You need to implement this method");
   }

 /**
	* Inserts the specified element into this tree.
	*
	*/
	public void insert(AnyType toInsert)
	{
		throw new RuntimeException ("You need to implement this method");
   }

	/*******************************************************
	*
	*  The private Node class
	*
	********************************************************/

	private static class BSTNode<AnyType>
	{
		private AnyType data;          //the Word object
		private BSTNode<AnyType> left;
		private BSTNode<AnyType> right;

		public BSTNode(AnyType data)
		{
			this(data, null, null);
		}

		public BSTNode(AnyType data, BSTNode<AnyType> lt, BSTNode<AnyType> rt)
		{
			this.data = data;
			left  = lt;
			right = rt;
		}

		public String toString()
		{
			return data.toString();
		}
	}

	/*****************************************************
	*
	*            TREE ITERATOR - INORDER
	*
	******************************************************/

   public Iterator<AnyType> iterator()
   {
      return new InOrderIterator();
   }


	/* Implement the InOrderIterator class here  */



	/*****************************************************
	*
	*       Include main() for debug purposes
	*
	******************************************************/


	public static void main(String[] args)
	{
		BSTConcordance<Integer> b = new BSTConcordance<Integer>();
		int[] ar = {31, 16, 49, 5, 18, 51, 4, 13, 17, 19, 8};

		for(Integer x : ar) b.insert(x);

		Iterator itr = b.iterator();
		while( itr.hasNext() )
			System.out.print( itr.next() + " ");

		System.out.println(  );

	}
}