org.roaringbitmap

Class FastRankRoaringBitmap

java.lang.Object

org.roaringbitmap.RoaringBitmap

org.roaringbitmap.FastRankRoaringBitmap

All Implemented Interfaces:

Externalizable, Serializable, Cloneable, Iterable<Integer>, BitmapDataProvider, ImmutableBitmapDataProvider

public class FastRankRoaringBitmap
extends RoaringBitmap

This extends RoaringBitmap to provide better performance for .rank and .select operations, at the cost of maintain a cache of cardinalities. On RoaringBitmap.select(int) and RoaringBitmap.rank(int) operations, RoaringBitmap needs to iterate along all underlying buckets to cumulate their cardinalities. This may lead to sub-optimal performance for application doing a large amount of .rank/.select over read-only RoaringBitmap, especially if the RoaringBitmap holds a large number of underlying buckets. This implementation will discard the cache of cardinality on any write operations, and it will memoize the computed cardinalities on any .rank or .select operation

Author:

Benoit Lacelle

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
FastRankRoaringBitmap()

Method Summary

Modifier and Type	Method and Description
void	add(int... dat) Set all the specified values to true.
void	add(int x) Add the value to the container (set the value to "true"), whether it already appears or not.
void	add(int rangeStart, int rangeEnd) Deprecated.
void	add(long rangeStart, long rangeEnd) Add to the current bitmap all integers in [rangeStart,rangeEnd).
void	and(RoaringBitmap x2) In-place bitwise AND (intersection) operation.
void	andNot(RoaringBitmap x2) In-place bitwise ANDNOT (difference) operation.
boolean	checkedAdd(int x) Add the value to the container (set the value to "true"), whether it already appears or not.
boolean	checkedRemove(int x) If present remove the specified integer (effectively, sets its bit value to false)
void	clear() reset to an empty bitmap; result occupies as much space a newly created bitmap.
void	flip(int x) Add the value if it is not already present, otherwise remove it.
void	flip(int rangeStart, int rangeEnd) Deprecated.
void	flip(long rangeStart, long rangeEnd) Modifies the current bitmap by complementing the bits in the given range, from rangeStart (inclusive) rangeEnd (exclusive).
void	or(RoaringBitmap x2) In-place bitwise OR (union) operation.
long	rankLong(int x) Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality()).
void	remove(int x) If present remove the specified integer (effectively, sets its bit value to false)
void	remove(int rangeStart, int rangeEnd) Deprecated.
void	remove(long rangeStart, long rangeEnd) Remove from the current bitmap all integers in [rangeStart,rangeEnd).
int	select(int j) Return the jth value stored in this bitmap.
void	xor(RoaringBitmap x2) In-place bitwise XOR (symmetric difference) operation.

Methods inherited from class org.roaringbitmap.RoaringBitmap

add, add, and, and, and, andCardinality, andNot, andNot, andNot, andNotCardinality, bitmapOf, bitmapOfUnordered, clone, contains, contains, deserialize, equals, first, flip, flip, forEach, getCardinality, getContainerPointer, getIntIterator, getLongCardinality, getLongSizeInBytes, getReverseIntIterator, getSizeInBytes, hashCode, hasRunCompression, intersects, isEmpty, isHammingSimilar, iterator, last, lazyor, lazyor, lazyorfromlazyinputs, limit, maximumSerializedSize, naivelazyor, or, or, or, or, or, orCardinality, rank, readExternal, remove, remove, removeRunCompression, repairAfterLazy, runOptimize, serialize, serializedSizeInBytes, toArray, toMutableRoaringBitmap, toString, trim, writeExternal, xor, xor, xor, xorCardinality

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

FastRankRoaringBitmap

public FastRankRoaringBitmap()

Method Detail

add

public void add(long rangeStart,
                long rangeEnd)

Description copied from class: RoaringBitmap

Add to the current bitmap all integers in [rangeStart,rangeEnd).

Overrides:

add in class RoaringBitmap

Parameters:

rangeStart - inclusive beginning of range

rangeEnd - exclusive ending of range

add

public void add(int x)

Description copied from class: RoaringBitmap

Add the value to the container (set the value to "true"), whether it already appears or not. Javac lacks native unsigned integers but the x argument is considered to be unsigned. Within bitmaps, numbers are ordered according to Integer.compareUnsigned(int, int). We order the numbers like 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1.

Specified by:

add in interface BitmapDataProvider

Overrides:

add in class RoaringBitmap

Parameters:

x - integer value

add

public void add(int... dat)

Description copied from class: RoaringBitmap

Set all the specified values to true. This can be expected to be slightly faster than calling "add" repeatedly. The provided integers values don't have to be in sorted order, but it may be preferable to sort them from a performance point of view.

Overrides:

add in class RoaringBitmap

Parameters:

dat - set values

add

@Deprecated
public void add(int rangeStart,
                            int rangeEnd)

Deprecated.

Description copied from class: RoaringBitmap

Add to the current bitmap all integers in [rangeStart,rangeEnd).

Overrides:

add in class RoaringBitmap

Parameters:

rangeStart - inclusive beginning of range

rangeEnd - exclusive ending of range

clear

public void clear()

Description copied from class: RoaringBitmap

reset to an empty bitmap; result occupies as much space a newly created bitmap.

Overrides:

clear in class RoaringBitmap

flip

public void flip(int x)

Description copied from class: RoaringBitmap

Add the value if it is not already present, otherwise remove it.

Overrides:

flip in class RoaringBitmap

Parameters:

x - integer value

flip

@Deprecated
public void flip(int rangeStart,
                             int rangeEnd)

Deprecated.

Description copied from class: RoaringBitmap

Modifies the current bitmap by complementing the bits in the given range, from rangeStart (inclusive) rangeEnd (exclusive).

Overrides:

flip in class RoaringBitmap

Parameters:

rangeStart - inclusive beginning of range

rangeEnd - exclusive ending of range

flip

public void flip(long rangeStart,
                 long rangeEnd)

Description copied from class: RoaringBitmap

Modifies the current bitmap by complementing the bits in the given range, from rangeStart (inclusive) rangeEnd (exclusive).

Overrides:

flip in class RoaringBitmap

Parameters:

rangeStart - inclusive beginning of range

rangeEnd - exclusive ending of range

and

public void and(RoaringBitmap x2)

Description copied from class: RoaringBitmap

In-place bitwise AND (intersection) operation. The current bitmap is modified.

Overrides:

and in class RoaringBitmap

Parameters:

x2 - other bitmap

andNot

public void andNot(RoaringBitmap x2)

Description copied from class: RoaringBitmap

In-place bitwise ANDNOT (difference) operation. The current bitmap is modified.

Overrides:

andNot in class RoaringBitmap

Parameters:

x2 - other bitmap

remove

@Deprecated
public void remove(int rangeStart,
                               int rangeEnd)

Deprecated.

Description copied from class: RoaringBitmap

Remove from the current bitmap all integers in [rangeStart,rangeEnd).

Overrides:

remove in class RoaringBitmap

Parameters:

rangeStart - inclusive beginning of range

rangeEnd - exclusive ending of range

remove

public void remove(int x)

Description copied from class: RoaringBitmap

If present remove the specified integer (effectively, sets its bit value to false)

Specified by:

remove in interface BitmapDataProvider

Overrides:

remove in class RoaringBitmap

Parameters:

x - integer value representing the index in a bitmap

remove

public void remove(long rangeStart,
                   long rangeEnd)

Description copied from class: RoaringBitmap

Remove from the current bitmap all integers in [rangeStart,rangeEnd).

Overrides:

remove in class RoaringBitmap

Parameters:

rangeStart - inclusive beginning of range

rangeEnd - exclusive ending of range

checkedAdd

public boolean checkedAdd(int x)

Description copied from class: RoaringBitmap

Add the value to the container (set the value to "true"), whether it already appears or not.

Overrides:

checkedAdd in class RoaringBitmap

Parameters:

x - integer value

Returns:

true if the added int wasn't already contained in the bitmap. False otherwise.

checkedRemove

public boolean checkedRemove(int x)

Description copied from class: RoaringBitmap

If present remove the specified integer (effectively, sets its bit value to false)

Overrides:

checkedRemove in class RoaringBitmap

Parameters:

x - integer value representing the index in a bitmap

Returns:

true if the unset bit was already in the bitmap

or

public void or(RoaringBitmap x2)

Description copied from class: RoaringBitmap

In-place bitwise OR (union) operation. The current bitmap is modified.

Overrides:

or in class RoaringBitmap

Parameters:

x2 - other bitmap

xor

public void xor(RoaringBitmap x2)

Description copied from class: RoaringBitmap

In-place bitwise XOR (symmetric difference) operation. The current bitmap is modified.

Overrides:

xor in class RoaringBitmap

Parameters:

x2 - other bitmap

rankLong

public long rankLong(int x)

Description copied from class: RoaringBitmap

Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality()).

Specified by:

rankLong in interface ImmutableBitmapDataProvider

Overrides:

rankLong in class RoaringBitmap

Parameters:

x - upper limit

Returns:

the rank

select

public int select(int j)

Description copied from class: RoaringBitmap

Return the jth value stored in this bitmap.

Specified by:

select in interface ImmutableBitmapDataProvider

Overrides:

select in class RoaringBitmap

Parameters:

j - index of the value

Returns:

the value