set.go

package set

type Hash int64
type Elem interface {
	Hash() Hash
	Equals(e Elem) bool
}

type Set struct {
	buckets map[Hash][]Elem
	size int
	...
}

func New() *Set { return &Set{make(map[Hash][]Elem)} }
func (s *Set) Insert(v Elem) { ... }
func (s *Set) Remove(v Elem) { ... }
func (s *Set) Union(s *Set) *Set { ... }
func (s *Set) Count() int { ... }
func (s *Set) Contains(v Elem) bool { ... }
func (s *Set) ForEach(fn func(Elem)) { ... }

set_test.go

package set_test

import "set"

type elem int
func (t elem) Hash() set.Hash { return Hash(t%7) }
func (t elem) Equals(v set.Elem) bool { return v.(elem) == t }

func randset(max, count int) *set.Set {
	s := set.New()
	for i := 0; i < count; i += 1 {
		s.Insert(elem(rand.IntN(max)))
	}
	return s
}

func TestOperators(t *testing.T) {
	a, b := randset(100, 50), randset(100, 50)
	
	union := a.Union(b)
	a_min_b := a.Subtract(b)
	b_min_a := b.Subtract(a)

	constraint := func(v bool, msg string) {
		if !v {
			t.Fatalf("%s: a=%+v b=%+v", msg, a, b)
		}
	}

	a.ForEach(func(v Elem){
		x := v.(elem)
		constraint(union.Contains(x), "union must contain x from a")
		constraint(!b_min_a.Contains(x), "b - a should not contain x from a")
		if !b.Contains(x) {
			constraint(a_min_b.Contains(x), "a - b should contain x from a if it doesn't exist in b")
		}
	})

	b.ForEach(func(v Elem){
		x := v.(elem)
		constraint(union.Contains(x), "union must contain x from a")
		constraint(!a_min_b.Contains(x), "a - b should not contain x from b")
		if !a.Contains(x) {
			constraint(b_min_a.Contains(x), "b - a should contain x from b if it doesn't exist in a")
		}
	})
}