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) GetCopyOnWrite() (val bool)
- 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) MarshalBinary() ([]byte, error)
- 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) SetCopyOnWrite(val bool)
- func (rb *Bitmap) String() string
- func (rb *Bitmap) ToArray() []uint32
- func (rb *Bitmap) ToBase64() (string, error)
- func (rb *Bitmap) UnmarshalBinary(data []byte) 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 ¶
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 ¶
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 ¶
HeapOr computes the union between many bitmaps quickly using a heap. It might be faster than calling Or repeatedly.
func HeapXor ¶
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 ¶
AddInt adds the integer x to the bitmap (convenience method: the parameter is casted to uint32 and we call Add)
func (*Bitmap) AddRange ¶
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 ¶
And computes the intersection between two bitmaps and stores the result in the current bitmap
func (*Bitmap) AndCardinality ¶
AndCardinality returns the cardinality of the intersection between two bitmaps, bitmaps are not modified
func (*Bitmap) AndNot ¶
AndNot computes the difference between two bitmaps and stores the result in the current bitmap
func (*Bitmap) CheckedAdd ¶
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 ¶
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 ¶
func (rb *Bitmap) Clear()
Clear removes all content from the Bitmap and frees the memory
func (*Bitmap) ContainsInt ¶
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) 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. 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) FromBase64 ¶
FromBase64 deserializes a bitmap from Base64
func (*Bitmap) GetCardinality ¶
GetCardinality returns the number of integers contained in the bitmap
func (*Bitmap) GetCopyOnWrite ¶
GetCopyOnWrite gets this bitmap's copy-on-write property
func (*Bitmap) GetSerializedSizeInBytes ¶
GetSerializedSizeInBytes computes the serialized size in bytes the Bitmap. It should correspond to the number of bytes written when invoking WriteTo
func (*Bitmap) GetSizeInBytes ¶
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 ¶
Intersects checks whether two bitmap intersects, bitmaps are not modified
func (*Bitmap) IsEmpty ¶
IsEmpty returns true if the Bitmap is empty (it is faster than doing (GetCardinality() == 0))
func (*Bitmap) Iterator ¶
func (rb *Bitmap) Iterator() IntIterable
Iterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order
func (*Bitmap) MarshalBinary ¶
MarshalBinary implements the encoding.BinaryMarshaler interface for the bitmap
func (*Bitmap) Or ¶
Or computes the union between two bitmaps and stores the result in the current bitmap
func (*Bitmap) OrCardinality ¶
OrCardinality returns the cardinality of the union between two bitmaps, bitmaps are not modified
func (*Bitmap) Rank ¶
Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality())
func (*Bitmap) RemoveRange ¶
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) SetCopyOnWrite ¶
SetCopyOnWrite sets this bitmap to use copy-on-write so that copies are fast and memory conscious if the parameter is true, otherwise we leave the default where hard copies are made (copy-on-write requires extra care in a threaded context).
func (*Bitmap) ToArray ¶
ToArray creates a new slice containing all of the integers stored in the Bitmap in sorted order
func (*Bitmap) UnmarshalBinary ¶
UnmarshalBinary implements the encoding.BinaryUnmarshaler interface for the bitmap
type IntIterable ¶
IntIterable allows you to iterate over the values in a Bitmap