bitset

Documentation

Index

• type Bitset
  • func Deserialize(data []byte) (*Bitset, error)
  • func NewBitset(size int) *Bitset
  • func (b *Bitset) Copy() *Bitset
  • func (b *Bitset) Count() int
  • func (b *Bitset) Deb() []uint64
  • func (b *Bitset) Fill() *Bitset
  • func (b *Bitset) Full() bool
  • func (b *Bitset) Get(x uint64) bool
  • func (b *Bitset) Intersect(a *Bitset) *Bitset
  • func (b *Bitset) Overlap(ranges []uint16) []uint16
  • func (b *Bitset) Print() string
  • func (b *Bitset) Ranges() []uint16
  • func (b *Bitset) Serialize() []byte
  • func (b *Bitset) Set(x uint64) *Bitset
  • func (b *Bitset) Size() int
  • func (b *Bitset) UnfilledItems(count int) []uint16
  • func (b *Bitset) UnfilledRanges() []common.Range
  • func (b *Bitset) Union(a *Bitset) *Bitset
  • func (b *Bitset) Unset(x uint64) *Bitset

Types

type Bitset

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

Bitset is simple bitset backed by a []uint64. The size of the bitset is unbounded and it will grow as required to support any Set() operations invoked. Bitset provides no compression.

func Deserialize

func Deserialize(data []byte) (*Bitset, error)

Deserialize converts a previously-serialized bitset into a realized bitset.

func NewBitset

func NewBitset(size int) *Bitset

NewBitset returns a new bitset of the specified size. Panics if size < 0. Providing a size is convenient for serialization, but not necessary. Get() and Set() operations work as described.

func (*Bitset) Copy

func (b *Bitset) Copy() *Bitset

Copy returns a copy of the bitset. Mutating the copy will not affect the original

func (*Bitset) Count

func (b *Bitset) Count() int

Count returns the number of elements in the bitset that are set (true)

func (*Bitset) Deb

func (b *Bitset) Deb() []uint64

func (*Bitset) Fill

func (b *Bitset) Fill() *Bitset

Fill sets all items between 0:size to true. Returns itself for syntactic convenience

func (*Bitset) Full

func (b *Bitset) Full() bool

Full returns true if all items between 0:size are set to true, and false if not.

func (*Bitset) Get

func (b *Bitset) Get(x uint64) bool

Get returns true if the specified index has been previously set and never subsequently unset. Safely false if the specified index is out of bounds.

func (*Bitset) Intersect

func (b *Bitset) Intersect(a *Bitset) *Bitset

Intersect returns the intersect between any two bitsets

func (*Bitset) Overlap

func (b *Bitset) Overlap(ranges []uint16) []uint16

Overlap takes a sorted list of ranges ([]uint16 of even length) where each consecutive pair of numbers represents an inclusive range [start, end] of bits. The return value is a sorted list of non-overallping ranges that are set to 'on' within the underlying bitset

func (*Bitset) Print

func (b *Bitset) Print() string

Print returns a 0/1-formatted string representation of the underlying bitset

func (*Bitset) Ranges

func (b *Bitset) Ranges() []uint16

Ranges returns a sorted, non-overallping list of ranges of the underlying bitset that are set to true.

func (*Bitset) Serialize

func (b *Bitset) Serialize() []byte

Serialize converts the bitset into a []byte so it can be transmitted somewhere. It makes a copy of its underlying data, but is not threadsafe. If race conditions are possible it is the caller's responsibility to maintain exclusivity.

func (*Bitset) Set

func (b *Bitset) Set(x uint64) *Bitset

Set sets the specified index to true. If the specified index is out of bounds, the bitset expands to incorporate the given index. The bitset will never shrink once expanded.

func (*Bitset) Size

func (b *Bitset) Size() int

Size returns the number of elements in the bitset, both set and unset. Size is always non-negative

func (*Bitset) UnfilledItems

func (b *Bitset) UnfilledItems(count int) []uint16

UnfilledItems returns the first `count` items in the bitset that are set to false. If there are fewer than `count` items it returns that many. TODO: this is super gross and inefficient... do something better

func (*Bitset) UnfilledRanges

func (b *Bitset) UnfilledRanges() []common.Range

UnfilledRanges returns a sorted, non-overlapping list of ranges of the underlying bitset that are set to false.

func (*Bitset) Union

func (b *Bitset) Union(a *Bitset) *Bitset

Union returns the union between any two bitsets

func (*Bitset) Unset

func (b *Bitset) Unset(x uint64) *Bitset

Unset sets the specified index to False. If the specified index is out of bounds, nothing happens. Does not cause size to shrink. Returns itself