1// Copyright 2017 Google Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14package sets 15 16import ( 17 "sort" 18 "testing" 19) 20 21func checkSameIntSet(t *testing.T, set *IntSet, unique []int) { 22 // Check that lengths are the same. 23 want := len(unique) 24 got := set.Len() 25 26 if got != want { 27 t.Errorf("NewIntSet(%v) want length %v, got %v", unique, want, got) 28 } 29 30 // Check that all ints are present in set. 31 for _, s := range unique { 32 want := true 33 got := set.Contains(s) 34 35 if got != want { 36 t.Errorf("Contains(%v) want %v, got %v", s, want, got) 37 } 38 } 39 40 // Check that all elements are present in ints. 41 sort.Ints(unique) 42 43 for i, got := range set.Sorted() { 44 want := unique[i] 45 if got != want { 46 t.Errorf("Sorted(%d) want %v, got %v", i, want, got) 47 } 48 } 49} 50 51type enumTest int 52 53const ( 54 et0 enumTest = iota 55 et1 56 et2 57 et3 58 et4 59) 60 61func TestNewIntSet(t *testing.T) { 62 empty := NewIntSet() 63 want := 0 64 got := empty.Len() 65 66 if got != want { 67 t.Errorf("NewIntSet() want length %v, got %v", want, got) 68 } 69 70 unique := []int{0, 1, 2} 71 set := NewIntSet(unique...) 72 checkSameIntSet(t, set, unique) 73 74 // Append an already-present element. 75 nonUnique := append(unique, unique[0]) 76 set = NewIntSet(nonUnique...) 77 78 // Non-unique unique should collapse to one. 79 want = len(unique) 80 got = set.Len() 81 82 if got != want { 83 t.Errorf("NewIntSet(%v) want length %v, got %v", nonUnique, want, got) 84 } 85 86 // Initialize with enum values cast to int. 87 set = NewIntSet(int(et0), int(et1), int(et2)) 88 checkSameIntSet(t, set, unique) 89} 90 91func TestIntSet_Copy(t *testing.T) { 92 // Check both copies represent the same set. 93 base := []int{1, 2, 3} 94 orig := NewIntSet(base...) 95 cpy := orig.Copy() 96 checkSameIntSet(t, orig, base) 97 checkSameIntSet(t, cpy, base) 98 99 // Check the two copies are independent. 100 more := []int{4} 101 orig.Insert(more...) 102 more = append(base, more...) 103 checkSameIntSet(t, orig, more) 104 checkSameIntSet(t, cpy, base) 105} 106 107func TestIntSet_Insert(t *testing.T) { 108 unique := []int{0, 1, 2} 109 set := NewIntSet(unique...) 110 111 // Insert existing element, which should basically be a no-op. 112 set.Insert(unique[0]) 113 checkSameIntSet(t, set, unique) 114 115 // Actually insert new unique elements (cast from enum values this time). 116 additional := []int{int(et3), int(et4)} 117 longer := append(unique, additional...) 118 set.Insert(additional...) 119 checkSameIntSet(t, set, longer) 120} 121 122func TestIntSet_Delete(t *testing.T) { 123 unique := []int{0, 1, 2} 124 set := NewIntSet(unique...) 125 126 // Delete non-existent element, which should basically be a no-op. 127 set.Delete(int(et4)) 128 checkSameIntSet(t, set, unique) 129 130 // Actually delete existing elements. 131 set.Delete(unique[1:]...) 132 checkSameIntSet(t, set, unique[:1]) 133} 134 135func TestIntSet_Intersect(t *testing.T) { 136 input1 := []int{1, 3, 4, 5, 6} 137 input2 := []int{2, 3, 5} 138 139 // Check Intersect(nil) returns an empty set. 140 setA := NewIntSet(input1...) 141 got := setA.Intersect(nil) 142 checkSameIntSet(t, got, []int{}) 143 // Check that the receiver is unchanged. 144 checkSameIntSet(t, setA, input1) 145 146 // Check Intersect returns the correct result. 147 setB := NewIntSet(input2...) 148 got = setA.Intersect(setB) 149 want := []int{3, 5} 150 checkSameIntSet(t, got, want) 151 // Also check the sources are unchanged. 152 checkSameIntSet(t, setA, input1) 153 checkSameIntSet(t, setB, input2) 154 155 // Reverse the inputs and verify Intersect produces the same results. 156 setA = NewIntSet(input2...) 157 setB = NewIntSet(input1...) 158 got = setA.Intersect(setB) 159 checkSameIntSet(t, got, want) 160 // Check the sources are again unchanged. 161 checkSameIntSet(t, setA, input2) 162 checkSameIntSet(t, setB, input1) 163} 164 165func TestIntSet_Disjoint(t *testing.T) { 166 input1 := []int{1, 3, 4, 5, 6} 167 input2 := []int{2, 3, 5} 168 input3 := []int{98, 99, 100} 169 170 // Check that sets are always disjoint with the empty set or nil 171 setA := NewIntSet(input1...) 172 emptySet := NewIntSet() 173 174 if disjoint := setA.Disjoint(nil); !disjoint { 175 t.Errorf("Disjoint(%s, %v) want %v, got %v", setA, nil, true, disjoint) 176 } 177 178 if disjoint := setA.Disjoint(emptySet); !disjoint { 179 t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, emptySet, true, disjoint) 180 } 181 182 if disjoint := emptySet.Disjoint(setA); !disjoint { 183 t.Errorf("Disjoint(%s, %s) want %v, got %v", emptySet, setA, true, disjoint) 184 } 185 186 if disjoint := emptySet.Disjoint(emptySet); !disjoint { 187 t.Errorf("Disjoint(%s, %s) want %v, got %v", emptySet, emptySet, true, disjoint) 188 } 189 190 // Also check the sources are unchanged. 191 checkSameIntSet(t, setA, input1) 192 checkSameIntSet(t, emptySet, []int{}) 193 194 // Check two non-empty, non-nil disjoint sets. 195 setC := NewIntSet(input3...) 196 197 if disjoint := setA.Disjoint(setC); !disjoint { 198 t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, setC, true, disjoint) 199 } 200 201 // Also check the sources are unchanged. 202 checkSameIntSet(t, setA, input1) 203 checkSameIntSet(t, setC, input3) 204 205 // Check that two intersecting sets are not Disjoint. 206 setB := NewIntSet(input2...) 207 208 if disjoint := setA.Disjoint(setB); disjoint { 209 t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, setB, false, disjoint) 210 } 211 212 // Also check the sources are unchanged. 213 checkSameIntSet(t, setA, input1) 214 checkSameIntSet(t, setB, input2) 215} 216 217func TestIntSet_Difference(t *testing.T) { 218 input1 := []int{1, 3, 4, 5, 6} 219 input2 := []int{2, 3, 5} 220 input3 := []int{98, 99, 100} 221 222 // Check Difference(nil) returns a copy of the receiver. 223 setA := NewIntSet(input1...) 224 got := setA.Difference(nil) 225 checkSameIntSet(t, got, input1) 226 // Check that the receiver is unchanged. 227 checkSameIntSet(t, setA, input1) 228 229 // Check A - A returns the empty set. 230 got = setA.Difference(setA) 231 232 if !got.Empty() { 233 t.Errorf("Difference(%s, %s).Empty() want %v, got %v", 234 setA, setA, true, false) 235 } 236 237 checkSameIntSet(t, got, []int{}) 238 // Check that the receiver is unchanged. 239 checkSameIntSet(t, setA, input1) 240 241 // Check A - C simply returns elements in A if A and C are disjoint. 242 setC := NewIntSet(input3...) 243 got = setA.Difference(setC) 244 checkSameIntSet(t, got, input1) 245 // Also check the sources are unchanged. 246 checkSameIntSet(t, setA, input1) 247 checkSameIntSet(t, setC, input3) 248 249 // Check A - B returns elements in A not in B. 250 setB := NewIntSet(input2...) 251 got = setA.Difference(setB) 252 want := []int{1, 4, 6} 253 checkSameIntSet(t, got, want) 254 255 // Also check the sources are unchanged. 256 checkSameIntSet(t, setA, input1) 257 checkSameIntSet(t, setB, input2) 258 259 // Check B - A returns elements in B not in A. 260 got = setB.Difference(setA) 261 want = []int{2} 262 checkSameIntSet(t, got, want) 263 // Also check the sources are unchanged. 264 checkSameIntSet(t, setA, input1) 265 checkSameIntSet(t, setB, input2) 266} 267 268func TestIntSet_Unique(t *testing.T) { 269 input1 := []int{1, 3, 4, 5, 6} 270 input2 := []int{2, 3, 5} 271 input3 := []int{98, 99, 100} 272 273 // Check Unique(nil) returns a copy of the receiver. 274 setA := NewIntSet(input1...) 275 got := setA.Unique(nil) 276 checkSameIntSet(t, got, input1) 277 // Check that the receiver is unchanged. 278 checkSameIntSet(t, setA, input1) 279 280 // Check Unique returns only elements in A and B not in both A and B. 281 setB := NewIntSet(input2...) 282 got = setA.Unique(setB) 283 want := []int{1, 2, 4, 6} 284 checkSameIntSet(t, got, want) 285 // Also check the sources are unchanged. 286 checkSameIntSet(t, setA, input1) 287 checkSameIntSet(t, setB, input2) 288 289 // Check Unique of two disjoint sets is the Union of those sets. 290 setC := NewIntSet(input3...) 291 got = setA.Unique(setC) 292 union := setA.Union(setC) 293 294 if equal := union.Equal(got); !equal { 295 t.Errorf("Union of disjoint Equal(%s, %s) want %v, got %v", 296 union, got, true, equal) 297 } 298 299 // Check Unique is the Union of A - B and B - A. 300 aNotInB := setA.Difference(setB) 301 bNotInA := setB.Difference(setA) 302 union = aNotInB.Union(bNotInA) 303 want = []int{1, 2, 4, 6} 304 checkSameIntSet(t, union, want) 305 got = setA.Unique(setB) 306 307 if equal := union.Equal(got); !equal { 308 t.Errorf("Union of differences Equal(%s, %s) want %v, got %v", 309 union, got, true, equal) 310 } 311 312 // Also check the sources are unchanged. 313 checkSameIntSet(t, setA, input1) 314 checkSameIntSet(t, setB, input2) 315} 316 317func TestIntSet_Equal(t *testing.T) { 318 input1 := []int{1, 3, 4, 5, 6} 319 input2 := []int{2, 3, 5} 320 input3 := []int{1, 3, 4, 5, 7} 321 322 // Check Equal(nil) returns false. 323 setA := NewIntSet(input1...) 324 325 if equal := setA.Equal(nil); equal { 326 t.Errorf("Equal(%s, %v) want %v, got %v", setA, nil, false, true) 327 } 328 329 // Check that the receiver is unchanged. 330 checkSameIntSet(t, setA, input1) 331 332 // Check Equal returns true for a set and itself. 333 if equal := setA.Equal(setA); !equal { 334 t.Errorf("Equal(%s, %s) want %v, got %v", setA, setA, true, false) 335 } 336 337 // Check that the receiver is unchanged. 338 checkSameIntSet(t, setA, input1) 339 340 // Check Equal returns false for sets of non-equal length. 341 setB := NewIntSet(input2...) 342 343 if equal := setA.Equal(setB); equal { 344 t.Errorf("Equal(%s, %s) want %v, got %v", setA, setB, false, true) 345 } 346 347 // Also check the sources are unchanged. 348 checkSameIntSet(t, setA, input1) 349 checkSameIntSet(t, setB, input2) 350 351 // Check Equal returns false for equal-length sets with different elements. 352 setC := NewIntSet(input3...) 353 354 if equal := setA.Equal(setC); equal { 355 t.Errorf("Equal(%s, %s) want %v, got %v", setA, setC, false, true) 356 } 357 358 if equal := setC.Equal(setA); equal { 359 t.Errorf("Equal(%s, %s) want %v, got %v", setC, setA, false, true) 360 } 361 362 // Also check the sources are unchanged. 363 checkSameIntSet(t, setA, input1) 364 checkSameIntSet(t, setC, input3) 365 366 // Check Equal returns true for a set with itself. 367 if equal := setA.Equal(setA); !equal { 368 t.Errorf("Equal(%s, %s) want %v, got %v", setA, setA, true, false) 369 } 370 371 // Also check the source is unchanged. 372 checkSameIntSet(t, setA, input1) 373 374 // Check Equal returns true for two separate equal sets. 375 anotherA := NewIntSet(input1...) 376 377 if equal := setA.Equal(anotherA); !equal { 378 t.Errorf("Equal(%s, %s) want %v, got %v", setA, anotherA, true, false) 379 } 380 381 // Also check the sources are unchanged. 382 checkSameIntSet(t, setA, input1) 383 checkSameIntSet(t, anotherA, input1) 384 385 // Check for equality comparing to nil struct. 386 var nilSet *IntSet 387 if equal := nilSet.Equal(setA); equal { 388 t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, setA, false, true) 389 } 390 if equal := setA.Equal(nilSet); equal { 391 t.Errorf("Equal(%s, %s) want %v, got %v", setA, nilSet, false, true) 392 } 393 if equal := nilSet.Equal(nilSet); !equal { 394 t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, nilSet, true, false) 395 } 396 397 // Edge case: consider the empty set to be different than the nil set. 398 emptySet := NewIntSet() 399 if equal := nilSet.Equal(emptySet); equal { 400 t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, emptySet, false, true) 401 } 402 if equal := emptySet.Equal(nilSet); equal { 403 t.Errorf("Equal(%s, %s) want %v, got %v", emptySet, nilSet, false, true) 404 } 405 if equal := emptySet.Equal(emptySet); !equal { 406 t.Errorf("Equal(%s, %s) want %v, got %v", emptySet, emptySet, true, false) 407 } 408} 409 410func TestIntSet_Union(t *testing.T) { 411 input1 := []int{1, 3, 4, 5, 6} 412 input2 := []int{2, 3, 5} 413 414 // Check Union(nil) returns a copy of the receiver. 415 setA := NewIntSet(input1...) 416 got := setA.Union(nil) 417 checkSameIntSet(t, got, input1) 418 // Check that the receiver is unchanged. 419 checkSameIntSet(t, setA, input1) 420 421 // Check Union returns the correct result. 422 setB := NewIntSet(input2...) 423 got = setA.Union(setB) 424 want := []int{1, 2, 3, 4, 5, 6} 425 checkSameIntSet(t, got, want) 426 // Also check the sources are unchanged. 427 checkSameIntSet(t, setA, input1) 428 checkSameIntSet(t, setB, input2) 429 430 // Reverse the inputs and verify Union produces the same results. 431 setA = NewIntSet(input2...) 432 setB = NewIntSet(input1...) 433 got = setA.Union(setB) 434 checkSameIntSet(t, got, want) 435 // Check the sources are again unchanged. 436 checkSameIntSet(t, setA, input2) 437 checkSameIntSet(t, setB, input1) 438} 439