// BSTNode.java
// Login:
// Date:

/* BSTNode is a BST node that uses Java Strings as keys and
 * can hold any Java Objects as data (a.k.a values associated with
 * the keys.) 
 * 
 * These nodes are modeled after Racket BSTs, in which a BST is 
 * never modified.
 * 
 * The typical properties of Binary Search Trees (BSTs) hold for 
 * every BSTNode in this stucture:
 * 
 *   - every BSTNode except emptyNode has 0, 1, or 2 _non-empty_ children.
 *   - every BSTNode except emptyNode has 2 children which are valid BSTNodes
 *   - emptyNode is a special object of type BSTNode representing the empty BST
 * 
 *   - the key of a BSTNode is less than every key in its right subtree.
 *   - the key of a BSTNode is greater than every key in its left subtree.
 *   - there are no duplicate keys.
 */

// Template updated: 2013/10/28

class BSTNode {

	// the data members are private, only
	// to be accessed by the class itself
	private String key;
	private Object value;
	private BSTNode left;
	private BSTNode right;

	/*
	 * this is _the_ empty BSTNode (i.e. the empty tree) there is only one,
	 * because it is static
	 */
	public static BSTNode emptyNode = new BSTNode(null, null);

	/*
	 * This is the standard constructor for a BSTNode, which creates a new,
	 * single-node BSTNode provided the key and value of that node.
	 */
	public BSTNode(String key, Object value) {
		this.key = key;
		this.value = value;
		this.left = emptyNode;
		this.right = emptyNode;
	}

	/*
	 * Constructs a new BSTNode provided the key and value of that node and
	 * BSTNodes for the left and right children.
	 */
	public BSTNode(String key, Object value, BSTNode left, BSTNode right) {
		this.key = key;
		this.value = value;
		this.left = left;
		this.right = right;
	}

	/*
	 * nonstatic version of isEmpty
	 */
	public boolean isEmpty() {
		return this == emptyNode;
	}

	/*
	 * access method to inspect the private instance variable key nonstatic
	 * method
	 */
	public String key() {
		if (this.isEmpty()) {
			System.out.println("You can't call key on an empty BSTNode!");
			System.exit(0);
		}
		return this.key;
	}

	/*
	 * access method to inspect the private instance variable value nonstatic
	 * method
	 */
	public Object value() {
		if (this.isEmpty()) {
			System.out.println("You can't call value on an empty BSTNode!");
			System.exit(0);
		}
		return this.value;
	}

	/*
	 * access method to inspect the private instance variable left nonstatic
	 * method
	 */
	public BSTNode left() {
		if (this.isEmpty()) {
			System.out.println("You can't call left on an empty BSTNode!");
			System.exit(0);
		}
		return this.left;
	}

	/*
	 * access method to inspect the private instance variable right nonstatic
	 * method
	 */
	public BSTNode right() {
		if (this.isEmpty()) {
			System.out.println("You can't call right on an empty BSTNode!");
			System.exit(0);
		}
		return this.right;
	}

	/*
	 * nonstatic method that finds the minimum key, i.e., alphabetically
	 * earliest, key in the BST rooted at this node We return the empty string
	 * if min is called on the empty BST
	 */
	public String min() {
		if (this.isEmpty()) {
			return "";
		} else if (this.left().isEmpty()) {
			return this.key();
		} else {
			return this.left.min();
		}
	}

	/*
	 * Returns the value associated with the argument key. Prints
	 * "Object not found" and returns null if the key is not found within the
	 * tree.
	 */
	public Object find(String input_key) {
		if (this.isEmpty()) { // not found
			System.out.println("Object not found");
			return null;
		}

		// Find information about String's compareTo here:
		// http://docs.oracle.com/javase/6/docs/api/java/lang/String.html#compareTo(java.lang.String)
		int compareToResult = this.key().compareTo(input_key);

		if (compareToResult == 0) { // found!
			return this.value();
		} else if (compareToResult < 0) { // check the right
			return this.right().find(input_key);
		} else { // check the left
			return this.left().find(input_key);
		}
	}

	/*
	 * Creates new BSTNodes as necessary to return a BSTNode representing the
	 * BST with the key and value inserted as a leaf.
	 * 
	 * If the key already exists in the tree, the structure of the BSTNode that
	 * is returned should be identical to the original BSTNode structure.
	 * 
	 * No BSTNodes are modified by calling insert.
	 */
	public BSTNode insert(String new_key, Object new_value) {
		return null; // Write this :)
	}

	/*
	 * Creates new BSTNodes as necessary to return a BSTNode representing the
	 * BST with the input key removed from the tree (and its corresponding
	 * value).
	 * 
	 * If the key isn't in the tree, the returned tree should have identical
	 * structure to "this" object (it can be the same reference or a copy).
	 * 
	 * No BSTNodes are modified by calling delete.
	 */
	public BSTNode delete(String key_to_go) {
		return null; // fill this one in, too !!
	}

	/*
	 * equals allows comparisons between this BSTNode and another object by
	 * "deep" comparison, i.e., structural comparison, rather than
	 * reference-only comparison, which is ==
	 */
	public boolean equals(Object o) {
		if (o instanceof BSTNode) {
			BSTNode other_tree = (BSTNode) o;
			if (other_tree.isEmpty())
				return this.isEmpty();
			if (this.isEmpty())
				return false; // because other_tree is NOT empty here!
			return other_tree.key.equals(this.key()) && // check keys
					other_tree.value.equals(this.value()) && // check values
					other_tree.left.equals(this.left()) && // check lefts
					other_tree.right.equals(this.right()); // check rights
		} else // not the right type, so we return false
		{
			return false;
		}
	}

	/*
	 * toString is the standard method for converting a Java object to a string
	 * for printing
	 */
	public String toString() {
		return "[" + this.printItems() + "]";
	}

	/*
	 * printItems returns a string representing all of the items rooted at
	 * "this" BSTNode
	 */
	private String printItems() {
		if (this.isEmpty()) {
			return "";
		}
		return "(" + this.key() + "," + this.value() + ")" + this.left().toString()
				+ this.right().toString();
	}

	/*
	 * the public method prettyPrint() works by calling the private
	 * prettyPrint(int level) method to print a nested representation of the BST
	 * rooted at this BSTNode.
	 */
	public void prettyPrint() {
		this.prettyPrint(0);
	}

	/*
	 * Called internally by the public method prettyPrint(). Tracks and prints
	 * the appropriate level of nesting within the BST.
	 */
	private void prettyPrint(int level) {
		for (int i = 0; i < level; i++) {
			System.out.print("    ");
		}

		// if this is a leaf only print []
		if (this.isEmpty()) {
			System.out.println("[]");
			return;
		}

		// otherwise print the key and value as an ordered pair
		System.out.println("[(" + this.key() + "," + this.value() + ")");

		// print children at one level deeper
		this.left().prettyPrint(level + 1);
		this.right().prettyPrint(level + 1);

		// print closing bracket at same indentation
		for (int i = 0; i < level; i++) {
			System.out.print("    ");
		}
		System.out.println("]");
	}

	/*
	 * A main method for testing things out...
	 */
	public static void main(String[] args) {
		BSTNode tree1 = new BSTNode("dime", 10);
		System.out.println("Converted to a String, Tree1 is " + tree1);
		System.out.println();
		System.out.println("When pretty-printing, Tree1 is\n");
		tree1.prettyPrint();
		System.out.println();
		System.out.print("Result of finding \"dime\": ");
		System.out.println(tree1.find("dime"));

		/*
		 * here's a check of equals
		 */
		BSTNode treeBAC = new BSTNode("B", "B value", new BSTNode("A",
				"A value"), // LEFT
				new BSTNode("C", "C value")); // RIGHT
		BSTNode treeBAC2 = new BSTNode("B", "B value", new BSTNode("A",
				"A value"), // LEFT
				new BSTNode("C", "C value")); // RIGHT
		boolean trees_equal_as_references = (treeBAC == treeBAC2);
		boolean trees_equal_as_structures = (treeBAC.equals(treeBAC2));
		System.out.println("trees_equal_as_references is "
				+ trees_equal_as_references);
		System.out.println("trees_equal_as_structures is "
				+ trees_equal_as_structures);
	}
}