//Realizzazione dell'interfaccia Set con un array invece che con una lista

import java.util.*;

public class InsiemeArray implements Set, Cloneable {


  // campi dati
  protected Object[] array;
  protected static final int dimInit = 10; //dim. iniz. array
  
  protected int cardinalita;
  protected Class elemClass;

  // costruttori
  public InsiemeArray(Class cl) {
    array = new Object[dimInit];
    cardinalita = 0;
    elemClass = cl;
  }

  // funzioni proprie della classe
  // (realizzazione delle funzioni di Set)

  // basic operations
  public int size() {
    return cardinalita;
  }

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

  public boolean contains(Object e) {
    if (!elemClass.isInstance(e)) return false;
    else return appartiene(e);
  }

  public boolean add(Object e) {
    if (!elemClass.isInstance(e)) return false;
    else if (appartiene(e)) return false;
    else {
      if (cardinalita == array.length) {// raddoppia array
        Object[] aux = new Object[array.length*2];
        for(int i = 0; i < array.length; i++) 
          aux[i] = array[i];
        array = aux;
      }
      array[cardinalita] = e;
      cardinalita++;
      return true;
    }
  }

  public boolean remove(Object e) {
    if (!elemClass.isInstance(e)) return false;
    if (!appartiene(e)) return false;
    else {
      int k = 0;                  // trova l'elemento
      while (!array[k].equals(e))
        k++;
      for(int i = k; i < cardinalita-1; i++) // sposta di una poss
         array[i] = array[i+1];              // verso il basso gli
                                             // elementi dell'array
      cardinalita--;

      // rimpicciolisci l'array se e' il caso
      if (cardinalita > dimInit && cardinalita < array.length/3) {
        Object[] aux = new Object[array.length/2];
        for(int i = 0; i < cardinalita; i++)
          aux[i]=array[i];
        array = aux;
      }
      return true;
    }
  }

  public Iterator iterator() {
    return new IteratorInsiemeArray(this);
  }


  // bulk operations
  public boolean containsAll(Collection c) {
    Iterator it = c.iterator();
    while (it.hasNext()) {
      Object e = it.next();
      if (!contains(e)) return false;
    }
    return true;
  }

  public boolean addAll(Collection c){ 
    throw new UnsupportedOperationException("addlAll() non e' supportata");
  }
  public boolean removeAll(Collection c) {
    throw new UnsupportedOperationException("removeAll() non e' supportata");
  }
  public boolean retainAll(Collection c) {
    throw new UnsupportedOperationException("retainAll() non e' supportata");
  }
  public void clear() {
    throw new UnsupportedOperationException("clear() non e' supportata");
  }

  // array operations
  public Object[] toArray() {
    Object[] a = new Object[size()];
    int i = 0;
    Iterator it = iterator();
    while (it.hasNext()) {
      a[i] = it.next();
      i++;
    }
    return a;
  }

  public Object[] toArray(Object[] a) {
    if (a.length < size()) 
      a = new Object[size()];
    int i = 0;
    Iterator it = iterator();
    while (it.hasNext()) {
      a[i] = it.next();
      i++;
    }
    for (; i < a.length; i++) 
      a[i] = null;
    return a;
  }


  // funzioni speciali ereditate da Object
  public boolean equals(Object o) {
    if (o != null && getClass().equals(o.getClass())) {
      InsiemeArray ins = (InsiemeArray)o;
      if (!elemClass.equals(ins.elemClass)) return false;
      // ins non e' un insieme del tipo voluto
      else if (cardinalita != ins.cardinalita) return false;
      // ins non ha la cardinalita' giusta
      else {
        // verifica che gli elementi nella lista siano gli stessi
        for(int i = 0; i < ins.cardinalita; i++) 
          if (!appartiene(ins.array[i])) return false;
        return true;
      }
    }
    return false;
  }

  public Object clone() {
    try {
      InsiemeArray ins = (InsiemeArray) super.clone();
      ins.array = new Object[array.length];
      for(int i = 0; i < cardinalita; i++)
        ins.array[i]=array[i];
      return ins;
    } catch(CloneNotSupportedException e) {
      throw new InternalError(e.toString());
    }
  }
  public String toString() {
    String s = "{ ";
    for(int i = 0; i < cardinalita; i++) 
      s = s + array[i] + " ";
    s = s + "}";
    return s;
  }

  // funzioni ausiliarie

  protected boolean appartiene(Object e) {
    for(int i = 0; i < cardinalita; i++)
      if (array[i].equals(e)) return true;
    return false;
  }
}