// 第 6 周 – 用无序数组表示的集合
// 运行：java UnorderedSet.java
import java.util.Arrays;

public class UnorderedSet {
    private int[] data = new int[4];
    private int size = 0;

    // 属于判断：顺序查找 – O(n)
    boolean contains(int x) {
        for (int i = 0; i < size; i++) if (data[i] == x) return true;
        return false;
    }

    // 插入：只在尚不存在时插入（集合没有重复元素）– O(n)
    void add(int x) {
        if (contains(x)) return;
        if (size == data.length) data = Arrays.copyOf(data, 2 * size);
        data[size++] = x;
    }

    // 删除：顺序无关紧要，所以把最后一个元素移到它的位置 – 由于需要查找，所以是 O(n)
    void remove(int x) {
        for (int i = 0; i < size; i++) {
            if (data[i] == x) {
                data[i] = data[--size];
                return;
            }
        }
    }

    // A ⊆ B：在 B 中查找 A 的每个元素 – O(n·m)
    boolean subsetOf(UnorderedSet b) {
        for (int i = 0; i < size; i++) if (!b.contains(data[i])) return false;
        return true;
    }

    // 并集：A 的所有元素，加上 B 中不属于 A 的元素 – O(n·m)
    UnorderedSet union(UnorderedSet b) {
        UnorderedSet r = new UnorderedSet();
        for (int i = 0; i < size; i++) r.add(data[i]);
        for (int i = 0; i < b.size; i++) r.add(b.data[i]);
        return r;
    }

    // 交集：A 中也属于 B 的元素 – O(n·m)
    UnorderedSet intersection(UnorderedSet b) {
        UnorderedSet r = new UnorderedSet();
        for (int i = 0; i < size; i++) if (b.contains(data[i])) r.add(data[i]);
        return r;
    }

    // 差集：A 中不属于 B 的元素 – O(n·m)
    UnorderedSet difference(UnorderedSet b) {
        UnorderedSet r = new UnorderedSet();
        for (int i = 0; i < size; i++) if (!b.contains(data[i])) r.add(data[i]);
        return r;
    }

    static UnorderedSet of(int... xs) {
        UnorderedSet s = new UnorderedSet();
        for (int x : xs) s.add(x);
        return s;
    }

    public String toString() {
        return Arrays.toString(Arrays.copyOf(data, size)).replace('[', '{').replace(']', '}');
    }

    public static void main(String[] args) {
        UnorderedSet a = of(8, 2, 11, 5, 2, 8); // 重复元素不会加入
        UnorderedSet b = of(9, 5, 14, 3, 11);
        System.out.println("A = " + a + ", B = " + b);
        System.out.println("A ∪ B = " + a.union(b));
        System.out.println("A ∩ B = " + a.intersection(b));
        System.out.println("A \\ B = " + a.difference(b));
        System.out.println("{5, 11} ⊆ A? " + of(5, 11).subsetOf(a) + ", A ⊆ B? " + a.subsetOf(b));
        a.remove(2);
        System.out.println("after A.remove(2): " + a);
    }
}