class SetOfGabsOrdered extends SetOfGabs{

/* IMPLEMENTS
  public int findElement(SetElement  element)
  public void insert(SetElement  element)
  public void deleteAtIndex(int index)
******/

  public SetOfGabsOrdered(int capacity) { super(capacity);}


public int findElement(SetElement element){
    // returns the index of the element in the array
    // or -1 if its not there.
    return this.binarySearch(element,0,getsize()-1);
  }

public void insert(SetElement element){
    // the set is not at full capacity and
    // the element is not already there
    int i = getsize();
    while (i > 0 && element.issmaller(getElement(i-1)) ){
      setElement(i,  getElement(i-1));
      i = i-1;
    }
    setElement(i,  element);
    setsize ( getsize() + 1);
  }


 public void deleteAtIndex(int index){
    // deletes the item at the given index in the array

      for (int i = index;i < getsize(); i=i+1)
        setElement(i,getElement(i+1));
      setsize ( getsize()-1);
  }

private int binarySearch(SetElement element, int low, int high){
    // a recursive version
    if (low > high)
      return NOT_FOUND;
    int middle = (low+high)/2;
    if (element.equals(getElement(middle) ))
      return middle;
    else if (getElement(middle).issmaller(element))
      return binarySearch(element,middle+1,high);
    else
      return binarySearch(element, low, middle - 1);
  }

}