blob: d3d7f89ab557d22b8b2839ee337e4b9b0ce27ebd [file] [log] [blame]
amit.ghosh258d14c2020-10-02 15:13:38 +02001// 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.
6package set
7
8import "math/bits"
9
10// int64s represents a set of integers within the range of 0..63.
11type int64s uint64
12
13func (bs *int64s) Len() int {
14 return bits.OnesCount64(uint64(*bs))
15}
16func (bs *int64s) Has(n uint64) bool {
17 return uint64(*bs)&(uint64(1)<<n) > 0
18}
19func (bs *int64s) Set(n uint64) {
20 *(*uint64)(bs) |= uint64(1) << n
21}
22func (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.
27type Ints struct {
28 lo int64s
29 hi map[uint64]struct{}
30}
31
32func (bs *Ints) Len() int {
33 return bs.lo.Len() + len(bs.hi)
34}
35func (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}
42func (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}
52func (bs *Ints) Clear(n uint64) {
53 if n < 64 {
54 bs.lo.Clear(n)
55 return
56 }
57 delete(bs.hi, n)
58}