
class ArrayList {
  private Object[] array;
  private int size;
  
  public ArrayList() {
    array = new Object[ 8 ];
  }
  
  public void add( Object obj ) {
    if ( size >= array.length )
      expand();
    
    array[ size++ ] = obj;
  }
  
  public void addAll( ArrayList other ) {
    for ( int i=0; i<other.size; i++ )
      add( other.get( i ) );
  }
  
  public Object get( int index ) {
    checkIndex( index );
    
    return array[ index ];
  }
  
  public Object set( int index, Object obj ) {
    checkIndex( index );

    Object result = array[ index ];
    
    array[ index ] = obj;
    
    return result;
  }

  public void insert( int index, Object obj ) {
    if ( size >= array.length )
      expand();

    // push tail
    for ( int i=size-1; i>=index; i-- )
      array[ i + 1 ] = array[ i ];

    array[ index ] = obj;
    size++;
  }
  
  public Object remove( int index ) {
    checkIndex( index );
    
    Object result = array[ index ];

    for ( int i=index; i<size-1; i++ )
      array[ i ] = array[ i + 1 ];
    
    size--;
    
    return result;
  }
  
  public boolean remove( Object obj ) {
    int index = indexOf( obj );
    
    if ( index >= 0 ) {
      remove( index );
      return true;
    } else
      return false;
  }
  
  public void clear() {
    size = 0;
  }
  
  public int size() {
    return size;
  }
  
  public boolean isEmpty() {
    return size == 0;
  }
  
  public boolean contains( Object target ) {
    return indexOf( target ) >= 0;
  }
  
  public int indexOf( Object target ) {
    for ( int i=0; i<size; i++ )
      if ( array[ i ].equals( target ) )
        return i;
    
    return -1;
  }
  
  public int lastIndexOf( Object target ) {
    for ( int i=size-1; i>=0; i-- )
      if ( array[ i ].equals( target ) )
        return i;
    
    return -1;
  }
  
  public Object[] toArray() {
    Object[] result = new Object[ size ];
    
    for ( int i=0; i<size; i++ )
      result[ i ] = array[ i ];
    
    return result;
  }
  
  private void checkIndex( int index ) {
    if ( index < 0 || index >= size )
      throwRuntimeError( "IndexOutOfBoundsException", "index", "" + index );
  }
  
  private void expand() {
    Object[] newArray = new Object[ 2 * array.length ];
    
    for ( int i=0; i<array.length; i++ )
      newArray[ i ] = array[ i ];
    
    array = newArray;
  }

  public String toString() {
    String result = "[ArrayList:";

    if ( size > 0 )
      for ( int i=0; i<size; i++ ) {
        result += " " + array[ i ];

        if ( i < size - 1 )
          result += ",";
      }
    else
      result += " empty";

    result += "]";

    return result;
  }
}
