README
¶
Bitvector library written in go
This library contains a simple bitvector implementation. Additionaly there are methods for efficient rank queries and naive select queries.
Complexity
| Time (Query) | Time (Construction) | Space | |
|---|---|---|---|
| Bitvector | O(1) | O(n) | o(n) |
| Rank.Rank0 | O(1) | O(n) | o(n) |
| Rank.Rank1 | O(1) | O(n) | o(n) |
| Rank0Once | O(n) | - | - |
| Rank1Once | O(n) | - | - |
| Select0Once | O(n) | - | - |
| Select1Once | O(n) | - | - |
Example
package main
import (
"fmt"
"github.com/Atgoogat/bitvector"
)
func main() {
bv := bitvector.NewBitvector(10)
for i := 0; i < 10; i += 2 {
bv.Set(i) // set every second bit
}
rank := bitvector.NewRank(bv)
for i := 0; i <= 10; i += 1 {
fmt.Println(rank.Rank0(i))
}
}
// Output:
// 0
// 0
// 1
// 1
// 2
// 2
// 3
// 3
// 4
// 4
// 5
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Rank0Once ¶
func Rank0Once(bv ReadonlyBitvector, index int) int
Return how many zeros there are before index. For index = 0 => 0 Complexity: O(n) (n = index) Consider using Rank.Rank0 if you do multiple requests
func Rank1Once ¶
func Rank1Once(bv ReadonlyBitvector, index int) int
Return how many ones there are before index. For index = 0 => 0 Complexity: O(n) (n = index) Consider using Rank.Rank1 if you do multiple requests
func Select0Once ¶
func Select0Once(bv ReadonlyBitvector, ith int) (index int)
Return the index where the ith-zero is. When there is not ith-zero bv.Len() will be returned. Complexity: O(n)
func Select1Once ¶
func Select1Once(bv ReadonlyBitvector, ith int) (index int)
Return the index where the ith-one is. When there is not ith-one bv.Len() will be returned. Complexity: O(n)
Types ¶
type Bitvector ¶
type Bitvector struct {
// contains filtered or unexported fields
}
type Rank ¶
type Rank struct {
// contains filtered or unexported fields
}
Datastructure to allow for fast rank queries
func NewRank ¶
func NewRank(bv ReadonlyBitvector) Rank
Build rank datastructure for this bitvector
Caution: Any changes to the underlying bitvector lead to undefined behaviour regarding the rank queries Complexity: O(n) (n == bv.Len())
Source Files
Directories