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 bitmap contains bitmaps of length 32 and 64 for tracking bool values without the need for arrays or hashing.

    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

    func Marshal

    func Marshal(ba BitArray) ([]byte, error)

      Marshal takes a dense or sparse bit array and serializes it to a byte slice.

      func Uint64FromBytes

      func Uint64FromBytes(b []byte) (uint64, int)

        This function is a copy from the binary package, with some added error checking to avoid panics. The function will return the value, and the number of bytes read from the buffer. If the number of bytes is negative, then not enough bytes were passed in and the return value will be zero.

        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
        	// Nand will bitwise nand the two bitarrays and return a new bitarray
        	// representing the result.
        	Nand(other BitArray) BitArray
        	// ToNums converts this bit array to the list of numbers contained
        	// within it.
        	ToNums() []uint64
        	// IsEmpty checks to see if any values are set on the bitarray
        	IsEmpty() bool
        }

          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

          func NewBitArray(size uint64, args ...bool) BitArray

            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.

              func Unmarshal

              func Unmarshal(input []byte) (BitArray, error)

                Unmarshal takes a byte slice, of the same format produced by Marshal, and returns a BitArray.

                type Bitmap32

                type Bitmap32 uint32

                  Bitmap32 tracks 32 bool values within a uint32

                  func (Bitmap32) ClearBit

                  func (b Bitmap32) ClearBit(pos uint) Bitmap32

                    ClearBit returns a Bitmap32 with the bit at the given position set to 0

                    func (Bitmap32) GetBit

                    func (b Bitmap32) GetBit(pos uint) bool

                      GetBit returns true if the bit at the given position in the Bitmap32 is 1

                      func (Bitmap32) PopCount

                      func (b Bitmap32) PopCount() int

                        PopCount returns the amount of bits set to 1 in the Bitmap32

                        func (Bitmap32) SetBit

                        func (b Bitmap32) SetBit(pos uint) Bitmap32

                          SetBit returns a Bitmap32 with the bit at the given position set to 1

                          type Bitmap64

                          type Bitmap64 uint64

                            Bitmap64 tracks 64 bool values within a uint64

                            func (Bitmap64) ClearBit

                            func (b Bitmap64) ClearBit(pos uint) Bitmap64

                              ClearBit returns a Bitmap64 with the bit at the given position set to 0

                              func (Bitmap64) GetBit

                              func (b Bitmap64) GetBit(pos uint) bool

                                GetBit returns true if the bit at the given position in the Bitmap64 is 1

                                func (Bitmap64) PopCount

                                func (b Bitmap64) PopCount() int

                                  PopCount returns the amount of bits set to 1 in the Bitmap64

                                  func (Bitmap64) SetBit

                                  func (b Bitmap64) SetBit(pos uint) Bitmap64

                                    SetBit returns a Bitmap64 with the bit at the given position set to 1

                                    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.