/**
 * 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 boolean locate (Comparable key, BTree curr)
   {  
      if ( curr == null) {
	 return false;
      } // end of if ()

      BTree 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 String toString()
   {
      StringBuffer s = new StringBuffer();
      Iterator it = tree.preorderTraversal();
      while (it.hasNext()) {
	 s.append(" " + ((Item)(it.next())).getElement());
      } // end of while ()
      return s.toString();
   }

}// BSTree