rrr

README

rrr

rrr implements compressed bitvectors supporting rank and select

References

• Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti: Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets

Documentation

Index

• type RRR
  • func NewFromBitVector(uncompressed *bv.BV) (*RRR, error)
  • func NewFromSerialized(buf []byte) (r *RRR, lengthBytes int, err error)
  • func (r *RRR) Access(i uint64) bool
  • func (r *RRR) Rank0(i uint64) uint64
  • func (r *RRR) Rank1(i uint64) uint64
  • func (r *RRR) Select0(i uint64) uint64
  • func (r *RRR) Select1(i uint64) uint64
  • func (r *RRR) Size() int
  • func (r *RRR) SizeInBytes() uint64
  • func (r *RRR) Uncompress() *bv.BV
  • func (r *RRR) WriteTo(w io.Writer) (err error)

Types

type RRR

type RRR struct {
	// contains filtered or unexported fields
}

RRR is a static compressed bit vector represented as

Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

func NewFromBitVector

func NewFromBitVector(uncompressed *bv.BV) (*RRR, error)

NewFromBitVector builds a compressed bitvector from the bits in bv

func NewFromSerialized

func NewFromSerialized(buf []byte) (r *RRR, lengthBytes int, err error)

NewFromSerialized returns a RRR value which was serialized via WriteTo

func (*RRR) Access

func (r *RRR) Access(i uint64) bool

Access returns true if i is set

func (*RRR) Rank0

func (r *RRR) Rank0(i uint64) uint64

Rank0 returns the number of set bits up-to and including the ith bit.

func (*RRR) Rank1

func (r *RRR) Rank1(i uint64) uint64

Rank1 returns the number of set bits up-to and including the ith bit.

func (*RRR) Select0

func (r *RRR) Select0(i uint64) uint64

Select0 returns the number of index of the ith unset bit. TODO verify correctness

func (*RRR) Select1

func (r *RRR) Select1(i uint64) uint64

Select1 returns the number of index of the ith set bit.

func (*RRR) Size

func (r *RRR) Size() int

Size returns the number of bits in r

func (*RRR) SizeInBytes

func (r *RRR) SizeInBytes() uint64

SizeInBytes returns the size of r if it was serialized.

func (*RRR) Uncompress

func (r *RRR) Uncompress() *bv.BV

Uncompress returns an uncompressed bit vector

func (*RRR) WriteTo

func (r *RRR) WriteTo(w io.Writer) (err error)

WriteTo serializes RRR to w