public final class EWAHCompressedBitmap32 extends java.lang.Object implements java.lang.Cloneable, java.io.Externalizable, java.lang.Iterable<java.lang.Integer>, BitmapStorage32, LogicalElement<EWAHCompressedBitmap32>
This implements the patent-free EWAH scheme. Roughly speaking, it is a 32-bit variant of the BBC compression scheme used by Oracle for its bitmap indexes.
In contrast with the 64-bit EWAH scheme (javaewah.EWAHCompressedBitmap), you can expect this class to compress better, but to be slower at processing the data. In effect, there is a trade-off between memory usage and performances.
Here is a code sample to illustrate usage:
EWAHCompressedBitmap32 ewahBitmap1 = EWAHCompressedBitmap32.bitmapOf(0, 2, 55, 64, 1 << 30); EWAHCompressedBitmap32 ewahBitmap2 = EWAHCompressedBitmap32.bitmapOf(1, 3, 64, 1 << 30); EWAHCompressedBitmap32 ewahBitmap3 = EWAHCompressedBitmap32 .bitmapOf(5, 55, 1 << 30); EWAHCompressedBitmap32 ewahBitmap4 = EWAHCompressedBitmap32 .bitmapOf(4, 66, 1 << 30); EWAHCompressedBitmap32 orBitmap = ewahBitmap1.or(ewahBitmap2); EWAHCompressedBitmap32 andbitmap = ewahBitmap1.and(ewahBitmap2); EWAHCompressedBitmap32 xorbitmap = ewahBitmap1.xor(ewahBitmap2); andbitmap = EWAHCompressedBitmap32.and(ewahBitmap1, ewahBitmap2, ewahBitmap3, ewahBitmap4); ByteArrayOutputStream bos = new ByteArrayOutputStream(); ObjectOutputStream oo = new ObjectOutputStream(bos); ewahBitmap1.writeExternal(oo); oo.close(); ewahBitmap1 = null; ewahBitmap1 = new EWAHCompressedBitmap32(); ByteArrayInputStream bis = new ByteArrayInputStream(bos.toByteArray()); ewahBitmap1.readExternal(new ObjectInputStream(bis)); EWAHCompressedBitmap32 threshold2 = EWAHCompressedBitmap32.threshold(2, ewahBitmap1, ewahBitmap2, ewahBitmap3, ewahBitmap4);
The objective of this compression type is to provide some compression, while reducing as much as possible the CPU cycle usage.
Once constructed, the bitmap is essentially immutable (unless you call the "set" or "add" methods). Thus, it can be safely used in multi-threaded programs.
For more details, see the following papers:
EWAHCompressedBitmap
,
Serialized FormModifier and Type | Field and Description |
---|---|
static boolean |
ADJUST_CONTAINER_SIZE_WHEN_AGGREGATING
whether we adjust after some aggregation by adding in zeroes *
|
(package private) Buffer32 |
buffer
The buffer
|
private RunningLengthWord32 |
rlw
The current (last) running length word.
|
(package private) static long |
serialVersionUID |
private int |
sizeInBits
sizeInBits: number of bits in the (uncompressed) bitmap.
|
static int |
WORD_IN_BITS
The Constant WORD_IN_BITS represents the number of bits in a int.
|
Modifier | Constructor and Description |
---|---|
|
EWAHCompressedBitmap32()
Creates an empty bitmap (no bit set to true).
|
private |
EWAHCompressedBitmap32(Buffer32 buffer) |
|
EWAHCompressedBitmap32(java.nio.ByteBuffer buffer)
Creates a bitmap with the specified ByteBuffer backend.
|
|
EWAHCompressedBitmap32(int bufferSize)
Sets explicitly the buffer size (in 32-bit words).
|
|
EWAHCompressedBitmap32(java.nio.IntBuffer buffer)
Creates a bitmap with the specified java.nio.IntBuffer backend.
|
Modifier and Type | Method and Description |
---|---|
void |
add(int newData)
Deprecated.
use addWord() instead.
|
void |
add(int newData,
int bitsThatMatter)
Deprecated.
use addWord() instead.
|
void |
addLiteralWord(int newData)
Adding literal words directly to the bitmap (for expert use).
|
void |
addStreamOfEmptyWords(boolean v,
int number)
For experts: You want to add many zeroes or ones? This is the method
you use.
|
void |
addStreamOfLiteralWords(Buffer32 buffer,
int start,
int number)
if you have several literal words to copy over, this might be faster.
|
void |
addStreamOfNegatedLiteralWords(Buffer32 buffer,
int start,
int number)
Same as addStreamOfLiteralWords, but the words are negated.
|
void |
addWord(int newData)
Adding words directly to the bitmap (for expert use).
|
void |
addWord(int newData,
int bitsThatMatter)
Adding words directly to the bitmap (for expert use).
|
static EWAHCompressedBitmap32 |
and(EWAHCompressedBitmap32... bitmaps)
Returns a new compressed bitmap containing the bitwise AND values of
the provided bitmaps.
|
EWAHCompressedBitmap32 |
and(EWAHCompressedBitmap32 a)
Returns a new compressed bitmap containing the bitwise AND values of
the current bitmap with some other bitmap.
|
static int |
andCardinality(EWAHCompressedBitmap32... bitmaps)
Returns the cardinality of the result of a bitwise AND of the values
of the provided bitmaps.
|
int |
andCardinality(EWAHCompressedBitmap32 a)
Returns the cardinality of the result of a bitwise AND of the values
of the current bitmap with some other bitmap.
|
EWAHCompressedBitmap32 |
andNot(EWAHCompressedBitmap32 a)
Returns a new compressed bitmap containing the bitwise AND NOT values
of the current bitmap with some other bitmap.
|
int |
andNotCardinality(EWAHCompressedBitmap32 a)
Returns the cardinality of the result of a bitwise AND NOT of the
values of the current bitmap with some other bitmap.
|
void |
andNotToContainer(EWAHCompressedBitmap32 a,
BitmapStorage32 container)
Returns a new compressed bitmap containing the bitwise AND NOT values
of the current bitmap with some other bitmap.
|
void |
andToContainer(EWAHCompressedBitmap32 a,
BitmapStorage32 container)
Computes new compressed bitmap containing the bitwise AND values of
the current bitmap with some other bitmap.
|
static void |
andWithContainer(BitmapStorage32 container,
EWAHCompressedBitmap32... bitmaps)
For internal use.
|
static EWAHCompressedBitmap32 |
bitmapOf(int... setbits)
Return a bitmap with the bit set to true at the given positions.
|
private static int |
calculateInitialSize(EWAHCompressedBitmap32... bitmaps) |
int |
cardinality()
reports the number of bits set to true.
|
ChunkIterator |
chunkIterator()
Iterator over the chunk of bits.
|
void |
clear()
Clear any set bits and set size in bits back to 0
|
boolean |
clear(int i)
Set the bit at position i to false.
|
IntIterator |
clearIntIterator()
Iterator over the clear bits.
|
EWAHCompressedBitmap32 |
clone() |
EWAHCompressedBitmap32 |
compose(EWAHCompressedBitmap32 a)
Returns a new compressed bitmap containing the composition of
the current bitmap with some other bitmap.
|
void |
composeToContainer(EWAHCompressedBitmap32 a,
EWAHCompressedBitmap32 container)
Computes a new compressed bitmap containing the composition of
the current bitmap with some other bitmap.
|
void |
deserialize(java.io.DataInput in)
Deserialize.
|
private int |
distanceInWords(int i)
For internal use.
|
boolean |
equals(java.lang.Object o)
Check to see whether the two compressed bitmaps contain the same set
bits.
|
private void |
extendAndSet(int i,
boolean value)
For internal use.
|
private void |
fastaddStreamOfEmptyWords(boolean v,
int number)
For experts: You want to add many zeroes or ones faster?
This method does not update sizeInBits.
|
boolean |
get(int i)
Query the value of a single bit.
|
EWAHIterator32 |
getEWAHIterator()
Gets an EWAHIterator32 over the data.
|
int |
getFirstSetBit()
getFirstSetBit is a light-weight method that returns the
location of the set bit (=1) or -1 if there is none.
|
IteratingRLW32 |
getIteratingRLW()
Gets an IteratingRLW to iterate over the data.
|
java.util.List<java.lang.Integer> |
getPositions()
Deprecated.
use toList() instead.
|
private ReverseEWAHIterator32 |
getReverseEWAHIterator()
Gets a ReverseEWAHIterator32 over the data.
|
int |
hashCode()
Returns a customized hash code (based on Karp-Rabin).
|
private void |
insertEmptyWord(boolean v)
For internal use.
|
private void |
insertLiteralWord(int newData)
For internal use.
|
boolean |
intersects(EWAHCompressedBitmap32 a)
Return true if the two EWAHCompressedBitmap have both at least one
true bit in the same position.
|
IntIterator |
intIterator()
Iterator over the set bits (this is what most people will want to use
to browse the content if they want an iterator).
|
boolean |
isEmpty()
Checks whether this bitmap is empty (has a cardinality of zero).
|
java.util.Iterator<java.lang.Integer> |
iterator()
Iterates over the positions of the true values.
|
private void |
locateAndSet(int i,
boolean value)
For internal use.
|
(package private) static int |
maxSizeInBits(EWAHCompressedBitmap32... bitmaps) |
private boolean |
mergeLiteralWordInCurrentRunningLength(boolean value,
boolean rb,
int rl,
int wordPosition) |
private boolean |
mergeLiteralWordInNextRunningLength(boolean value,
int lw,
int pos,
int wordPosition) |
void |
not()
Negate (bitwise) the current bitmap.
|
static EWAHCompressedBitmap32 |
or(EWAHCompressedBitmap32... bitmaps)
Returns a new compressed bitmap containing the bitwise OR values of
the provided bitmaps.
|
EWAHCompressedBitmap32 |
or(EWAHCompressedBitmap32 a)
Returns a new compressed bitmap containing the bitwise OR values of
the current bitmap with some other bitmap.
|
static int |
orCardinality(EWAHCompressedBitmap32... bitmaps)
Returns the cardinality of the result of a bitwise OR of the values
of the provided bitmaps.
|
int |
orCardinality(EWAHCompressedBitmap32 a)
Returns the cardinality of the result of a bitwise OR of the values
of the current bitmap with some other bitmap.
|
void |
orToContainer(EWAHCompressedBitmap32 a,
BitmapStorage32 container)
Computes the bitwise or between the current bitmap and the bitmap
"a".
|
static void |
orWithContainer(BitmapStorage32 container,
EWAHCompressedBitmap32... bitmaps)
For internal use.
|
void |
readExternal(java.io.ObjectInput in) |
IntIterator |
reverseIntIterator()
Iterator over the set bits in reverse order.
|
void |
serialize(java.io.DataOutput out)
Serialize.
|
int |
serializedSizeInBytes()
Report the number of bytes required to serialize this bitmap.
|
boolean |
set(int i)
Set the bit at position i to true.
|
private boolean |
set(int i,
boolean value)
For internal use.
|
private void |
setInLiteralWords(boolean value,
int i,
int nbits,
int pos,
int rl,
boolean rb,
int lw) |
private void |
setInRunningLength(boolean value,
int i,
int nbits,
int pos,
int rl,
boolean rb,
int lw) |
private void |
setRLWInfo(int pos,
boolean rb,
int rl,
int lw) |
boolean |
setSizeInBits(int size,
boolean defaultValue)
Change the reported size in bits of the *uncompressed* bitmap
represented by this compressed bitmap.
|
void |
setSizeInBitsWithinLastWord(int size)
Set the size in bits.
|
EWAHCompressedBitmap32 |
shift(int b)
Generate a new bitmap a new bitmap shifted by "b" bits.
|
int |
sizeInBits()
Returns the size in bits of the *uncompressed* bitmap represented by
this compressed bitmap.
|
int |
sizeInBytes()
Report the *compressed* size of the bitmap (equivalent to memory
usage, after accounting for some overhead).
|
void |
swap(EWAHCompressedBitmap32 other)
swap the content of the bitmap with another.
|
static EWAHCompressedBitmap32 |
threshold(int t,
EWAHCompressedBitmap32... bitmaps)
Compute a Boolean threshold function: bits are true where at least T
bitmaps have a true bit.
|
static void |
thresholdWithContainer(BitmapStorage32 container,
int t,
EWAHCompressedBitmap32... bitmaps)
Compute a Boolean threshold function: bits are true where at least T
bitmaps have a true bit.
|
int[] |
toArray()
Populate an array of (sorted integers) corresponding to the location
of the set bits.
|
java.lang.String |
toDebugString()
A more detailed string describing the bitmap (useful for debugging).
|
java.util.List<java.lang.Integer> |
toList()
Gets the locations of the true values as one list.
|
java.lang.String |
toString()
A string describing the bitmap.
|
void |
trim()
Reduce the internal buffer to its minimal allowable size (given by
this.actualsizeinwords).
|
void |
writeExternal(java.io.ObjectOutput out) |
static EWAHCompressedBitmap32 |
xor(EWAHCompressedBitmap32... bitmaps)
Returns a new compressed bitmap containing the bitwise XOR values of
the provided bitmaps.
|
EWAHCompressedBitmap32 |
xor(EWAHCompressedBitmap32 a)
Returns a new compressed bitmap containing the bitwise XOR values of
the current bitmap with some other bitmap.
|
int |
xorCardinality(EWAHCompressedBitmap32 a)
Returns the cardinality of the result of a bitwise XOR of the values
of the current bitmap with some other bitmap.
|
void |
xorToContainer(EWAHCompressedBitmap32 a,
BitmapStorage32 container)
Computes a new compressed bitmap containing the bitwise XOR values of
the current bitmap with some other bitmap.
|
static void |
xorWithContainer(BitmapStorage32 container,
EWAHCompressedBitmap32... bitmaps)
For internal use.
|
final Buffer32 buffer
private RunningLengthWord32 rlw
private int sizeInBits
public static final boolean ADJUST_CONTAINER_SIZE_WHEN_AGGREGATING
public static final int WORD_IN_BITS
static final long serialVersionUID
public EWAHCompressedBitmap32()
public EWAHCompressedBitmap32(int bufferSize)
bufferSize
- number of 32-bit words reserved when the object is
created)public EWAHCompressedBitmap32(java.nio.ByteBuffer buffer)
buffer
- data sourcepublic EWAHCompressedBitmap32(java.nio.IntBuffer buffer)
buffer
- data sourceprivate EWAHCompressedBitmap32(Buffer32 buffer)
@Deprecated public void add(int newData)
newData
- the word@Deprecated public void add(int newData, int bitsThatMatter)
newData
- the wordbitsThatMatter
- the number of significant bits (by default it should
be 64)public void addWord(int newData)
addWord
in interface BitmapStorage32
newData
- the wordpublic void addWord(int newData, int bitsThatMatter)
newData
- the wordbitsThatMatter
- the number of significant bits (by default it should
be 32)private void insertEmptyWord(boolean v)
v
- the boolean valuepublic void addLiteralWord(int newData)
addLiteralWord
in interface BitmapStorage32
newData
- the literal wordprivate void insertLiteralWord(int newData)
newData
- the literal wordpublic void addStreamOfLiteralWords(Buffer32 buffer, int start, int number)
addStreamOfLiteralWords
in interface BitmapStorage32
buffer
- the buffer wrapping the literal wordsstart
- the starting point in the arraynumber
- the number of literal words to addpublic void addStreamOfEmptyWords(boolean v, int number)
addStreamOfEmptyWords
in interface BitmapStorage32
v
- the boolean valuenumber
- the numberpublic void addStreamOfNegatedLiteralWords(Buffer32 buffer, int start, int number)
addStreamOfNegatedLiteralWords
in interface BitmapStorage32
buffer
- the buffer wrapping the literal wordsstart
- the starting point in the arraynumber
- the number of literal words to addpublic EWAHCompressedBitmap32 and(EWAHCompressedBitmap32 a)
and
in interface LogicalElement<EWAHCompressedBitmap32>
a
- the other bitmap (it will not be modified)public void andToContainer(EWAHCompressedBitmap32 a, BitmapStorage32 container)
a
- the other bitmap (it will not be modified)container
- where we store the resultpublic int andCardinality(EWAHCompressedBitmap32 a)
a
- the other bitmap (it will not be modified)public EWAHCompressedBitmap32 andNot(EWAHCompressedBitmap32 a)
andNot
in interface LogicalElement<EWAHCompressedBitmap32>
a
- the other bitmap (it will not be modified)public void andNotToContainer(EWAHCompressedBitmap32 a, BitmapStorage32 container)
a
- the other bitmap (it will not be modified)container
- where we store the resultpublic int andNotCardinality(EWAHCompressedBitmap32 a)
a
- the other bitmap (it will not be modified)public int cardinality()
public void clear()
clear
in interface BitmapStorage32
public EWAHCompressedBitmap32 clone() throws java.lang.CloneNotSupportedException
clone
in class java.lang.Object
java.lang.CloneNotSupportedException
public void serialize(java.io.DataOutput out) throws java.io.IOException
out
- the DataOutput streamjava.io.IOException
- Signals that an I/O exception has occurred.public void deserialize(java.io.DataInput in) throws java.io.IOException
in
- the ObjectInput streamjava.io.IOException
- Signals that an I/O exception has occurred.public boolean equals(java.lang.Object o)
equals
in class java.lang.Object
Object.equals(java.lang.Object)
private void fastaddStreamOfEmptyWords(boolean v, int number)
v
- the boolean valuenumber
- the number (must be greater than 0)public EWAHIterator32 getEWAHIterator()
private ReverseEWAHIterator32 getReverseEWAHIterator()
public IteratingRLW32 getIteratingRLW()
EWAHCompressedBitmap32 n = IteratorUtil32.materialize(bitmap.getIteratingRLW()));
n.setSizeInBitsWithinLastWord(bitmap.sizeInBits());
The current bitmap is not modified.@Deprecated public java.util.List<java.lang.Integer> getPositions()
public java.util.List<java.lang.Integer> toList()
public int hashCode()
hashCode
in class java.lang.Object
public boolean intersects(EWAHCompressedBitmap32 a)
a
- the other bitmap (it will not be modified)public IntIterator intIterator()
public IntIterator reverseIntIterator()
public boolean isEmpty()
public IntIterator clearIntIterator()
public ChunkIterator chunkIterator()
public java.util.Iterator<java.lang.Integer> iterator()
iterator
in interface java.lang.Iterable<java.lang.Integer>
public void not()
not
in interface LogicalElement<EWAHCompressedBitmap32>
public EWAHCompressedBitmap32 or(EWAHCompressedBitmap32 a)
or
in interface LogicalElement<EWAHCompressedBitmap32>
a
- the other bitmap (it will not be modified)public void orToContainer(EWAHCompressedBitmap32 a, BitmapStorage32 container)
a
- the other bitmap (it will not be modified)container
- where we store the resultpublic int orCardinality(EWAHCompressedBitmap32 a)
a
- the other bitmap (it will not be modified)public void readExternal(java.io.ObjectInput in) throws java.io.IOException, java.lang.ClassNotFoundException
readExternal
in interface java.io.Externalizable
java.io.IOException
java.lang.ClassNotFoundException
public void writeExternal(java.io.ObjectOutput out) throws java.io.IOException
writeExternal
in interface java.io.Externalizable
java.io.IOException
public int serializedSizeInBytes()
public boolean get(int i)
i
- the bit we are interested inpublic int getFirstSetBit()
public boolean clear(int i)
i
- the indexjava.lang.IndexOutOfBoundsException
- if i is negative or greater than Integer.MAX_VALUE - 32public boolean set(int i)
i
- the indexjava.lang.IndexOutOfBoundsException
- if i is negative or greater than Integer.MAX_VALUE - 32private boolean set(int i, boolean value)
i
- the indexvalue
- the valueprivate void extendAndSet(int i, boolean value)
i
- the indexvalue
- the valueprivate void locateAndSet(int i, boolean value)
i
- the indexvalue
- the valueprivate void setInRunningLength(boolean value, int i, int nbits, int pos, int rl, boolean rb, int lw)
private void setInLiteralWords(boolean value, int i, int nbits, int pos, int rl, boolean rb, int lw)
private boolean mergeLiteralWordInCurrentRunningLength(boolean value, boolean rb, int rl, int wordPosition)
private boolean mergeLiteralWordInNextRunningLength(boolean value, int lw, int pos, int wordPosition)
private void setRLWInfo(int pos, boolean rb, int rl, int lw)
public void setSizeInBitsWithinLastWord(int size)
setSizeInBitsWithinLastWord
in interface BitmapStorage32
size
- the size in bitspublic boolean setSizeInBits(int size, boolean defaultValue)
size
- the size in bitsdefaultValue
- the default boolean valueprivate int distanceInWords(int i)
i
- the indexpublic int sizeInBits()
sizeInBits
in interface LogicalElement<EWAHCompressedBitmap32>
public int sizeInBytes()
sizeInBytes
in interface LogicalElement<EWAHCompressedBitmap32>
public static EWAHCompressedBitmap32 threshold(int t, EWAHCompressedBitmap32... bitmaps)
t
- the thresholdbitmaps
- input datastatic int maxSizeInBits(EWAHCompressedBitmap32... bitmaps)
public static void thresholdWithContainer(BitmapStorage32 container, int t, EWAHCompressedBitmap32... bitmaps)
t
- the thresholdbitmaps
- input datacontainer
- where we write the aggregated bitmappublic int[] toArray()
public java.lang.String toDebugString()
public java.lang.String toString()
toString
in class java.lang.Object
public void swap(EWAHCompressedBitmap32 other)
other
- bitmap to swap withpublic void trim()
public EWAHCompressedBitmap32 xor(EWAHCompressedBitmap32 a)
xor
in interface LogicalElement<EWAHCompressedBitmap32>
a
- the other bitmap (it will not be modified)public void xorToContainer(EWAHCompressedBitmap32 a, BitmapStorage32 container)
a
- the other bitmap (it will not be modified)container
- where we store the resultpublic int xorCardinality(EWAHCompressedBitmap32 a)
a
- the other bitmap (it will not be modified)public EWAHCompressedBitmap32 compose(EWAHCompressedBitmap32 a)
compose
in interface LogicalElement<EWAHCompressedBitmap32>
a
- the other bitmap (it will not be modified)public void composeToContainer(EWAHCompressedBitmap32 a, EWAHCompressedBitmap32 container)
a
- the other bitmap (it will not be modified)container
- where we store the resultpublic static void andWithContainer(BitmapStorage32 container, EWAHCompressedBitmap32... bitmaps)
container
- where the result is storedbitmaps
- bitmaps to ANDprivate static int calculateInitialSize(EWAHCompressedBitmap32... bitmaps)
public static EWAHCompressedBitmap32 and(EWAHCompressedBitmap32... bitmaps)
bitmaps
- bitmaps to AND togetherpublic static int andCardinality(EWAHCompressedBitmap32... bitmaps)
bitmaps
- bitmaps to ANDpublic static EWAHCompressedBitmap32 bitmapOf(int... setbits)
setbits
- list of set bit positionspublic static void orWithContainer(BitmapStorage32 container, EWAHCompressedBitmap32... bitmaps)
container
- where store the resultbitmaps
- to be aggregatedpublic static void xorWithContainer(BitmapStorage32 container, EWAHCompressedBitmap32... bitmaps)
container
- where store the resultbitmaps
- to be aggregatedpublic static EWAHCompressedBitmap32 or(EWAHCompressedBitmap32... bitmaps)
bitmaps
- bitmaps to OR togetherpublic static EWAHCompressedBitmap32 xor(EWAHCompressedBitmap32... bitmaps)
bitmaps
- bitmaps to XOR togetherpublic static int orCardinality(EWAHCompressedBitmap32... bitmaps)
bitmaps
- bitmaps to ORpublic EWAHCompressedBitmap32 shift(int b)
b
- number of bits