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 checkSameStringSet(t *testing.T, set *StringSet, unique []string) { 22 // Check that lengths are the same. 23 want := len(unique) 24 got := set.Len() 25 26 if got != want { 27 t.Errorf("NewStringSet(%v) want length %v, got %v", unique, want, got) 28 } 29 30 // Check that all strings 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 strings. 41 sort.Strings(unique) 42 43 for i, got := range set.Sorted() { 44 want := unique[i] 45 46 if got != want { 47 t.Errorf("Sorted(%d) want %v, got %v", i, want, got) 48 } 49 } 50} 51 52func TestNewStringSet(t *testing.T) { 53 empty := NewStringSet() 54 want := 0 55 got := empty.Len() 56 57 if got != want { 58 t.Errorf("NewStringSet() want length %v, got %v", want, got) 59 } 60 61 unique := []string{"a", "b", "c"} 62 set := NewStringSet(unique...) 63 checkSameStringSet(t, set, unique) 64 65 // Append an already-present element. 66 nonUnique := append(unique, unique[0]) 67 set = NewStringSet(nonUnique...) 68 69 // Non-unique unique should collapse to one. 70 want = len(unique) 71 got = set.Len() 72 73 if got != want { 74 t.Errorf("NewStringSet(%v) want length %v, got %v", nonUnique, want, got) 75 } 76} 77 78func TestStringSet_Copy(t *testing.T) { 79 // Check both copies represent the same set. 80 base := []string{"a", "b", "c"} 81 orig := NewStringSet(base...) 82 cpy := orig.Copy() 83 checkSameStringSet(t, orig, base) 84 checkSameStringSet(t, cpy, base) 85 86 // Check the two copies are independent. 87 more := []string{"d"} 88 orig.Insert(more...) 89 more = append(base, more...) 90 checkSameStringSet(t, orig, more) 91 checkSameStringSet(t, cpy, base) 92} 93 94func TestStringSet_Insert(t *testing.T) { 95 unique := []string{"a", "b", "c"} 96 set := NewStringSet(unique...) 97 98 // Insert existing element, which should basically be a no-op. 99 set.Insert(unique[0]) 100 checkSameStringSet(t, set, unique) 101 102 // Actually insert new unique elements. 103 additional := []string{"d", "e"} 104 longer := append(unique, additional...) 105 set.Insert(additional...) 106 checkSameStringSet(t, set, longer) 107} 108 109func TestStringSet_Delete(t *testing.T) { 110 unique := []string{"a", "b", "c"} 111 set := NewStringSet(unique...) 112 113 // Delete non-existent element, which should basically be a no-op. 114 set.Delete("z") 115 checkSameStringSet(t, set, unique) 116 117 // Actually delete existing elements. 118 set.Delete(unique[1:]...) 119 checkSameStringSet(t, set, unique[:1]) 120} 121 122func TestStringSet_Intersect(t *testing.T) { 123 input1 := []string{"a", "c", "d", "e", "f"} 124 input2 := []string{"b", "c", "e"} 125 126 // Check Intersect(nil) returns an empty set. 127 setA := NewStringSet(input1...) 128 got := setA.Intersect(nil) 129 checkSameStringSet(t, got, []string{}) 130 // Check that the receiver is unchanged. 131 checkSameStringSet(t, setA, input1) 132 133 // Check Intersect returns the correct result. 134 setB := NewStringSet(input2...) 135 got = setA.Intersect(setB) 136 want := []string{"c", "e"} 137 checkSameStringSet(t, got, want) 138 // Also check the sources are unchanged. 139 checkSameStringSet(t, setA, input1) 140 checkSameStringSet(t, setB, input2) 141 142 // Reverse the inputs and verify Intersect produces the same results. 143 setA = NewStringSet(input2...) 144 setB = NewStringSet(input1...) 145 got = setA.Intersect(setB) 146 checkSameStringSet(t, got, want) 147 // Check the sources are again unchanged. 148 checkSameStringSet(t, setA, input2) 149 checkSameStringSet(t, setB, input1) 150} 151 152func TestStringSet_Disjoint(t *testing.T) { 153 input1 := []string{"a", "c", "d", "e", "f"} 154 input2 := []string{"b", "c", "e"} 155 input3 := []string{"x", "y", "z"} 156 157 // Check that sets are always disjoint with the empty set or nil 158 setA := NewStringSet(input1...) 159 emptySet := NewStringSet() 160 161 if disjoint := setA.Disjoint(nil); !disjoint { 162 t.Errorf("Disjoint(%s, %v) want %v, got %v", setA, nil, true, disjoint) 163 } 164 165 if disjoint := setA.Disjoint(emptySet); !disjoint { 166 t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, emptySet, true, disjoint) 167 } 168 169 if disjoint := emptySet.Disjoint(setA); !disjoint { 170 t.Errorf("Disjoint(%s, %s) want %v, got %v", emptySet, setA, true, disjoint) 171 } 172 173 if disjoint := emptySet.Disjoint(emptySet); !disjoint { 174 t.Errorf("Disjoint(%s, %s) want %v, got %v", emptySet, emptySet, true, disjoint) 175 } 176 177 // Also check the sources are unchanged. 178 checkSameStringSet(t, setA, input1) 179 checkSameStringSet(t, emptySet, []string{}) 180 181 // Check two non-empty, non-nil disjoint sets. 182 setC := NewStringSet(input3...) 183 184 if disjoint := setA.Disjoint(setC); !disjoint { 185 t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, setC, true, disjoint) 186 } 187 188 // Also check the sources are unchanged. 189 checkSameStringSet(t, setA, input1) 190 checkSameStringSet(t, setC, input3) 191 192 // Check that two intersecting sets are not Disjoint. 193 setB := NewStringSet(input2...) 194 195 if disjoint := setA.Disjoint(setB); disjoint { 196 t.Errorf("Disjoint(%s, %s) want %v, got %v", setA, setB, false, disjoint) 197 } 198 199 // Also check the sources are unchanged. 200 checkSameStringSet(t, setA, input1) 201 checkSameStringSet(t, setB, input2) 202} 203 204func TestStringSet_Difference(t *testing.T) { 205 input1 := []string{"a", "c", "d", "e", "f"} 206 input2 := []string{"b", "c", "e"} 207 input3 := []string{"x", "y", "z"} 208 209 // Check Difference(nil) returns a copy of the receiver. 210 setA := NewStringSet(input1...) 211 got := setA.Difference(nil) 212 checkSameStringSet(t, got, input1) 213 // Check that the receiver is unchanged. 214 checkSameStringSet(t, setA, input1) 215 216 // Check A - A returns the empty set. 217 got = setA.Difference(setA) 218 219 if !got.Empty() { 220 t.Errorf("Difference(%s, %s).Empty() want %v, got %v", 221 setA, setA, true, false) 222 } 223 224 checkSameStringSet(t, got, []string{}) 225 // Check that the receiver is unchanged. 226 checkSameStringSet(t, setA, input1) 227 228 // Check A - C simply returns elements in A if A and C are disjoint. 229 setC := NewStringSet(input3...) 230 got = setA.Difference(setC) 231 checkSameStringSet(t, got, input1) 232 // Also check the sources are unchanged. 233 checkSameStringSet(t, setA, input1) 234 checkSameStringSet(t, setC, input3) 235 236 // Check A - B returns elements in A not in B. 237 setB := NewStringSet(input2...) 238 got = setA.Difference(setB) 239 want := []string{"a", "d", "f"} 240 checkSameStringSet(t, got, want) 241 242 // Also check the sources are unchanged. 243 checkSameStringSet(t, setA, input1) 244 checkSameStringSet(t, setB, input2) 245 246 // Check B - A returns elements in B not in A. 247 got = setB.Difference(setA) 248 want = []string{"b"} 249 checkSameStringSet(t, got, want) 250 // Also check the sources are unchanged. 251 checkSameStringSet(t, setA, input1) 252 checkSameStringSet(t, setB, input2) 253} 254 255func TestStringSet_Unique(t *testing.T) { 256 input1 := []string{"a", "c", "d", "e", "f"} 257 input2 := []string{"b", "c", "e"} 258 input3 := []string{"x", "y", "z"} 259 260 // Check Unique(nil) returns a copy of the receiver. 261 setA := NewStringSet(input1...) 262 got := setA.Unique(nil) 263 checkSameStringSet(t, got, input1) 264 // Check that the receiver is unchanged. 265 checkSameStringSet(t, setA, input1) 266 267 // Check Unique returns only elements in A and B not in both A and B. 268 setB := NewStringSet(input2...) 269 got = setA.Unique(setB) 270 want := []string{"a", "b", "d", "f"} 271 checkSameStringSet(t, got, want) 272 // Also check the sources are unchanged. 273 checkSameStringSet(t, setA, input1) 274 checkSameStringSet(t, setB, input2) 275 276 // Check Unique of two disjoint sets is the Union of those sets. 277 setC := NewStringSet(input3...) 278 got = setA.Unique(setC) 279 union := setA.Union(setC) 280 281 if equal := union.Equal(got); !equal { 282 t.Errorf("Union of disjoint Equal(%s, %s) want %v, got %v", 283 union, got, true, equal) 284 } 285 286 // Check Unique is the Union of A - B and B - A. 287 aNotInB := setA.Difference(setB) 288 bNotInA := setB.Difference(setA) 289 union = aNotInB.Union(bNotInA) 290 want = []string{"a", "b", "d", "f"} 291 checkSameStringSet(t, union, want) 292 got = setA.Unique(setB) 293 294 if equal := union.Equal(got); !equal { 295 t.Errorf("Union of differences Equal(%s, %s) want %v, got %v", 296 union, got, true, equal) 297 } 298 299 // Also check the sources are unchanged. 300 checkSameStringSet(t, setA, input1) 301 checkSameStringSet(t, setB, input2) 302} 303 304func TestStringSet_Equal(t *testing.T) { 305 input1 := []string{"a", "c", "d", "e", "f"} 306 input2 := []string{"b", "c", "e"} 307 input3 := []string{"a", "c", "d", "e", "g"} 308 309 // Check Equal(nil) returns false. 310 setA := NewStringSet(input1...) 311 312 if equal := setA.Equal(nil); equal { 313 t.Errorf("Equal(%s, %v) want %v, got %v", setA, nil, false, true) 314 } 315 316 // Check that the receiver is unchanged. 317 checkSameStringSet(t, setA, input1) 318 319 // Check Equal returns true for a set and itself. 320 if equal := setA.Equal(setA); !equal { 321 t.Errorf("Equal(%s, %s) want %v, got %v", setA, setA, true, false) 322 } 323 324 // Check that the receiver is unchanged. 325 checkSameStringSet(t, setA, input1) 326 327 // Check Equal returns false for sets of non-equal length. 328 setB := NewStringSet(input2...) 329 330 if equal := setA.Equal(setB); equal { 331 t.Errorf("Equal(%s, %s) want %v, got %v", setA, setB, false, true) 332 } 333 334 // Also check the sources are unchanged. 335 checkSameStringSet(t, setA, input1) 336 checkSameStringSet(t, setB, input2) 337 338 // Check Equal returns false for equal-length sets with different elements. 339 setC := NewStringSet(input3...) 340 341 if equal := setA.Equal(setC); equal { 342 t.Errorf("Equal(%s, %s) want %v, got %v", setA, setC, false, true) 343 } 344 345 if equal := setC.Equal(setA); equal { 346 t.Errorf("Equal(%s, %s) want %v, got %v", setC, setA, false, true) 347 } 348 349 // Also check the sources are unchanged. 350 checkSameStringSet(t, setA, input1) 351 checkSameStringSet(t, setC, input3) 352 353 // Check Equal returns true for a set with itself. 354 if equal := setA.Equal(setA); !equal { 355 t.Errorf("Equal(%s, %s) want %v, got %v", setA, setA, true, false) 356 } 357 358 // Also check the source is unchanged. 359 checkSameStringSet(t, setA, input1) 360 361 // Check Equal returns true for two separate equal sets. 362 anotherA := NewStringSet(input1...) 363 364 if equal := setA.Equal(anotherA); !equal { 365 t.Errorf("Equal(%s, %s) want %v, got %v", setA, anotherA, true, false) 366 } 367 368 // Also check the sources are unchanged. 369 checkSameStringSet(t, setA, input1) 370 checkSameStringSet(t, anotherA, input1) 371 372 // Check for equality comparing to nil struct. 373 var nilSet *StringSet 374 if equal := nilSet.Equal(setA); equal { 375 t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, setA, false, true) 376 } 377 if equal := setA.Equal(nilSet); equal { 378 t.Errorf("Equal(%s, %s) want %v, got %v", setA, nilSet, false, true) 379 } 380 if equal := nilSet.Equal(nilSet); !equal { 381 t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, nilSet, true, false) 382 } 383 384 // Edge case: consider the empty set to be different than the nil set. 385 emptySet := NewStringSet() 386 if equal := nilSet.Equal(emptySet); equal { 387 t.Errorf("Equal(%s, %s) want %v, got %v", nilSet, emptySet, false, true) 388 } 389 if equal := emptySet.Equal(nilSet); equal { 390 t.Errorf("Equal(%s, %s) want %v, got %v", emptySet, nilSet, false, true) 391 } 392 if equal := emptySet.Equal(emptySet); !equal { 393 t.Errorf("Equal(%s, %s) want %v, got %v", emptySet, emptySet, true, false) 394 } 395} 396 397func TestStringSet_Union(t *testing.T) { 398 input1 := []string{"a", "c", "d", "e", "f"} 399 input2 := []string{"b", "c", "e"} 400 401 // Check Union(nil) returns a copy of the receiver. 402 setA := NewStringSet(input1...) 403 got := setA.Union(nil) 404 checkSameStringSet(t, got, input1) 405 // Check that the receiver is unchanged. 406 checkSameStringSet(t, setA, input1) 407 408 // Check Union returns the correct result. 409 setB := NewStringSet(input2...) 410 got = setA.Union(setB) 411 want := []string{"a", "b", "c", "d", "e", "f"} 412 checkSameStringSet(t, got, want) 413 // Also check the sources are unchanged. 414 checkSameStringSet(t, setA, input1) 415 checkSameStringSet(t, setB, input2) 416 417 // Reverse the inputs and verify Union produces the same results. 418 setA = NewStringSet(input2...) 419 setB = NewStringSet(input1...) 420 got = setA.Union(setB) 421 checkSameStringSet(t, got, want) 422 // Check the sources are again unchanged. 423 checkSameStringSet(t, setA, input2) 424 checkSameStringSet(t, setB, input1) 425} 426