import java.util.*;

class Lista {
    Object info;
    Lista next;
}

public class InsiemeLista implements Set, Cloneable {

  // campi dati
  protected Lista inizio;
  protected int cardinalita;
  protected Class elemClass;

  // costruttori
  public InsiemeLista(Class cl) {
    inizio = null;
    cardinalita = 0;
    elemClass = cl;
  }

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

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

  public boolean isEmpty() {
    return inizio == null;
  }

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

  public boolean add(Object e) {
    if (!elemClass.isInstance(e)) return false;
    else if (appartiene(e,inizio)) return false;
    else {
      Lista l = new Lista();
      l.info = e;
      l.next = inizio;
      inizio = l;
      cardinalita = cardinalita + 1;
      return true;
    }
  }

  public boolean remove(Object e) {
    if (!elemClass.isInstance(e)) return false;
    if (!appartiene(e,inizio)) return false;
    else {
      inizio = cancella(e,inizio);
      cardinalita = cardinalita - 1;
      return true;
    }
  }

  public Iterator iterator() {
    return new IteratorInsiemeLista(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())) {
      InsiemeLista ins = (InsiemeLista)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
        Lista l = inizio;
        while (l != null) {
          if (!appartiene(l.info,ins.inizio))
            return false;
          l = l.next;
        }
        return true;
      }
    }
    else return false;
  }

  public Object clone() {
    try {
      InsiemeLista ins = (InsiemeLista) super.clone();
      // chiamata a clone() di Object che esegue la copia campo a campo;
      // questa copia e' sufficiente per i campi cardinalita e elemClass
      // ma non per il campo inizio del quale va fatta una copia profonda
      ins.inizio = copia(inizio);
      return ins;
    } catch(CloneNotSupportedException e) {
      // non puo' accadere perche' implementiamo l'interfaccia cloneable,
      // ma va comunque gestita
      throw new InternalError(e.toString());
    }
  }
  public String toString() {
    String s = "{ ";
    Lista l = inizio;
    while (l != null) {
      s = s + l.info + " ";
      l = l.next;
    }
    s = s + "}";
    return s;
  }

  // funzioni ausiliarie

  protected static boolean appartiene(Object e, Lista l){
    return (l != null) && (l.info.equals(e) || appartiene(e,l.next));
  }

  protected static Lista copia (Lista l) {
    if (l == null) return null;
    else {
      Lista ll = new Lista();
      ll.info = l.info;
      ll.next = copia(l.next);
      return ll;
    }
  }
  protected static Lista cancella(Object e, Lista l) {
    if (l == null) return null;
    else if (l.info.equals(e)) return l.next;
    else {
      l.next = cancella(e,l.next);
      return l;
    }
  }
}