.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/container/intsets/sparse_test.go

   1 // Copyright 2014 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package intsets_test
   6
   7 import (
   8         "fmt"
   9         "log"
  10         "math/rand"
  11         "sort"
  12         "strings"
  13         "testing"
  14
  15         "golang.org/x/tools/container/intsets"
  16 )
  17
  18 func TestBasics(t *testing.T) {
  19         var s intsets.Sparse
  20         if len := s.Len(); len != 0 {
  21                 t.Errorf("Len({}): got %d, want 0", len)
  22         }
  23         if s := s.String(); s != "{}" {
  24                 t.Errorf("String({}): got %q, want \"{}\"", s)
  25         }
  26         if s.Has(3) {
  27                 t.Errorf("Has(3): got true, want false")
  28         }
  29         if err := s.Check(); err != nil {
  30                 t.Error(err)
  31         }
  32
  33         if !s.Insert(3) {
  34                 t.Errorf("Insert(3): got false, want true")
  35         }
  36         if max := s.Max(); max != 3 {
  37                 t.Errorf("Max: got %d, want 3", max)
  38         }
  39
  40         if !s.Insert(435) {
  41                 t.Errorf("Insert(435): got false, want true")
  42         }
  43         if s := s.String(); s != "{3 435}" {
  44                 t.Errorf("String({3 435}): got %q, want \"{3 435}\"", s)
  45         }
  46         if max := s.Max(); max != 435 {
  47                 t.Errorf("Max: got %d, want 435", max)
  48         }
  49         if len := s.Len(); len != 2 {
  50                 t.Errorf("Len: got %d, want 2", len)
  51         }
  52
  53         if !s.Remove(435) {
  54                 t.Errorf("Remove(435): got false, want true")
  55         }
  56         if s := s.String(); s != "{3}" {
  57                 t.Errorf("String({3}): got %q, want \"{3}\"", s)
  58         }
  59 }
  60
  61 // Insert, Len, IsEmpty, Hash, Clear, AppendTo.
  62 func TestMoreBasics(t *testing.T) {
  63         set := new(intsets.Sparse)
  64         set.Insert(456)
  65         set.Insert(123)
  66         set.Insert(789)
  67         if set.Len() != 3 {
  68                 t.Errorf("%s.Len: got %d, want 3", set, set.Len())
  69         }
  70         if set.IsEmpty() {
  71                 t.Errorf("%s.IsEmpty: got true", set)
  72         }
  73         if !set.Has(123) {
  74                 t.Errorf("%s.Has(123): got false", set)
  75         }
  76         if set.Has(1234) {
  77                 t.Errorf("%s.Has(1234): got true", set)
  78         }
  79         got := set.AppendTo([]int{-1})
  80         if want := []int{-1, 123, 456, 789}; fmt.Sprint(got) != fmt.Sprint(want) {
  81                 t.Errorf("%s.AppendTo: got %v, want %v", set, got, want)
  82         }
  83
  84         set.Clear()
  85
  86         if set.Len() != 0 {
  87                 t.Errorf("Clear: got %d, want 0", set.Len())
  88         }
  89         if !set.IsEmpty() {
  90                 t.Errorf("IsEmpty: got false")
  91         }
  92         if set.Has(123) {
  93                 t.Errorf("%s.Has: got false", set)
  94         }
  95 }
  96
  97 func TestTakeMin(t *testing.T) {
  98         var set intsets.Sparse
  99         set.Insert(456)
 100         set.Insert(123)
 101         set.Insert(789)
 102         set.Insert(-123)
 103         var got int
 104         for i, want := range []int{-123, 123, 456, 789} {
 105                 if !set.TakeMin(&got) || got != want {
 106                         t.Errorf("TakeMin #%d: got %d, want %d", i, got, want)
 107                 }
 108         }
 109         if set.TakeMin(&got) {
 110                 t.Errorf("%s.TakeMin returned true", &set)
 111         }
 112         if err := set.Check(); err != nil {
 113                 t.Fatalf("check: %s: %#v", err, &set)
 114         }
 115 }
 116
 117 func TestMinAndMax(t *testing.T) {
 118         values := []int{0, 456, 123, 789, -123} // elt 0 => empty set
 119         wantMax := []int{intsets.MinInt, 456, 456, 789, 789}
 120         wantMin := []int{intsets.MaxInt, 456, 123, 123, -123}
 121
 122         var set intsets.Sparse
 123         for i, x := range values {
 124                 if i != 0 {
 125                         set.Insert(x)
 126                 }
 127                 if got, want := set.Min(), wantMin[i]; got != want {
 128                         t.Errorf("Min #%d: got %d, want %d", i, got, want)
 129                 }
 130                 if got, want := set.Max(), wantMax[i]; got != want {
 131                         t.Errorf("Max #%d: got %d, want %d", i, got, want)
 132                 }
 133         }
 134
 135         set.Insert(intsets.MinInt)
 136         if got, want := set.Min(), intsets.MinInt; got != want {
 137                 t.Errorf("Min: got %d, want %d", got, want)
 138         }
 139
 140         set.Insert(intsets.MaxInt)
 141         if got, want := set.Max(), intsets.MaxInt; got != want {
 142                 t.Errorf("Max: got %d, want %d", got, want)
 143         }
 144 }
 145
 146 func TestEquals(t *testing.T) {
 147         var setX intsets.Sparse
 148         setX.Insert(456)
 149         setX.Insert(123)
 150         setX.Insert(789)
 151
 152         if !setX.Equals(&setX) {
 153                 t.Errorf("Equals(%s, %s): got false", &setX, &setX)
 154         }
 155
 156         var setY intsets.Sparse
 157         setY.Insert(789)
 158         setY.Insert(456)
 159         setY.Insert(123)
 160
 161         if !setX.Equals(&setY) {
 162                 t.Errorf("Equals(%s, %s): got false", &setX, &setY)
 163         }
 164
 165         setY.Insert(1)
 166         if setX.Equals(&setY) {
 167                 t.Errorf("Equals(%s, %s): got true", &setX, &setY)
 168         }
 169
 170         var empty intsets.Sparse
 171         if setX.Equals(&empty) {
 172                 t.Errorf("Equals(%s, %s): got true", &setX, &empty)
 173         }
 174
 175         // Edge case: some block (with offset=0) appears in X but not Y.
 176         setY.Remove(123)
 177         if setX.Equals(&setY) {
 178                 t.Errorf("Equals(%s, %s): got true", &setX, &setY)
 179         }
 180 }
 181
 182 // A pset is a parallel implementation of a set using both an intsets.Sparse
 183 // and a built-in hash map.
 184 type pset struct {
 185         hash map[int]bool
 186         bits intsets.Sparse
 187 }
 188
 189 func makePset() *pset {
 190         return &pset{hash: make(map[int]bool)}
 191 }
 192
 193 func (set *pset) add(n int) {
 194         prev := len(set.hash)
 195         set.hash[n] = true
 196         grewA := len(set.hash) > prev
 197
 198         grewB := set.bits.Insert(n)
 199
 200         if grewA != grewB {
 201                 panic(fmt.Sprintf("add(%d): grewA=%t grewB=%t", n, grewA, grewB))
 202         }
 203 }
 204
 205 func (set *pset) remove(n int) {
 206         prev := len(set.hash)
 207         delete(set.hash, n)
 208         shrankA := len(set.hash) < prev
 209
 210         shrankB := set.bits.Remove(n)
 211
 212         if shrankA != shrankB {
 213                 panic(fmt.Sprintf("remove(%d): shrankA=%t shrankB=%t", n, shrankA, shrankB))
 214         }
 215 }
 216
 217 func (set *pset) check(t *testing.T, msg string) {
 218         var eltsA []int
 219         for elt := range set.hash {
 220                 eltsA = append(eltsA, int(elt))
 221         }
 222         sort.Ints(eltsA)
 223
 224         eltsB := set.bits.AppendTo(nil)
 225
 226         if a, b := fmt.Sprint(eltsA), fmt.Sprint(eltsB); a != b {
 227                 t.Errorf("check(%s): hash=%s bits=%s (%s)", msg, a, b, &set.bits)
 228         }
 229
 230         if err := set.bits.Check(); err != nil {
 231                 t.Fatalf("Check(%s): %s: %#v", msg, err, &set.bits)
 232         }
 233 }
 234
 235 // randomPset returns a parallel set of random size and elements.
 236 func randomPset(prng *rand.Rand, maxSize int) *pset {
 237         set := makePset()
 238         size := int(prng.Int()) % maxSize
 239         for i := 0; i < size; i++ {
 240                 // TODO(adonovan): benchmark how performance varies
 241                 // with this sparsity parameter.
 242                 n := int(prng.Int()) % 10000
 243                 set.add(n)
 244         }
 245         return set
 246 }
 247
 248 // TestRandomMutations performs the same random adds/removes on two
 249 // set implementations and ensures that they compute the same result.
 250 func TestRandomMutations(t *testing.T) {
 251         const debug = false
 252
 253         set := makePset()
 254         prng := rand.New(rand.NewSource(0))
 255         for i := 0; i < 10000; i++ {
 256                 n := int(prng.Int())%2000 - 1000
 257                 if i%2 == 0 {
 258                         if debug {
 259                                 log.Printf("add %d", n)
 260                         }
 261                         set.add(n)
 262                 } else {
 263                         if debug {
 264                                 log.Printf("remove %d", n)
 265                         }
 266                         set.remove(n)
 267                 }
 268                 if debug {
 269                         set.check(t, "post mutation")
 270                 }
 271         }
 272         set.check(t, "final")
 273         if debug {
 274                 log.Print(&set.bits)
 275         }
 276 }
 277
 278 func TestLowerBound(t *testing.T) {
 279         // Use random sets of sizes from 0 to about 4000.
 280         prng := rand.New(rand.NewSource(0))
 281         for i := uint(0); i < 12; i++ {
 282                 x := randomPset(prng, 1<<i)
 283                 for j := 0; j < 10000; j++ {
 284                         found := intsets.MaxInt
 285                         for e := range x.hash {
 286                                 if e >= j && e < found {
 287                                         found = e
 288                                 }
 289                         }
 290                         if res := x.bits.LowerBound(j); res != found {
 291                                 t.Errorf("%s: LowerBound(%d)=%d, expected %d", &x.bits, j, res, found)
 292                         }
 293                 }
 294         }
 295 }
 296
 297 // TestSetOperations exercises classic set operations: ∩ , ∪, \.
 298 func TestSetOperations(t *testing.T) {
 299         prng := rand.New(rand.NewSource(0))
 300
 301         // Use random sets of sizes from 0 to about 4000.
 302         // For each operator, we test variations such as
 303         // Z.op(X, Y), Z.op(X, Z) and Z.op(Z, Y) to exercise
 304         // the degenerate cases of each method implementation.
 305         for i := uint(0); i < 12; i++ {
 306                 X := randomPset(prng, 1<<i)
 307                 Y := randomPset(prng, 1<<i)
 308
 309                 // TODO(adonovan): minimise dependencies between stanzas below.
 310
 311                 // Copy(X)
 312                 C := makePset()
 313                 C.bits.Copy(&Y.bits) // no effect on result
 314                 C.bits.Copy(&X.bits)
 315                 C.hash = X.hash
 316                 C.check(t, "C.Copy(X)")
 317                 C.bits.Copy(&C.bits)
 318                 C.check(t, "C.Copy(C)")
 319
 320                 // U.Union(X, Y)
 321                 U := makePset()
 322                 U.bits.Union(&X.bits, &Y.bits)
 323                 for n := range X.hash {
 324                         U.hash[n] = true
 325                 }
 326                 for n := range Y.hash {
 327                         U.hash[n] = true
 328                 }
 329                 U.check(t, "U.Union(X, Y)")
 330
 331                 // U.Union(X, X)
 332                 U.bits.Union(&X.bits, &X.bits)
 333                 U.hash = X.hash
 334                 U.check(t, "U.Union(X, X)")
 335
 336                 // U.Union(U, Y)
 337                 U = makePset()
 338                 U.bits.Copy(&X.bits)
 339                 U.bits.Union(&U.bits, &Y.bits)
 340                 for n := range X.hash {
 341                         U.hash[n] = true
 342                 }
 343                 for n := range Y.hash {
 344                         U.hash[n] = true
 345                 }
 346                 U.check(t, "U.Union(U, Y)")
 347
 348                 // U.Union(X, U)
 349                 U.bits.Copy(&Y.bits)
 350                 U.bits.Union(&X.bits, &U.bits)
 351                 U.check(t, "U.Union(X, U)")
 352
 353                 // U.UnionWith(U)
 354                 U.bits.UnionWith(&U.bits)
 355                 U.check(t, "U.UnionWith(U)")
 356
 357                 // I.Intersection(X, Y)
 358                 I := makePset()
 359                 I.bits.Intersection(&X.bits, &Y.bits)
 360                 for n := range X.hash {
 361                         if Y.hash[n] {
 362                                 I.hash[n] = true
 363                         }
 364                 }
 365                 I.check(t, "I.Intersection(X, Y)")
 366
 367                 // I.Intersection(X, X)
 368                 I.bits.Intersection(&X.bits, &X.bits)
 369                 I.hash = X.hash
 370                 I.check(t, "I.Intersection(X, X)")
 371
 372                 // I.Intersection(I, X)
 373                 I.bits.Intersection(&I.bits, &X.bits)
 374                 I.check(t, "I.Intersection(I, X)")
 375
 376                 // I.Intersection(X, I)
 377                 I.bits.Intersection(&X.bits, &I.bits)
 378                 I.check(t, "I.Intersection(X, I)")
 379
 380                 // I.Intersection(I, I)
 381                 I.bits.Intersection(&I.bits, &I.bits)
 382                 I.check(t, "I.Intersection(I, I)")
 383
 384                 // D.Difference(X, Y)
 385                 D := makePset()
 386                 D.bits.Difference(&X.bits, &Y.bits)
 387                 for n := range X.hash {
 388                         if !Y.hash[n] {
 389                                 D.hash[n] = true
 390                         }
 391                 }
 392                 D.check(t, "D.Difference(X, Y)")
 393
 394                 // D.Difference(D, Y)
 395                 D.bits.Copy(&X.bits)
 396                 D.bits.Difference(&D.bits, &Y.bits)
 397                 D.check(t, "D.Difference(D, Y)")
 398
 399                 // D.Difference(Y, D)
 400                 D.bits.Copy(&X.bits)
 401                 D.bits.Difference(&Y.bits, &D.bits)
 402                 D.hash = make(map[int]bool)
 403                 for n := range Y.hash {
 404                         if !X.hash[n] {
 405                                 D.hash[n] = true
 406                         }
 407                 }
 408                 D.check(t, "D.Difference(Y, D)")
 409
 410                 // D.Difference(X, X)
 411                 D.bits.Difference(&X.bits, &X.bits)
 412                 D.hash = nil
 413                 D.check(t, "D.Difference(X, X)")
 414
 415                 // D.DifferenceWith(D)
 416                 D.bits.Copy(&X.bits)
 417                 D.bits.DifferenceWith(&D.bits)
 418                 D.check(t, "D.DifferenceWith(D)")
 419
 420                 // SD.SymmetricDifference(X, Y)
 421                 SD := makePset()
 422                 SD.bits.SymmetricDifference(&X.bits, &Y.bits)
 423                 for n := range X.hash {
 424                         if !Y.hash[n] {
 425                                 SD.hash[n] = true
 426                         }
 427                 }
 428                 for n := range Y.hash {
 429                         if !X.hash[n] {
 430                                 SD.hash[n] = true
 431                         }
 432                 }
 433                 SD.check(t, "SD.SymmetricDifference(X, Y)")
 434
 435                 // X.SymmetricDifferenceWith(Y)
 436                 SD.bits.Copy(&X.bits)
 437                 SD.bits.SymmetricDifferenceWith(&Y.bits)
 438                 SD.check(t, "X.SymmetricDifference(Y)")
 439
 440                 // Y.SymmetricDifferenceWith(X)
 441                 SD.bits.Copy(&Y.bits)
 442                 SD.bits.SymmetricDifferenceWith(&X.bits)
 443                 SD.check(t, "Y.SymmetricDifference(X)")
 444
 445                 // SD.SymmetricDifference(X, X)
 446                 SD.bits.SymmetricDifference(&X.bits, &X.bits)
 447                 SD.hash = nil
 448                 SD.check(t, "SD.SymmetricDifference(X, X)")
 449
 450                 // SD.SymmetricDifference(X, Copy(X))
 451                 X2 := makePset()
 452                 X2.bits.Copy(&X.bits)
 453                 SD.bits.SymmetricDifference(&X.bits, &X2.bits)
 454                 SD.check(t, "SD.SymmetricDifference(X, Copy(X))")
 455
 456                 // Copy(X).SymmetricDifferenceWith(X)
 457                 SD.bits.Copy(&X.bits)
 458                 SD.bits.SymmetricDifferenceWith(&X.bits)
 459                 SD.check(t, "Copy(X).SymmetricDifferenceWith(X)")
 460         }
 461 }
 462
 463 func TestIntersectionWith(t *testing.T) {
 464         // Edge cases: the pairs (1,1), (1000,2000), (8000,4000)
 465         // exercise the <, >, == cases in IntersectionWith that the
 466         // TestSetOperations data is too dense to cover.
 467         var X, Y intsets.Sparse
 468         X.Insert(1)
 469         X.Insert(1000)
 470         X.Insert(8000)
 471         Y.Insert(1)
 472         Y.Insert(2000)
 473         Y.Insert(4000)
 474         X.IntersectionWith(&Y)
 475         if got, want := X.String(), "{1}"; got != want {
 476                 t.Errorf("IntersectionWith: got %s, want %s", got, want)
 477         }
 478 }
 479
 480 func TestIntersects(t *testing.T) {
 481         prng := rand.New(rand.NewSource(0))
 482
 483         for i := uint(0); i < 12; i++ {
 484                 X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
 485                 x, y := &X.bits, &Y.bits
 486
 487                 // test the slow way
 488                 var z intsets.Sparse
 489                 z.Copy(x)
 490                 z.IntersectionWith(y)
 491
 492                 if got, want := x.Intersects(y), !z.IsEmpty(); got != want {
 493                         t.Errorf("Intersects(%s, %s): got %v, want %v (%s)", x, y, got, want, &z)
 494                 }
 495
 496                 // make it false
 497                 a := x.AppendTo(nil)
 498                 for _, v := range a {
 499                         y.Remove(v)
 500                 }
 501
 502                 if got, want := x.Intersects(y), false; got != want {
 503                         t.Errorf("Intersects: got %v, want %v", got, want)
 504                 }
 505
 506                 // make it true
 507                 if x.IsEmpty() {
 508                         continue
 509                 }
 510                 i := prng.Intn(len(a))
 511                 y.Insert(a[i])
 512
 513                 if got, want := x.Intersects(y), true; got != want {
 514                         t.Errorf("Intersects: got %v, want %v", got, want)
 515                 }
 516         }
 517 }
 518
 519 func TestSubsetOf(t *testing.T) {
 520         prng := rand.New(rand.NewSource(0))
 521
 522         for i := uint(0); i < 12; i++ {
 523                 X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
 524                 x, y := &X.bits, &Y.bits
 525
 526                 // test the slow way
 527                 var z intsets.Sparse
 528                 z.Copy(x)
 529                 z.DifferenceWith(y)
 530
 531                 if got, want := x.SubsetOf(y), z.IsEmpty(); got != want {
 532                         t.Errorf("SubsetOf: got %v, want %v", got, want)
 533                 }
 534
 535                 // make it true
 536                 y.UnionWith(x)
 537
 538                 if got, want := x.SubsetOf(y), true; got != want {
 539                         t.Errorf("SubsetOf: got %v, want %v", got, want)
 540                 }
 541
 542                 // make it false
 543                 if x.IsEmpty() {
 544                         continue
 545                 }
 546                 a := x.AppendTo(nil)
 547                 i := prng.Intn(len(a))
 548                 y.Remove(a[i])
 549
 550                 if got, want := x.SubsetOf(y), false; got != want {
 551                         t.Errorf("SubsetOf: got %v, want %v", got, want)
 552                 }
 553         }
 554 }
 555
 556 func TestBitString(t *testing.T) {
 557         for _, test := range []struct {
 558                 input []int
 559                 want  string
 560         }{
 561                 {nil, "0"},
 562                 {[]int{0}, "1"},
 563                 {[]int{0, 4, 5}, "110001"},
 564                 {[]int{0, 7, 177}, "1" + strings.Repeat("0", 169) + "10000001"},
 565                 {[]int{-3, 0, 4, 5}, "110001.001"},
 566                 {[]int{-3}, "0.001"},
 567         } {
 568                 var set intsets.Sparse
 569                 for _, x := range test.input {
 570                         set.Insert(x)
 571                 }
 572                 if got := set.BitString(); got != test.want {
 573                         t.Errorf("BitString(%s) = %s, want %s", set.String(), got, test.want)
 574                 }
 575         }
 576 }
 577
 578 func TestFailFastOnShallowCopy(t *testing.T) {
 579         var x intsets.Sparse
 580         x.Insert(1)
 581
 582         y := x // shallow copy (breaks representation invariants)
 583         defer func() {
 584                 got := fmt.Sprint(recover())
 585                 want := "interface conversion: interface {} is nil, not intsets.to_copy_a_sparse_you_must_call_its_Copy_method"
 586                 if got != want {
 587                         t.Errorf("shallow copy: recover() = %q, want %q", got, want)
 588                 }
 589         }()
 590         _ = y.String() // panics
 591         t.Error("didn't panic as expected")
 592 }
 593
 594 // -- Benchmarks -------------------------------------------------------
 595
 596 // TODO(adonovan):
 597 // - Add benchmarks of each method.
 598 // - Gather set distributions from pointer analysis.
 599 // - Measure memory usage.
 600
 601 func benchmarkInsertProbeSparse(b *testing.B, size, spread int) {
 602         prng := rand.New(rand.NewSource(0))
 603         // Generate our insertions and probes beforehand (we don't want to benchmark
 604         // the prng).
 605         insert := make([]int, size)
 606         probe := make([]int, size*2)
 607         for i := range insert {
 608                 insert[i] = prng.Int() % spread
 609         }
 610         for i := range probe {
 611                 probe[i] = prng.Int() % spread
 612         }
 613
 614         b.ResetTimer()
 615         var x intsets.Sparse
 616         for tries := 0; tries < b.N; tries++ {
 617                 x.Clear()
 618                 for _, n := range insert {
 619                         x.Insert(n)
 620                 }
 621                 hits := 0
 622                 for _, n := range probe {
 623                         if x.Has(n) {
 624                                 hits++
 625                         }
 626                 }
 627                 // Use the variable so it doesn't get optimized away.
 628                 if hits > len(probe) {
 629                         b.Fatalf("%d hits, only %d probes", hits, len(probe))
 630                 }
 631         }
 632 }
 633
 634 func BenchmarkInsertProbeSparse_2_10(b *testing.B) {
 635         benchmarkInsertProbeSparse(b, 2, 10)
 636 }
 637
 638 func BenchmarkInsertProbeSparse_10_10(b *testing.B) {
 639         benchmarkInsertProbeSparse(b, 10, 10)
 640 }
 641
 642 func BenchmarkInsertProbeSparse_10_1000(b *testing.B) {
 643         benchmarkInsertProbeSparse(b, 10, 1000)
 644 }
 645
 646 func BenchmarkInsertProbeSparse_100_100(b *testing.B) {
 647         benchmarkInsertProbeSparse(b, 100, 100)
 648 }
 649
 650 func BenchmarkInsertProbeSparse_100_10000(b *testing.B) {
 651         benchmarkInsertProbeSparse(b, 100, 1000)
 652 }
 653
 654 func BenchmarkUnionDifferenceSparse(b *testing.B) {
 655         prng := rand.New(rand.NewSource(0))
 656         for tries := 0; tries < b.N; tries++ {
 657                 var x, y, z intsets.Sparse
 658                 for i := 0; i < 1000; i++ {
 659                         n := int(prng.Int()) % 100000
 660                         if i%2 == 0 {
 661                                 x.Insert(n)
 662                         } else {
 663                                 y.Insert(n)
 664                         }
 665                 }
 666                 z.Union(&x, &y)
 667                 z.Difference(&x, &y)
 668         }
 669 }
 670
 671 func BenchmarkUnionDifferenceHashTable(b *testing.B) {
 672         prng := rand.New(rand.NewSource(0))
 673         for tries := 0; tries < b.N; tries++ {
 674                 x, y, z := make(map[int]bool), make(map[int]bool), make(map[int]bool)
 675                 for i := 0; i < 1000; i++ {
 676                         n := int(prng.Int()) % 100000
 677                         if i%2 == 0 {
 678                                 x[n] = true
 679                         } else {
 680                                 y[n] = true
 681                         }
 682                 }
 683                 // union
 684                 for n := range x {
 685                         z[n] = true
 686                 }
 687                 for n := range y {
 688                         z[n] = true
 689                 }
 690                 // difference
 691                 z = make(map[int]bool)
 692                 for n := range y {
 693                         if !x[n] {
 694                                 z[n] = true
 695                         }
 696                 }
 697         }
 698 }
 699
 700 func BenchmarkAppendTo(b *testing.B) {
 701         prng := rand.New(rand.NewSource(0))
 702         var x intsets.Sparse
 703         for i := 0; i < 1000; i++ {
 704                 x.Insert(int(prng.Int()) % 10000)
 705         }
 706         var space [1000]int
 707         for tries := 0; tries < b.N; tries++ {
 708                 x.AppendTo(space[:0])
 709         }
 710 }