/**
 *
 * @author Stephen Colegrove
 *
 * @param <Key>
 * @param <Value>
 */
public class MyBinarySearchTree< Key extends Comparable< Key >, Value extends Comparable< Value > > implements BinarySearchTreeInterface< Key , Value> {

	private Node root = null;
	private Node current = root;

	private int size = 0;

	private class Node{

		private Node parent;
		private Node leftChild;
		private Node rightChild;
		public KeyValuePair<Key, Value> theData;


		//constructor?
		public Node(KeyValuePair<Key, Value> data){


			theData = data;
			parent = null;
			leftChild = null;
			rightChild = null;
		}

		//getters
		public Key getKey(){

			return theData.getKey();

		}

		public Value getValue(){

			return theData.getValue();
		}


		public Node getParent(){

			return parent;
		}

		public Node getLeftChild(){

			return leftChild;
		}

		public Node getRightChild(){

			return rightChild;
		}

		//setters
		public void setKey(Key k ){
			theData.setKey(k);
		}

		public void setValue(Value v){
			theData.setValue(v);
		}

		public void setParent(Node n){

			parent = n;
		}

		public void setleftChild(Node n){

			leftChild = n;
		}

		public void setRightChild(Node n){

			leftChild = n;
		}

		//sanity checks

		public boolean hasLeftChild(){

			return leftChild == null;
		}

		public boolean hasRightChild(){

			return rightChild == null;
		}

	}


	// Return the value at the tree node indicated by the key.
	// If none exists, return null;
	public Value get( Key key ) {

		if(this.isEmpty()){
			return null;
		}

		if(root.getKey().compareTo(key) == 0){
			return root.getValue();
		}

		if(current.hasLeftChild()){
			if(key.compareTo(current.getKey()) < 0){
				current = current.leftChild;
			}
			//current.setleftChild(current);

			return get(current.getLeftChild().getKey());

		} else {

			if(current.hasRightChild())
				return get(current.getRightChild().getKey());

		}



		return null;
	}
	//To do
	public Value getHelp(Key key, Node currentNode){





		return null;

	}

	// Insert or replace the value at the tree node indicated by key.
	// Return the previous value or null if none existed.
	public Value put( Key key, Value value ) {

		Node temp = root;

		if (root == null) {
			//make new node
			KeyValuePair<Key,Value> pair = new KeyValuePair<Key,Value>();
			pair.setKey(key);
			pair.setValue(value);
			temp = new Node(pair);
			size++;
			root = temp;
			return null;
		}

		if(key.compareTo(current.getKey()) < 0){
			if(current.hasLeftChild()){

			}


		}
		return value;
	}

	// Remove the tree node indicated by key.
	// Return the previous value or null if none existed.
	public Value remove( Key key ) {
		return null;
	}

	// Return the list of KeyValuePairs produced by a pre-order traversal of the tree.
	// Return an empty list of the tree is empty.
	public List<KeyValuePair<Key,Value>> preOrderTraversal( ) {
		return null;
	}

	// Return the list of KeyValuePairs produced by an in-order traversal of the tree.
	// Return an empty list of the tree is empty.
	public List<KeyValuePair<Key,Value>> inOrderTraversal( ) {
		return null;
	}

	// Return the list of KeyValuePairs produced by a post-order traversal of the tree.
	// Return an empty list of the tree is empty.
	public List<KeyValuePair<Key,Value>> postOrderTraversal( ) {
		return null;
	}

	// Return an array of KeyValuePairs produced by a breadth-first traversal of the tree.
	// Return an empty array of the tree is empty.
	// Missing children should be represented by a null entry in the array.
	public KeyValuePair< Key, Value > [ ] breadthFirstTraversal( ) {
		return null;
	}

	// Returns the number of nodes in tree.
	public int getSize( ) {

		return size;
	}

	// Return true if there are no nodes in the tree
	public boolean isEmpty( ) {
		if(size == 0){
			return true;
		}

		return false;
	}

	// Return a String representation of the tree.
	// Nodes should be ordered as if by breadth-first traversal.
	public String toString( ) {
		return null;
	}

}