/**
 *  BSTNode is a BST node that uses Java Strings as keys 
 * and can hold any Java Objects as values (or "data")
 * These data values are the information being "looked up"
 * via the keys... .
 * 
 * These nodes are modeled after Racket (and Prolog) BSTs, 
 * in which a single BST was never modified -- rather, new
 * BSTs were created as return values in Racket 
 * (or bound to variables in Prolog)
 * 
 * The typical properties of Binary Search Trees (BSTs) hold for 
 * every BSTNode in this structure:
 * 
 *   - 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 *
 *   
 *   Please do put your login, the login of a pair-programmer, if any,
 *   as well as any thoughts/comments:
 *    
 *   @author
 *   
 *   Notes/comments:
 *   
 */

// Template updated: 2014/03/31

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
   * This means that *one* emptyNode is owned by the _class_ BSTNode,
   *   rather than having separate ones for each tree. This single
   *   one is simply shared across all empty leaves!
   * This saves LOTS of memory!!
   */
  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.
   * @param key, a String by which the value is looked up
   * @param value, an Object that's looked up by the key
   */
  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.
   * @param key, a String by which the value is looked up
   * @param value, an Object that's looked up by the key
   * @param left, an object of type BSTNode to be the left subtree
   * @param right, an object of type BSTNode to be the right subtree
   */
  public BSTNode(String key, Object value, BSTNode left, BSTNode right) {
    this(key,value);  // calls the above constructor!
    this.left = left;
    this.right = right;
  }

  /**
   * nonstatic version of isEmpty
   * @return true or false, whether this is empty!
   */
  public boolean isEmpty() {
    return this == BSTNode.emptyNode;
  }
  
  /**
   * static version of isEmpty
   * @param N, a BSTNode we're checking for emptiness!
   * @return true or false, whether this is empty!
   */
  public static boolean isEmpty(BSTNode N) {
    return N.isEmpty();  // delegating to the nonstatic version :-)
    // alternatively, we could
    // return N == BSTNode.emptyNode;
  }

  /**
   * access method to inspect the private instance variable key 
   * nonstatic version!
   * @return the value of the key of this BSTNode
   */
  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 key 
   * static version!
   * @return the value of the key of this BSTNode
   */
  public static String key(BSTNode N) {
    return N.key(); // delegation is key here!
  }

  /**
   * access method to inspect the private instance variable value 
   * static version!
   * @param N, the BSTNode whose value will be returned
   * @return the value of the value (indeed!) of this BSTNode
   */
  public static Object value(BSTNode N) {
    if (N.isEmpty()) {
      System.out.println("You can't call value on an empty BSTNode!");
      System.exit(0);
    }
    return N.value;
  }
  
  /**
   * access method to inspect the private instance variable value 
   * nonstatic version!
   * @return the value of the value (indeed!) of this BSTNode
   */
  public Object value() {
    return BSTNode.value(this); // as long as you don't object ;^) 
                                // to delegating this to the nonstatic f'n
  }

  /**
   * access method to inspect the private instance variable left 
   * nonstatic method
   * @return the value of the left child of this BSTNode
   */
  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 left 
   * *static* method
   * @param N, the tree whose left child will be returned
   * @return the value of the left child of this BSTNode
   */
  public static BSTNode left(BSTNode N) {
    // TODO -- write static version of left
    return null;
  }

  /**
   * access method to inspect the private instance variable right 
   * static method
   * @param N, the BSTNode whose right child will be returned
   * @return the value of the right child of this BSTNode
   */
  public static BSTNode right(BSTNode N) {
    if (N.isEmpty()) {
      System.out.println("You can't call right on an empty BSTNode!");
      System.exit(0);
    }
    return N.right;
  }
  
  /**
   * access method to inspect the private instance variable right 
   * *nonstatic* method
   * @param N, the BSTNode whose right child will be returned
   * @return the value of the right child of this BSTNode
   */
  public BSTNode right() {
    // TODO -- write the nonstatic right right (right!)
    return null;
  }

  /**
   * 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
   * @return the String at the min of this BSTNode
   */
  public String min() {
    if (this.isEmpty()) {
      return "";
    } else if (this.left().isEmpty()) {
      return this.key();
    } else {
      return this.left.min();
    }
  }
  
  /**
   * static 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
   * @param N, the BSTNode whose min will be returned
   * @return the String at the min of this BSTNode
   */
  public static String min(BSTNode N) {
    // TODO - write static min
    return null;
  }

  /**
   * Returns the value associated with the argument key. Prints
   * "Object not found" and returns null if the key is not found within the
   * tree.
   * @param input_key, the key to check
   * @param N, the BSTNode in which to check for input_key
   * @result the Object (value) associated with input_key in N
   * 
   * static version
   */
  public static Object find(String input_key, BSTNode N) {
    if (N.isEmpty()) { // not found
      System.out.println("Object not found");
      return null;
    }

    int compareToResult = N.key().compareTo(input_key);

    if (compareToResult == 0) {       // found!
      return N.value();
    } else if (compareToResult < 0) { // check the right
      return BSTNode.find(input_key, right(N));
    } else {                          // check the left
      return BSTNode.find(input_key, N.left());
    }
  }
  
  /**
   * Returns the value associated with the argument key. Prints
   * "Object not found" and returns null if the key is not found within the
   * tree.
   * @param input_key, the key to check within this
   * @result the Object (value) associated with input_key in N
   * 
   * *nonstatic* version
   */
  public Object find(String input_key) {
    // TODO - nonstatic find
    return null;
  }
  
  /** remove_min
   * 
   * Removes the minimum from the tree, returning a WHOLE NEW tree
   *   -- the same as this, but without the minimum in this
   * If this tree is empty, it returns the empty tree.
   * 
   * No BSTNodes should be harmed by calling this method!
     *
   * the *nonstatic* version
   * 
   * @result a new tree, identical to this, except that the minimum
   *         element is removed
   */
  public BSTNode remove_min() {
    if (this.isEmpty()) {
      return BSTNode.emptyNode;
    }
    else if (this.left.isEmpty()) {
      return this.right;  // the root is the min - get rid of it!
    }
    else {
      BSTNode new_right = this.right;
      BSTNode new_left = this.left.remove_min();
      return new BSTNode(this.key, this.value, new_left, new_right);
    }
  }
  
  /** remove_min
   * 
   * Removes the minimum from the tree, returning a WHOLE NEW tree
   *   -- the same as this, but without the minimum in this
   * If this tree is empty, it returns the empty tree.
   * 
   * No BSTNodes should be harmed by calling this method!
     *
   * the *static* version - feel free to delegate to the other!
   * 
   * @param N, the tree whose min should be removed (non-destructively)
   * @result a new tree, identical to this, except that the minimum
   *         element is removed
   */
  public static BSTNode remove_min(BSTNode N) {
    // TODO - write static remove_min
    return null;
  }

  /**
   * 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.
   * 
   * This is the *nonstatic* version
   * 
   * No BSTNodes are modified (or harmed) by calling insert.
   * 
   * @param new_key, the key to be inserted
   * @param new_value, the value that that key will look up
   * @return a completely new BSTNode in which no old data (or references)
   *         get clobbered -- same as this, but with the new node
   */
  public BSTNode insert(String new_key, Object new_value) {
    // TODO - write nonstatic insert
    return null; 
  }
  
  /**
   * 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.
   * 
   * This is the *static* version  (feel free to delegate one way or the other)
   * 
   * No BSTNodes are modified (or harmed) by calling insert.
   * 
   * @param new_key, the key to be inserted
   * @param new_value, the value that that key will look up
   * @param old_tree, the old object of type BSTNode that is the
   *        basis for the new object to be constructed and returned
   * @return a completely new BSTNode in which no old data (or references)
   *         get clobbered -- same as old_tree, but with the new node
   */
  public static BSTNode insert(String new_key, Object new_value,
                           BSTNode old_tree) {
    // TODO - write static insert
    return null; 
  }

  /**
   * 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  copy or the same reference).
   * 
   * This is the *nonstatic* version (feel free to delegate one way or the other)
   * 
   * No BSTNodes are modified (or clobbered) by calling delete.
   * 
   * @param key_to_go, the key of the BSTNode that should be deleted, if present
   * @return a completely new BSTNode in which no old data (or references)
   *         get clobbered -- same as this, but without key_to_go's node
   */
  public BSTNode delete(String key_to_go) {
    // TODO - write the nonstatic version of delete
    return null; 
  }
  
  
  /**
   * 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  copy or the same reference).
   * 
   * This is the *static* version (feel free to delegate one way or the other)
   * 
   * No BSTNodes are modified (or clobbered) by calling delete.
   * 
   * @param key_to_go, the key of the BSTNode that should be deleted, if present
   * @param old_tree, the tree from which that node should be deleted
   * @return a completely new BSTNode in which no old data (or references)
   *         get clobbered -- same as this, but without key_to_go's node
   */
  public static BSTNode delete(String key_to_go, BSTNode N) {
    // TODO - write the static version of delete
    return null; 
  }
  
  // ------------------ other helper methods -- no need to change -------------------

  /**
   * equals allows comparisons between this BSTNode and another object by
   * "deep" comparison, i.e., structural comparison, 
   * rather than "shallow" or reference comparison, which is ==
   * @param o, any Java Object
   * @return true or false, depending if o is both of type BSTNode
   *         and has the same structure as this
   */
  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
          right(other_tree).equals(right(this)); // 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
   * @return the String representation of this BSTNode
   */
  public String toString() {
    return "[" + this.printItems() + "]";
  }

  /**
   * printItems returns a string representing all of the items rooted at
   * "this" BSTNode
   * @return the String representation of the internal items
   *         of this BSTNode
   */
  private String printItems() {
    if (this.isEmpty()) {
      return "";
    }
    return "(" + this.key() + "," 
               + this.value() + ")" 
               + this.left().toString()
           + right(this).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);
    right(this).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);
  }
}