// Week 6 – A set represented by a boolean vector (and by a bit mask)
// Run: java BitVectorSet.java
public class BitVectorSet {

    // The universe: the days of the week. A set is a boolean vector of length n:
    // in[i] is true if the i-th element of the universe is in the set.
    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]; }   // membership – 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;
    }

    // Subset? A ⊆ B if there is no element that is in A but not in 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();
    }

    // ----- The same with a bit mask: the i-th bit of an int marks the i-th element -----
    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); // Mon, Wed, Thu, Sat
        BitVectorSet b = of(1, 2, 3);    // Tue, Wed, Thu
        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));

        // Bit mask: a single machine instruction for a whole set operation (universe of at most 32/64 elements)
        int ma = 0b0101101; // Mon(0), Wed(2), Thu(3), Sat(5)
        int mb = 0b0001110; // Tue(1), Wed(2), Thu(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));
    }
}