/**
  * ArraySet
  * Insieme: realizzazione con array ridimensionabile parzialmente
  * riempito
  * @author M. Dalpasso modificato da A. Luchetta
  * @version 2-Dic-2006
  * @see Set
  */
public class ArraySet implements Set
{
   private static int SET_DIM = 1;

   private Object[] v;
   private int vSize;
   
   public ArraySet()
   {
      makeEmpty();
   }

   public void makeEmpty()
   {  v = new Object[SET_DIM];
      vSize = 0;
   }

   public boolean isEmpty()
   {  return vSize == 0;
   }

   public int size()
   {  return vSize;
   }

  /**
    verifica se l'elemento specificato e' contenuto nell'insieme
    Complessita' temporale O(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)
   {
      for (int i = 0; i < vSize; i++)
         if (v[i].equals(x))
            return true;

      return false;
   }

  /**
    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(Object x)
   {
      if (contains(x)) return;

      if (vSize >= v.length)
         v = resize(v, 2 * v.length);

      v[vSize++] = x;
   }
   
  /**
    restituisce un array contenente gli elementi
    dell'insieme
    Complessita' temporale O(n)
    @return array ordinato
  */
   public Object[] toArray()
   {
      Object[] tmp = new Object[vSize];
      
      for (int i = 0; i < vSize; i++)
         tmp[i] = v[i];   // non si puo' fare meglio!

      return tmp;
   }
   
  /**
    restituisce l'insieme unione degli insiemi specificati
    Complessita' temporale O(n^2)
    @param il primo insieme
    @param il secondo insieme
    @return l'insieme unione
  */
   public static Set union(Set s1, Set s2)
   {
      Set x = new ArraySet();

      // inseriamo gli elementi del primo insieme
      Object[] v = s1.toArray();

      for (int i = 0; i < v.length; i++)
         x.add(v[i]);

      // inseriamo tutti gli elementi del
      // secondo insieme, sfruttando le
      // proprietà di add (niente duplicati...)
      v = s2.toArray();
      for (int i = 0; i < v.length; i++)
         x.add(v[i]);

      return x;
   }

  /**
    restituisce l'insieme intersezione degli insiemi specificati
    Complessita' temporale O(n^2)
    @param il primo insieme
    @param il secondo insieme
    @return l'insieme intersezione
  */
   public static Set intersection(Set s1, Set s2)
   {  Set x = new ArraySet();
      Object[] v = s1.toArray();
      for (int i = 0; i < v.length; i++)
        if (s2.contains(v[i]))
          x.add(v[i]);

      return x;
   }

  /**
    restituisce l'insieme differenza degli insiemi specificati
    Complessita' temporale O(n^2)
    @param il primo insieme
    @param il secondo insieme
    @return l'insieme differenza
  */
   public static Set subtract(Set s1, Set s2)
   {  Set x = new ArraySet();
      Object[] v = s1.toArray();
      for (int i = 0; i < v.length; i++)
         if (!s2.contains(v[i]))
            x.add(v[i]);
      return x;
   }                                 
   // ridimensionamento dinamico di array
   private Object[] resize(Object[] a, int length)
   {
      Object[] tmp = new Object[length];
      int minLength = a.length < length ? a.length : length;
      for (int i = 0; i < minLength; i++)
         tmp[i] = a[i];
         
      return tmp;
   }
}