ints.go raw

   1  // Copyright 2018 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 set provides simple set data structures for uint64s.
   6  package set
   7  
   8  import "math/bits"
   9  
  10  // int64s represents a set of integers within the range of 0..63.
  11  type int64s uint64
  12  
  13  func (bs *int64s) Len() int {
  14  	return bits.OnesCount64(uint64(*bs))
  15  }
  16  func (bs *int64s) Has(n uint64) bool {
  17  	return uint64(*bs)&(uint64(1)<<n) > 0
  18  }
  19  func (bs *int64s) Set(n uint64) {
  20  	*(*uint64)(bs) |= uint64(1) << n
  21  }
  22  func (bs *int64s) Clear(n uint64) {
  23  	*(*uint64)(bs) &^= uint64(1) << n
  24  }
  25  
  26  // Ints represents a set of integers within the range of 0..math.MaxUint64.
  27  type Ints struct {
  28  	lo int64s
  29  	hi map[uint64]struct{}
  30  }
  31  
  32  func (bs *Ints) Len() int {
  33  	return bs.lo.Len() + len(bs.hi)
  34  }
  35  func (bs *Ints) Has(n uint64) bool {
  36  	if n < 64 {
  37  		return bs.lo.Has(n)
  38  	}
  39  	_, ok := bs.hi[n]
  40  	return ok
  41  }
  42  func (bs *Ints) Set(n uint64) {
  43  	if n < 64 {
  44  		bs.lo.Set(n)
  45  		return
  46  	}
  47  	if bs.hi == nil {
  48  		bs.hi = make(map[uint64]struct{})
  49  	}
  50  	bs.hi[n] = struct{}{}
  51  }
  52  func (bs *Ints) Clear(n uint64) {
  53  	if n < 64 {
  54  		bs.lo.Clear(n)
  55  		return
  56  	}
  57  	delete(bs.hi, n)
  58  }
  59