ints.go (1191B)
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 }