/**
 * BSTree.java
 *
 *
 * Created: Tue Oct 22 11:36:57 2002
 *
 * @author <a href="mailto: "bina@cse.buffalo.edu</a>
 * @version
 */
import java.util.*;
import binaryTree.*;

public class BSTree implements BSTreeInterface{
   BTree tree = null;
   protected BTree cursor;
   protected BTree parentOfCursor;

   protected boolean locate (Comparable key, BTree curr)
   {  
      if ( curr == null) {
	 return false;
      } // end of if ()

      parentOfCursor = cursor;
      cursor = curr; // save the current position
      Object currKey = ((Item)(curr.getData())).getKey();

      if ( key.compareTo((Comparable)currKey) < 0) //go left
	 return (locate(key, curr.getLeft()));
      else 
	 if ( key.compareTo(currKey) > 0) // go right
	    return (locate(key, curr.getRight()));
	 else 
	    // key == currkey; found
	    return true;
   }
   
   public int size()
   {
      return tree.size();
   }

   public boolean isEmpty()
   {
      return tree.isEmpty();
   }

   public Object search(Comparable ky)
   {
      if (locate(ky, tree))
	 return ((Item)(cursor.getData())).getElement();
      return null;
   }
    

   public void insert(Comparable key, Object elem)
   {  
      Item newItem = new Item(key,elem);
      
      cursor = tree;
      
      if ( !locate(key,tree)&& (cursor != null)) {
	 // key is not found
	 // cursor has the location to insert

    	BTree newNode = new BTree(newItem, null, null);

	if (key.compareTo(((Item)(cursor.getData())).getKey()) < 0) {
	    cursor.setLeft(newNode);
	 } // end of if ()
	 else {
	    cursor.setRight(newNode);
	 } // end of else
      }
      else { //brand new tree
      tree = new BTree(newItem, null, null);
      cursor = tree;}
   } 


   public Object remove(Comparable key)
   {  
      //case 1: empty tree
      if ( tree == null) {
	 throw new java.util.NoSuchElementException();
      } // end of if ()
      
      //case 2: nonempty tree: key found
      if ( locate(key, tree)) {
	 Object toReturn = cursor.getData();
		 
	 // case 2.1 cursor with left subtree empty
	 if ( cursor.getLeft() == null) {
	    BTree rgt = cursor.getRight();
	    if ( cursor == parentOfCursor.getLeft()) 
		  parentOfCursor.setLeft(rgt);
	    else 
		  parentOfCursor.setRight(rgt);
	 }
	 else {
	    //case 2.2 cursor has non empty left subtree 
	    BTree replacement = cursor.getLeft().getRightmost();
	    cursor.setData(replacement.getData());
	    cursor.setLeft(cursor.getLeft().removeRightmost()); 
	    //remove replacement
	 }
	 return toReturn;
      } // end of if ()
      else { // case 3: key not found
	 throw new java.util.NoSuchElementException();
      } // end of else
   }

      
   public String toString()
   {
      StringBuffer s = new StringBuffer();
      Iterator it = tree.preorderTraversal();
       while (it.hasNext()) {
	 s.append(" " + ((Item)(it.next())));
      } // end of while ()
      return s.toString();
   }

}// BSTree