//
// BinarySearchTree.java: generic binary search tree with a test-bed main
//
// Compiling from the command line:
//      javac -target 1.8 BinarySearchTree.java
//
// Running from the command line:
//      java -ea BinarySearchTree
//
// Author: Robert W. Hasker
//

import java.util.Stack;
import java.util.Iterator;

public class BinarySearchTree<E extends Comparable<E>> implements Iterable {
   protected static class Node<E>
   {
      protected E data;
      protected Node<E> left, right;
      public Node(E data, Node<E> l, Node<E> r) {
         this.data = data;
         this.left = l;
         this.right = r;
      }
      public Node(E data) {
         this(data, null, null);
      }
   }
   
   protected Node<E> root = null;

   //public BinarySearchTree<E>() { } // nothing to do

   //------------------------------------------------------------
   // erase all nodes from tree
   public void clear() { root = null; }

   //------------------------------------------------------------
   // return true if tree is empty
   public boolean isEmpty() { return root == null; }

   //------------------------------------------------------------
   // return true if TARGET in tree
   public boolean contains(E target) {
      return contains(root, target);
   }

   protected boolean contains(Node<E> current, E target) {
      if ( current == null )
         return false;
      else {
         int cmp = target.compareTo(current.data);
         if ( cmp == 0 )
            return true;
         else if ( cmp < 0 )
            return contains(current.left, target);
         else
            return contains(current.right, target);
      }
   }
         
   //------------------------------------------------------------
   // insert X into tree; does nothing if value already in tree
   public void add(E x)
   {
      if ( root == null )
         root = new Node<>(x);
      else
         add(x, root);
   }

   // precondition: node is not null
   private void add(E x, Node<E> node)
   {
      int cmp = x.compareTo(node.data);

      if ( cmp == 0 )
         return;                   // item already in tree

      else if ( cmp < 0 )
      {
         if ( node.left == null )
            node.left = new Node<>(x);
         else
            add(x, node.left);
      }
      else // x > node.data
      {
         if ( node.right == null )
            node.right = new Node<>(x);
         else
            add(x, node.right);
      }
   }
   
   //------------------------------------------------------------
   // return number of nodes in tree
   public int size() { return size(root); }
   
   protected int size(Node<E> node) {
      if ( node == null )
         return 0;
      else 
         return 1 + size(node.left) + size(node.right);
   }

   //------------------------------------------------------------
   // return level of deepest leaf + 1
   public int height() { 
      return height(root);
   }

   protected int height(Node<E> node) {
      if ( node == null )
         return 0;
      else {
         int left_height = height(node.left);
         int right_height = height(node.right);
         if ( left_height < right_height) 
            return 1 + right_height;
         else
            return 1 + left_height;
      }
   }
   
   // remove item from tree, doing nothing if item not in tree
   public void remove(E item) {
      remove(item, root, null);
   }

   public void remove(E x, Node<E> node, Node<E> parent) {
      if ( node == null )
         // no such entry - do nothing
         return;
      else {
         int cmp = x.compareTo(node.data);
         if ( cmp < 0 )
            remove(x, node.left, node);
         else if ( cmp > 0 )
            remove(x, node.right, node);
         else { // found x
            if ( node.left == null ) {
               // will promote right subtree; works if right is null as well
               if ( parent == null ) // root
                  root = node.right;
               else if ( parent.left == node ) // we are to the left of parent
                  parent.left = node.right;
               else
                  parent.right = node.right;
            }
            else if ( node.right == null ) {
               // promote left subtree
               if ( parent == null ) // root
                  root = node.left;
               else if ( parent.left == node ) // to the left of the parent
                  parent.left = node.left;
               else
                  parent.right = node.left;
            }
            else {
               // have two children, so need to find predecessor
               Node<E> p = node.left, ps_parent = node;
               while ( p.right != null ) {
                  ps_parent = p;
                  p = p.right;
               }
               node.data = p.data;
               // now, need to remove p's data from p's subtree
               remove(p.data, p, ps_parent);
            }
         }
      }
   }

   private static class InorderIterator<E> implements Iterator<E>
   {
      // production code would use a better class than Stack
      private Stack<Node<E>> tovisit = new Stack<>(); // will never push null

      public InorderIterator(Node<E> root) {
         if ( root != null )
            tovisit.push(root);
      }

      public boolean hasNext() { return !tovisit.isEmpty(); }

      public E next() {
         Node<E> node = tovisit.pop();
         // travel down left branch, keeping track of right branches to visit
         while ( node.left != null ) {
            // will visit right after done with rest
            if ( node.right != null )
               tovisit.push(node.right);
            // create temporary node to process this node
            //   this has no children, so we'll finish eventually
            tovisit.push(new Node<>(node.data));
            // now shift down left one
            node = node.left;
         }
         // finally, at a leftmost child, so push any bits remaining
         if ( node.right != null )
            tovisit.push(node.right);
         // and return the node's data
         return node.data;
      }
   }
   
   // return an iterator
   public Iterator<E> iterator() {
      return new InorderIterator<>(root);
   }
   
   // return tree as a string with spaces between elements and brackets
   //    around the whole list (based on an inorder traversal)
   public String toString() {
      Iterator<E> it = this.iterator();
      String result = "[";
      while ( it.hasNext() )
         result += " " + it.next();
      result += " ]";
      return result;
   }

   // run all implemented tests
   public static void main(String[] args) {
      testSimpleTree();
      testIterator();
      testLargerTree();
      testSizeAndHeight();
      System.out.println("All tests passed.");
   }

   // test simple case of adding a single value and then removing it
   private static void testSimpleTree() {
      BinarySearchTree<Integer> x = new BinarySearchTree<>();
      // simple test of primary operations:
      if ( ! x.isEmpty() )
         throw new AssertionError("Initial tree not empty");
      if ( x.contains(8) )
         throw new AssertionError("Mysterious 8 in empty tree");
      x.add(8);
      if ( x.isEmpty() )
         throw new AssertionError("Tree empty after adding 8");
      if ( ! x.contains(8) )
         throw new AssertionError("Tree missing 8");
      x.remove(8);
      if ( x.contains(8) )
         throw new AssertionError("8 not removed");
      if ( ! x.isEmpty() )
         throw new AssertionError("Tree not empty at end");
   }

   // test that the iterator processes nodes in order
   private static void testIterator() {
      BinarySearchTree<Integer> x = new BinarySearchTree<>();
      if ( ! x.toString().equals("[ ]") )
         throw new AssertionError("toString for empty tree not []");
      int[] nums = {14, 5, 25, 8, 3, 10, 12, 11, 21};
      for(int n : nums)
         x.add(n);
      String s = x.toString();
      if ( ! s.equals("[ 3 5 8 10 11 12 14 21 25 ]") )
         throw new AssertionError("Unexpected items in tree: " + s);
      x.clear();
      if ( ! x.toString().equals("[ ]") )
         throw new AssertionError("Unexpected items in empty tree: " + s);
   }

   // more complete test, covering most cases of add and removal:
   // Note: this should be broken into a number of smaller cases
   //       to simplify debugging and maintenance
   private static void testLargerTree()
   {
      BinarySearchTree<Integer> x = new BinarySearchTree<>();
      int[] nums = {14, 5, 25, 8, 3, 10, 12, 11, 21};
      // strategy: create tree, fill tree with values, delete each node,
      //           confirm deletion worked
      //           This is tested with each possible node to delete -
      //           some overkill, but the amount of data is small anyways.
      for(int todel = 0; todel < nums.length; ++todel)
      {
         if ( ! x.isEmpty() )
            throw new AssertionError("Tree not empty before adding items");
         for(int n : nums)
         {
            if ( x.contains(n) )
               throw new AssertionError("Tree unexpectedly contains " + n);
            x.add(n);
            if ( ! x.contains(n) )
               throw new AssertionError("Tree missing " + n);
         }
         if ( x.isEmpty() )
            throw new AssertionError("Tree should not be empty");
         x.add(nums[todel]); // should have no effect
         //System.err.println("Deleting " + nums[todel] + " from " + x);
         x.remove(nums[todel]);
         if ( x.contains(nums[todel]) )
            throw new AssertionError("Tree contains deleted " + nums[todel]);
         x.remove(nums[todel]); // should have no effect
         if ( x.contains(nums[todel]) )
            throw new AssertionError("Tree still has deleted " + nums[todel]);
         // confirm all other values still there
         //System.err.println("Checking deletions for " + x);
         for(int i = 0; i < nums.length; ++i)
            if ( i != todel ) {
               //System.err.println("Checking contains " + nums[i]
               //                   + " after deleting " + nums[todel]);
               if ( ! x.contains(nums[i]) )
                  throw new AssertionError("X fails to have " + nums[i]);
            }
         // clean out the tree to reset it
         for(int i = 0; i < nums.length; ++i) {
            //System.err.println("Deleting " + nums[i] + " from " + x);
            x.remove(nums[i]);
         }
         // confirm tree is empty
         if ( ! x.isEmpty() )
            throw new AssertionError("Tree not empty after additions");
      }
   }

   protected static void testSizeAndHeight() {
      BinarySearchTree<Integer> x = new BinarySearchTree<>();
      int[] nums = {14, 5, 25, 8, 3, 10, 12, 11, 21};
      for(int n : nums)
         x.add(n);
      // just to make sure have the right picture
      if ( ! x.toString().equals("[ 3 5 8 10 11 12 14 21 25 ]") )
         throw new AssertionError("Initial tree wrong: " + x);
      // check size, height:
      if ( x.size() != nums.length )
         throw new AssertionError("Tree size wrong: " + x.size());
      if ( x.height() != 6 )
         throw new AssertionError("Tree height not 6");
      // add enough (and remove enough) to make the right taller
      x.remove(8);
      x.remove(10);
      x.add(22);
      x.add(23);
      x.add(24);
      if ( x.size() != nums.length + 1 )
         throw new AssertionError("Tree size should be length + 1");
      if ( x.height() != 6 )
         throw new AssertionError("Tree height should still be 6");
      // sanity check
      if ( ! x.toString().equals("[ 3 5 11 12 14 21 22 23 24 25 ]") )
         throw new AssertionError("Final tree not " + x);
   }

}