graph/internal/set: improve test coverage and docs
MODIFY
graph/internal/set/set.go
graph/internal/set/set.go
@@ -129,14 +129,17 @@ func (s *Nodes) clear() {
}
}
-// Copy performs a perfect copy from src to dst (meaning the sets will
-// be equal).
+// Copy performs a perfect copy from src to dst returning the result.
+// If len(dst) is not 0, a new Nodes is made and returned.
func (dst Nodes) Copy(src Nodes) Nodes {
+ // FIXME(kortschak): The behaviour is this method is very surprising.
+ // Whether the return is required or not depends on len(dst).
+
if same(src, dst) {
return dst
}
- if len(dst) > 0 {
+ if len(dst) != 0 {
dst = make(Nodes, len(src))
}
@@ -221,31 +224,29 @@ func (dst Nodes) Union(a, b Nodes) Nodes {
// {a,b,c} INTERSECT {d,e,f} = {}
//
func (dst Nodes) Intersect(a, b Nodes) Nodes {
- var swap Nodes
-
if same(a, b) {
return dst.Copy(a)
}
- if same(a, dst) {
- swap = b
- } else if same(b, dst) {
- swap = a
- } else {
- dst.clear()
+ var swap Nodes
+ switch {
+ default:
+ dst.clear()
if len(a) > len(b) {
a, b = b, a
}
-
for e, n := range a {
if _, ok := b[e]; ok {
dst[e] = n
}
}
-
return dst
- }
+ case same(a, dst):
+ swap = b
+ case same(b, dst):
+ swap = a
+ }
for e := range dst {
if _, ok := swap[e]; !ok {
delete(dst, e)

MODIFY
graph/internal/set/set_test.go
graph/internal/set/set_test.go
package set
-import "testing"
+import (
+ "reflect"
+ "testing"
+)
type node int64
@@ -19,8 +22,283 @@ func (s Nodes) count() int {
// of a map[int]struct{} to uintptr is a valid test for perfect identity between
// set values. If any of the tests in TestSame fail, the package is broken and same
// must be reimplemented to conform to the runtime map implementation. The relevant
-// code to look at (at least for gc) is in runtime/hashmap.{h,goc}.
-func TestSame(t *testing.T) {
+// code to look at (at least for gc) is the hmap type in runtime/map.go.
+
+func TestSameInt64s(t *testing.T) {
+ var (
+ a = make(Int64s)
+ b = make(Int64s)
+ c = a
+ )
+
+ if int64sSame(a, b) {
+ t.Error("Independently created sets test as same")
+ }
+ if !int64sSame(a, c) {
+ t.Error("Set copy and original test as not same.")
+ }
+ a.Add(1)
+ if !int64sSame(a, c) {
+ t.Error("Set copy and original test as not same after addition.")
+ }
+ if !int64sSame(nil, nil) {
+ t.Error("nil sets test as not same.")
+ }
+ if int64sSame(b, nil) {
+ t.Error("nil and empty sets test as same.")
+ }
+}
+
+func TestAddInt64s(t *testing.T) {
+ s := make(Int64s)
+ if s == nil {
+ t.Fatal("Set cannot be created successfully")
+ }
+
+ if s.Count() != 0 {
+ t.Error("Set somehow contains new elements upon creation")
+ }
+
+ s.Add(1)
+ s.Add(3)
+ s.Add(5)
+
+ if s.Count() != 3 {
+ t.Error("Incorrect number of set elements after adding")
+ }
+
+ if !s.Has(1) || !s.Has(3) || !s.Has(5) {
+ t.Error("Set doesn't contain element that was added")
+ }
+
+ s.Add(1)
+
+ if s.Count() > 3 {
+ t.Error("Set double-adds element (element not unique)")
+ } else if s.Count() < 3 {
+ t.Error("Set double-add lowered len")
+ }
+
+ if !s.Has(1) {
+ t.Error("Set doesn't contain double-added element")
+ }
+
+ if !s.Has(3) || !s.Has(5) {
+ t.Error("Set removes element on double-add")
+ }
+}
+
+func TestRemoveInt64s(t *testing.T) {
+ s := make(Int64s)
+
+ s.Add(1)
+ s.Add(3)
+ s.Add(5)
+
+ s.Remove(1)
+
+ if s.Count() != 2 {
+ t.Error("Incorrect number of set elements after removing an element")
+ }
+
+ if s.Has(1) {
+ t.Error("Element present after removal")
+ }
+
+ if !s.Has(3) || !s.Has(5) {
+ t.Error("Set remove removed wrong element")
+ }
+
+ s.Remove(1)
+
+ if s.Count() != 2 || s.Has(1) {
+ t.Error("Double set remove does something strange")
+ }
+
+ s.Add(1)
+
+ if s.Count() != 3 || !s.Has(1) {
+ t.Error("Cannot add element after removal")
+ }
+}
+
+func TestSelfEqualInt64s(t *testing.T) {
+ s := make(Int64s)
+
+ if !Int64sEqual(s, s) {
+ t.Error("Set is not equal to itself")
+ }
+
+ s.Add(1)
+
+ if !Int64sEqual(s, s) {
+ t.Error("Set ceases self equality after adding element")
+ }
+}
+
+func TestEqualInt64s(t *testing.T) {
+ a := make(Int64s)
+ b := make(Int64s)
+
+ if !Int64sEqual(a, b) {
+ t.Error("Two different empty sets not equal")
+ }
+
+ a.Add(1)
+ if Int64sEqual(a, b) {
+ t.Error("Two different sets with different sizes equal")
+ }
+
+ b.Add(1)
+ if !Int64sEqual(a, b) {
+ t.Error("Two sets with same element not equal")
+ }
+
+ b.Remove(1)
+ b.Add(2)
+ if Int64sEqual(a, b) {
+ t.Error("Two different sets with different elements equal")
+ }
+}
+
+func TestSameInts(t *testing.T) {
+ var (
+ a = make(Ints)
+ b = make(Ints)
+ c = a
+ )
+
+ if intsSame(a, b) {
+ t.Error("Independently created sets test as same")
+ }
+ if !intsSame(a, c) {
+ t.Error("Set copy and original test as not same.")
+ }
+ a.Add(1)
+ if !intsSame(a, c) {
+ t.Error("Set copy and original test as not same after addition.")
+ }
+ if !intsSame(nil, nil) {
+ t.Error("nil sets test as not same.")
+ }
+ if intsSame(b, nil) {
+ t.Error("nil and empty sets test as same.")
+ }
+}
+
+func TestAddInts(t *testing.T) {
+ s := make(Ints)
+ if s == nil {
+ t.Fatal("Set cannot be created successfully")
+ }
+
+ if s.Count() != 0 {
+ t.Error("Set somehow contains new elements upon creation")
+ }
+
+ s.Add(1)
+ s.Add(3)
+ s.Add(5)
+
+ if s.Count() != 3 {
+ t.Error("Incorrect number of set elements after adding")
+ }
+
+ if !s.Has(1) || !s.Has(3) || !s.Has(5) {
+ t.Error("Set doesn't contain element that was added")
+ }
+
+ s.Add(1)
+
+ if s.Count() > 3 {
+ t.Error("Set double-adds element (element not unique)")
+ } else if s.Count() < 3 {
+ t.Error("Set double-add lowered len")
+ }
+
+ if !s.Has(1) {
+ t.Error("Set doesn't contain double-added element")
+ }
+
+ if !s.Has(3) || !s.Has(5) {
+ t.Error("Set removes element on double-add")
+ }
+}
+
+func TestRemoveInts(t *testing.T) {
+ s := make(Ints)
+
+ s.Add(1)
+ s.Add(3)
+ s.Add(5)
+
+ s.Remove(1)
+
+ if s.Count() != 2 {
+ t.Error("Incorrect number of set elements after removing an element")
+ }
+
+ if s.Has(1) {
+ t.Error("Element present after removal")
+ }
+
+ if !s.Has(3) || !s.Has(5) {
+ t.Error("Set remove removed wrong element")
+ }
+
+ s.Remove(1)
+
+ if s.Count() != 2 || s.Has(1) {
+ t.Error("Double set remove does something strange")
+ }
+
+ s.Add(1)
+
+ if s.Count() != 3 || !s.Has(1) {
+ t.Error("Cannot add element after removal")
+ }
+}
+
+func TestSelfEqualInts(t *testing.T) {
+ s := make(Ints)
+
+ if !IntsEqual(s, s) {
+ t.Error("Set is not equal to itself")
+ }
+
+ s.Add(1)
+
+ if !IntsEqual(s, s) {
+ t.Error("Set ceases self equality after adding element")
+ }
+}
+
+func TestEqualInts(t *testing.T) {
+ a := make(Ints)
+ b := make(Ints)
+
+ if !IntsEqual(a, b) {
+ t.Error("Two different empty sets not equal")
+ }
+
+ a.Add(1)
+ if IntsEqual(a, b) {
+ t.Error("Two different sets with different sizes equal")
+ }
+
+ b.Add(1)
+ if !IntsEqual(a, b) {
+ t.Error("Two sets with same element not equal")
+ }
+
+ b.Remove(1)
+ b.Add(2)
+ if IntsEqual(a, b) {
+ t.Error("Two different sets with different elements equal")
+ }
+}
+
+func TestSameNodes(t *testing.T) {
var (
a = make(Nodes)
b = make(Nodes)
@@ -45,7 +323,7 @@ func TestSame(t *testing.T) {
}
}
-func TestAdd(t *testing.T) {
+func TestAddNodes(t *testing.T) {
s := make(Nodes)
if s == nil {
t.Fatal("Set cannot be created successfully")
@@ -90,7 +368,7 @@ func TestAdd(t *testing.T) {
}
}
-func TestRemove(t *testing.T) {
+func TestRemoveNodes(t *testing.T) {
s := make(Nodes)
s.Add(node(1))
@@ -124,7 +402,7 @@ func TestRemove(t *testing.T) {
}
}
-func TestClear(t *testing.T) {
+func TestClearNodes(t *testing.T) {
s := make(Nodes)
s.Add(node(8))
@@ -138,7 +416,7 @@ func TestClear(t *testing.T) {
}
}
-func TestSelfEqual(t *testing.T) {
+func TestSelfEqualNodes(t *testing.T) {
s := make(Nodes)
if !Equal(s, s) {
@@ -152,7 +430,7 @@ func TestSelfEqual(t *testing.T) {
}
}
-func TestEqual(t *testing.T) {
+func TestEqualNodes(t *testing.T) {
a := make(Nodes)
b := make(Nodes)
@@ -162,16 +440,22 @@ func TestEqual(t *testing.T) {
a.Add(node(1))
if Equal(a, b) {
- t.Error("Two different sets with different elements not equal")
+ t.Error("Two different sets with different sizes equal")
}
b.Add(node(1))
if !Equal(a, b) {
t.Error("Two sets with same element not equal")
}
+
+ b.Remove(node(1))
+ b.Add(node(2))
+ if Equal(a, b) {
+ t.Error("Two different sets with different elements equal")
+ }
}
-func TestCopy(t *testing.T) {
+func TestCopyNodes(t *testing.T) {
a := make(Nodes)
b := make(Nodes)
@@ -182,17 +466,23 @@ func TestCopy(t *testing.T) {
b.Copy(a)
if !Equal(a, b) {
- t.Fatalf("Two sets not equal after copy")
+ t.Fatalf("Two sets not equal after copy: %v != %v", a, b)
}
b.Remove(node(1))
if Equal(a, b) {
- t.Errorf("Mutating one set mutated another after copy")
+ t.Errorf("Mutating one set mutated another after copy: %v == %v", a, b)
+ }
+
+ b = b.Copy(a) // Assignment is needed because b is not empty.
+
+ if !Equal(a, b) {
+ t.Fatalf("Two sets not equal after second copy: %v != %v", a, b)
}
}
-func TestSelfCopy(t *testing.T) {
+func TestSelfCopyNodes(t *testing.T) {
a := make(Nodes)
a.Add(node(1))
@@ -205,7 +495,7 @@ func TestSelfCopy(t *testing.T) {
}
}
-func TestUnionSame(t *testing.T) {
+func TestUnionSameNodes(t *testing.T) {
a := make(Nodes)
b := make(Nodes)
c := make(Nodes)
@@ -235,7 +525,7 @@ func TestUnionSame(t *testing.T) {
}
}
-func TestUnionDiff(t *testing.T) {
+func TestUnionDiffNodes(t *testing.T) {
a := make(Nodes)
b := make(Nodes)
c := make(Nodes)
@@ -270,9 +560,14 @@ func TestUnionDiff(t *testing.T) {
}
}
}
+
+ c = c.Union(a, a) // Assignment is necessary because c is not empty.
+ if !reflect.DeepEqual(c, a) {
+ t.Errorf("Union of equal sets not equal to sets: %v != %v", c, a)
+ }
}
-func TestUnionOverlapping(t *testing.T) {
+func TestUnionOverlappingNodes(t *testing.T) {
a := make(Nodes)
b := make(Nodes)
c := make(Nodes)
@@ -308,9 +603,14 @@ func TestUnionOverlapping(t *testing.T) {
}
}
}
+
+ c = c.Intersect(a, a) // Assignment is necessary because c is not empty.
+ if !reflect.DeepEqual(c, a) {
+ t.Errorf("Intersection of equal sets not equal to sets: %v != %v", c, a)
+ }
}
-func TestIntersectSame(t *testing.T) {
+func TestIntersectSameNodes(t *testing.T) {
a := make(Nodes)
b := make(Nodes)
c := make(Nodes)
@@ -340,7 +640,7 @@ func TestIntersectSame(t *testing.T) {
}
}
-func TestIntersectDiff(t *testing.T) {
+func TestIntersectDiffNodes(t *testing.T) {
a := make(Nodes)
b := make(Nodes)
c := make(Nodes)
@@ -374,7 +674,7 @@ func TestIntersectDiff(t *testing.T) {
}
}
-func TestIntersectOverlapping(t *testing.T) {
+func TestIntersectOverlappingNodes(t *testing.T) {
a := make(Nodes)
b := make(Nodes)
c := make(Nodes)
@@ -410,4 +710,14 @@ func TestIntersectOverlapping(t *testing.T) {
}
}
}
+
+ c = c.Intersect(c, a) // Assignment is necessary because c is not empty.
+ want := Nodes{3: node(3)}
+ if !reflect.DeepEqual(c, want) {
+ t.Errorf("Intersection of sets with dst equal to a not equal: %v != %v", c, want)
+ }
+ c = c.Intersect(a, c) // Assignment is necessary because c is not empty.
+ if !reflect.DeepEqual(c, want) {
+ t.Errorf("Intersection of sets with dst equal to a not equal: %v != %v", c, want)
+ }
}

graph/internal/set: improve test coverage and docs