sparse.go

Documentation: golang.org/x/tools/container/intsets

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