.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/container/intsets/sparse.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 provides Sparse, a compact and fast representation
   6 // for sparse sets of int values.
   7 //
   8 // The time complexity of the operations Len, Insert, Remove and Has
   9 // is in O(n) but in practice those methods are faster and more
  10 // space-efficient than equivalent operations on sets based on the Go
  11 // map type.  The IsEmpty, Min, Max, Clear and TakeMin operations
  12 // require constant time.
  13 //
  14 package intsets // import "golang.org/x/tools/container/intsets"
  15
  16 // TODO(adonovan):
  17 // - Add InsertAll(...int), RemoveAll(...int)
  18 // - Add 'bool changed' results for {Intersection,Difference}With too.
  19 //
  20 // TODO(adonovan): implement Dense, a dense bit vector with a similar API.
  21 // The space usage would be proportional to Max(), not Len(), and the
  22 // implementation would be based upon big.Int.
  23 //
  24 // TODO(adonovan): opt: make UnionWith and Difference faster.
  25 // These are the hot-spots for go/pointer.
  26
  27 import (
  28         "bytes"
  29         "fmt"
  30 )
  31
  32 // A Sparse is a set of int values.
  33 // Sparse operations (even queries) are not concurrency-safe.
  34 //
  35 // The zero value for Sparse is a valid empty set.
  36 //
  37 // Sparse sets must be copied using the Copy method, not by assigning
  38 // a Sparse value.
  39 //
  40 type Sparse struct {
  41         // An uninitialized Sparse represents an empty set.
  42         // An empty set may also be represented by
  43         //  root.next == root.prev == &root.
  44         //
  45         // The root is always the block with the smallest offset.
  46         // It can be empty, but only if it is the only block; in that case, offset is
  47         // MaxInt (which is not a valid offset).
  48         root block
  49 }
  50
  51 type word uintptr
  52
  53 const (
  54         _m            = ^word(0)
  55         bitsPerWord   = 8 << (_m>>8&1 + _m>>16&1 + _m>>32&1)
  56         bitsPerBlock  = 256 // optimal value for go/pointer solver performance
  57         wordsPerBlock = bitsPerBlock / bitsPerWord
  58 )
  59
  60 // Limit values of implementation-specific int type.
  61 const (
  62         MaxInt = int(^uint(0) >> 1)
  63         MinInt = -MaxInt - 1
  64 )
  65
  66 // -- block ------------------------------------------------------------
  67
  68 // A set is represented as a circular doubly-linked list of blocks,
  69 // each containing an offset and a bit array of fixed size
  70 // bitsPerBlock; the blocks are ordered by increasing offset.
  71 //
  72 // The set contains an element x iff the block whose offset is x - (x
  73 // mod bitsPerBlock) has the bit (x mod bitsPerBlock) set, where mod
  74 // is the Euclidean remainder.
  75 //
  76 // A block may only be empty transiently.
  77 //
  78 type block struct {
  79         offset     int                 // offset mod bitsPerBlock == 0
  80         bits       [wordsPerBlock]word // contains at least one set bit
  81         next, prev *block              // doubly-linked list of blocks
  82 }
  83
  84 // wordMask returns the word index (in block.bits)
  85 // and single-bit mask for the block's ith bit.
  86 func wordMask(i uint) (w uint, mask word) {
  87         w = i / bitsPerWord
  88         mask = 1 << (i % bitsPerWord)
  89         return
  90 }
  91
  92 // insert sets the block b's ith bit and
  93 // returns true if it was not already set.
  94 //
  95 func (b *block) insert(i uint) bool {
  96         w, mask := wordMask(i)
  97         if b.bits[w]&mask == 0 {
  98                 b.bits[w] |= mask
  99                 return true
 100         }
 101         return false
 102 }
 103
 104 // remove clears the block's ith bit and
 105 // returns true if the bit was previously set.
 106 // NB: may leave the block empty.
 107 //
 108 func (b *block) remove(i uint) bool {
 109         w, mask := wordMask(i)
 110         if b.bits[w]&mask != 0 {
 111                 b.bits[w] &^= mask
 112                 return true
 113         }
 114         return false
 115 }
 116
 117 // has reports whether the block's ith bit is set.
 118 func (b *block) has(i uint) bool {
 119         w, mask := wordMask(i)
 120         return b.bits[w]&mask != 0
 121 }
 122
 123 // empty reports whether b.len()==0, but more efficiently.
 124 func (b *block) empty() bool {
 125         for _, w := range b.bits {
 126                 if w != 0 {
 127                         return false
 128                 }
 129         }
 130         return true
 131 }
 132
 133 // len returns the number of set bits in block b.
 134 func (b *block) len() int {
 135         var l int
 136         for _, w := range b.bits {
 137                 l += popcount(w)
 138         }
 139         return l
 140 }
 141
 142 // max returns the maximum element of the block.
 143 // The block must not be empty.
 144 func (b *block) max() int {
 145         bi := b.offset + bitsPerBlock
 146         // Decrement bi by number of high zeros in last.bits.
 147         for i := len(b.bits) - 1; i >= 0; i-- {
 148                 if w := b.bits[i]; w != 0 {
 149                         return bi - nlz(w) - 1
 150                 }
 151                 bi -= bitsPerWord
 152         }
 153         panic("BUG: empty block")
 154 }
 155
 156 // min returns the minimum element of the block,
 157 // and also removes it if take is set.
 158 // The block must not be initially empty.
 159 // NB: may leave the block empty.
 160 func (b *block) min(take bool) int {
 161         for i, w := range b.bits {
 162                 if w != 0 {
 163                         tz := ntz(w)
 164                         if take {
 165                                 b.bits[i] = w &^ (1 << uint(tz))
 166                         }
 167                         return b.offset + int(i*bitsPerWord) + tz
 168                 }
 169         }
 170         panic("BUG: empty block")
 171 }
 172
 173 // lowerBound returns the smallest element of the block that is greater than or
 174 // equal to the element corresponding to the ith bit. If there is no such
 175 // element, the second return value is false.
 176 func (b *block) lowerBound(i uint) (int, bool) {
 177         w := i / bitsPerWord
 178         bit := i % bitsPerWord
 179
 180         if val := b.bits[w] >> bit; val != 0 {
 181                 return b.offset + int(i) + ntz(val), true
 182         }
 183
 184         for w++; w < wordsPerBlock; w++ {
 185                 if val := b.bits[w]; val != 0 {
 186                         return b.offset + int(w*bitsPerWord) + ntz(val), true
 187                 }
 188         }
 189
 190         return 0, false
 191 }
 192
 193 // forEach calls f for each element of block b.
 194 // f must not mutate b's enclosing Sparse.
 195 func (b *block) forEach(f func(int)) {
 196         for i, w := range b.bits {
 197                 offset := b.offset + i*bitsPerWord
 198                 for bi := 0; w != 0 && bi < bitsPerWord; bi++ {
 199                         if w&1 != 0 {
 200                                 f(offset)
 201                         }
 202                         offset++
 203                         w >>= 1
 204                 }
 205         }
 206 }
 207
 208 // offsetAndBitIndex returns the offset of the block that would
 209 // contain x and the bit index of x within that block.
 210 //
 211 func offsetAndBitIndex(x int) (int, uint) {
 212         mod := x % bitsPerBlock
 213         if mod < 0 {
 214                 // Euclidean (non-negative) remainder
 215                 mod += bitsPerBlock
 216         }
 217         return x - mod, uint(mod)
 218 }
 219
 220 // -- Sparse --------------------------------------------------------------
 221
 222 // none is a shared, empty, sentinel block that indicates the end of a block
 223 // list.
 224 var none block
 225
 226 // Dummy type used to generate an implicit panic. This must be defined at the
 227 // package level; if it is defined inside a function, it prevents the inlining
 228 // of that function.
 229 type to_copy_a_sparse_you_must_call_its_Copy_method struct{}
 230
 231 // init ensures s is properly initialized.
 232 func (s *Sparse) init() {
 233         root := &s.root
 234         if root.next == nil {
 235                 root.offset = MaxInt
 236                 root.next = root
 237                 root.prev = root
 238         } else if root.next.prev != root {
 239                 // Copying a Sparse x leads to pernicious corruption: the
 240                 // new Sparse y shares the old linked list, but iteration
 241                 // on y will never encounter &y.root so it goes into a
 242                 // loop.  Fail fast before this occurs.
 243                 // We don't want to call panic here because it prevents the
 244                 // inlining of this function.
 245                 _ = (interface{}(nil)).(to_copy_a_sparse_you_must_call_its_Copy_method)
 246         }
 247 }
 248
 249 func (s *Sparse) first() *block {
 250         s.init()
 251         if s.root.offset == MaxInt {
 252                 return &none
 253         }
 254         return &s.root
 255 }
 256
 257 // next returns the next block in the list, or end if b is the last block.
 258 func (s *Sparse) next(b *block) *block {
 259         if b.next == &s.root {
 260                 return &none
 261         }
 262         return b.next
 263 }
 264
 265 // prev returns the previous block in the list, or end if b is the first block.
 266 func (s *Sparse) prev(b *block) *block {
 267         if b.prev == &s.root {
 268                 return &none
 269         }
 270         return b.prev
 271 }
 272
 273 // IsEmpty reports whether the set s is empty.
 274 func (s *Sparse) IsEmpty() bool {
 275         return s.root.next == nil || s.root.offset == MaxInt
 276 }
 277
 278 // Len returns the number of elements in the set s.
 279 func (s *Sparse) Len() int {
 280         var l int
 281         for b := s.first(); b != &none; b = s.next(b) {
 282                 l += b.len()
 283         }
 284         return l
 285 }
 286
 287 // Max returns the maximum element of the set s, or MinInt if s is empty.
 288 func (s *Sparse) Max() int {
 289         if s.IsEmpty() {
 290                 return MinInt
 291         }
 292         return s.root.prev.max()
 293 }
 294
 295 // Min returns the minimum element of the set s, or MaxInt if s is empty.
 296 func (s *Sparse) Min() int {
 297         if s.IsEmpty() {
 298                 return MaxInt
 299         }
 300         return s.root.min(false)
 301 }
 302
 303 // LowerBound returns the smallest element >= x, or MaxInt if there is no such
 304 // element.
 305 func (s *Sparse) LowerBound(x int) int {
 306         offset, i := offsetAndBitIndex(x)
 307         for b := s.first(); b != &none; b = s.next(b) {
 308                 if b.offset > offset {
 309                         return b.min(false)
 310                 }
 311                 if b.offset == offset {
 312                         if y, ok := b.lowerBound(i); ok {
 313                                 return y
 314                         }
 315                 }
 316         }
 317         return MaxInt
 318 }
 319
 320 // block returns the block that would contain offset,
 321 // or nil if s contains no such block.
 322 // Precondition: offset is a multiple of bitsPerBlock.
 323 func (s *Sparse) block(offset int) *block {
 324         for b := s.first(); b != &none && b.offset <= offset; b = s.next(b) {
 325                 if b.offset == offset {
 326                         return b
 327                 }
 328         }
 329         return nil
 330 }
 331
 332 // Insert adds x to the set s, and reports whether the set grew.
 333 func (s *Sparse) Insert(x int) bool {
 334         offset, i := offsetAndBitIndex(x)
 335
 336         b := s.first()
 337         for ; b != &none && b.offset <= offset; b = s.next(b) {
 338                 if b.offset == offset {
 339                         return b.insert(i)
 340                 }
 341         }
 342
 343         // Insert new block before b.
 344         new := s.insertBlockBefore(b)
 345         new.offset = offset
 346         return new.insert(i)
 347 }
 348
 349 // removeBlock removes a block and returns the block that followed it (or end if
 350 // it was the last block).
 351 func (s *Sparse) removeBlock(b *block) *block {
 352         if b != &s.root {
 353                 b.prev.next = b.next
 354                 b.next.prev = b.prev
 355                 if b.next == &s.root {
 356                         return &none
 357                 }
 358                 return b.next
 359         }
 360
 361         first := s.root.next
 362         if first == &s.root {
 363                 // This was the only block.
 364                 s.Clear()
 365                 return &none
 366         }
 367         s.root.offset = first.offset
 368         s.root.bits = first.bits
 369         if first.next == &s.root {
 370                 // Single block remaining.
 371                 s.root.next = &s.root
 372                 s.root.prev = &s.root
 373         } else {
 374                 s.root.next = first.next
 375                 first.next.prev = &s.root
 376         }
 377         return &s.root
 378 }
 379
 380 // Remove removes x from the set s, and reports whether the set shrank.
 381 func (s *Sparse) Remove(x int) bool {
 382         offset, i := offsetAndBitIndex(x)
 383         if b := s.block(offset); b != nil {
 384                 if !b.remove(i) {
 385                         return false
 386                 }
 387                 if b.empty() {
 388                         s.removeBlock(b)
 389                 }
 390                 return true
 391         }
 392         return false
 393 }
 394
 395 // Clear removes all elements from the set s.
 396 func (s *Sparse) Clear() {
 397         s.root = block{
 398                 offset: MaxInt,
 399                 next:   &s.root,
 400                 prev:   &s.root,
 401         }
 402 }
 403
 404 // If set s is non-empty, TakeMin sets *p to the minimum element of
 405 // the set s, removes that element from the set and returns true.
 406 // Otherwise, it returns false and *p is undefined.
 407 //
 408 // This method may be used for iteration over a worklist like so:
 409 //
 410 //      var x int
 411 //      for worklist.TakeMin(&x) { use(x) }
 412 //
 413 func (s *Sparse) TakeMin(p *int) bool {
 414         if s.IsEmpty() {
 415                 return false
 416         }
 417         *p = s.root.min(true)
 418         if s.root.empty() {
 419                 s.removeBlock(&s.root)
 420         }
 421         return true
 422 }
 423
 424 // Has reports whether x is an element of the set s.
 425 func (s *Sparse) Has(x int) bool {
 426         offset, i := offsetAndBitIndex(x)
 427         if b := s.block(offset); b != nil {
 428                 return b.has(i)
 429         }
 430         return false
 431 }
 432
 433 // forEach applies function f to each element of the set s in order.
 434 //
 435 // f must not mutate s.  Consequently, forEach is not safe to expose
 436 // to clients.  In any case, using "range s.AppendTo()" allows more
 437 // natural control flow with continue/break/return.
 438 //
 439 func (s *Sparse) forEach(f func(int)) {
 440         for b := s.first(); b != &none; b = s.next(b) {
 441                 b.forEach(f)
 442         }
 443 }
 444
 445 // Copy sets s to the value of x.
 446 func (s *Sparse) Copy(x *Sparse) {
 447         if s == x {
 448                 return
 449         }
 450
 451         xb := x.first()
 452         sb := s.first()
 453         for xb != &none {
 454                 if sb == &none {
 455                         sb = s.insertBlockBefore(sb)
 456                 }
 457                 sb.offset = xb.offset
 458                 sb.bits = xb.bits
 459                 xb = x.next(xb)
 460                 sb = s.next(sb)
 461         }
 462         s.discardTail(sb)
 463 }
 464
 465 // insertBlockBefore returns a new block, inserting it before next.
 466 // If next is the root, the root is replaced. If next is end, the block is
 467 // inserted at the end.
 468 func (s *Sparse) insertBlockBefore(next *block) *block {
 469         if s.IsEmpty() {
 470                 if next != &none {
 471                         panic("BUG: passed block with empty set")
 472                 }
 473                 return &s.root
 474         }
 475
 476         if next == &s.root {
 477                 // Special case: we need to create a new block that will become the root
 478                 // block.The old root block becomes the second block.
 479                 second := s.root
 480                 s.root = block{
 481                         next: &second,
 482                 }
 483                 if second.next == &s.root {
 484                         s.root.prev = &second
 485                 } else {
 486                         s.root.prev = second.prev
 487                         second.next.prev = &second
 488                         second.prev = &s.root
 489                 }
 490                 return &s.root
 491         }
 492         if next == &none {
 493                 // Insert before root.
 494                 next = &s.root
 495         }
 496         b := new(block)
 497         b.next = next
 498         b.prev = next.prev
 499         b.prev.next = b
 500         next.prev = b
 501         return b
 502 }
 503
 504 // discardTail removes block b and all its successors from s.
 505 func (s *Sparse) discardTail(b *block) {
 506         if b != &none {
 507                 if b == &s.root {
 508                         s.Clear()
 509                 } else {
 510                         b.prev.next = &s.root
 511                         s.root.prev = b.prev
 512                 }
 513         }
 514 }
 515
 516 // IntersectionWith sets s to the intersection s ∩ x.
 517 func (s *Sparse) IntersectionWith(x *Sparse) {
 518         if s == x {
 519                 return
 520         }
 521
 522         xb := x.first()
 523         sb := s.first()
 524         for xb != &none && sb != &none {
 525                 switch {
 526                 case xb.offset < sb.offset:
 527                         xb = x.next(xb)
 528
 529                 case xb.offset > sb.offset:
 530                         sb = s.removeBlock(sb)
 531
 532                 default:
 533                         var sum word
 534                         for i := range sb.bits {
 535                                 r := xb.bits[i] & sb.bits[i]
 536                                 sb.bits[i] = r
 537                                 sum |= r
 538                         }
 539                         if sum != 0 {
 540                                 sb = s.next(sb)
 541                         } else {
 542                                 // sb will be overwritten or removed
 543                         }
 544
 545                         xb = x.next(xb)
 546                 }
 547         }
 548
 549         s.discardTail(sb)
 550 }
 551
 552 // Intersection sets s to the intersection x ∩ y.
 553 func (s *Sparse) Intersection(x, y *Sparse) {
 554         switch {
 555         case s == x:
 556                 s.IntersectionWith(y)
 557                 return
 558         case s == y:
 559                 s.IntersectionWith(x)
 560                 return
 561         case x == y:
 562                 s.Copy(x)
 563                 return
 564         }
 565
 566         xb := x.first()
 567         yb := y.first()
 568         sb := s.first()
 569         for xb != &none && yb != &none {
 570                 switch {
 571                 case xb.offset < yb.offset:
 572                         xb = x.next(xb)
 573                         continue
 574                 case xb.offset > yb.offset:
 575                         yb = y.next(yb)
 576                         continue
 577                 }
 578
 579                 if sb == &none {
 580                         sb = s.insertBlockBefore(sb)
 581                 }
 582                 sb.offset = xb.offset
 583
 584                 var sum word
 585                 for i := range sb.bits {
 586                         r := xb.bits[i] & yb.bits[i]
 587                         sb.bits[i] = r
 588                         sum |= r
 589                 }
 590                 if sum != 0 {
 591                         sb = s.next(sb)
 592                 } else {
 593                         // sb will be overwritten or removed
 594                 }
 595
 596                 xb = x.next(xb)
 597                 yb = y.next(yb)
 598         }
 599
 600         s.discardTail(sb)
 601 }
 602
 603 // Intersects reports whether s ∩ x ≠ ∅.
 604 func (s *Sparse) Intersects(x *Sparse) bool {
 605         sb := s.first()
 606         xb := x.first()
 607         for sb != &none && xb != &none {
 608                 switch {
 609                 case xb.offset < sb.offset:
 610                         xb = x.next(xb)
 611                 case xb.offset > sb.offset:
 612                         sb = s.next(sb)
 613                 default:
 614                         for i := range sb.bits {
 615                                 if sb.bits[i]&xb.bits[i] != 0 {
 616                                         return true
 617                                 }
 618                         }
 619                         sb = s.next(sb)
 620                         xb = x.next(xb)
 621                 }
 622         }
 623         return false
 624 }
 625
 626 // UnionWith sets s to the union s ∪ x, and reports whether s grew.
 627 func (s *Sparse) UnionWith(x *Sparse) bool {
 628         if s == x {
 629                 return false
 630         }
 631
 632         var changed bool
 633         xb := x.first()
 634         sb := s.first()
 635         for xb != &none {
 636                 if sb != &none && sb.offset == xb.offset {
 637                         for i := range xb.bits {
 638                                 if sb.bits[i] != xb.bits[i] {
 639                                         sb.bits[i] |= xb.bits[i]
 640                                         changed = true
 641                                 }
 642                         }
 643                         xb = x.next(xb)
 644                 } else if sb == &none || sb.offset > xb.offset {
 645                         sb = s.insertBlockBefore(sb)
 646                         sb.offset = xb.offset
 647                         sb.bits = xb.bits
 648                         changed = true
 649
 650                         xb = x.next(xb)
 651                 }
 652                 sb = s.next(sb)
 653         }
 654         return changed
 655 }
 656
 657 // Union sets s to the union x ∪ y.
 658 func (s *Sparse) Union(x, y *Sparse) {
 659         switch {
 660         case x == y:
 661                 s.Copy(x)
 662                 return
 663         case s == x:
 664                 s.UnionWith(y)
 665                 return
 666         case s == y:
 667                 s.UnionWith(x)
 668                 return
 669         }
 670
 671         xb := x.first()
 672         yb := y.first()
 673         sb := s.first()
 674         for xb != &none || yb != &none {
 675                 if sb == &none {
 676                         sb = s.insertBlockBefore(sb)
 677                 }
 678                 switch {
 679                 case yb == &none || (xb != &none && xb.offset < yb.offset):
 680                         sb.offset = xb.offset
 681                         sb.bits = xb.bits
 682                         xb = x.next(xb)
 683
 684                 case xb == &none || (yb != &none && yb.offset < xb.offset):
 685                         sb.offset = yb.offset
 686                         sb.bits = yb.bits
 687                         yb = y.next(yb)
 688
 689                 default:
 690                         sb.offset = xb.offset
 691                         for i := range xb.bits {
 692                                 sb.bits[i] = xb.bits[i] | yb.bits[i]
 693                         }
 694                         xb = x.next(xb)
 695                         yb = y.next(yb)
 696                 }
 697                 sb = s.next(sb)
 698         }
 699
 700         s.discardTail(sb)
 701 }
 702
 703 // DifferenceWith sets s to the difference s ∖ x.
 704 func (s *Sparse) DifferenceWith(x *Sparse) {
 705         if s == x {
 706                 s.Clear()
 707                 return
 708         }
 709
 710         xb := x.first()
 711         sb := s.first()
 712         for xb != &none && sb != &none {
 713                 switch {
 714                 case xb.offset > sb.offset:
 715                         sb = s.next(sb)
 716
 717                 case xb.offset < sb.offset:
 718                         xb = x.next(xb)
 719
 720                 default:
 721                         var sum word
 722                         for i := range sb.bits {
 723                                 r := sb.bits[i] & ^xb.bits[i]
 724                                 sb.bits[i] = r
 725                                 sum |= r
 726                         }
 727                         if sum == 0 {
 728                                 sb = s.removeBlock(sb)
 729                         } else {
 730                                 sb = s.next(sb)
 731                         }
 732                         xb = x.next(xb)
 733                 }
 734         }
 735 }
 736
 737 // Difference sets s to the difference x ∖ y.
 738 func (s *Sparse) Difference(x, y *Sparse) {
 739         switch {
 740         case x == y:
 741                 s.Clear()
 742                 return
 743         case s == x:
 744                 s.DifferenceWith(y)
 745                 return
 746         case s == y:
 747                 var y2 Sparse
 748                 y2.Copy(y)
 749                 s.Difference(x, &y2)
 750                 return
 751         }
 752
 753         xb := x.first()
 754         yb := y.first()
 755         sb := s.first()
 756         for xb != &none && yb != &none {
 757                 if xb.offset > yb.offset {
 758                         // y has block, x has &none
 759                         yb = y.next(yb)
 760                         continue
 761                 }
 762
 763                 if sb == &none {
 764                         sb = s.insertBlockBefore(sb)
 765                 }
 766                 sb.offset = xb.offset
 767
 768                 switch {
 769                 case xb.offset < yb.offset:
 770                         // x has block, y has &none
 771                         sb.bits = xb.bits
 772
 773                         sb = s.next(sb)
 774
 775                 default:
 776                         // x and y have corresponding blocks
 777                         var sum word
 778                         for i := range sb.bits {
 779                                 r := xb.bits[i] & ^yb.bits[i]
 780                                 sb.bits[i] = r
 781                                 sum |= r
 782                         }
 783                         if sum != 0 {
 784                                 sb = s.next(sb)
 785                         } else {
 786                                 // sb will be overwritten or removed
 787                         }
 788
 789                         yb = y.next(yb)
 790                 }
 791                 xb = x.next(xb)
 792         }
 793
 794         for xb != &none {
 795                 if sb == &none {
 796                         sb = s.insertBlockBefore(sb)
 797                 }
 798                 sb.offset = xb.offset
 799                 sb.bits = xb.bits
 800                 sb = s.next(sb)
 801
 802                 xb = x.next(xb)
 803         }
 804
 805         s.discardTail(sb)
 806 }
 807
 808 // SymmetricDifferenceWith sets s to the symmetric difference s ∆ x.
 809 func (s *Sparse) SymmetricDifferenceWith(x *Sparse) {
 810         if s == x {
 811                 s.Clear()
 812                 return
 813         }
 814
 815         sb := s.first()
 816         xb := x.first()
 817         for xb != &none && sb != &none {
 818                 switch {
 819                 case sb.offset < xb.offset:
 820                         sb = s.next(sb)
 821                 case xb.offset < sb.offset:
 822                         nb := s.insertBlockBefore(sb)
 823                         nb.offset = xb.offset
 824                         nb.bits = xb.bits
 825                         xb = x.next(xb)
 826                 default:
 827                         var sum word
 828                         for i := range sb.bits {
 829                                 r := sb.bits[i] ^ xb.bits[i]
 830                                 sb.bits[i] = r
 831                                 sum |= r
 832                         }
 833                         if sum == 0 {
 834                                 sb = s.removeBlock(sb)
 835                         } else {
 836                                 sb = s.next(sb)
 837                         }
 838                         xb = x.next(xb)
 839                 }
 840         }
 841
 842         for xb != &none { // append the tail of x to s
 843                 sb = s.insertBlockBefore(sb)
 844                 sb.offset = xb.offset
 845                 sb.bits = xb.bits
 846                 sb = s.next(sb)
 847                 xb = x.next(xb)
 848         }
 849 }
 850
 851 // SymmetricDifference sets s to the symmetric difference x ∆ y.
 852 func (s *Sparse) SymmetricDifference(x, y *Sparse) {
 853         switch {
 854         case x == y:
 855                 s.Clear()
 856                 return
 857         case s == x:
 858                 s.SymmetricDifferenceWith(y)
 859                 return
 860         case s == y:
 861                 s.SymmetricDifferenceWith(x)
 862                 return
 863         }
 864
 865         sb := s.first()
 866         xb := x.first()
 867         yb := y.first()
 868         for xb != &none && yb != &none {
 869                 if sb == &none {
 870                         sb = s.insertBlockBefore(sb)
 871                 }
 872                 switch {
 873                 case yb.offset < xb.offset:
 874                         sb.offset = yb.offset
 875                         sb.bits = yb.bits
 876                         sb = s.next(sb)
 877                         yb = y.next(yb)
 878                 case xb.offset < yb.offset:
 879                         sb.offset = xb.offset
 880                         sb.bits = xb.bits
 881                         sb = s.next(sb)
 882                         xb = x.next(xb)
 883                 default:
 884                         var sum word
 885                         for i := range sb.bits {
 886                                 r := xb.bits[i] ^ yb.bits[i]
 887                                 sb.bits[i] = r
 888                                 sum |= r
 889                         }
 890                         if sum != 0 {
 891                                 sb.offset = xb.offset
 892                                 sb = s.next(sb)
 893                         }
 894                         xb = x.next(xb)
 895                         yb = y.next(yb)
 896                 }
 897         }
 898
 899         for xb != &none { // append the tail of x to s
 900                 if sb == &none {
 901                         sb = s.insertBlockBefore(sb)
 902                 }
 903                 sb.offset = xb.offset
 904                 sb.bits = xb.bits
 905                 sb = s.next(sb)
 906                 xb = x.next(xb)
 907         }
 908
 909         for yb != &none { // append the tail of y to s
 910                 if sb == &none {
 911                         sb = s.insertBlockBefore(sb)
 912                 }
 913                 sb.offset = yb.offset
 914                 sb.bits = yb.bits
 915                 sb = s.next(sb)
 916                 yb = y.next(yb)
 917         }
 918
 919         s.discardTail(sb)
 920 }
 921
 922 // SubsetOf reports whether s ∖ x = ∅.
 923 func (s *Sparse) SubsetOf(x *Sparse) bool {
 924         if s == x {
 925                 return true
 926         }
 927
 928         sb := s.first()
 929         xb := x.first()
 930         for sb != &none {
 931                 switch {
 932                 case xb == &none || xb.offset > sb.offset:
 933                         return false
 934                 case xb.offset < sb.offset:
 935                         xb = x.next(xb)
 936                 default:
 937                         for i := range sb.bits {
 938                                 if sb.bits[i]&^xb.bits[i] != 0 {
 939                                         return false
 940                                 }
 941                         }
 942                         sb = s.next(sb)
 943                         xb = x.next(xb)
 944                 }
 945         }
 946         return true
 947 }
 948
 949 // Equals reports whether the sets s and t have the same elements.
 950 func (s *Sparse) Equals(t *Sparse) bool {
 951         if s == t {
 952                 return true
 953         }
 954         sb := s.first()
 955         tb := t.first()
 956         for {
 957                 switch {
 958                 case sb == &none && tb == &none:
 959                         return true
 960                 case sb == &none || tb == &none:
 961                         return false
 962                 case sb.offset != tb.offset:
 963                         return false
 964                 case sb.bits != tb.bits:
 965                         return false
 966                 }
 967
 968                 sb = s.next(sb)
 969                 tb = t.next(tb)
 970         }
 971 }
 972
 973 // String returns a human-readable description of the set s.
 974 func (s *Sparse) String() string {
 975         var buf bytes.Buffer
 976         buf.WriteByte('{')
 977         s.forEach(func(x int) {
 978                 if buf.Len() > 1 {
 979                         buf.WriteByte(' ')
 980                 }
 981                 fmt.Fprintf(&buf, "%d", x)
 982         })
 983         buf.WriteByte('}')
 984         return buf.String()
 985 }
 986
 987 // BitString returns the set as a string of 1s and 0s denoting the sum
 988 // of the i'th powers of 2, for each i in s.  A radix point, always
 989 // preceded by a digit, appears if the sum is non-integral.
 990 //
 991 // Examples:
 992 //              {}.BitString() =      "0"
 993 //           {4,5}.BitString() = "110000"
 994 //            {-3}.BitString() =      "0.001"
 995 //      {-3,0,4,5}.BitString() = "110001.001"
 996 //
 997 func (s *Sparse) BitString() string {
 998         if s.IsEmpty() {
 999                 return "0"
1000         }
1001
1002         min, max := s.Min(), s.Max()
1003         var nbytes int
1004         if max > 0 {
1005                 nbytes = max
1006         }
1007         nbytes++ // zero bit
1008         radix := nbytes
1009         if min < 0 {
1010                 nbytes += len(".") - min
1011         }
1012
1013         b := make([]byte, nbytes)
1014         for i := range b {
1015                 b[i] = '0'
1016         }
1017         if radix < nbytes {
1018                 b[radix] = '.'
1019         }
1020         s.forEach(func(x int) {
1021                 if x >= 0 {
1022                         x += len(".")
1023                 }
1024                 b[radix-x] = '1'
1025         })
1026         return string(b)
1027 }
1028
1029 // GoString returns a string showing the internal representation of
1030 // the set s.
1031 //
1032 func (s *Sparse) GoString() string {
1033         var buf bytes.Buffer
1034         for b := s.first(); b != &none; b = s.next(b) {
1035                 fmt.Fprintf(&buf, "block %p {offset=%d next=%p prev=%p",
1036                         b, b.offset, b.next, b.prev)
1037                 for _, w := range b.bits {
1038                         fmt.Fprintf(&buf, " 0%016x", w)
1039                 }
1040                 fmt.Fprintf(&buf, "}\n")
1041         }
1042         return buf.String()
1043 }
1044
1045 // AppendTo returns the result of appending the elements of s to slice
1046 // in order.
1047 func (s *Sparse) AppendTo(slice []int) []int {
1048         s.forEach(func(x int) {
1049                 slice = append(slice, x)
1050         })
1051         return slice
1052 }
1053
1054 // -- Testing/debugging ------------------------------------------------
1055
1056 // check returns an error if the representation invariants of s are violated.
1057 func (s *Sparse) check() error {
1058         s.init()
1059         if s.root.empty() {
1060                 // An empty set must have only the root block with offset MaxInt.
1061                 if s.root.next != &s.root {
1062                         return fmt.Errorf("multiple blocks with empty root block")
1063                 }
1064                 if s.root.offset != MaxInt {
1065                         return fmt.Errorf("empty set has offset %d, should be MaxInt", s.root.offset)
1066                 }
1067                 return nil
1068         }
1069         for b := s.first(); ; b = s.next(b) {
1070                 if b.offset%bitsPerBlock != 0 {
1071                         return fmt.Errorf("bad offset modulo: %d", b.offset)
1072                 }
1073                 if b.empty() {
1074                         return fmt.Errorf("empty block")
1075                 }
1076                 if b.prev.next != b {
1077                         return fmt.Errorf("bad prev.next link")
1078                 }
1079                 if b.next.prev != b {
1080                         return fmt.Errorf("bad next.prev link")
1081                 }
1082                 if b.next == &s.root {
1083                         break
1084                 }
1085                 if b.offset >= b.next.offset {
1086                         return fmt.Errorf("bad offset order: b.offset=%d, b.next.offset=%d",
1087                                 b.offset, b.next.offset)
1088                 }
1089         }
1090         return nil
1091 }