ints.go 1.2 KB

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