// 第 6 周 – 用位向量和位掩码表示集合
// 运行：go run ./w06/bitvectorset
package main

import (
	"fmt"
	"math/bits"
	"strings"
)

var days = []string{"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"}

// BitVectorSet：如果全集的第 i 个元素在集合中，s[i] 为 true。
type BitVectorSet [7]bool

func of(idx ...int) BitVectorSet {
	var s BitVectorSet
	for _, i := range idx {
		s[i] = true
	}
	return s
}

func (s BitVectorSet) Contains(i int) bool { return s[i] } // O(1)

func (s BitVectorSet) Union(o BitVectorSet) (r BitVectorSet) { // O(|U|)
	for i := range s {
		r[i] = s[i] || o[i]
	}
	return
}

func (s BitVectorSet) Intersection(o BitVectorSet) (r BitVectorSet) {
	for i := range s {
		r[i] = s[i] && o[i]
	}
	return
}

func (s BitVectorSet) Difference(o BitVectorSet) (r BitVectorSet) {
	for i := range s {
		r[i] = s[i] && !o[i]
	}
	return
}

func (s BitVectorSet) SubsetOf(o BitVectorSet) bool {
	for i := range s {
		if s[i] && !o[i] {
			return false
		}
	}
	return true
}

func (s BitVectorSet) String() string {
	var parts []string
	for i, b := range s {
		if b {
			parts = append(parts, days[i])
		}
	}
	return "{" + strings.Join(parts, ", ") + "}"
}

// 位掩码：uint 的第 i 位表示第 i 个元素
func maskString(m uint) string {
	var parts []string
	for i := range days {
		if m&(1<<i) != 0 {
			parts = append(parts, days[i])
		}
	}
	return "{" + strings.Join(parts, ", ") + "}"
}

func main() {
	a := of(0, 2, 3, 5) // 周一、周三、周四、周六
	b := of(1, 2, 3)    // 周二、周三、周四
	fmt.Println("A =", a, ", B =", b)
	fmt.Println("A ∪ B =", a.Union(b))
	fmt.Println("A ∩ B =", a.Intersection(b))
	fmt.Println(`A \ B =`, a.Difference(b))
	fmt.Println("Wed ∈ A?", a.Contains(2), ", A ∩ B ⊆ A?", a.Intersection(b).SubsetOf(a))

	var ma uint = 0b0101101
	var mb uint = 0b0001110
	fmt.Println("\nWith bit masks:")
	fmt.Println("A | B  =", maskString(ma|mb))
	fmt.Println("A & B  =", maskString(ma&mb))
	fmt.Println("A &^ B =", maskString(ma&^mb), "  (Go: &^ = 'and not')")
	fmt.Println("|A| =", bits.OnesCount(ma), ", A ⊆ B?", ma&^mb == 0)
}