Documentation ¶
Overview ¶
Package ranksel provides a bit vector that can answer rank and select queries.
Index ¶
- type BitVector
- func (v *BitVector) Add(bits uint64, size int)
- func (v *BitVector) Bit(i int) uint
- func (v *BitVector) Get(idx, size int) uint64
- func (v *BitVector) GobDecode(data []byte) error
- func (v *BitVector) GobEncode() ([]byte, error)
- func (v *BitVector) Len() int
- func (v *BitVector) PopCount() int
- func (v *BitVector) Rank0(i int) int
- func (v *BitVector) Rank1(i int) int
- func (v *BitVector) Select0(i int) int
- func (v *BitVector) Select1(i int) int
- func (v *BitVector) Size() int
- func (v *BitVector) String() string
- type Options
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BitVector ¶
type BitVector struct {
// contains filtered or unexported fields
}
BitVector is a bitmap with added data structure described by G. Navarro and E. Providel's `A Structure for Plain Bitmaps: Combined Sampling` in "Fast, Small, Simple Rank/Select on Bitmaps" with some minor modifications.
See http://dcc.uchile.cl/~gnavarro/ps/sea12.1.pdf for more details.
func NewBitVector ¶
NewBitVector creates a new BitVector.
func (*BitVector) Get ¶
Get returns the uint64 representation of bits starting from index idx given the bit size.
func (*BitVector) Select0 ¶
Select0 returns the index of the ith zero. Panics if i is zero or greater than the number of zeroes. This is slower than Select1 in most cases.
type Options ¶
type Options struct { // Sr is the rank sampling block size. // This represents the number of bits in // each rank sampling block. Default is 1024. Sr int // Ss is the select sampling block size. // This represents the number of 1s in each // select sampling block. Default is 8192. Ss int }
Options determines the size of the rank and select sampling block. Lower values translates to faster operations but results in larger size.
func NewOptions ¶
func NewOptions() *Options
NewOptions creates an Options object with default values.