bitmap

Documentation

Overview

Package bitmap provides basic bitmap operations. A bitmap uses []uint64 as storage.

Since 0.1.8

Index

• Variables
• func FromStr32(s string, frombit, tobit int32) (int32, uint64)
• func Get(bm []uint64, i int32) uint64
• func Get1(bm []uint64, i int32) uint64
• func Getw(bm []uint64, i int32, w int32) uint64
• func IndexRank64(words []uint64) []int32
• func IndexRank128(words []uint64) []int32
• func IndexSelect32(words []uint64) []int32
• func Join(subs []uint64, size int32) []uint64
• func Of(bitPositions []int32, opts ...int32) []uint64
• func OfMany(subs [][]int32, sizes []int32) []uint64
• func Rank64(words []uint64, rindex []int32, i int32) (int32, int32)
• func Rank128(words []uint64, rindex []int32, i int32) (int32, int32)
• func SafeGet(bm []uint64, i int32) uint64
• func SafeGet1(bm []uint64, i int32) uint64
• func Select32(words []uint64, selectIndex []int32, i int32) (int32, int32)
• func Slice(words []uint64, from, to int32) []uint64
• func ToArray(words []uint64) []int32

Variables

var (
	// Mask are pre-calculated width-indexed bit masks.
	// E.g. Mask[1] is 63 "0" and 1 "1": 000..01 .
	//
	// Since 0.1.9
	Mask [65]uint64

	// RMask are pre-calculated reverse mask of Mask.
	//
	// Since 0.1.9
	RMask [65]uint64

	// MaskUpto are mask with bits set upto i-th bit(include i-th bit).
	// E.g. MaskUpto[1] == Mask[2] == 000..011 .
	//
	// Since 0.1.9
	MaskUpto [64]uint64

	// RMaskUpto are reverse of MaskUpto.
	//
	// Since 0.1.9
	RMaskUpto [64]uint64

	// Bit set i-th bit to 1.
	//
	// Since 0.1.9
	Bit [64]uint64
)

Functions

func FromStr32

func FromStr32(s string, frombit, tobit int32) (int32, uint64)

FromStr32 returns a bit array from string and put them in the least significant "to-from" bits of a uint64. "to-from" must be smaller than or equal 32.

It returns actual number of bits used from the string, and a uint64.

Since 0.1.9

func Get

func Get(bm []uint64, i int32) uint64

Get returns a uint64 with the (i%64)-th bit set.

Since 0.1.9

func Get1

func Get1(bm []uint64, i int32) uint64

Get1 returns a uint64 with the least significant bit set if (i%64)-th bit is set.

Since 0.1.9

func Getw

func Getw(bm []uint64, i int32, w int32) uint64

Getw returns the i-th w-bit word in the least significant w bits of a uint64. "w" must be one of 1, 2, 4, 8, 16, 32 and 64.

Since 0.1.9

func IndexRank64

func IndexRank64(words []uint64) []int32

IndexRank64 creates a rank index for a bitmap. rank(i) is defined as number of "1" upto position i, excluding i.

It returns an index of []int32. Every element in it is rank(i*64)

Since 0.1.8

func IndexRank128

func IndexRank128(words []uint64) []int32

IndexRank128 creates a rank index for a bitmap. rank(i) is defined as number of "1" upto position i, excluding i.

It returns an index of []int32. Every element in it is rank(i*128).

It also adds a last index item if len(words) % 2 == 0, in order to make the distance from any bit to the closest index be less than 64.

Since 0.1.8

func IndexSelect32

func IndexSelect32(words []uint64) []int32

IndexSelect32 creates a index for operation "select" on a bitmap. select(i) returns the position of the i-th "1". E.g.:

bitmap = 100100..
select(bitmap, 0) = 1
select(bitmap, 1) = 3

It returns an index of []int32. An element in it is the value of select(i*32)

Since 0.1.9

func Join

func Join(subs []uint64, size int32) []uint64

Join creates a bitmap from a list of sub-bitmaps. "size" specifies the size of every sub-bitmap. Sub bitmaps must be of equal size.

Since 0.1.9

func Of

func Of(bitPositions []int32, opts ...int32) []uint64

Of creates a bitmap of bits set to 1 at specified positions.

An optional argument n can be provided to make the result bitmap have at least n bits.

Since 0.1.9

func OfMany

func OfMany(subs [][]int32, sizes []int32) []uint64

OfMany creates a bitmap from a list of sub-bitmap bit positions. "sizes" specifies the total bits in every sub-bitmap.

Since 0.1.9

func Rank64

func Rank64(words []uint64, rindex []int32, i int32) (int32, int32)

Rank64 returns the count of 1 up to i excluding i and the bit value at i, with the help of a 64-bit index.

It takes about 2~3 ns/op.

Since 0.1.9

func Rank128

func Rank128(words []uint64, rindex []int32, i int32) (int32, int32)

Rank128 returns the count of 1 up to i excluding i and bit value at i, with the help of a 128-bit index.

It takes about 2~3 ns/op.

Since 0.1.9

func SafeGet

func SafeGet(bm []uint64, i int32) uint64

SafeGet is same as Get() except it return 0 instead of a panic when index out of boundary.

Since 0.1.9

func SafeGet1

func SafeGet1(bm []uint64, i int32) uint64

SafeGet1 is same as Get1() except it return 0 instead of a panic when index out of boundary.

Since 0.1.9

func Select32

func Select32(words []uint64, selectIndex []int32, i int32) (int32, int32)

Select32 returns the indexes of the i-th "1" and the (i+1)-th "1".

Since 0.1.9

func Slice

func Slice(words []uint64, from, to int32) []uint64

Slice returns a new bitmap which is a "slice" of the input bitmap.

Since 0.1.9

func ToArray

func ToArray(words []uint64) []int32

ToArray creates a new slice of int32 containing all of the integers stored in the bitmap in sorted order.

Since 0.1.9