bitmap

package
v0.1.21 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 27, 2021 License: MIT Imports: 4 Imported by: 18

README

bitmap - bitmap operation creation, query, rank/select impl

A bitmap is a []uint64.

BenchmarkFromStr32-4                  147230166                8.07 ns/op
BenchmarkStringToBytes-4              201391240                5.95 ns/op
BenchmarkNextOne/FoundInCurrentWord-4 334609323                3.56 ns/op
BenchmarkNextOne/EnumerateAllBits-4   294496100                4.03 ns/op
BenchmarkPrevOne/FoundInCurrentWord-4 334022793                3.59 ns/op
BenchmarkPrevOne/EnumerateAllBits-4   286702246                4.12 ns/op
BenchmarkRank64_5_bits-4              672754074                1.77 ns/op
BenchmarkRank128_5_bits-4             486679581                2.49 ns/op
BenchmarkRank64_64k_bits-4            881509602                1.35 ns/op
BenchmarkRank128_64k_bits-4           424685930                2.84 ns/op
BenchmarkSelect-4                     70999674                16.1 ns/op
BenchmarkSelect32-4                   141631495                8.54 ns/op
BenchmarkSelect32R64-4                153702387                7.85 ns/op
BenchmarkSelectU64Indexed-4           365140676                3.29 ns/op

Documentation

Overview

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

Since 0.1.8

Index

Constants

This section is empty.

Variables

View Source 
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 Fmt added in v0.1.11 

func Fmt(x interface{}) string

Fmt converts bitmap in an integer or in a slice of integer to binary format string, with significant bits at right. E.g.: 

int32(0x0102) --> 01000000 10000000

Since 0.1.11

func FromStr32 added in v0.1.9 

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 added in v0.1.9 

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

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

Since 0.1.9

func Get1 added in v0.1.9 

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 added in v0.1.9 

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 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 IndexRank64 

func IndexRank64(words []uint64, opts ...bool) []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.11 An optional bool specifies whether to add a last index entry of count of all "1".

Since 0.1.8

func IndexSelect32 added in v0.1.9 

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 IndexSelect32R64 added in v0.1.13 

func IndexSelect32R64(words []uint64) ([]int32, []int32)

IndexSelect32R64 creates indexes 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 a select index in []int32 and an index of Rank64.

Since 0.1.13

func Join added in v0.1.9 

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 NextOne added in v0.1.12 

func NextOne(bm []uint64, i, end int32) int32

NextOne find the next "1" in range `[i, end)`. If there is no "1" found, it returns `end`.

Since 0.1.11

func Of added in v0.1.9 

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 added in v0.1.9 

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 PrevOne added in v0.1.12 

func PrevOne(bm []uint64, i, end int32) int32

PrevOne find the previous "1" in range `[i, end)` If there is no "1" found, it returns -1.

Since 0.1.11

func Rank128 added in v0.1.9 

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. Rank128 is about 50% slower than Rank64

Since 0.1.9

func Rank64 added in v0.1.9 

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 SafeGet added in v0.1.9 

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 added in v0.1.9 

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 added in v0.1.9 

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 Select32R64 added in v0.1.13 

func Select32R64(words []uint64, selectIndex, rankIndex []int32, i int32) (int32, int32)

Select32R64 returns the indexes of the i-th "1" and the (i+1)-th "1". It requires a Rank64 index for speeding up and a Select32 index

Since 0.1.13

func Slice added in v0.1.9 

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 added in v0.1.9 

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

Types

type Builder added in v0.1.19 

type Builder struct {
	Words  []uint64
	Offset int32
}

Builder provides continous bitmap building.

Since 0.1.19

func NewBuilder added in v0.1.19 

func NewBuilder(n int32) *Builder

NewBuilder creates a new Builder with preallocated n bits.

Since 0.1.19

func (*Builder) Extend added in v0.1.19 

func (b *Builder) Extend(bitPositions []int32, size int32)

Extend add bits into builder, the bit position are relative to current Builder.Offset and the size in bit of the bitmap is size.

Since 0.1.19

func (*Builder) Set added in v0.1.19 

func (b *Builder) Set(bitPosition int32, value int32)

Set a bit to `value` in the bitmap builder. Builder.Offset is updated to the last set bit if it is smaller.

Since 0.1.19

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.