134 lines
2.8 KiB
Go
134 lines
2.8 KiB
Go
package main
|
||
|
||
import (
|
||
"fmt"
|
||
"math/big"
|
||
)
|
||
|
||
func main() {
|
||
// create an empty set
|
||
var s0 big.Int
|
||
|
||
// create sets with elements
|
||
s1 := newSet(3)
|
||
s2 := newSet(3, 1)
|
||
s3 := newSet(3, 1, 4, 1, 5, 9)
|
||
|
||
// output
|
||
fmt.Println("s0:", format(s0))
|
||
fmt.Println("s1:", format(s1))
|
||
fmt.Println("s2:", format(s2))
|
||
fmt.Println("s3:", format(s3))
|
||
|
||
// element predicate
|
||
fmt.Printf("%v ∈ s0: %t\n", 3, hasElement(s0, 3))
|
||
fmt.Printf("%v ∈ s3: %t\n", 3, hasElement(s3, 3))
|
||
fmt.Printf("%v ∈ s3: %t\n", 2, hasElement(s3, 2))
|
||
|
||
// union
|
||
b := newSet(4, 2)
|
||
fmt.Printf("s3 ∪ %v: %v\n", format(b), format(union(s3, b)))
|
||
|
||
// intersection
|
||
fmt.Printf("s3 ∩ %v: %v\n", format(b), format(intersection(s3, b)))
|
||
|
||
// difference
|
||
fmt.Printf("s3 \\ %v: %v\n", format(b), format(difference(s3, b)))
|
||
|
||
// subset predicate
|
||
fmt.Printf("%v ⊆ s3: %t\n", format(b), subset(b, s3))
|
||
fmt.Printf("%v ⊆ s3: %t\n", format(s2), subset(s2, s3))
|
||
fmt.Printf("%v ⊆ s3: %t\n", format(s0), subset(s0, s3))
|
||
|
||
// equality
|
||
s2Same := newSet(1, 3)
|
||
fmt.Printf("%v = s2: %t\n", format(s2Same), equal(s2Same, s2))
|
||
|
||
// proper subset
|
||
fmt.Printf("%v ⊂ s2: %t\n", format(s2Same), properSubset(s2Same, s2))
|
||
fmt.Printf("%v ⊂ s3: %t\n", format(s2Same), properSubset(s2Same, s3))
|
||
|
||
// delete
|
||
remove(&s3, 3)
|
||
fmt.Println("s3, 3 removed:", format(s3))
|
||
}
|
||
|
||
func newSet(ms ...int) (set big.Int) {
|
||
for _, m := range ms {
|
||
set.SetBit(&set, m, 1)
|
||
}
|
||
return
|
||
}
|
||
|
||
func remove(set *big.Int, m int) {
|
||
set.SetBit(set, m, 0)
|
||
}
|
||
|
||
func format(set big.Int) string {
|
||
if len(set.Bits()) == 0 {
|
||
return "∅"
|
||
}
|
||
r := "{"
|
||
for e, l := 0, set.BitLen(); e < l; e++ {
|
||
if set.Bit(e) == 1 {
|
||
r = fmt.Sprintf("%s%v, ", r, e)
|
||
}
|
||
}
|
||
return r[:len(r)-2] + "}"
|
||
}
|
||
|
||
func hasElement(set big.Int, m int) bool {
|
||
return set.Bit(m) == 1
|
||
}
|
||
|
||
func union(a, b big.Int) (set big.Int) {
|
||
set.Or(&a, &b)
|
||
return
|
||
}
|
||
|
||
func intersection(a, b big.Int) (set big.Int) {
|
||
set.And(&a, &b)
|
||
return
|
||
}
|
||
|
||
func difference(a, b big.Int) (set big.Int) {
|
||
set.AndNot(&a, &b)
|
||
return
|
||
}
|
||
|
||
func subset(a, b big.Int) bool {
|
||
ab := a.Bits()
|
||
bb := b.Bits()
|
||
if len(ab) > len(bb) {
|
||
return false
|
||
}
|
||
for i, aw := range ab {
|
||
if aw&^bb[i] != 0 {
|
||
return false
|
||
}
|
||
}
|
||
return true
|
||
}
|
||
|
||
func equal(a, b big.Int) bool {
|
||
return a.Cmp(&b) == 0
|
||
}
|
||
|
||
func properSubset(a, b big.Int) (p bool) {
|
||
ab := a.Bits()
|
||
bb := b.Bits()
|
||
if len(ab) > len(bb) {
|
||
return false
|
||
}
|
||
for i, aw := range ab {
|
||
bw := bb[i]
|
||
if aw&^bw != 0 {
|
||
return false
|
||
}
|
||
if aw != bw {
|
||
p = true
|
||
}
|
||
}
|
||
return
|
||
}
|