bitarray

Documentation

Index

• func Compare(lhs, rhs BitArray) int
• func EncodingPartsForBitLen(bitLen uint) ([]uint64, uint64)
• func SizesForBitLen(bitLen uint) (uint, uint64)
• type BitArray
  • func And(lhs, rhs BitArray) BitArray
  • func Concat(lhs, rhs BitArray) BitArray
  • func FromEncodingParts(words []uint64, lastBitsUsed uint64) (BitArray, error)
  • func MakeBitArrayFromInt64(bitLen uint, val int64, valWidth uint) BitArray
  • func MakeZeroBitArray(bitLen uint) BitArray
  • func Next(d BitArray) BitArray
  • func Not(d BitArray) BitArray
  • func Or(lhs, rhs BitArray) BitArray
  • func Parse(s string) (res BitArray, err error)
  • func Rand(rng *rand.Rand, bitLen uint) BitArray
  • func Xor(lhs, rhs BitArray) BitArray
  • func (d BitArray) AsInt64(nbits uint) int64
  • func (d BitArray) BitLen() uint
  • func (d BitArray) Clone() BitArray
  • func (d BitArray) EncodingParts() ([]uint64, uint64)
  • func (d BitArray) Format(buf *bytes.Buffer)
  • func (d BitArray) GetBitAtIndex(index int) (int, error)
  • func (d BitArray) IsEmpty() bool
  • func (d BitArray) LeftShiftAny(n int64) BitArray
  • func (d BitArray) SetBitAtIndex(index, toSet int) (BitArray, error)
  • func (d BitArray) Sizeof() uintptr
  • func (d BitArray) String() string
  • func (d BitArray) ToWidth(desiredLen uint) BitArray

Functions

func Compare

func Compare(lhs, rhs BitArray) int

Compare compares two bit arrays. They can have mixed sizes.

func EncodingPartsForBitLen

func EncodingPartsForBitLen(bitLen uint) ([]uint64, uint64)

EncodingPartsForBitLen creates a word backing array and the "last bits used" value given the given total number of bits.

func SizesForBitLen

func SizesForBitLen(bitLen uint) (uint, uint64)

SizesForBitLen computes the number of words and last bits used for the requested bit array size.

Types

type BitArray

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

BitArray implements a bit string of arbitrary length.

This uses a packed encoding (i.e. groups of 64 bits at a time) for memory efficiency and speed of bitwise operations (enables use of full machine registers for comparisons and logical operations), akin to the big.nat type.

There is something fancy needed to handle sorting values properly: the last group of bits must be padded right (start on the MSB) inside its word to compare properly according to pg semantics.

This type is designed for immutable instances. The functions and methods defined below never write to a bit array in-place. Of note, the ToWidth() and Next() functions will share the backing array between their operand and their result in some cases.

For portability, the size of the backing word is guaranteed to be 64 bits.

func And

func And(lhs, rhs BitArray) BitArray

And computes the logical AND of two bit arrays. The caller must ensure they have the same bit size.

func Concat

func Concat(lhs, rhs BitArray) BitArray

Concat concatenates two bit arrays.

func FromEncodingParts

func FromEncodingParts(words []uint64, lastBitsUsed uint64) (BitArray, error)

FromEncodingParts creates a bit array from the encoding parts.

func MakeBitArrayFromInt64

func MakeBitArrayFromInt64(bitLen uint, val int64, valWidth uint) BitArray

MakeBitArrayFromInt64 creates a bit array with the specified size. The bits from the integer are written to the right of the bit array and the sign bit is extended.

func MakeZeroBitArray

func MakeZeroBitArray(bitLen uint) BitArray

MakeZeroBitArray creates a bit array with the specified bit size.

func Next

func Next(d BitArray) BitArray

Next returns the next possible bit array in lexicographic order. The backing array of words is shared if possible.

func Not

func Not(d BitArray) BitArray

Not computes the complement of a bit array.

func Or

func Or(lhs, rhs BitArray) BitArray

Or computes the logical OR of two bit arrays. The caller must ensure they have the same bit size.

func Parse

func Parse(s string) (res BitArray, err error)

Parse parses a bit array from the specified string.

func Rand

func Rand(rng *rand.Rand, bitLen uint) BitArray

Rand generates a random bit array of the specified length.

func Xor

func Xor(lhs, rhs BitArray) BitArray

Xor computes the logical XOR of two bit arrays. The caller must ensure they have the same bit size.

func (BitArray) AsInt64

func (d BitArray) AsInt64(nbits uint) int64

AsInt64 returns the int constituted from the rightmost bits in the bit array.

func (BitArray) BitLen

func (d BitArray) BitLen() uint

BitLen returns the number of bits stored.

func (BitArray) Clone

func (d BitArray) Clone() BitArray

Clone makes a copy of the bit array.

func (BitArray) EncodingParts

func (d BitArray) EncodingParts() ([]uint64, uint64)

EncodingParts retrieves the encoding bits from the bit array. The words are presented in big-endian order, with the leftmost bits of the bitarray (MSB) in the MSB of each word.

func (BitArray) Format

func (d BitArray) Format(buf *bytes.Buffer)

Format prints out the bit array to the buffer.

func (BitArray) GetBitAtIndex

func (d BitArray) GetBitAtIndex(index int) (int, error)

GetBitAtIndex extract bit at given index in the BitArray.

func (BitArray) IsEmpty

func (d BitArray) IsEmpty() bool

IsEmpty returns true iff the array is empty.

func (BitArray) LeftShiftAny

func (d BitArray) LeftShiftAny(n int64) BitArray

LeftShiftAny performs a logical left shift, with a possible negative count. The number of bits to shift can be arbitrarily large (i.e. possibly larger than 64 in absolute value).

func (BitArray) SetBitAtIndex

func (d BitArray) SetBitAtIndex(index, toSet int) (BitArray, error)

SetBitAtIndex returns the BitArray with an updated bit at a given index.

func (BitArray) Sizeof

func (d BitArray) Sizeof() uintptr

Sizeof returns the size in bytes of the bit array and its components.

func (BitArray) String

func (d BitArray) String() string

String implements the fmt.Stringer interface.

func (BitArray) ToWidth

func (d BitArray) ToWidth(desiredLen uint) BitArray

ToWidth resizes the bit array to the specified size. If the specified width is shorter, bits on the right are truncated away. If the specified width is larger, zero bits are added on the right.