// 第 6 周 – 用位向量（以及位掩码）表示的集合
// 运行：java BitVectorSet.java
public class BitVectorSet {

    // 全集：一周的七天。集合是一个长度为 n 的布尔向量：
    // 如果全集的第 i 个元素在集合中，in[i] 为 true。
    static final String[] DAYS = { "Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun" };
    final boolean[] in = new boolean[DAYS.length];

    static BitVectorSet of(int... idx) {
        BitVectorSet s = new BitVectorSet();
        for (int i : idx) s.in[i] = true;
        return s;
    }

    boolean contains(int i) { return in[i]; }   // 属于判断 – O(1)

    BitVectorSet union(BitVectorSet o) {          // O(|U|)
        BitVectorSet r = new BitVectorSet();
        for (int i = 0; i < in.length; i++) r.in[i] = in[i] || o.in[i];
        return r;
    }

    BitVectorSet intersection(BitVectorSet o) {
        BitVectorSet r = new BitVectorSet();
        for (int i = 0; i < in.length; i++) r.in[i] = in[i] && o.in[i];
        return r;
    }

    BitVectorSet difference(BitVectorSet o) {
        BitVectorSet r = new BitVectorSet();
        for (int i = 0; i < in.length; i++) r.in[i] = in[i] && !o.in[i];
        return r;
    }

    // 子集？如果没有属于 A 但不属于 B 的元素，则 A ⊆ B。
    boolean subsetOf(BitVectorSet o) {
        for (int i = 0; i < in.length; i++) if (in[i] && !o.in[i]) return false;
        return true;
    }

    int size() {
        int c = 0;
        for (boolean b : in) if (b) c++;
        return c;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("{");
        for (int i = 0; i < in.length; i++) {
            if (in[i]) sb.append(sb.length() > 1 ? ", " : "").append(DAYS[i]);
        }
        return sb.append("}").toString();
    }

    // ----- 用位掩码实现同样的功能：int 的第 i 位表示第 i 个元素 -----
    static String maskToString(int m) {
        StringBuilder sb = new StringBuilder("{");
        for (int i = 0; i < DAYS.length; i++) {
            if ((m & (1 << i)) != 0) sb.append(sb.length() > 1 ? ", " : "").append(DAYS[i]);
        }
        return sb.append("}").toString();
    }

    public static void main(String[] args) {
        BitVectorSet a = of(0, 2, 3, 5); // 周一、周三、周四、周六
        BitVectorSet b = of(1, 2, 3);    // 周二、周三、周四
        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("Wed ∈ A? " + a.contains(2) + ", |A| = " + a.size());
        System.out.println("A ∩ B ⊆ A? " + a.intersection(b).subsetOf(a));

        // 位掩码：一条机器指令完成一次集合运算（全集至多 32/64 个元素）
        int ma = 0b0101101; // 周一（0）、周三（2）、周四（3）、周六（5）
        int mb = 0b0001110; // 周二（1）、周三（2）、周四（3）
        System.out.println("\nWith bit masks:");
        System.out.println("A | B  = " + maskToString(ma | mb));
        System.out.println("A & B  = " + maskToString(ma & mb));
        System.out.println("A & ~B = " + maskToString(ma & ~mb));
        System.out.println("|A| = Integer.bitCount(A) = " + Integer.bitCount(ma));
        System.out.println("A ⊆ B? " + ((ma & ~mb) == 0));
    }
}