public class BSTUnboundedEnv extends SquareEnvironment
{
  private TreeNode root; // root of the BST
  private int numObj; // stores the number of objects

  // constructors

  public BSTUnboundedEnv()
  {
    // Construct and initialize inherited attributes.
    super();

    root = null;
    numObj = 0;
  }

  // accessor methods

  public int numRows()
  {
    return -1;
  }

  public int numCols()
  {
    return -1;
  }

  public boolean isValid(Location loc)
  {
    return loc != null;
  }

  public int numObjects()
  {
    return numObj;
  }

  public Locatable[] allObjects()
  {
    Locatable[] objectArray = new Locatable[numObjects()];

    // Put all the environment objects in the list.
    // Uses inorder traversal with allObjectsHelper method.
    allObjectsHelper(root, objectArray, 0);
    return objectArray;
  }

  private int allObjectsHelper(TreeNode node,
                               Locatable[] objectArray, int indexIn)
  {
    if ( node != null )
    {
      int index = allObjectsHelper(node.getLeft(),
                                   objectArray, indexIn);

      objectArray[index] = (Locatable)node.getValue();
      index++;

      return allObjectsHelper(node.getRight(), objectArray, index);
    }
    else
    {
      return indexIn;
    }
  }

  public boolean isEmpty(Location loc)
  {
    return (objectAt(loc) == null);
  }

  public Locatable objectAt(Location loc)
  {
    return objectAtHelper(root, loc);
  }

  private Locatable objectAtHelper(TreeNode node, Location loc)
  {
    if ( node == null )
      return null;
    else
    {
      int cmp =
          loc.compareTo(((Locatable)node.getValue()).location());
      if (cmp == 0)
        return (Locatable)node.getValue();
      else if ( cmp < 0 )
        return objectAtHelper(node.getLeft(), loc);
      else // cmp > 0
        return objectAtHelper(node.getRight(), loc);
    }
  }

  public String toString()
  {
    Locatable[] theObjects = allObjects();
    String s = "Environment contains " + numObjects() + " objects: ";
    for ( int index = 0; index < theObjects.length; index++ )
      s += theObjects[index].toString() + " ";
    return s;
  }

  // modifier methods

  public void add(Locatable obj)
  {
    if ( !isEmpty(obj.location()) )
      throw new IllegalArgumentException("Location " + obj.location() +
                                      " is not a valid empty location");
    root = addHelper(root, obj);
  }

  private TreeNode addHelper(TreeNode node, Locatable obj)
  {
    if ( node == null )
    {
      numObj++;
      return new TreeNode(obj);
    }

    Location loc = obj.location();
    if ( loc.compareTo(((Locatable)node.getValue()).location()) < 0 )
      node.setLeft(addHelper(node.getLeft(), obj));
    else //loc.compareTo(((Locatable)node.getValue()).location()) > 0
      node.setRight(addHelper(node.getRight(), obj));

    return node;
  }

  public void remove(Locatable obj)
  {
    root = removeHelper(root, obj, obj.location());
  }

  private TreeNode removeHelper(TreeNode node,
                                Locatable obj, Location loc)
  {
    if ( node == null )
    {
      throw new IllegalArgumentException("Cannot remove " +
                                          obj + "; not there");
    }
    else if ( node.getValue().equals(obj) ) // found it
    {
      numObj--;
      return removeTargetNode(node);
    }
    else if ( ((Locatable)node.getValue()).location().equals(loc) )
    {
      throw new IllegalArgumentException("Cannot remove " + obj +
                                  "; different object at its location");
    }
    else if (loc.compareTo(((Locatable)node.getValue()).location()) < 0)
    {
      node.setLeft(removeHelper(node.getLeft(), obj, loc));
      return node;
    }
    else //loc.compareTo(((Locatable)node.getValue()).location()) > 0
    {
      node.setRight(removeHelper(node.getRight(), obj, loc));
      return node;
    }
  }

  private TreeNode removeTargetNode(TreeNode target)
  {
    if ( target.getRight() == null )
    {
      return target.getLeft();
    }
    else if ( target.getLeft() == null )
    {
      return target.getRight();
    }
    else if ( target.getRight().getLeft() == null )
    {
      target.setValue(target.getRight().getValue());
      target.setRight(target.getRight().getRight());
      return target;
    }
    else // right child has left child
    {
      TreeNode parent = target.getRight();
      while ( parent.getLeft().getLeft() != null )
        parent = parent.getLeft();

      target.setValue(parent.getLeft().getValue());
      parent.setLeft(parent.getLeft().getRight());
      return target;
    }
  }

  public void recordMove(Locatable obj, Location oldLoc)
  {
    Location newLoc = obj.location();
    int oldCount = numObj;

    root = removeHelper(root, obj, oldLoc);

    if ( oldCount == numObj || !isEmpty(newLoc) )
    {
      throw new
        IllegalArgumentException("Precondition violation moving "
                                  + obj + " from " + oldLoc);
    }

    root = addHelper(root, obj);
  }
}