Documentation ¶
Overview ¶
Package roaring is an implementation of Roaring Bitmaps in Go. They provide fast compressed bitmap data structures (also called bitset). They are ideally suited to represent sets of integers over relatively small ranges. See http://roaringbitmap.org for details.
Example (Roaring) ¶
Example_roaring demonstrates how to use the roaring library.
package main import ( "bytes" "fmt" "github.com/RoaringBitmap/roaring" ) func main() { // example inspired by https://github.com/fzandona/goroar fmt.Println("==roaring==") rb1 := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000) fmt.Println(rb1.String()) rb2 := roaring.BitmapOf(3, 4, 1000) fmt.Println(rb2.String()) rb3 := roaring.NewBitmap() fmt.Println(rb3.String()) fmt.Println("Cardinality: ", rb1.GetCardinality()) fmt.Println("Contains 3? ", rb1.Contains(3)) rb1.And(rb2) rb3.Add(1) rb3.Add(5) rb3.Or(rb1) // prints 1, 3, 4, 5, 1000 i := rb3.Iterator() for i.HasNext() { fmt.Println(i.Next()) } fmt.Println() // next we include an example of serialization buf := new(bytes.Buffer) size, err := rb1.WriteTo(buf) if err != nil { fmt.Println("Failed writing") return } else { fmt.Println("Wrote ", size, " bytes") } newrb := roaring.NewBitmap() _, err = newrb.ReadFrom(buf) if err != nil { fmt.Println("Failed reading") return } if !rb1.Equals(newrb) { fmt.Println("I did not get back to original bitmap?") return } else { fmt.Println("I wrote the content to a byte stream and read it back.") } }
Output:
Index ¶
- func BoundSerializedSizeInBytes(cardinality uint64, universeSize uint64) uint64
- type Bitmap
- func And(x1, x2 *Bitmap) *Bitmap
- func AndNot(x1, x2 *Bitmap) *Bitmap
- func BitmapOf(dat ...uint32) *Bitmap
- func FastAnd(bitmaps ...*Bitmap) *Bitmap
- func FastOr(bitmaps ...*Bitmap) *Bitmap
- func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap
- func FlipInt(bm *Bitmap, rangeStart, rangeEnd int) *Bitmap
- func HeapOr(bitmaps ...*Bitmap) *Bitmap
- func HeapXor(bitmaps ...*Bitmap) *Bitmap
- func NewBitmap() *Bitmap
- func Or(x1, x2 *Bitmap) *Bitmap
- func Xor(x1, x2 *Bitmap) *Bitmap
- func (rb *Bitmap) Add(x uint32)
- func (rb *Bitmap) AddInt(x int)
- func (rb *Bitmap) AddRange(rangeStart, rangeEnd uint64)
- func (rb *Bitmap) And(x2 *Bitmap)
- func (rb *Bitmap) AndCardinality(x2 *Bitmap) uint64
- func (rb *Bitmap) AndNot(x2 *Bitmap)
- func (rb *Bitmap) CheckedAdd(x uint32) bool
- func (rb *Bitmap) CheckedRemove(x uint32) bool
- func (rb *Bitmap) Clear()
- func (rb *Bitmap) Clone() *Bitmap
- func (rb *Bitmap) Contains(x uint32) bool
- func (rb *Bitmap) ContainsInt(x int) bool
- func (rb *Bitmap) Equals(o interface{}) bool
- func (rb *Bitmap) Flip(rangeStart, rangeEnd uint64)
- func (rb *Bitmap) FlipInt(rangeStart, rangeEnd int)
- func (rb *Bitmap) FromBase64(str string) (int64, error)
- func (rb *Bitmap) GetCardinality() uint64
- func (rb *Bitmap) GetSerializedSizeInBytes() uint64
- func (rb *Bitmap) GetSizeInBytes() uint64
- func (rb *Bitmap) Intersects(x2 *Bitmap) bool
- func (rb *Bitmap) IsEmpty() bool
- func (rb *Bitmap) Iterator() IntIterable
- func (rb *Bitmap) Or(x2 *Bitmap)
- func (rb *Bitmap) OrCardinality(x2 *Bitmap) uint64
- func (rb *Bitmap) Rank(x uint32) uint64
- func (rb *Bitmap) ReadFrom(stream io.Reader) (int64, error)
- func (rb *Bitmap) Remove(x uint32)
- func (rb *Bitmap) RemoveRange(rangeStart, rangeEnd uint64)
- func (rb *Bitmap) Select(x uint32) (uint32, error)
- func (rb *Bitmap) String() string
- func (rb *Bitmap) ToArray() []uint32
- func (rb *Bitmap) ToBase64() (string, error)
- func (rb *Bitmap) WriteTo(stream io.Writer) (int64, error)
- func (rb *Bitmap) Xor(x2 *Bitmap)
- type IntIterable
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BoundSerializedSizeInBytes ¶ added in v0.2.1
BoundSerializedSizeInBytes returns an upper bound on the serialized size in bytes assuming that one wants to store "cardinality" integers in [0, universe_size)
Types ¶
type Bitmap ¶ added in v0.2.0
type Bitmap struct {
// contains filtered or unexported fields
}
Bitmap represents a compressed bitmap where you can add integers.
func FastAnd ¶
FastAnd computes the intersection between many bitmaps quickly Compared to the And function, it can take many bitmaps as input, thus saving the trouble of manually calling "And" many times.
func FastOr ¶
FastOr computes the union between many bitmaps quickly, as opposed to having to call Or repeatedly. It might also be faster than calling Or repeatedly.
func Flip ¶
Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed, and any integer present in the range and not in the bitmap is added, a new bitmap is returned leaving the current bitmap unchanged. The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range while uint64(0x100000000) cannot be represented as a 32-bit value.
func HeapOr ¶ added in v0.1.1
HeapOr computes the union between many bitmaps quickly using a heap. It might be faster than calling Or repeatedly.
func HeapXor ¶ added in v0.1.1
HeapXor computes the symmetric difference between many bitmaps quickly (as opposed to calling Xor repeated). Internally, this function uses a heap. It might be faster than calling Xor repeatedly.
func (*Bitmap) AddInt ¶ added in v0.2.0
AddInt adds the integer x to the bitmap (convenience method: the parameter is casted to uint32 and we call Add)
func (*Bitmap) AddRange ¶ added in v0.2.0
AddRange adds the integers in [rangeStart, rangeEnd) to the bitmap. The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range while uint64(0x100000000) cannot be represented as a 32-bit value.
func (*Bitmap) And ¶ added in v0.2.0
And computes the intersection between two bitmaps and stores the result in the current bitmap
func (*Bitmap) AndCardinality ¶ added in v0.2.0
AndCardinality returns the cardinality of the intersection between two bitmaps, bitmaps are not modified
func (*Bitmap) AndNot ¶ added in v0.2.0
AndNot computes the difference between two bitmaps and stores the result in the current bitmap
func (*Bitmap) CheckedAdd ¶ added in v0.2.0
CheckedAdd adds the integer x to the bitmap and return true if it was added (false if the integer was already present)
func (*Bitmap) CheckedRemove ¶ added in v0.2.0
CheckedRemove removes the integer x from the bitmap and return true if the integer was effectively remove (and false if the integer was not present)
func (*Bitmap) Clear ¶ added in v0.2.0
func (rb *Bitmap) Clear()
Clear removes all content from the Bitmap and frees the memory
func (*Bitmap) Contains ¶ added in v0.2.0
Contains returns true if the integer is contained in the bitmap
func (*Bitmap) ContainsInt ¶ added in v0.2.0
ContainsInt returns true if the integer is contained in the bitmap (this is a convenience method, the parameter is casted to uint32 and Contains is called)
func (*Bitmap) Equals ¶ added in v0.2.0
Equals returns true if the two bitmaps contain the same integers
func (*Bitmap) Flip ¶ added in v0.2.0
Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed, and any integer present in the range and not in the bitmap is added. The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range while uint64(0x100000000) cannot be represented as a 32-bit value.
func (*Bitmap) FlipInt ¶ added in v0.2.0
FlipInt calls Flip after casting the parameters (convenience method)
func (*Bitmap) FromBase64 ¶ added in v0.2.0
FromBase64 deserializes a bitmap from Base64
func (*Bitmap) GetCardinality ¶ added in v0.2.0
GetCardinality returns the number of integers contained in the bitmap
func (*Bitmap) GetSerializedSizeInBytes ¶ added in v0.2.0
GetSerializedSizeInBytes computes the serialized size in bytes the Bitmap. It should correspond to the number of bytes written when invoking WriteTo
func (*Bitmap) GetSizeInBytes ¶ added in v0.2.0
GetSizeInBytes estimates the memory usage of the Bitmap. Note that this might differ slightly from the amount of bytes required for persistent storage
func (*Bitmap) Intersects ¶ added in v0.2.0
Intersects checks whether two bitmap intersects, bitmaps are not modified
func (*Bitmap) IsEmpty ¶ added in v0.2.0
IsEmpty returns true if the Bitmap is empty (it is faster than doing (GetCardinality() == 0))
func (*Bitmap) Iterator ¶ added in v0.2.0
func (rb *Bitmap) Iterator() IntIterable
Iterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order
func (*Bitmap) Or ¶ added in v0.2.0
Or computes the union between two bitmaps and stores the result in the current bitmap
func (*Bitmap) OrCardinality ¶ added in v0.2.0
OrCardinality returns the cardinality of the union between two bitmaps, bitmaps are not modified
func (*Bitmap) Rank ¶ added in v0.2.0
Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality())
func (*Bitmap) ReadFrom ¶ added in v0.2.0
ReadFrom reads a serialized version of this bitmap from stream
func (*Bitmap) RemoveRange ¶ added in v0.2.0
RemoveRange removes the integers in [rangeStart, rangeEnd) from the bitmap. The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range while uint64(0x100000000) cannot be represented as a 32-bit value.
func (*Bitmap) ToArray ¶ added in v0.2.0
ToArray creates a new slice containing all of the integers stored in the Bitmap in sorted order
type IntIterable ¶
IntIterable allows you to iterate over the values in a Bitmap