Documentation
¶
Overview ¶
Package bitset implements bitsets, a mapping between non-negative integers and boolean values.
Studied github.com/bits-and-blooms/bitset inside out and rewrote needed parts from scratch for this project.
This implementation is smaller and faster as the more general github.com/bits-and-blooms/bitset.
All functions can be inlined!
can inline BitSet.Set with cost 63 can inline BitSet.Clear with cost 24 can inline BitSet.Test with cost 26 can inline BitSet.Rank0 with cost 57 can inline BitSet.Clone with cost 7 can inline BitSet.Compact with cost 35 can inline BitSet.FirstSet with cost 25 can inline BitSet.NextSet with cost 71 can inline BitSet.AsSlice with cost 50 can inline BitSet.All with cost 70 can inline BitSet.IntersectsAny with cost 42 can inline BitSet.IntersectionTop with cost 56 can inline BitSet.IntersectionCardinality with cost 35 can inline (*BitSet).InPlaceIntersection with cost 71 can inline (*BitSet).InPlaceUnion with cost 77 can inline BitSet.Size with cost 16 can inline popcount with cost 12 can inline popcountAnd with cost 30
Index ¶
- type BitSet
- func (b BitSet) All() []uint
- func (b BitSet) AsSlice(buf []uint) []uint
- func (b BitSet) Clear(i uint) BitSet
- func (b BitSet) Clone() BitSet
- func (b BitSet) Compact() BitSet
- func (b BitSet) FirstSet() (uint, bool)
- func (b *BitSet) InPlaceIntersection(c BitSet)
- func (b *BitSet) InPlaceUnion(c BitSet)
- func (b BitSet) IntersectionCardinality(c BitSet) int
- func (b BitSet) IntersectionTop(c BitSet) (top uint, ok bool)
- func (b BitSet) IntersectsAny(c BitSet) bool
- func (b BitSet) NextSet(i uint) (uint, bool)
- func (b BitSet) Rank0(i uint) (rnk int)
- func (b BitSet) Set(i uint) BitSet
- func (b BitSet) Size() int
- func (b BitSet) Test(i uint) (ok bool)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BitSet ¶
type BitSet []uint64
A BitSet is a slice of words. This is an internal package with a wide open public API.
func (BitSet) AsSlice ¶
AsSlice returns all set bits as slice of uint without heap allocations.
This is faster than All, but also more dangerous, it panics if the capacity of buf is < b.Size()
func (*BitSet) InPlaceIntersection ¶
InPlaceIntersection overwrites and computes the intersection of base set with the compare set. This is the BitSet equivalent of & (and). If len(c) > len(b), new memory is allocated.
func (*BitSet) InPlaceUnion ¶
InPlaceUnion creates the destructive union of base set with compare set. This is the BitSet equivalent of | (or). If len(c) > len(b), new memory is allocated.
func (BitSet) IntersectionCardinality ¶
IntersectionCardinality computes the popcount of the intersection.
func (BitSet) IntersectionTop ¶
IntersectionTop computes the intersection of base set with the compare set. If the result set isn't empty, it returns the top most set bit and true.
func (BitSet) IntersectsAny ¶
IntersectsAny returns true if the intersection of base set with the compare set is not the empty set.
func (BitSet) NextSet ¶
NextSet returns the next bit set from the specified index, including possibly the current index along with an ok code.
func (BitSet) Rank0 ¶
Rank0 is equal to Rank(i) - 1
With inlined popcount to make Rank0 itself inlineable.
Source Files