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.NewRoaringBitmap() 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.NewRoaringBitmap() size, 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 ¶
- type IntIterable
- type RoaringBitmap
- func And(x1, x2 *RoaringBitmap) *RoaringBitmap
- func AndNot(x1, x2 *RoaringBitmap) *RoaringBitmap
- func BitmapOf(dat ...uint32) *RoaringBitmap
- func FastAnd(bitmaps ...*RoaringBitmap) *RoaringBitmap
- func FastOr(bitmaps ...*RoaringBitmap) *RoaringBitmap
- func Flip(bm *RoaringBitmap, rangeStart, rangeEnd uint32) *RoaringBitmap
- func FlipInt(bm *RoaringBitmap, rangeStart, rangeEnd int) *RoaringBitmap
- func HeapOr(bitmaps ...*RoaringBitmap) *RoaringBitmap
- func HeapXor(bitmaps ...*RoaringBitmap) *RoaringBitmap
- func NewRoaringBitmap() *RoaringBitmap
- func Or(x1, x2 *RoaringBitmap) *RoaringBitmap
- func Xor(x1, x2 *RoaringBitmap) *RoaringBitmap
- func (rb *RoaringBitmap) Add(x uint32)
- func (rb *RoaringBitmap) AddInt(x int)
- func (rb *RoaringBitmap) AddRange(rangeStart, rangeEnd uint32)
- func (rb *RoaringBitmap) And(x2 *RoaringBitmap)
- func (rb *RoaringBitmap) AndCardinality(x2 *RoaringBitmap) uint64
- func (rb *RoaringBitmap) AndNot(x2 *RoaringBitmap)
- func (rb *RoaringBitmap) CheckedAdd(x uint32) bool
- func (rb *RoaringBitmap) CheckedRemove(x uint32) bool
- func (rb *RoaringBitmap) Clear()
- func (rb *RoaringBitmap) Clone() *RoaringBitmap
- func (rb *RoaringBitmap) Contains(x uint32) bool
- func (rb *RoaringBitmap) ContainsInt(x int) bool
- func (rb *RoaringBitmap) Equals(o interface{}) bool
- func (rb *RoaringBitmap) Flip(rangeStart, rangeEnd uint32)
- func (rb *RoaringBitmap) FlipInt(rangeStart, rangeEnd int)
- func (b *RoaringBitmap) FromBase64(str string) (int, error)
- func (rb *RoaringBitmap) GetCardinality() uint64
- func (rb *RoaringBitmap) GetSerializedSizeInBytes() uint64
- func (rb *RoaringBitmap) GetSizeInBytes() uint64
- func (rb *RoaringBitmap) Intersects(x2 *RoaringBitmap) bool
- func (rb *RoaringBitmap) IsEmpty() bool
- func (rb *RoaringBitmap) Iterator() IntIterable
- func (rb *RoaringBitmap) Or(x2 *RoaringBitmap)
- func (x1 *RoaringBitmap) OrCardinality(x2 *RoaringBitmap) uint64
- func (rb *RoaringBitmap) Rank(x uint32) uint32
- func (b *RoaringBitmap) ReadFrom(stream io.Reader) (int, error)
- func (rb *RoaringBitmap) Remove(x uint32)
- func (rb *RoaringBitmap) RemoveRange(rangeStart, rangeEnd uint32)
- func (rb *RoaringBitmap) Select(x uint32) (uint32, error)
- func (rb *RoaringBitmap) String() string
- func (rb *RoaringBitmap) ToArray() []uint32
- func (b *RoaringBitmap) ToBase64() (string, error)
- func (b *RoaringBitmap) WriteTo(stream io.Writer) (int, error)
- func (rb *RoaringBitmap) Xor(x2 *RoaringBitmap)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type IntIterable ¶
IntIterable allows you to iterate over the values in a RoaringBitmap
type RoaringBitmap ¶
type RoaringBitmap struct {
// contains filtered or unexported fields
}
RoaringBitmap represents a compressed bitmap where you can add integers.
func And ¶
func And(x1, x2 *RoaringBitmap) *RoaringBitmap
And computes the intersection between two bitmaps and returns the result
func AndNot ¶
func AndNot(x1, x2 *RoaringBitmap) *RoaringBitmap
AndNot computes the difference between two bitmaps and returns the result
func BitmapOf ¶
func BitmapOf(dat ...uint32) *RoaringBitmap
BitmapOf generates a new bitmap filled with the specified integer
func FastAnd ¶
func FastAnd(bitmaps ...*RoaringBitmap) *RoaringBitmap
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 ¶
func FastOr(bitmaps ...*RoaringBitmap) *RoaringBitmap
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 ¶
func Flip(bm *RoaringBitmap, rangeStart, rangeEnd uint32) *RoaringBitmap
Flip negates the bits in the given range, 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
func FlipInt ¶
func FlipInt(bm *RoaringBitmap, rangeStart, rangeEnd int) *RoaringBitmap
FlipInt calls Flip after casting the parameters to uint32 (convenience method)
func HeapOr ¶ added in v0.1.1
func HeapOr(bitmaps ...*RoaringBitmap) *RoaringBitmap
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
func HeapXor(bitmaps ...*RoaringBitmap) *RoaringBitmap
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 NewRoaringBitmap ¶
func NewRoaringBitmap() *RoaringBitmap
NewRoaringBitmap creates a new empty RoaringBitmap
func Or ¶
func Or(x1, x2 *RoaringBitmap) *RoaringBitmap
Or computes the union between two bitmaps and returns the result
func Xor ¶
func Xor(x1, x2 *RoaringBitmap) *RoaringBitmap
Xor computes the symmetric difference between two bitmaps and returns the result
func (*RoaringBitmap) AddInt ¶
func (rb *RoaringBitmap) AddInt(x int)
Add the integer x to the bitmap (convenience method: the parameter is casted to uint32 and we call Add)
func (*RoaringBitmap) AddRange ¶
func (rb *RoaringBitmap) AddRange(rangeStart, rangeEnd uint32)
Add the integers in [rangeStart, rangeEnd) to the bitmap
func (*RoaringBitmap) And ¶
func (rb *RoaringBitmap) And(x2 *RoaringBitmap)
And computes the intersection between two bitmaps and stores the result in the current bitmap
func (*RoaringBitmap) AndCardinality ¶
func (rb *RoaringBitmap) AndCardinality(x2 *RoaringBitmap) uint64
AndCardinality returns the cardinality of the intersection between two bitmaps, bitmaps are not modified
func (*RoaringBitmap) AndNot ¶
func (rb *RoaringBitmap) AndNot(x2 *RoaringBitmap)
AndNot computes the difference between two bitmaps and stores the result in the current bitmap
func (*RoaringBitmap) CheckedAdd ¶
func (rb *RoaringBitmap) CheckedAdd(x uint32) bool
Add the integer x to the bitmap and return true if it was added (false if the integer was already present)
func (*RoaringBitmap) CheckedRemove ¶
func (rb *RoaringBitmap) CheckedRemove(x uint32) bool
Remove the integer x from the bitmap and return true if the integer was effectively remove (and false if the integer was not present)
func (*RoaringBitmap) Clear ¶
func (rb *RoaringBitmap) Clear()
Clear removes all content from the RoaringBitmap and frees the memory
func (*RoaringBitmap) Clone ¶
func (rb *RoaringBitmap) Clone() *RoaringBitmap
Clone creates a copy of the RoaringBitmap
func (*RoaringBitmap) Contains ¶
func (rb *RoaringBitmap) Contains(x uint32) bool
Contains returns true if the integer is contained in the bitmap
func (*RoaringBitmap) ContainsInt ¶
func (rb *RoaringBitmap) ContainsInt(x int) bool
Contains 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 (*RoaringBitmap) Equals ¶
func (rb *RoaringBitmap) Equals(o interface{}) bool
Equals returns true if the two bitmaps contain the same integers
func (*RoaringBitmap) Flip ¶
func (rb *RoaringBitmap) Flip(rangeStart, rangeEnd uint32)
Flip negates the bits in the given range, 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
func (*RoaringBitmap) FlipInt ¶
func (rb *RoaringBitmap) FlipInt(rangeStart, rangeEnd int)
FlipInt calls Flip after casting the parameters to uint32 (convenience method)
func (*RoaringBitmap) FromBase64 ¶
func (b *RoaringBitmap) FromBase64(str string) (int, error)
func (*RoaringBitmap) GetCardinality ¶
func (rb *RoaringBitmap) GetCardinality() uint64
GetCardinality returns the number of integers contained in the bitmap
func (*RoaringBitmap) GetSerializedSizeInBytes ¶
func (rb *RoaringBitmap) GetSerializedSizeInBytes() uint64
GetSerializedSizeInBytes computes the serialized size in bytes the RoaringBitmap. It should correspond to the number of bytes written when invoking WriteTo
func (*RoaringBitmap) GetSizeInBytes ¶
func (rb *RoaringBitmap) GetSizeInBytes() uint64
GetSizeInBytes estimates the memory usage of the RoaringBitmap. Note that this might differ slightly from the amount of bytes required for persistent storage
func (*RoaringBitmap) Intersects ¶
func (rb *RoaringBitmap) Intersects(x2 *RoaringBitmap) bool
Intersects checks whether two bitmap intersects, bitmaps are not modified
func (*RoaringBitmap) IsEmpty ¶
func (rb *RoaringBitmap) IsEmpty() bool
IsEmpty returns true if the RoaringBitmap is empty (it is faster than doing (GetCardinality() == 0))
func (*RoaringBitmap) Iterator ¶
func (rb *RoaringBitmap) Iterator() IntIterable
Iterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order
func (*RoaringBitmap) Or ¶
func (rb *RoaringBitmap) Or(x2 *RoaringBitmap)
Or computes the union between two bitmaps and stores the result in the current bitmap
func (*RoaringBitmap) OrCardinality ¶
func (x1 *RoaringBitmap) OrCardinality(x2 *RoaringBitmap) uint64
OrCardinality returns the cardinality of the union between two bitmaps, bitmaps are not modified
func (*RoaringBitmap) Rank ¶
func (rb *RoaringBitmap) Rank(x uint32) uint32
Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality())
func (*RoaringBitmap) ReadFrom ¶
func (b *RoaringBitmap) ReadFrom(stream io.Reader) (int, error)
Read a serialized version of this bitmap from stream
func (*RoaringBitmap) Remove ¶
func (rb *RoaringBitmap) Remove(x uint32)
Remove the integer x from the bitmap
func (*RoaringBitmap) RemoveRange ¶
func (rb *RoaringBitmap) RemoveRange(rangeStart, rangeEnd uint32)
Remove the integers in [rangeStart, rangeEnd) from the bitmap
func (*RoaringBitmap) Select ¶
func (rb *RoaringBitmap) Select(x uint32) (uint32, error)
Select returns the xth integer in the bitmap
func (*RoaringBitmap) String ¶
func (rb *RoaringBitmap) String() string
String creates a string representation of the RoaringBitmap
func (*RoaringBitmap) ToArray ¶
func (rb *RoaringBitmap) ToArray() []uint32
ToArray creates a new slice containing all of the integers stored in the RoaringBitmap in sorted order
func (*RoaringBitmap) ToBase64 ¶
func (b *RoaringBitmap) ToBase64() (string, error)
func (*RoaringBitmap) WriteTo ¶
func (b *RoaringBitmap) WriteTo(stream io.Writer) (int, error)
Write out a serialized version of this bitmap to stream
func (*RoaringBitmap) Xor ¶
func (rb *RoaringBitmap) Xor(x2 *RoaringBitmap)
Xor computes the symmetric difference between two bitmaps and stores the result in the current bitmap