import java.util.Iterator;

public class Set<T> implements Iterable<T> {
    
    /**
     * Diese Klasse implementiert eine unveränderliche, einfach verkettete 
     * Liste von Elementen eines generischen Typs E. Diese Klasse ist nur für
     * Sets zugreifbar (da private).
     * @param <E> der Typ der Elemente, die in der Liste gespeichert werden
     */
    private class List<E> implements Iterable<E> {
        
        /**
         * Diese Klasse repräsentiert die Knoten der Liste. Ein Knoten speichert
         * dabei seinen Nachfolger und seinen Inhalt. Mehrere Knoten ergeben
         * dann die Liste, wobei lediglich der erste Knoten gespeichert werden
         * muss, um auf alle anderen zuzugreifen.
         * @param <X> der Typ des Elements, das der Listenknoten speichert.
         *            Dieser könnte sich syntaktisch (!) vom generischen Typ
         *            der Liste unterscheiden (wie hier gezeigt werden soll).
         */
        private class ListElement<X> {
            public final X content;
            public final ListElement<X> next;
                        
            public ListElement(X content, ListElement<X> next) {
                this.content = content;
                this.next = next;
            }
            
            public ListElement(X content) {
                this(content, null);
            }
            
            /**
             * Fügt ein neues Listenelement (Knoten) hinten an die Liste an,
             * wobei die aktuelle Liste unverändert bleibt und stattdessen eine
             * neue Liste erzeugt wird (element==null -> Kopie der Liste).
             */
            private ListElement<X> append(ListElement<X> element) {              
                if (next == null)
                    return new ListElement<>(this.content, element);
                return new ListElement<>(this.content, next.append(element));
            }
            
            private ListElement<X> remove(Object content) { 
                if (this.content.equals(content)) {
                    // -> aktueller Knoten darf nicht übernommen werden
                    if (next == null) // kein nächster -> Ende erreich
                        return null;
                    return next.remove(content);  // wird nur noch kopieren
                }
                if (next == null)
                    return new ListElement<>(this.content);
                return new ListElement<>(this.content, next.remove(content));
            }
        }
        
        
        private final ListElement<E> first;
        
        public List(ListElement<E> first) {
            this.first = first;
        }
        
        public List() {
            this(null);
        }
                
        public List<E> append(E content) {
            if (first == null)
                return new List<>(new ListElement<>(content));
            return new List<>(first.append(new ListElement<>(content)));
        }
        
        public List<E> remove(Object content) {
            if (first == null)
                return new List<>();
            return new List<>(first.remove(content));
        }
        
        public boolean contains(Object content) {
            if (content == null)
                return false;
            
            for (ListElement<E> current = first; current != null; 
                                                    current = current.next) {
                if (current.content.equals(content))
                    return true;
            }
            return false;
        }
        
        public int size() {
            int size = 0;
            for (ListElement<E> current = first; current != null; 
                                                    current = current.next) {
                size++;
            }
            return size;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null)
                return false;
            if (!(o instanceof List))
                return false;
            
            List<E> other = (List<E>) o;
            
            if (this.size() != other.size())
                return false;            
            // Erkennt auch das leere Set, denn das hat eine Liste der Länge 0:
            for (ListElement<E> current = first; current != null; 
                                                    current = current.next) {
                if (! other.contains(current.content))
                    return false;
            }
            return true;
        }
        
        @Override
        public String toString() {
            // Letztes Komma vermeiden, indem first gesondert hinzugefügt wird:
            if (first == null)
                return "";
                        
            String ret = first.content.toString();
            
            for (ListElement<E> current = first.next; current != null; 
                                                    current = current.next) {
                ret += "," + current.content;
            }
            
            return ret;
        }
        
        
        @Override
        public Iterator<E> iterator() {
            return new ImmutableListIterator<>(this.first);
        }
        
        /**
         * Diese Klasse implementiert einen Iterator für die unveränderliche 
         * Liste, der  beginnend bei einem Element first mittels next() jeweils
         * das nächste Element (vom Typ X) zurückliefert. X ist im Endeffekt T,
         * allerdings soll hier gezeigt werden, dass das T hier syntaktisch
         * nichts mit dem obigen zu tun hätte, daher verwende ich X. Ein List-
         * Iterator wird dann aber mit new ListIterator<T> erzeugt, also wird
         * T eben gerade für X eingesetzt ;-)
         */
        public class ImmutableListIterator<X> implements Iterator<X> {
            
            private ListElement<X> current;
            
            public ImmutableListIterator(ListElement<X> first) {
                current = first;
            }

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public X next() {
                if (current == null)
                    throw new java.util.NoSuchElementException();
                X content = current.content;
                current = current.next;
                return content;
            }
            
        }
    }
    
    
    private final List<T> list;  // darf nicht null sein
    
    private Set(List<T> list) {
        if (list == null)
            throw new IllegalArgumentException("Liste darf nicht null sein.");
        this.list = list;
    }
    
    public Set() {
        this.list = new List<>();
    }
    
    public Set<T> add(T e) {
        if (e == null)
            throw new NullPointerException("null darf nicht in ein Set "
                    + "hinzugefügt werden");
        if (this.contains(e))
            return this;
        return new Set<>(list.append(e));
    }
    
    public Set<T> remove(Object o) {
        if (o == null)
            throw new NullPointerException("null kann nicht existieren und "
                    + "darf somit auch nicht entfernt werden.");
        // Auch wenn das Set leer ist, soll ein neues Set zurückgegeben werden!
        return new Set<>(list.remove(o));
    }
    
    public boolean contains(Object o) {
        return list.contains(o);
    }
    
    public int size() {
        return list.size();
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o)  // trivialer Fall s.equals(s)
            return true;
        if (o == null || !(o instanceof Set))
            return false;
        return this.list.equals(((Set) o).list);
    }
    
    @Override
    public String toString() {
        return "{" + list.toString() + "}";
    }
    
    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }
    
}