summaryrefslogtreecommitdiff
path: root/go/custom-set/custom_set_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'go/custom-set/custom_set_test.go')
-rw-r--r--go/custom-set/custom_set_test.go268
1 files changed, 268 insertions, 0 deletions
diff --git a/go/custom-set/custom_set_test.go b/go/custom-set/custom_set_test.go
new file mode 100644
index 0000000..7b8d0ba
--- /dev/null
+++ b/go/custom-set/custom_set_test.go
@@ -0,0 +1,268 @@
+package stringset
+
+// Implement Set as a collection of unique string values.
+//
+// API:
+//
+// New() Set
+// NewFromSlice([]string) Set
+// (s Set) Add(string) // modify s
+// (s Set) Delete(string) // modify s
+// (s Set) Has(string) bool
+// (s Set) IsEmpty() bool
+// (s Set) Len() int
+// (s Set) Slice() []string
+// (s Set) String() string
+// Equal(s1, s2 Set) bool
+// Subset(s1, s2 Set) bool // return s1 ⊆ s2
+// Disjoint(s1, s2 Set) bool
+// Intersection(s1, s2 Set) Set
+// Union(s1, s2 Set) Set
+// Difference(s1, s2 Set) Set // return s1 ∖ s2
+// SymmetricDifference(s1, s2 Set) Set
+//
+// For Set.String, use '{' and '}', output elements as double-quoted strings
+// safely escaped with Go syntax, and use a comma and a single space between
+// elements. For example {"a", "b"}.
+// Format the empty set as {}.
+
+import (
+ "math/rand"
+ "reflect"
+ "strconv"
+ "testing"
+)
+
+const targetTestVersion = 3
+
+func TestTestVersion(t *testing.T) {
+ if testVersion != targetTestVersion {
+ t.Fatalf("Found testVersion = %v, want %v", testVersion, targetTestVersion)
+ }
+}
+
+// A first set of tests uses Set.String() to judge correctness.
+
+func TestNew(t *testing.T) {
+ // New must return an empty set.
+ want := "{}"
+ if got := New().String(); got != want {
+ t.Fatalf(`New().String() = %s, want %s.`, got, want)
+ }
+}
+
+func TestNewFromSlice(t *testing.T) {
+ // nil slice should give empty set
+ want := "{}"
+ if got := NewFromSlice(nil).String(); got != want {
+ t.Fatalf(`NewFromSlice(nil) = %s, want %s.`, got, want)
+ }
+
+ // slice with one element:
+ want = `{"a"}`
+ if got := NewFromSlice([]string{"a"}).String(); got != want {
+ t.Fatalf(`NewFromSlice([]string{"a"}) = %s, want %s.`, got, want)
+ }
+
+ // slice with repeated element:
+ if got := NewFromSlice([]string{"a", "a"}).String(); got != want {
+ t.Fatalf(`NewFromSlice([]string{"a", "a"}) = %s, want %s.`, got, want)
+ }
+
+ // slice with two elements:
+ got := NewFromSlice([]string{"a", "b"}).String()
+ want1 := `{"a", "b"}`
+ want2 := `{"b", "a"}`
+ if got != want1 && got != want2 { // order undefined
+ t.Fatalf(`NewFromSlice([]string{"a", "b"}) = %s, want %s or (%s).`,
+ got, want1, want2)
+ }
+}
+
+func TestSlice(t *testing.T) {
+ // empty set should produce empty slice
+ s := New()
+ if l := s.Slice(); len(l) != 0 {
+ t.Fatalf(`s.Slice() = %q, want []`, l)
+ }
+
+ // one element:
+ want := []string{"a"}
+ s = NewFromSlice(want)
+ got := s.Slice()
+ if !reflect.DeepEqual(got, want) {
+ t.Fatalf(`%v Slice = %q, want %q`, s, got, want)
+ }
+
+ // two elements:
+ w1 := []string{"a", "b"}
+ w2 := []string{"b", "a"}
+ s = NewFromSlice(w1)
+ got = s.Slice()
+ if !reflect.DeepEqual(got, w1) && !reflect.DeepEqual(got, w2) {
+ t.Fatalf(`%v Slice = %q, want %q`, s, got, w1)
+ }
+}
+
+// Trusting NewFromSlice now, remaining tests are table driven, taking data
+// from cases_test.go and building sets with NewFromSlice.
+
+// test case types used in cases_test.go
+type (
+ // binary function, bool result (Equal, Subset, Disjoint)
+ binBoolCase struct {
+ set1 []string
+ set2 []string
+ want bool
+ }
+ // unary function, bool result (IsEmpty)
+ unaryBoolCase struct {
+ set []string
+ want bool
+ }
+ // unary function, int result (Len)
+ unaryIntCase struct {
+ set []string
+ want int
+ }
+ // set-element function, bool result (Has)
+ eleBoolCase struct {
+ set []string
+ ele string
+ want bool
+ }
+ // set-element operator (Add, Delete)
+ eleOpCase struct {
+ set []string
+ ele string
+ want []string
+ }
+ // set-set operator (Union, Intersection, Difference, Symmetric-Difference)
+ binOpCase struct {
+ set1 []string
+ set2 []string
+ want []string
+ }
+)
+
+// helper for testing Equal, Subset, Disjoint
+func testBinBool(name string, f func(Set, Set) bool, cases []binBoolCase, t *testing.T) {
+ for _, tc := range cases {
+ s1 := NewFromSlice(tc.set1)
+ s2 := NewFromSlice(tc.set2)
+ got := f(s1, s2)
+ if got != tc.want {
+ t.Fatalf("%s(%v, %v) = %t, want %t", name, s1, s2, got, tc.want)
+ }
+ }
+}
+
+func TestEqual(t *testing.T) {
+ testBinBool("Equal", Equal, eqCases, t)
+}
+
+// With Equal tested, remaining tests use it to judge correctness.
+
+// helper for testing Add, Delete
+func testEleOp(name string, op func(Set, string), cases []eleOpCase, t *testing.T) {
+ for _, tc := range cases {
+ s := NewFromSlice(tc.set)
+ op(s, tc.ele)
+ want := NewFromSlice(tc.want)
+ if !Equal(s, want) {
+ t.Fatalf("%v %s %q = %v, want %v",
+ NewFromSlice(tc.set), name, tc.ele, s, want)
+ }
+ }
+}
+
+func TestAdd(t *testing.T) {
+ testEleOp("Add", Set.Add, addCases, t)
+}
+
+func TestDelete(t *testing.T) {
+ testEleOp("Delete", Set.Delete, delCases, t)
+}
+
+func TestHas(t *testing.T) {
+ for _, tc := range hasCases {
+ s := NewFromSlice(tc.set)
+ got := s.Has(tc.ele)
+ if got != tc.want {
+ t.Fatalf("%v Has %q = %t, want %t", s, tc.ele, got, tc.want)
+ }
+ }
+}
+
+func TestIsEmpty(t *testing.T) {
+ for _, tc := range emptyCases {
+ s := NewFromSlice(tc.set)
+ got := s.IsEmpty()
+ if got != tc.want {
+ t.Fatalf("%v IsEmpty = %t, want %t", s, got, tc.want)
+ }
+ }
+}
+
+func TestLen(t *testing.T) {
+ for _, tc := range lenCases {
+ s := NewFromSlice(tc.set)
+ got := s.Len()
+ if got != tc.want {
+ t.Fatalf("%v Len = %d, want %d", s, got, tc.want)
+ }
+ }
+}
+
+func TestSubset(t *testing.T) {
+ testBinBool("Subset", Subset, subsetCases, t)
+}
+
+func TestDisjoint(t *testing.T) {
+ testBinBool("Disjoint", Disjoint, disjointCases, t)
+}
+
+// helper for testing Union, Intersection, Difference, SymmetricDifference
+func testBinOp(name string, f func(Set, Set) Set, cases []binOpCase, t *testing.T) {
+ for _, tc := range cases {
+ s1 := NewFromSlice(tc.set1)
+ s2 := NewFromSlice(tc.set2)
+ want := NewFromSlice(tc.want)
+ got := f(s1, s2)
+ if !Equal(got, want) {
+ t.Fatalf("%s(%v, %v) = %v, want %v", name, s1, s2, got, want)
+ }
+ }
+}
+
+func TestUnion(t *testing.T) {
+ testBinOp("Union", Union, unionCases, t)
+}
+
+func TestIntersection(t *testing.T) {
+ testBinOp("Intersection", Intersection, intersectionCases, t)
+}
+
+func TestDifference(t *testing.T) {
+ testBinOp("Difference", Difference, differenceCases, t)
+}
+
+func TestSymmetricDifference(t *testing.T) {
+ testBinOp("SymmetricDifference", SymmetricDifference, symmetricDifferenceCases, t)
+}
+
+func BenchmarkNewFromSlice1e1(b *testing.B) { bench(1e1, b) }
+func BenchmarkNewFromSlice1e2(b *testing.B) { bench(1e2, b) }
+func BenchmarkNewFromSlice1e3(b *testing.B) { bench(1e3, b) }
+func BenchmarkNewFromSlice1e4(b *testing.B) { bench(1e4, b) }
+
+func bench(nAdd int, b *testing.B) {
+ s := make([]string, nAdd)
+ for i := range s {
+ s[i] = strconv.Itoa(rand.Intn(len(s)))
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ NewFromSlice(s)
+ }
+}