import java.util.*;

abstract class absVector {

  static final boolean equals (absVector x, absVector y) {
    // NOTE: should it sort the indices ???
    if (x instanceof absEmpty && y instanceof absEmpty) {
      return ((absEmpty) x).size==((absEmpty) y).size
          && ((absEmpty) x).increment==((absEmpty) y).increment
          && ((absEmpty) x).capacity==((absEmpty) y).capacity;
    } else if (x instanceof absMap && y instanceof absMap) {
      return ((absMap) x).index==((absMap) y).index
	  && ((absMap) x).object.equals(((absMap) y).object)
          && equals(((absMap) x).vector,((absMap) y).vector);
    } else {
      return false;
    }
  }

  static final Object [] copyInto (absVector v) {
    Object [] array = new TestDriver.Vobject [size(v)];
    while (v instanceof absMap) {
      array [((absMap) v).index] = ((absMap) v).object;
      v = ((absMap) v).vector;
    }
    return array;
  }

  static final absVector trimToSize (absVector v) {
    if (v instanceof absEmpty) {
      return new absEmpty (
        ((absEmpty) v).size,
        ((absEmpty) v).increment,
        ((absEmpty) v).size);
    } else {
      return new absMap (
        ((absMap) v).index,
        ((absMap) v).object,
        trimToSize (((absMap) v).vector));
    }
  }

  static final absVector ensureCapacity (int minCapacity, absVector v) {
    if (v instanceof absEmpty) {
      int incr = ((absEmpty) v).increment;
      int oldCap = ((absEmpty) v).capacity;
      int newCap =
        (minCapacity > oldCap)
           ? Math.max (minCapacity, incr==0 ? 2 * oldCap : oldCap + incr) 
           : oldCap;
      return new absEmpty (((absEmpty) v).size, incr, newCap);
    } else {
      return new absMap (
        ((absMap) v).index,
        ((absMap) v).object,
        ensureCapacity (minCapacity, ((absMap) v).vector));
    }
  }

  static final absVector setSize (int newSize, absVector v) {
    if (newSize > size(v))
      return setSize1(newSize, ensureCapacity (newSize, v));
    else
      return setNullAbove (newSize, v);
  }

  static final absVector setSize1 (int newSize, absVector v) {
    if (v instanceof absEmpty) {
      return new absEmpty (
        newSize,
        ((absEmpty) v).increment,
        ((absEmpty) v).capacity);
    } else {
      return new absMap (
        ((absMap) v).index,
        ((absMap) v).object,
	setSize1 (newSize, ((absMap) v).vector));
    }
  }


  static final private absVector setNullAbove (int newSize, absVector v) {
    if (v instanceof absEmpty) {
      return new absEmpty (
        newSize,
        ((absEmpty) v).increment,
        ((absEmpty) v).capacity);
    } else {
      absVector tmp = setNullAbove (newSize, ((absMap) v).vector);
      int i = ((absMap) v).index;
      if (i >= newSize) return tmp;
      else return new absMap (((absMap) v).index, ((absMap) v).object, tmp);
    }
  }

  static final int capacity (absVector v) {
    if (v instanceof absEmpty) return ((absEmpty) v).capacity;
    else return capacity(((absMap) v).vector);
  }

  static final int size (absVector v) {
    if (v instanceof absEmpty) return ((absEmpty) v).size;
    else return size (((absMap) v).vector);
  }

  static final boolean isEmpty (absVector v) {
    return size(v) == 0;
  }

  static final Enumeration elements (Vector concrete,  absVector v) {
    return new VectorEnumerator(concrete);
  }

  static final boolean contains (Object o, absVector v) {
    if (v instanceof absEmpty) return false;
    else if (((absMap) v).object.equals(o)) return true;
    else return contains (o, ((absMap) v).vector);
  }

  static final int indexOf (Object o, absVector v) {
    return indexOf (o, 0, v);
  }

  static final int indexOf (Object o, int i, absVector v) {
    // the smallest index of o starting with i
    if (v instanceof absEmpty) return -1;
    else {
      int next = indexOf (o, i, ((absMap) v).vector);
      if (((absMap) v).object.equals(o)) {
	int curr = ((absMap) v).index;
        if (curr >= i && (next == -1 || curr < next)) return curr;
	else return next;
      } else return next;
    }
  }

  static final int lastIndexOf (Object o, absVector v) {
    return lastIndexOf (o, size(v)-1, v);
  }

  static final int lastIndexOf (Object o, int i, absVector v) {
    // the largest index of o starting with i
    if (v instanceof absEmpty) return -1;
    else {
      int next = lastIndexOf (o, i, ((absMap) v).vector);
      if (((absMap) v).object.equals(o)) {
	int curr = ((absMap) v).index;
        if (curr <= i && (next == -1 || curr > next)) return curr;
	else return next;
      } else return next;
    }
  }

  static final Object elementAt(int index, absVector v) {
    if (v instanceof absEmpty) {
      if (index < ((absEmpty) v).capacity) return null;
      else throw new RuntimeException ("absVector elementAt CONSISTENCY");
    } else {
      if (((absMap) v).index == index)
	return ((absMap) v).object;
      else
	return elementAt(index, ((absMap) v).vector);
    }

  }

  static final Object firstElement(absVector v) {
    if (v instanceof absEmpty) {
      if (((absEmpty) v).capacity > 0) return null;
      else throw new RuntimeException ("absVector firstElement CONSISTENCY");
    } else {
      if (((absMap) v).index == 0) return ((absMap) v).object;
      else return firstElement (((absMap) v).vector);
    }
  }

  static final Object lastElement(absVector v) {
    return elementAt (size(v)-1, v);
  }

  static final absVector setElementAt (Object o, int i, absVector v) {
    if (v instanceof absEmpty) {
      if (i < 0 || i >= ((absEmpty) v).capacity) 
	throw new RuntimeException ("absVector setElementAt CONSISTENCY");
      else return new absMap (i, o, v);
    } else {
      absVector tmp = ((absMap) v).vector;
      int j = ((absMap) v).index;
      if (j == i) return new absMap (i, o, tmp);
      else return new absMap (j, ((absMap) v).object, setElementAt (o, i, tmp));
    }
  }

  static final absVector removeElementAt (int i, absVector v) {
    if (v instanceof absEmpty) {
      if (i < 0 || i >= ((absEmpty) v).capacity)
	// if we throw, we may have done a lot of work for nothing
	throw new RuntimeException ("absVector removeElementAt CONSISTENCY");
      else return new absEmpty (
        ((absEmpty) v).size-1,
        ((absEmpty) v).increment,
        ((absEmpty) v).capacity);
    } else {
      absVector tmp = ((absMap) v).vector;
      int j = ((absMap) v).index;
      if (i > j) return new absMap (j, ((absMap) v).object, removeElementAt (i, tmp));
      else if (i == j) return removeElementAt (i, tmp);
      else return new absMap (j-1, ((absMap) v).object, removeElementAt (i, tmp));
    }
  }

  static final absVector insertElementAt (Object o, int i, absVector v) {
    if (v instanceof absEmpty) {
      int tmp = ((absEmpty) v).size+1;
      if (i < 0 || i >= tmp)
	throw new RuntimeException ("absVector insertElementAt CONSISTENCY");
      else
	return new absMap (i, o, ensureCapacity (tmp,
                     new absEmpty (tmp,
                                   ((absEmpty) v).increment,
                                   ((absEmpty) v).capacity)));
    } else {
      absVector tmp = ((absMap) v).vector;
      Object obj = ((absMap) v).object;
      int j = ((absMap) v).index;
      if (j >= i) return new absMap (j+1, obj, insertElementAt (o, i, tmp));
      else return new absMap (j, obj, insertElementAt (o, i, tmp));
    }
  }

  static final absVector addElement (Object o, absVector v) {
    if (v instanceof absEmpty) {
      int tmp = ((absEmpty) v).size;
      return new absMap (tmp, o,
                ensureCapacity(tmp+1, new absEmpty (
                                         tmp+1,
                                         ((absEmpty) v).increment,
                                         ((absEmpty) v).capacity)));
    } else {
      return new absMap (
        ((absMap) v).index,
        ((absMap) v).object,
	addElement (o, ((absMap) v).vector));

    }
  }

  static final boolean removeElement (Object o, absVector v) {
    return indexOf(o, v) >= 0;
  }

  static final absVector removeElementSide (Object o, absVector v) {
    int index = indexOf(o, v);
    if (index >= 0) return removeElementAt(index, v);
    else return v;
  }

  static final absVector removeAllElements (absVector v) {
    if (v instanceof absEmpty) {
      return new absEmpty (
                0,
                ((absEmpty) v).increment,
                ((absEmpty) v).capacity);
    } else {
      return removeAllElements (((absMap) v).vector);
    }
  }

  static final absVector clone (absVector v) {
    return v;
  }

  static final String toString (absVector v) {
    if (v instanceof absEmpty) {
      return "empty("
        + ((absEmpty) v).size + ","
        + ((absEmpty) v).increment + ","
        + ((absEmpty) v).capacity + ")";
    } else {
      Object tmpo = ((absMap) v).object;
      String tmps = tmpo == null ? "null" : tmpo.toString();
      return "map("
        + ((absMap) v).index + ","
        + tmps + ","
        + toString(((absMap) v).vector) + ")";
    }
  }

  static final String toConcrString (absVector v) {
    // we take advantage of a questionable feature of the
    // corresponding method in Vector.java which throws an
    // exception over null elements in the vector.
    StringBuffer buf = new StringBuffer();
    buf.append("[");
    boolean needComma = false;
    while (v instanceof absMap) {
      if (needComma) buf.insert(1, ", ");
      Object tmpo = ((absMap) v).object;
      String tmps = tmpo == null ? "null" : tmpo.toString();
      buf.insert(1, tmps);
      needComma = true;
      v = ((absMap) v).vector;
    }
    buf.append("]");
    return buf.toString();
  }

}