public class OrderedSetOfInts extends SetOfInts{
/******
    We represent here the set of integers as an ORDERED array
    and we prevent duplicate elements.
 The menu of SetOfInts has: 
  public boolean isMember(int element)
  public void    addElement(int element)
  public void    deleteElement(int element)
  public void    union(OrderedSetOfInts A)
  public void    intersect(OrderedSetOfInts A)
  public void    print()
  public int     getElement(int i)
  public int     setElement(int i, int element)
  public int     getsize()

  public void setsize(int i)
  public int findElement (int i)
  public void insert(int element)
  public void deleteAtIndex(int index)
******/

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

// methods that override. 

public int findElement(int 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(int element){
    // the set is not at full capacity and
    // the element is not already there
    int i = getsize();
    while (i > 0 && getElement(i-1)  > element){
      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(int element, int low, int high){
    // a recursive version
    if (low > high)
      return NOT_FOUND;
    int middle = (low+high)/2;
    if (getElement(middle) == element)
      return middle;
    else if (element < getElement(middle))
      return binarySearch(element, low, middle - 1);
    else
      return binarySearch(element,middle+1,high);
  }
}