// Modelliert eine endliche Menge von int Werten. Interne Darstellung durch
// Array. Nur Klassen aus java.lang (keine imports)
public class FiniteSet {
    private int size = 0;
    private int[] elems;

    // Konstruktor, der die Kapazität festlegt, welche anfangs für Elemente der
    // Menge reserviert wird. Falls die Kapazität kleiner 1 ist soll statt
    // dessen ein sinnvoller Wert gewählt werden. Initial ist die erzeugte Menge
    // leer.
    public FiniteSet(int capacity) {
        elems = new int[Math.max(capacity, 1)];
    }

    // Fügt die Zahl elem in die Menge ein, falls diese noch nicht enthalten
    // ist. Falls das Array zu klein ist, legen Sie ein neues um den Faktor zwei
    // größeres Array an.
    public void insert(int elem) {
        if (contains(elem)) return;

        if (size == elems.length) {
            int[] newElems = new int[elems.length * 2];
            System.arraycopy(elems, 0, newElems, 0, size);
            elems = newElems;
        }
        elems[size++] = elem;
    }

    // Löscht die Zahl elem aus der Menge, sofern diese in ihr enthalten ist.
    public void remove(int elem) {
        for (int i = 0; i < size; ++i) {
            if (elems[i] == elem) {
                elems[i] = elems[--size];
            }
        }
    }

    // Gibt true zurück, genau dann wenn elem in der Menge enthalten ist.
    public boolean contains(int elem) {
        for (int i = 0; i < size; ++i) {
            if (elems[i] == elem) return true;
        }
        return false;
    }

    // Bildet den (mathematischen) Schnitt der aktuellen Menge mit m und gibt
    // diesen als neues Objekt des Typs FiniteSet zurück. Die maximale Größe des
    // erzeugten Objekts soll das Minimum der Kapazität der beteiligten Mengen
    // sein.
    public FiniteSet intersect(FiniteSet m) {
        int newSize = Math.min(elems.length, m.elems.length);
        FiniteSet newSet = new FiniteSet(newSize);

        for (int i = 0; i < size; ++i) {
            int x = elems[i];
            if (m.contains(x)) newSet.insert(x);
        }
        return newSet;
    }

    // Bildet die (mathematische) Vereinigung der aktuellen Menge mit m und gibt
    // diese als neues Objekt des Typs FiniteSet zurück. Die maximale Größe des
    // erzeugten Objekts soll die Summe der Kapazität der beteiligten Mengen
    // sein.
    public FiniteSet union(FiniteSet m) {
        int newSize = elems.length + m.elems.length;
        FiniteSet newSet = new FiniteSet(newSize);

        for (int i = 0; i < size; ++i) {
            int x = elems[i];
            newSet.insert(x);
        }
        for (int i = 0; i < m.size; ++i) {
            int x = m.elems[i];
            newSet.insert(x);
        }
        return newSet;
    }

    // Bildet die Differenz der aktuellen Menge und der Menge m und gibt diese
    // als neues Objekt des Typs FiniteSet zurück. Die maximale Größe des
    // erzeugten Objekts soll die Kapazität der aktuellen Menge sein.
    public FiniteSet difference(FiniteSet m) {
        FiniteSet newSet = new FiniteSet(elems.length);
        System.arraycopy(elems, 0, newSet.elems, 0, size);
        newSet.size = size;

        for (int i = 0; i < m.size; ++i) {
            newSet.remove(m.elems[i]);
        }
        return newSet;
    }

    // Prüft, ob die aktuelle Menge gleich der Menge m ist und gibt im positiven
    // Fall true zurück. Gleichheit ist hierbei im mathematischen Sinne zu
    // verstehen.
    public boolean equals(FiniteSet m) {
        if (size != m.size) return false;

        for (int i = 0; i < size; ++i) {
            if (!m.contains(elems[i])) {
                return false;
            }
        }
        return true;
    }

    // Liefert eine String-Darstellung der aktuellen Menge in mathematischer
    // Notation, z.B. {3,7,5}
    public String toString() {
        StringBuilder sb = new StringBuilder(size * 2 + 1);
        for (int i = 0; i < size; ++i) {
            sb.append(elems[i]).append(",");
        }
        if (size > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        sb.insert(0, "{").append("}");
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(new FiniteSet(0));

        FiniteSet lost = new FiniteSet(2);
        lost.insert(4);
        lost.insert(8);
        lost.insert(15);
        lost.insert(16);
        lost.insert(23);
        lost.insert(42);
        // {4,8,15,16,23,42}
        System.out.println(lost);

        FiniteSet dual = new FiniteSet(2);
        dual.insert(1);
        dual.insert(2);
        dual.insert(4);
        dual.insert(8);
        dual.insert(16);
        dual.insert(32);
        // {1,2,4,8,16,32}
        System.out.println(dual);

        System.out.println(lost.union(dual));
        System.out.println(lost.intersect(dual));
        System.out.println(lost.difference(dual));
        System.out.println(lost.equals(dual));
    }
}