import java.util.ArrayList;
public class SLUnboundedEnv extends SquareEnvironment
{
  private ArrayList objectList;

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

    objectList = new ArrayList();
  }

  // accessor methods

  public int numRows()
  {
    return -1;
  }

  public int numCols()
  {
    return -1;
  }

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

  public int numObjects()
  {
    return objectList.size();
  }

  public Locatable[] allObjects()
  {
    Locatable[] objectArray = new Locatable[objectList.size()];

    // Put all the environment objects in the list.
    for ( int index = 0; index < objectList.size(); index++ )
    {
      objectArray[index] = (Locatable) objectList.get(index);
    }

    return objectArray;
  }

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

  public Locatable objectAt(Location loc)
  {
    int index = indexOf(loc);
    if ( index >= objectList.size())
      return null;

    Locatable objAtIndex = (Locatable)objectList.get(index);
    if (!objAtIndex.location().equals(loc) )
      return null;

    return objAtIndex;
  }

  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)
  {
    // Check precondition. Location should be empty.
    Location loc = obj.location();
    if ( ! isEmpty(loc) ) // loc is not empty
    {
      throw new IllegalArgumentException("Location " + loc +
                                    " is not a valid empty location");
    }
    else
    {   // add object to list in correct position
      objectList.add(indexOf(loc), obj);
    }
  }

  public void remove(Locatable obj)
  {
    // Find the index of the object to remove.
    int index = indexOf(obj.location());
    if (index >= objectList.size() || objectList.get(index) != obj)
    {
      throw new IllegalArgumentException("Cannot remove " +
                                          obj + "; not there");
    }
    else
    {
      // Remove the object.
      objectList.remove(index);
    }
  }

  public void recordMove(Locatable obj, Location oldLoc)
  {
    // We cannot use binary search to find the existing object
    // (or object at the new location) since the object
    // being moved is in the list, but at the "wrong" place
    // for its current location. We have to find the object
    // the "hard" way with an ordinary linear search
    int objectsAtOldLoc = 0;
    int objectsAtNewLoc = 0;
    int foundIndex = -1;

    // Look through the list to find how many objects are at old
    // and new locations.
    Location newLoc = obj.location();
    for ( int index = 0; index < objectList.size(); index++ )
    {
      Locatable thisObj = (Locatable) objectList.get(index);
      if ( thisObj.location().equals(oldLoc) )
        objectsAtOldLoc++;
      if ( thisObj.location().equals(newLoc) )
        objectsAtNewLoc++;
      if (thisObj == obj)
        foundIndex = index;
    }

    // There should be one object at newLoc. If oldLoc equals
    // newLoc, there should be one at oldLoc; otherwise, there
    // should be none.
    if ( ! ( objectsAtNewLoc == 1 &&
             ( oldLoc.equals(newLoc) || objectsAtOldLoc == 0 ) ) )
    {
      throw new
        IllegalArgumentException("Precondition violation moving "
                                   + obj + " from " + oldLoc);
    }
    int index = foundIndex;
    if ( newLoc.compareTo(oldLoc) < 0 )
    {
      // move to earlier position in list, sliding elements up
      while (index > 0 &&
        newLoc.compareTo(((Locatable)objectList.get(index-1)).location())<0)
      {
        objectList.set(index, objectList.get(index - 1));
        index--;
      }
      objectList.set(index, obj);
    }
    else if ( newLoc.compareTo(oldLoc) > 0 )
    {
      // move to later position in list, sliding elements down
      while (index < objectList.size() - 1 &&
        newLoc.compareTo(((Locatable)objectList.get(index+1)).location())>0)
      {
        objectList.set(index, objectList.get(index + 1));
        index++;
      }
      objectList.set(index, obj);
    }
  }

  // internal helper method
  /** Get the index of the object at the specified location or
   *  or the index where an object at that location should be added
   *  to the list.
   *  Uses binary seach, so time is O(log K) for K fish,
   *  Returns the location of the object if found, or where it
   *  should be, if not found
   **/
  protected int indexOf(Location loc)
  {
    int low = 0;
    int high = objectList.size() - 1;

    while ( low <= high )
    {
      int mid = (low + high) / 2;
      Location midLoc = ((Locatable)objectList.get(mid)).location();
      if ( loc.equals(midLoc) )
      {
        Debug.println("indexof " + loc + " is " + mid);
        return mid;
      }
      else if ( loc.compareTo(midLoc) < 0 )
        high = mid - 1;
      else // loc > midLoc
        low = mid + 1;
    }
    Debug.println("indexof " + loc + " is " + low);
    return low;
  }

}