README
¶
bitset: Bitsets for Go
This package includes a radix-tree implementation that uses Hash Array Mapped Tries as well as a more traditional dense implementation.
Documentation
¶
Overview ¶
Package bitset implements bitsets. A bitset is a set of non-negative integers represented using a bit for each integer.
There are three implementations:
Use Dense for the common case where you know the largest value that could be in the set, and you want to use a sequence of bits. Addition, removal and membership tests on a Dense bitset are very fast, and memory is proportional to the largest possible value (one bit per possible value).
Use Sparse for bitsets whose values can come from a wide range. Sparse bitsets take more time per operation, but can use less memory than a Dense bitset if the set contains relatively few elements drawn from a large range. For example, A Dense bitset with the elements 1000, 2000, ...., 1_000_000 would occupy 122K, while a Sparse one would take about 57K.
Set64 is a faster version of Dense when the largest possible value is 63.
Index ¶
- type Dense
- func (s *Dense) Add(n uint)
- func (s1 *Dense) AddIn(s2 *Dense)
- func (s *Dense) Cap() int
- func (s *Dense) Clear()
- func (s *Dense) Complement()
- func (s *Dense) Contains(n uint) bool
- func (s *Dense) Copy() *Dense
- func (s *Dense) Elements(f func([]uint) bool)
- func (s *Dense) Empty() bool
- func (s1 *Dense) Equal(s2 *Dense) bool
- func (s *Dense) Len() int
- func (s1 *Dense) LenRemoveIn(s2 *Dense) int
- func (s *Dense) Remove(n uint)
- func (s1 *Dense) RemoveIn(s2 *Dense)
- func (s1 *Dense) RemoveNotIn(s2 *Dense)
- func (s *Dense) SetCap(newCapacity int)
- type Set64
- func (s *Set64) Add(u uint8)
- func (s1 *Set64) AddIn(s2 Set64)
- func (s *Set64) Clear()
- func (s *Set64) Complement()
- func (s *Set64) Contains(u uint8) bool
- func (s Set64) Empty() bool
- func (s1 Set64) Equal(s2 Set64) bool
- func (s Set64) Len() int
- func (s *Set64) Remove(u uint8)
- func (s1 *Set64) RemoveIn(s2 Set64)
- func (s1 *Set64) RemoveNotIn(s2 Set64)
- func (s Set64) String() string
- type Sparse
- func (s *Sparse) Add(n uint)
- func (s *Sparse) Add64(n uint64)
- func (s1 *Sparse) AddIn(s2 *Sparse)
- func (s *Sparse) Clear()
- func (s *Sparse) Contains(n uint) bool
- func (s *Sparse) Contains64(n uint64) bool
- func (s *Sparse) Copy() *Sparse
- func (s *Sparse) Elements(f func([]uint64) bool)
- func (s *Sparse) Empty() bool
- func (s1 *Sparse) Equal(s2 *Sparse) bool
- func (s *Sparse) Len() int
- func (s *Sparse) Remove(n uint)
- func (s *Sparse) Remove64(n uint64)
- func (s1 *Sparse) RemoveIn(s2 *Sparse)
- func (s1 *Sparse) RemoveNotIn(s2 *Sparse)
- func (s *Sparse) String() string
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Dense ¶
type Dense struct {
// contains filtered or unexported fields
}
Dense is a standard bitset, represented as a sequence of bits. See Sparse in this package for a more memory-efficient storage scheme for sparse bitsets.
func NewDense ¶
NewDense creates a set capable of representing values in the range [0, capacity), at least. The Cap method reports the exact capacity. NewDense panics if capacity is negative.
func (*Dense) AddIn ¶
AddIn adds all the elements in s2 to s1. It sets s1 to the union of s1 and s2.
func (*Dense) Cap ¶
Cap returns the maximum number of elements the set can contain, which is one greater than the largest element it can contain.
func (*Dense) Elements ¶
Elements calls f on successive slices of the set's elements, from lowest to highest. If f returns false, the iteration stops. The slice passed to f will be reused when f returns.
func (*Dense) Equal ¶
Equal reports whether s2 has the same elements as s1. It may have a different capacity.
func (*Dense) LenRemoveIn ¶ added in v0.1.1
LenRemoveIn returns what s1.Len() would be after s1.RemoveIn(s2), without modifying s1.
func (*Dense) RemoveIn ¶
RemoveIn removes from s1 all the elements that are in s2. It sets s1 to the set difference of s1 and s2.
func (*Dense) RemoveNotIn ¶
RemoveNotIn removes from s1 all the elements that are not in s2. It sets s1 to the intersection of s1 and s2.
type Set64 ¶
type Set64 uint64
Set64 is an efficient representation of a bitset that can represent integers in the range [0, 64). For efficiency, the methods of Set64 perform no bounds checking on their arguments.
func (*Set64) AddIn ¶
AddIn adds all the elements in s2 to s1. It sets s1 to the union of s1 and s2.
func (*Set64) RemoveIn ¶
RemoveIn removes from s1 all the elements that are in s2. It sets s1 to the set difference of s1 and s2.
func (*Set64) RemoveNotIn ¶
RemoveNotIn removes from s1 all the elements that are not in s2. It sets s1 to the intersection of s1 and s2.
type Sparse ¶
type Sparse struct {
// contains filtered or unexported fields
}
Sparse is a sparse bitset. It can represent any uint64 and uses memory proportional to the number of elements it contains.
func (*Sparse) AddIn ¶
AddIn adds all the elements in s2 to s1. It sets s1 to the union of s1 and s2.
func (*Sparse) Contains64 ¶
Contains64 reports whether s contains s.
func (*Sparse) Elements ¶
Elements calls f on successive slices of the set's elements, from lowest to highest. If f returns false, the iteration stops. The slice passed to f will be reused when f returns.
func (*Sparse) RemoveIn ¶
RemoveIn removes from s1 all the elements that are in s2. It sets s1 to the set difference of s1 and s2.
func (*Sparse) RemoveNotIn ¶
RemoveNotIn removes from s1 all the elements that are not in s2. It sets s1 to the intersection of s1 and s2.
Source Files