/**
  * ArraySortedSet
  * Insieme ordinato
  * @author M. Dalpasso modificato da A. Luchetta
  * @version 2-Dic-2006
  * @see SortedSet
  * @see Set
  */
public class ArraySortedSet implements SortedSet
{ private static int INITIAL_DIM = 1;
  private Comparable[] v;
  private int vSize = 0;

  public ArraySortedSet()
  { makeEmpty(); }
  
  public void makeEmpty()
  { v = new Comparable[INITIAL_DIM];
    vSize = 0;
  }
  public boolean isEmpty()
  { return vSize == 0;
  }
  public int size()
  { return vSize;
  }

  /**
    restituisce un array ordinato contenente gli elementi
    dell'insieme
    Complessita' temporale O(n)
    @return array ordinato
  */
  public Comparable[] toSortedArray()
  {
    Comparable[] x = new Comparable[vSize];
    System.arraycopy(v, 0, x, 0, vSize);
    return x;
  }

  /**
    restituisce un array ordinato contenente gli elementi
    dell'insieme
    Complessita' temporale O(n)
    @return array ordinato
  */
  public Object[] toArray()
  { return toSortedArray();
  }

  /**
    verifica se l'elemento specificato e' contenuto nell'insieme
    Complessita' temporale O(log n)
    @param x elemento su cui si effettua la verifica
    @return true se l'elemento e' contenuto nell'insieme
    false altrimenti
  */
  public boolean contains(Object x)  // O(log n)
  { Comparable target = (Comparable) x;
    int i = binSearch(v, 0, vSize - 1, target);
    return i != -1;
  }

  /**
    realizza il metodo omonimo dell'interfaccia Set
    non deve essere usato. In questo insieme si possono
    inserire solo oggetti comparabili!
    @throws IllegalArgumentException
  */
  public void add(Object x) // non deve essere usato!
  { throw new IllegalArgumentException();
  }

  /**
    aggiunge un elemento all'insieme, se l'elemento
    specificato non e' gia' presente, altrimenti
    termina silenziosamente
    Complessita' temporale O(n)
    @param x l'elemento da inserire
  */
  public void add(Comparable x)      // O(n)
  { if (contains(x))
       return;

    // ridimensionamento dell'array, se richiesto
    if (vSize >= v.length)
       v = resize(v, 2 * vSize);

    // inserimento in array ordinato
    int j;
    for (j = vSize; j > 0 && x.compareTo(v[j - 1]) < 0; j--)
       v[j] = v[j - 1];

    v[j] = x;
    vSize++;
  }

  /**
    genera l'insieme unione degli insiemi specificati
    x appartiene a s1 U s2 se x appartiene a s1 o x appartiene a s2
    Complessita' temporale O(n log n): il motivo e' che il metodo
    add diventa O(log n) quando si inseriscono elementi in modo
    ordinato
    @param s1 primo insieme
    @param s2 secondo insieme
    @return insieme unione
  */
  public static SortedSet union(SortedSet s1, SortedSet s2)
  {
    SortedSet x = new ArraySortedSet();

    Comparable[] v1 = s1.toSortedArray();
    Comparable[] v2 = s2.toSortedArray();

    int i = 0, j = 0;
    while (i < v1.length && j < v2.length)
       if (v1[i].compareTo(v2[j]) < 0)
          x.add(v1[i++]); // inserisce da v1 e ne incrementa l'indice
       else if (v1[i].compareTo(v2[j]) > 0)
          x.add(v2[j++]); // inserisce da v2 e ne incrementa l'indice
       else // se sono uguali, inserisce da v1 (andrebbe bene anche da v2)
       {  x.add(v1[i++]); // ma incrementa entrambi gli indici
          j++;
       }
    while (i < v1.length)
       x.add(v1[i++]);
    while (j < v2.length)
       x.add(v2[j++]);

    return x;
  }

  /**
    genera l'insieme intersezione degli insiemi specificati
    x appartiene a s1 INT s2 se x appartiene a s1 e x appartiene a s2
    Complessita' temporale O(n log n): il motivo e' che il metodo
    add diventa O(log n) quando si inseriscono elementi in modo
    ordinato
    @param s1 primo insieme
    @param s2 secondo insieme
    @return insieme intersezione
  */
  public static SortedSet intersection(SortedSet s1, SortedSet s2)
  {
    SortedSet x = new ArraySortedSet();

    Comparable[] v1 = s1.toSortedArray();
    Comparable[] v2 = s2.toSortedArray();

    int i = 0;
    int j = 0;
    while (i < v1.length && j < v2.length)
    {
       // finche' v1[i] > v2[j] si incrementa l'indice di v2
       while (j < v2.length && v1[i].compareTo(v2[j]) > 0)
         j++;
 
       // se v2 non e' finito e v1[i] == v2[j], allora si inserisce
       // v1[i]
       if (j != v2.length && v1[i].compareTo(v2[j]) == 0)
         x.add(v1[i]);
         
       i++;
    }

    return x;
  }

  /**
    genera l'insieme differenza degli insiemi specificati
    x appartiene a s1 - s2 se x appartiene a s1 e x non appartiene a s2
    Complessita' temporale O(n log n): il motivo e' che il metodo
    add diventa O(log n) quando si inseriscono elementi in modo
    ordinato)
    @param s1 primo insieme
    @param s2 secondo insieme
    @return insieme intersezione
  */
  public static SortedSet subtract(SortedSet s1, SortedSet s2)
  {
    SortedSet x = new ArraySortedSet();

    Comparable[] v1 = s1.toSortedArray();
    Comparable[] v2 = s2.toSortedArray();

    int i = 0;
    int j = 0;
    while (i < v1.length && j < v2.length)
    {
       // finche' v1[i] > v2[j] si incrememta l'indice di v2
       while (j < v2.length && v1[i].compareTo(v2[j]) > 0)
         j++;

       // se v2 non e' finito e v1[i] != v2[j], allora si inserisce
       // v1[i]
       if (j != v2.length && v1[i].compareTo(v2[j]) != 0)
         x.add(v1[i]);

       i++;
    }

    while(i < v1.length)
       x.add(v1[i++]);

    return x;
  }

  private static int binSearch(Comparable[] a, int from, int to, Comparable t)
  {
     if (to < from)
        return -1;

     int m = (from + to) / 2;

     if (t.compareTo(a[m]) == 0)
        return m;

     else if (t.compareTo(a[m]) < 0)
        return binSearch(a, from, m - 1, t);
     else
        return binSearch(a, m + 1, to, t);
  }

  private static Comparable[] resize(Comparable[] s, int length)
  {
     Comparable[] c = new Comparable[length];

     int minLength = s.length < length ? s.length : length;

     for (int i = 0; i < minLength; i++)
        c[i] = s[i];

     return c;
  }
}