public abstract class OrderedSeq // abstract superclass
{ 
  protected OrderedSeq() {}            // for subclasses
  public abstract int capacity();      // capacity of sequence
  public abstract void remove(int i);  // remove by index
  public abstract int length();        // current length of seq
  public boolean isFull()
  { return length()==capacity(); }
  // public type get(int i);           // implemented by subclass

/** Enter entry into ordered sequence, false if failed */
 public boolean enter(Object any)
  {   boolean ok = append(any);        // append to end
      if ( ok ) sorted(false);
      return(ok);
  }

/** Returns index of desired entry found or -1 if not found */
  public int index(Object key)
  {     if ( ! sorted() ) sort();
        int low = 0, high = length()-1, mid, test;
        while (low <= high)
        {   mid = (high + low)/2;
            test = cmp(key, mid);
            if ( test == 0 )
                 return( mid );
            else if ( test > 0 )
                 low = mid + 1;
            else high = mid - 1;
        }
        return(-1);   // entry not found
  }

// protected section
  protected boolean sorted() { return ordered;}     // 0 if arr is not sorted
  protected void sorted(boolean s) { ordered = s;}  // set sorted flag
  protected abstract boolean append(Object a); // add to end, false if failed
  protected abstract void swap(int i, int j);  // interchange elements
  protected abstract int cmp(int i, int j);    // compare elements
  protected abstract int cmp(Object key, int j);// compare key to element

// basic sorting using quicksort
  protected void sort()
  {    if ( sorted() ) return;
       quicksort(0, length()-1);
       sorted(true);
  }
  
  // private section
  private int partition(int l, int r)
  { int i=l, j=r;
       swap((i+j)/2, r);                        // pivot moved to r
       while (i < j)
       {  while (cmp(i, r) <= 0 && i < j) i++;  // cmp  
          while (j > i && cmp(j, r) >= 0) j--;  // cmp  
          if (i < j) swap(i++,j);               // swap 
       }
       if (i != r) swap(i,r);                   // swap 
       return(i);
  }
  
  private void quicksort(int l, int r)
  {    if ( l >= r || l < 0 )
           return;
       int k = partition(l, r);
       quicksort(l, k-1);
       quicksort(k+1, r);  
  }
  
  private boolean ordered = false;               // sorted flag
}