// BSTNode.java
// Name:
// 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: 2012/10/13

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, which is similar to isEmpty in OpenList
   */
  public boolean isEmpty()
  {
    return this.key == null && this.value == null;
  }
  
  
  /*
   * 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);
    
    
    /*
     * Once you've written insert, bring these lines
     * back into main to test your insert method...
     */
    /*
    BSTNode tree2 = tree1.insert("nickel", 5);
    BSTNode tree3 = tree2.insert("quarter", 25);
    BSTNode tree4 = tree3.insert("penny", 1);
    BSTNode tree5 = tree4.insert("acorn", 0);
    System.out.println(tree4);
    tree4.prettyPrint();
    System.out.println(tree4.find("penny"));
    System.out.println(tree4.find("nickel"));
    System.out.println(tree4.find("dime"));
    System.out.println(tree4.find("quarter"));
    */
    
    /*
     * Once you've written delete, bring these lines
     * back into main to test your delete method...
     */
    /*
    BSTNode no_dime = tree5.delete( "dime" );
    no_dime.prettyPrint();
    BSTNode no_nickel = no_dime.delete( "nickel" );
    no_nickel.prettyPrint();
    BSTNode no_q = no_nickel.delete( "quarter" );
    no_q.prettyPrint();
    */
  }
}