//  Data Structures with Java by John R. Hubbard
//  Copyright McGraw-Hill, 2001
//  Example 3.11 on page 64
//  An ArraySequence class to implement the Sequential interface

public class ArraySequence implements Sequential
{ protected int length=0;
  protected Object[] a;
  protected int capacity=16;
  // INVARIANT: a[i] != null for 0 <= i < length;
  
  public ArraySequence()
  { a = new Object[capacity];
  }
  
  public void append(Object object)
  { if (length==capacity) // double the capacity
    { Object[] tmp = a;
      capacity *= 2;
      a = new Object[capacity];
      for (int i=0; i<length; i++)
        a[i] = tmp[i];
    }
    a[length++] = object;
  }
  
  public int count(Object object)
  { int c=0;
    for (int i=0; i<getLength(); i++)
      if (object.equals(get(i))) ++c;
    return c;
  }
  
  public Object get(int index)
  { if (index >= length) return null;
    return a[index];
  }
  
  public int getLength()
  { return length;
  }
  
  public int indexOf(Object object)
  { for (int i=0; i<length; i++)
      if (object.equals(get(i))) return i;
    return -1;
  }
  
  public Object remove(int index)
  { if (index >= length) return null;
    Object x = a[index];
    for (int i=index; i<length; i++)
      a[i] = a[i+1];
    --length;
    return x;
  }
  public boolean remove(Object object)
  { int i=indexOf(object);
    if (i == -1) return false;
    remove(i);
    return true;
  }
  
  public Object set(int index, Object object)
  { if (index >= length) return null;
    Object x = a[index];
    a[index] = object;
    return x;
  } 

  public String toString()
  { if (length==0) return "()";
    String s = "(" + get(0);
    for (int i=1; i<length; i++)
      s += "," + get(i);
    return s + ")";    
}