package bitset
import "github.com/bits-and-blooms/bitset"
Package bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool.
It provides methods for setting, clearing, flipping, and testing individual integers.
But it also provides set intersection, union, difference, complement, and symmetric operations, as well as tests to check whether any, all, or no bits are set, and querying a bitset's current length and number of positive bits.
BitSets are expanded to the size of the largest set bit; the memory allocation is approximately Max bits, where Max is the largest set bit. BitSets are never shrunk. On creation, a hint can be given for the number of bits that will be used.
Many of the methods, including Set,Clear, and Flip, return a BitSet pointer, which allows for chaining.
Example use:
import "bitset"
var b BitSet
b.Set(10).Set(11)
if b.Test(1000) {
b.Clear(1000)
}
if B.Intersection(bitset.New(100).Set(10)).Count() > 1 {
fmt.Println("Intersection works.")
}
As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets.
Index ¶
- func Base64StdEncoding()
- func Cap() uint
- func LittleEndian()
- type BitSet
- func From(buf []uint64) *BitSet
- func New(length uint) (bset *BitSet)
- func (b *BitSet) All() bool
- func (b *BitSet) Any() bool
- func (b *BitSet) BinaryStorageSize() int
- func (b *BitSet) Bytes() []uint64
- func (b *BitSet) Clear(i uint) *BitSet
- func (b *BitSet) ClearAll() *BitSet
- func (b *BitSet) Clone() *BitSet
- func (b *BitSet) Complement() (result *BitSet)
- func (b *BitSet) Copy(c *BitSet) (count uint)
- func (b *BitSet) Count() uint
- func (b *BitSet) DeleteAt(i uint) *BitSet
- func (b *BitSet) Difference(compare *BitSet) (result *BitSet)
- func (b *BitSet) DifferenceCardinality(compare *BitSet) uint
- func (b *BitSet) DumpAsBits() string
- func (b *BitSet) Equal(c *BitSet) bool
- func (b *BitSet) Flip(i uint) *BitSet
- func (b *BitSet) InPlaceDifference(compare *BitSet)
- func (b *BitSet) InPlaceIntersection(compare *BitSet)
- func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet)
- func (b *BitSet) InPlaceUnion(compare *BitSet)
- func (b *BitSet) InsertAt(idx uint) *BitSet
- func (b *BitSet) Intersection(compare *BitSet) (result *BitSet)
- func (b *BitSet) IntersectionCardinality(compare *BitSet) uint
- func (b *BitSet) IsStrictSuperSet(other *BitSet) bool
- func (b *BitSet) IsSuperSet(other *BitSet) bool
- func (b *BitSet) Len() uint
- func (b *BitSet) MarshalBinary() ([]byte, error)
- func (b *BitSet) MarshalJSON() ([]byte, error)
- func (b *BitSet) NextClear(i uint) (uint, bool)
- func (b *BitSet) NextSet(i uint) (uint, bool)
- func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint)
- func (b *BitSet) None() bool
- func (b *BitSet) ReadFrom(stream io.Reader) (int64, error)
- func (b *BitSet) Set(i uint) *BitSet
- func (b *BitSet) SetTo(i uint, value bool) *BitSet
- func (b *BitSet) Shrink(length uint) *BitSet
- func (b *BitSet) String() string
- func (b *BitSet) SymmetricDifference(compare *BitSet) (result *BitSet)
- func (b *BitSet) SymmetricDifferenceCardinality(compare *BitSet) uint
- func (b *BitSet) Test(i uint) bool
- func (b *BitSet) Union(compare *BitSet) (result *BitSet)
- func (b *BitSet) UnionCardinality(compare *BitSet) uint
- func (b *BitSet) UnmarshalBinary(data []byte) error
- func (b *BitSet) UnmarshalJSON(data []byte) error
- func (b *BitSet) WriteTo(stream io.Writer) (int64, error)
- type Error
Functions ¶
func Base64StdEncoding ¶
func Base64StdEncoding()
Base64StdEncoding Marshal/Unmarshal BitSet with base64.StdEncoding(Default: base64.URLEncoding)
func Cap ¶
func Cap() uint
Cap returns the total possible capacity, or number of bits
func LittleEndian ¶
func LittleEndian()
LittleEndian Marshal/Unmarshal Binary as Little Endian(Default: binary.BigEndian)
Types ¶
type BitSet ¶
type BitSet struct {
// contains filtered or unexported fields
}
A BitSet is a set of bits. The zero value of a BitSet is an empty set of length 0.
func From ¶
From is a constructor used to create a BitSet from an array of integers
func New ¶
New creates a new BitSet with a hint that length bits will be required
func (*BitSet) All ¶
All returns true if all bits are set, false otherwise. Returns true for empty sets.
func (*BitSet) Any ¶
Any returns true if any bit is set, false otherwise
func (*BitSet) BinaryStorageSize ¶
BinaryStorageSize returns the binary storage requirements
func (*BitSet) Bytes ¶
Bytes returns the bitset as array of integers
func (*BitSet) Clear ¶
Clear bit i to 0
func (*BitSet) ClearAll ¶
ClearAll clears the entire BitSet
func (*BitSet) Clone ¶
Clone this BitSet
func (*BitSet) Complement ¶
Complement computes the (local) complement of a biset (up to length bits)
func (*BitSet) Copy ¶
Copy into a destination BitSet Returning the size of the destination BitSet like array copy
func (*BitSet) Count ¶
Count (number of set bits)
func (*BitSet) DeleteAt ¶
DeleteAt deletes the bit at the given index position from within the bitset All the bits residing on the left of the deleted bit get shifted right by 1 The running time of this operation may potentially be relatively slow, O(length)
func (*BitSet) Difference ¶
Difference of base set and other set This is the BitSet equivalent of &^ (and not)
func (*BitSet) DifferenceCardinality ¶
DifferenceCardinality computes the cardinality of the differnce
func (*BitSet) DumpAsBits ¶
DumpAsBits dumps a bit set as a string of bits
func (*BitSet) Equal ¶
Equal tests the equvalence of two BitSets. False if they are of different sizes, otherwise true only if all the same bits are set
func (*BitSet) Flip ¶
Flip bit at i
func (*BitSet) InPlaceDifference ¶
InPlaceDifference computes the difference of base set and other set This is the BitSet equivalent of &^ (and not)
func (*BitSet) InPlaceIntersection ¶
InPlaceIntersection destructively computes the intersection of base set and the compare set. This is the BitSet equivalent of & (and)
func (*BitSet) InPlaceSymmetricDifference ¶
InPlaceSymmetricDifference creates the destructive SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)
func (*BitSet) InPlaceUnion ¶
InPlaceUnion creates the destructive union of base set and compare set. This is the BitSet equivalent of | (or).
func (*BitSet) InsertAt ¶
InsertAt takes an index which indicates where a bit should be inserted. Then it shifts all the bits in the set to the left by 1, starting from the given index position, and sets the index position to 0.
Depending on the size of your BitSet, and where you are inserting the new entry, this method could be extremely slow and in some cases might cause the entire BitSet to be recopied.
func (*BitSet) Intersection ¶
Intersection of base set and other set This is the BitSet equivalent of & (and)
func (*BitSet) IntersectionCardinality ¶
IntersectionCardinality computes the cardinality of the union
func (*BitSet) IsStrictSuperSet ¶
IsStrictSuperSet returns true if this is a strict superset of the other set
func (*BitSet) IsSuperSet ¶
IsSuperSet returns true if this is a superset of the other set
func (*BitSet) Len ¶
Len returns the length of the BitSet in words
func (*BitSet) MarshalBinary ¶
MarshalBinary encodes a BitSet into a binary form and returns the result.
func (*BitSet) MarshalJSON ¶
MarshalJSON marshals a BitSet as a JSON structure
func (*BitSet) NextClear ¶
NextClear returns the next clear bit from the specified index, including possibly the current index along with an error code (true = valid, false = no bit found i.e. all bits are set)
func (*BitSet) NextSet ¶
NextSet returns the next bit set from the specified index, including possibly the current index along with an error code (true = valid, false = no set bit found) for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) {...}
func (*BitSet) NextSetMany ¶
NextSetMany returns many next bit sets from the specified index, including possibly the current index and up to cap(buffer). If the returned slice has len zero, then no more set bits were found
buffer := make([]uint, 256) // this should be reused
j := uint(0)
j, buffer = bitmap.NextSetMany(j, buffer)
for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j,buffer) {
for k := range buffer {
do something with buffer[k]
}
j += 1
}
func (*BitSet) None ¶
None returns true if no bit is set, false otherwise. Retursn true for empty sets.
func (*BitSet) ReadFrom ¶
ReadFrom reads a BitSet from a stream written using WriteTo
func (*BitSet) Set ¶
Set bit i to 1
func (*BitSet) SetTo ¶
SetTo sets bit i to value
func (*BitSet) Shrink ¶
Shrink shrinks BitSet to desired length in bits. It clears all bits > length and reduces the size and length of the set.
A new slice is allocated to store the new bits, so you may see an increase in memory usage until the GC runs. Normally this should not be a problem, but if you have an extremely large BitSet its important to understand that the old BitSet will remain in memory until the GC frees it.
func (*BitSet) String ¶
String creates a string representation of the Bitmap
func (*BitSet) SymmetricDifference ¶
SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)
func (*BitSet) SymmetricDifferenceCardinality ¶
SymmetricDifferenceCardinality computes the cardinality of the symmetric difference
func (*BitSet) Test ¶
Test whether bit i is set.
func (*BitSet) Union ¶
Union of base set and other set This is the BitSet equivalent of | (or)
func (*BitSet) UnionCardinality ¶
UnionCardinality computes the cardinality of the uniton of the base set and the compare set.
func (*BitSet) UnmarshalBinary ¶
UnmarshalBinary decodes the binary form generated by MarshalBinary.
func (*BitSet) UnmarshalJSON ¶
UnmarshalJSON unmarshals a BitSet from JSON created using MarshalJSON
func (*BitSet) WriteTo ¶
WriteTo writes a BitSet to a stream
type Error ¶
type Error string
Error is used to distinguish errors (panics) generated in this package.
Source Files ¶
bitset.go popcnt.go popcnt_19.go trailing_zeros_19.go
- Version
- v1.1.10
- Published
- Feb 19, 2019
- Platform
- js/wasm
- Imports
- 10 packages
- Last checked
- now –
Tools for package owners.