Documentation
¶
Overview ¶
Package bitarray implements a bit array. Useful for tracking bool type values in a space efficient way. This is *NOT* a threadsafe package.
Package bitarray or bitmap is useful when comparing large amounts of structured data if the data can be represented as integers. For instance, set intersection of {1, 3, 5} and {3, 5, 7} represented as bitarrays can be done in a single clock cycle (not counting the time it takes to convert) the resultant array back into integers). When Go implements a command to get trailing zeroes, the reconversion back into integers should be much faster.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type BitArray ¶
type BitArray interface {
// SetBit sets the bit at the given position. This
// function returns an error if the position is out
// of range. A sparse bit array never returns an error.
SetBit(k uint64) error
// GetBit gets the bit at the given position. This
// function returns an error if the position is out
// of range. A sparse bit array never returns an error.
GetBit(k uint64) (bool, error)
// ClearBit clears the bit at the given position. This
// function returns an error if the position is out
// of range. A sparse bit array never returns an error.
ClearBit(k uint64) error
// Reset sets all values to zero.
Reset()
// Blocks returns an iterator to be used to iterate
// over the bit array.
Blocks() Iterator
// Equals returns a bool indicating equality between the
// two bit arrays.
Equals(other BitArray) bool
// Intersects returns a bool indicating if the other bit
// array intersects with this bit array.
Intersects(other BitArray) bool
// Capacity returns either the given capacity of the bit array
// in the case of a dense bit array or the highest possible
// seen capacity of the sparse array.
Capacity() uint64
// Or will bitwise or the two bitarrays and return a new bitarray
// representing the result.
Or(other BitArray) BitArray
// And will bitwise and the two bitarrays and return a new bitarray
// representing the result.
And(other BitArray) BitArray
// ToNums converts this bit array to the list of numbers contained
// within it.
ToNums() []uint64
}
BitArray represents a structure that can be used to quickly check for existence when using a large number of items in a very memory efficient way.
func NewBitArray ¶
NewBitArray returns a new BitArray at the specified size. The optional arg denotes whether this bitarray should be set to the bitwise complement of the empty array, ie. sets all bits.
func NewSparseBitArray ¶
func NewSparseBitArray() BitArray
NewSparseBitArray will create a bit array that consumes a great deal less memory at the expense of longer sets and gets.
type Iterator ¶
type Iterator interface {
// Next moves the pointer to the next block. Returns
// false when no blocks remain.
Next() bool
// Value returns the next block and its index
Value() (uint64, block)
}
Iterator defines methods used to iterate over a bit array.
type OutOfRangeError ¶
type OutOfRangeError uint64
OutOfRangeError is an error caused by trying to access a bitarray past the end of its capacity.
func (OutOfRangeError) Error ¶
func (err OutOfRangeError) Error() string
Error returns a human readable description of the out-of-range error.
Source Files