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 postive 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 Cap() uint
- type BitSet
- func New(length uint) *BitSet
- func (b *BitSet) All() bool
- func (b *BitSet) Any() bool
- 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) 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) Intersection(compare *BitSet) (result *BitSet)
- func (b *BitSet) IntersectionCardinality(compare *BitSet) uint
- func (b *BitSet) Len() uint
- func (b *BitSet) MarshalJSON() ([]byte, error)
- func (b *BitSet) NextSet(i uint) (uint, bool)
- func (b *BitSet) None() bool
- func (b *BitSet) Set(i uint) *BitSet
- func (b *BitSet) SetTo(i uint, value bool) *BitSet
- 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) UnmarshalJSON(data []byte) error
- type BitSetError
Functions ¶
func Cap ¶
func Cap() uint
Types ¶
type BitSet ¶
type BitSet struct {
// contains filtered or unexported fields
}
The zero value of a BitSet is an empty set of length 0.
func New ¶
func (*BitSet) All ¶
Returns true if all bits are set, false otherwise
func (*BitSet) Any ¶
Return true if any bit is set, false otherwise
func (*BitSet) Clear ¶
Clear bit i to 0
func (*BitSet) ClearAll ¶
Clear entire BitSet
func (*BitSet) Clone ¶
Clone this BitSet
func (*BitSet) Complement ¶
Return the (local) Complement of a biset (up to length bits)
func (*BitSet) Copy ¶
Copy this BitSet into a destination BitSet Returning the size of the destination BitSet like array copy
func (*BitSet) Count ¶
Count (number of set bits)
func (*BitSet) Difference ¶
Difference of base set and other set This is the BitSet equivalent of &^ (and not)
func (*BitSet) DifferenceCardinality ¶
computes the cardinality of the differnce
func (*BitSet) DumpAsBits ¶
Dump as bits
func (*BitSet) Equal ¶
Test 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 ¶
Difference of base set and other set This is the BitSet equivalent of &^ (and not)
func (*BitSet) InPlaceIntersection ¶
Intersection of base set and other set This is the BitSet equivalent of & (and)
func (*BitSet) InPlaceSymmetricDifference ¶
SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)
func (*BitSet) InPlaceUnion ¶
Union of base set and other set This is the BitSet equivalent of | (or)
func (*BitSet) Intersection ¶
Intersection of base set and other set This is the BitSet equivalent of & (and)
func (*BitSet) IntersectionCardinality ¶
Computes the cardinality of the union
func (*BitSet) Len ¶
func (*BitSet) MarshalJSON ¶
func (*BitSet) NextSet ¶
return 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) None ¶
Return true if no bit is set, false otherwise
func (*BitSet) Set ¶
Set bit i to 1
func (*BitSet) SetTo ¶
Set bit i to value
func (*BitSet) SymmetricDifference ¶
SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)
func (*BitSet) 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 ¶
func (*BitSet) UnmarshalJSON ¶
type BitSetError ¶
type BitSetError string
Source Files ¶
- Version
- v1.0.0
- Published
- Feb 15, 2014
- Platform
- js/wasm
- Imports
- 6 packages
- Last checked
- now –
Tools for package owners.