diff options
Diffstat (limited to 'internal/sets/stringset_test.go')
| -rw-r--r-- | internal/sets/stringset_test.go | 425 |
1 files changed, 425 insertions, 0 deletions
diff --git a/internal/sets/stringset_test.go b/internal/sets/stringset_test.go new file mode 100644 index 0000000..2ed452c --- /dev/null +++ b/internal/sets/stringset_test.go @@ -0,0 +1,425 @@ +// Copyright 2017 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package sets + +import ( + "sort" + "testing" +) + +func checkSameStringSet(t *testing.T, set *StringSet, unique []string) { + // Check that lengths are the same. + want := len(unique) + got := set.Len() + + if got != want { + t.Errorf("NewStringSet(%v) want length %v, got %v", unique, want, got) + } + + // Check that all strings are present in set. + for _, s := range unique { + want := true + got := set.Contains(s) + + if got != want { + t.Errorf("Contains(%v) want %v, got %v", s, want, got) + } + } + + // Check that all elements are present in strings. + sort.Strings(unique) + + for i, got := range set.Sorted() { + want := unique[i] + + if got != want { + t.Errorf("Sorted(%d) want %v, got %v", i, want, got) + } + } +} + +func TestNewStringSet(t *testing.T) { + empty := NewStringSet() + want := 0 + got := empty.Len() + + if got != want { + t.Errorf("NewStringSet() want length %v, got %v", want, got) + } + + unique := []string{"a", "b", "c"} + set := NewStringSet(unique...) + checkSameStringSet(t, set, unique) + + // Append an already-present element. + nonUnique := append(unique, unique[0]) + set = NewStringSet(nonUnique...) + + // Non-unique unique should collapse to one. + want = len(unique) + got = set.Len() + + if got != want { + t.Errorf("NewStringSet(%v) want length %v, got %v", nonUnique, want, got) + } +} + +func TestStringSet_Copy(t *testing.T) { + // Check both copies represent the same set. + base := []string{"a", "b", "c"} + orig := NewStringSet(base...) + cpy := orig.Copy() + checkSameStringSet(t, orig, base) + checkSameStringSet(t, cpy, base) + + // Check the two copies are independent. + more := []string{"d"} + orig.Insert(more...) + more = append(base, more...) + checkSameStringSet(t, orig, more) + checkSameStringSet(t, cpy, base) +} + +func TestStringSet_Insert(t *testing.T) { + unique := []string{"a", "b", "c"} + set := NewStringSet(unique...) + + // Insert existing element, which should basically be a no-op. + set.Insert(unique[0]) + checkSameStringSet(t, set, unique) + + // Actually insert new unique elements. + additional := []string{"d", "e"} + longer := append(unique, additional...) + set.Insert(additional...) + checkSameStringSet(t, set, longer) +} + +func TestStringSet_Delete(t *testing.T) { + unique := []string{"a", "b", "c"} + set := NewStringSet(unique...) + + // Delete non-existent element, which should basically be a no-op. + set.Delete("z") + checkSameStringSet(t, set, unique) + + // Actually delete existing elements. + set.Delete(unique[1:]...) + checkSameStringSet(t, set, unique[:1]) +} + +func TestStringSet_Intersect(t *testing.T) { + input1 := []string{"a", "c", "d", "e", "f"} + input2 := []string{"b", "c", "e"} + + // Check Intersect(nil) returns an empty set. + setA := NewStringSet(input1...) + got := setA.Intersect(nil) + checkSameStringSet(t, got, []string{}) + // Check that the receiver is unchanged. + checkSameStringSet(t, setA, input1) + + // Check Intersect returns the correct result. + setB := NewStringSet(input2...) + got = setA.Intersect(setB) + want := []string{"c", "e"} + checkSameStringSet(t, got, want) + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setB, input2) + + // Reverse the inputs and verify Intersect produces the same results. + setA = NewStringSet(input2...) + setB = NewStringSet(input1...) + got = setA.Intersect(setB) + checkSameStringSet(t, got, want) + // Check the sources are again unchanged. + checkSameStringSet(t, setA, input2) + checkSameStringSet(t, setB, input1) +} + +func TestStringSet_Disjoint(t *testing.T) { + input1 := []string{"a", "c", "d", "e", "f"} + input2 := []string{"b", "c", "e"} + input3 := []string{"x", "y", "z"} + + // Check that sets are always disjoint with the empty set or nil + setA := NewStringSet(input1...) + emptySet := NewStringSet() + + if disjoint := setA.Disjoint(nil); !disjoint { + t.Errorf("Disjoint(%s, %v) want %v, got %v", setA, nil, true, disjoint) + } + + if disjoint := setA.Disjoint(emptySet); !disjoint { + t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, emptySet, true, disjoint) + } + + if disjoint := emptySet.Disjoint(setA); !disjoint { + t.Errorf("Disjoint(%s, %s) want %v, got %v", emptySet, setA, true, disjoint) + } + + if disjoint := emptySet.Disjoint(emptySet); !disjoint { + t.Errorf("Disjoint(%s, %s) want %v, got %v", emptySet, emptySet, true, disjoint) + } + + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, emptySet, []string{}) + + // Check two non-empty, non-nil disjoint sets. + setC := NewStringSet(input3...) + + if disjoint := setA.Disjoint(setC); !disjoint { + t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, setC, true, disjoint) + } + + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setC, input3) + + // Check that two intersecting sets are not Disjoint. + setB := NewStringSet(input2...) + + if disjoint := setA.Disjoint(setB); disjoint { + t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, setB, false, disjoint) + } + + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setB, input2) +} + +func TestStringSet_Difference(t *testing.T) { + input1 := []string{"a", "c", "d", "e", "f"} + input2 := []string{"b", "c", "e"} + input3 := []string{"x", "y", "z"} + + // Check Difference(nil) returns a copy of the receiver. + setA := NewStringSet(input1...) + got := setA.Difference(nil) + checkSameStringSet(t, got, input1) + // Check that the receiver is unchanged. + checkSameStringSet(t, setA, input1) + + // Check A - A returns the empty set. + got = setA.Difference(setA) + + if !got.Empty() { + t.Errorf("Difference(%s, %s).Empty() want %v, got %v", + setA, setA, true, false) + } + + checkSameStringSet(t, got, []string{}) + // Check that the receiver is unchanged. + checkSameStringSet(t, setA, input1) + + // Check A - C simply returns elements in A if A and C are disjoint. + setC := NewStringSet(input3...) + got = setA.Difference(setC) + checkSameStringSet(t, got, input1) + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setC, input3) + + // Check A - B returns elements in A not in B. + setB := NewStringSet(input2...) + got = setA.Difference(setB) + want := []string{"a", "d", "f"} + checkSameStringSet(t, got, want) + + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setB, input2) + + // Check B - A returns elements in B not in A. + got = setB.Difference(setA) + want = []string{"b"} + checkSameStringSet(t, got, want) + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setB, input2) +} + +func TestStringSet_Unique(t *testing.T) { + input1 := []string{"a", "c", "d", "e", "f"} + input2 := []string{"b", "c", "e"} + input3 := []string{"x", "y", "z"} + + // Check Unique(nil) returns a copy of the receiver. + setA := NewStringSet(input1...) + got := setA.Unique(nil) + checkSameStringSet(t, got, input1) + // Check that the receiver is unchanged. + checkSameStringSet(t, setA, input1) + + // Check Unique returns only elements in A and B not in both A and B. + setB := NewStringSet(input2...) + got = setA.Unique(setB) + want := []string{"a", "b", "d", "f"} + checkSameStringSet(t, got, want) + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setB, input2) + + // Check Unique of two disjoint sets is the Union of those sets. + setC := NewStringSet(input3...) + got = setA.Unique(setC) + union := setA.Union(setC) + + if equal := union.Equal(got); !equal { + t.Errorf("Union of disjoint Equal(%s, %s) want %v, got %v", + union, got, true, equal) + } + + // Check Unique is the Union of A - B and B - A. + aNotInB := setA.Difference(setB) + bNotInA := setB.Difference(setA) + union = aNotInB.Union(bNotInA) + want = []string{"a", "b", "d", "f"} + checkSameStringSet(t, union, want) + got = setA.Unique(setB) + + if equal := union.Equal(got); !equal { + t.Errorf("Union of differences Equal(%s, %s) want %v, got %v", + union, got, true, equal) + } + + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setB, input2) +} + +func TestStringSet_Equal(t *testing.T) { + input1 := []string{"a", "c", "d", "e", "f"} + input2 := []string{"b", "c", "e"} + input3 := []string{"a", "c", "d", "e", "g"} + + // Check Equal(nil) returns false. + setA := NewStringSet(input1...) + + if equal := setA.Equal(nil); equal { + t.Errorf("Equal(%s, %v) want %v, got %v", setA, nil, false, true) + } + + // Check that the receiver is unchanged. + checkSameStringSet(t, setA, input1) + + // Check Equal returns true for a set and itself. + if equal := setA.Equal(setA); !equal { + t.Errorf("Equal(%s, %s) want %v, got %v", setA, setA, true, false) + } + + // Check that the receiver is unchanged. + checkSameStringSet(t, setA, input1) + + // Check Equal returns false for sets of non-equal length. + setB := NewStringSet(input2...) + + if equal := setA.Equal(setB); equal { + t.Errorf("Equal(%s, %s) want %v, got %v", setA, setB, false, true) + } + + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setB, input2) + + // Check Equal returns false for equal-length sets with different elements. + setC := NewStringSet(input3...) + + if equal := setA.Equal(setC); equal { + t.Errorf("Equal(%s, %s) want %v, got %v", setA, setC, false, true) + } + + if equal := setC.Equal(setA); equal { + t.Errorf("Equal(%s, %s) want %v, got %v", setC, setA, false, true) + } + + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setC, input3) + + // Check Equal returns true for a set with itself. + if equal := setA.Equal(setA); !equal { + t.Errorf("Equal(%s, %s) want %v, got %v", setA, setA, true, false) + } + + // Also check the source is unchanged. + checkSameStringSet(t, setA, input1) + + // Check Equal returns true for two separate equal sets. + anotherA := NewStringSet(input1...) + + if equal := setA.Equal(anotherA); !equal { + t.Errorf("Equal(%s, %s) want %v, got %v", setA, anotherA, true, false) + } + + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, anotherA, input1) + + // Check for equality comparing to nil struct. + var nilSet *StringSet + if equal := nilSet.Equal(setA); equal { + t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, setA, false, true) + } + if equal := setA.Equal(nilSet); equal { + t.Errorf("Equal(%s, %s) want %v, got %v", setA, nilSet, false, true) + } + if equal := nilSet.Equal(nilSet); !equal { + t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, nilSet, true, false) + } + + // Edge case: consider the empty set to be different than the nil set. + emptySet := NewStringSet() + if equal := nilSet.Equal(emptySet); equal { + t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, emptySet, false, true) + } + if equal := emptySet.Equal(nilSet); equal { + t.Errorf("Equal(%s, %s) want %v, got %v", emptySet, nilSet, false, true) + } + if equal := emptySet.Equal(emptySet); !equal { + t.Errorf("Equal(%s, %s) want %v, got %v", emptySet, emptySet, true, false) + } +} + +func TestStringSet_Union(t *testing.T) { + input1 := []string{"a", "c", "d", "e", "f"} + input2 := []string{"b", "c", "e"} + + // Check Union(nil) returns a copy of the receiver. + setA := NewStringSet(input1...) + got := setA.Union(nil) + checkSameStringSet(t, got, input1) + // Check that the receiver is unchanged. + checkSameStringSet(t, setA, input1) + + // Check Union returns the correct result. + setB := NewStringSet(input2...) + got = setA.Union(setB) + want := []string{"a", "b", "c", "d", "e", "f"} + checkSameStringSet(t, got, want) + // Also check the sources are unchanged. + checkSameStringSet(t, setA, input1) + checkSameStringSet(t, setB, input2) + + // Reverse the inputs and verify Union produces the same results. + setA = NewStringSet(input2...) + setB = NewStringSet(input1...) + got = setA.Union(setB) + checkSameStringSet(t, got, want) + // Check the sources are again unchanged. + checkSameStringSet(t, setA, input2) + checkSameStringSet(t, setB, input1) +} |