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
| Modifier and Type | Field and Description |
|---|---|
| public static final boolean | ADJUST_CONTAINER_SIZE_WHEN_AGGREGATING
whether we adjust after some aggregation by adding in zeroes * |
| pack-priv final Buffer32 | buffer
The buffer |
| private RunningLengthWord32 | rlw
The current (last) running length word. |
| pack-priv static final long | |
| private int | sizeInBits
sizeInBits: number of bits in the (uncompressed) bitmap. |
| public static final int | WORD_IN_BITS
The Constant WORD_IN_BITS represents the number of bits in a int. |
| Access | Constructor and Description |
|---|---|
| public | |
| public | EWAHCompressedBitmap32(int
number of 32-bit words reserved when the object is
created) bufferSize)Sets explicitly the buffer size (in 32-bit words). |
| public | EWAHCompressedBitmap32(ByteBuffer
data source buffer)Creates a bitmap with the specified ByteBuffer backend. |
| public | EWAHCompressedBitmap32(IntBuffer
data source buffer)Creates a bitmap with the specified java.nio.IntBuffer backend. |
| private |
| Modifier and Type | Method and Description |
|---|---|
| public void | |
| public void | add(final int
the word newData, final int the number of significant bits (by default it should
be 64) bitsThatMatter)
Deprecated
use addWord() instead.
|
| public void | addLiteralWord(final int
the literal word newData)Implements com. Adding literal words directly to the bitmap (for expert use). |
| public void | addStreamOfEmptyWords(final boolean
the boolean value v, int the number number)Implements com. For experts: You want to add many zeroes or ones? |
| public void | addStreamOfLiteralWords(final Buffer32
the buffer wrapping the literal words buffer, final int the starting point in the array start, final int the number of literal words to add number)Implements com. if you have several literal words to copy over, this might be faster. |
| public void | addStreamOfNegatedLiteralWords(final Buffer32
the buffer wrapping the literal words buffer, final int the starting point in the array start, final int the number of literal words to add number)Implements com. Same as addStreamOfLiteralWords, but the words are negated. |
| public void | addWord(final int
the word newData)Implements com. Adding words directly to the bitmap (for expert use). |
| public void | addWord(final int
the word newData, final int the number of significant bits (by default it should
be 32) bitsThatMatter)Adding words directly to the bitmap (for expert use). |
| public EWAHCompressedBitmap32 | Returns: the EWAH compressed bitmapthe other bitmap (it will not be modified) a)Implements com. Returns a new compressed bitmap containing the bitwise AND values of the current bitmap with some other bitmap. |
| public static EWAHCompressedBitmap32 | Returns: result of the ANDbitmaps to AND together bitmaps)Implements com. Returns a new compressed bitmap containing the bitwise AND values of the provided bitmaps. |
| public int | Returns: the cardinalitythe other bitmap (it will not be modified) a)Returns the cardinality of the result of a bitwise AND of the values of the current bitmap with some other bitmap. |
| public static int | Returns: the cardinalitybitmaps to AND bitmaps)Returns the cardinality of the result of a bitwise AND of the values of the provided bitmaps. |
| public EWAHCompressedBitmap32 | Returns: the EWAH compressed bitmapthe other bitmap (it will not be modified) a)Implements com. Returns a new compressed bitmap containing the bitwise AND NOT values of the current bitmap with some other bitmap. |
| public int | Returns: the cardinalitythe other bitmap (it will not be modified) a)Returns the cardinality of the result of a bitwise AND NOT of the values of the current bitmap with some other bitmap. |
| public void | andNotToContainer(final EWAHCompressedBitmap32
the other bitmap (it will not be modified) a, final BitmapStorage32 where we store the result container)Returns a new compressed bitmap containing the bitwise AND NOT values of the current bitmap with some other bitmap. |
| public void | andToContainer(final EWAHCompressedBitmap32
the other bitmap (it will not be modified) a, final BitmapStorage32 where we store the result container)Computes new compressed bitmap containing the bitwise AND values of the current bitmap with some other bitmap. |
| public static void | andWithContainer(final BitmapStorage32
where the result is stored container, final EWAHCompressedBitmap32... bitmaps to AND bitmaps)For internal use. |
| public static EWAHCompressedBitmap32 | Returns: the bitmaplist of set bit positions setbits)Return a bitmap with the bit set to true at the given positions. |
| private static int | |
| public int | |
| public ChunkIterator | |
| public void | clear()
Implements com. Clear any set bits and set size in bits back to 0 |
| public boolean | |
| public IntIterator | |
| public EWAHCompressedBitmap32 | |
| public EWAHCompressedBitmap32 | Returns: the EWAH compressed bitmapthe other bitmap (it will not be modified) a)Implements com. Returns a new compressed bitmap containing the composition of the current bitmap with some other bitmap. |
| public void | composeToContainer(final EWAHCompressedBitmap32
the other bitmap (it will not be modified) a, final EWAHCompressedBitmap32 where we store the result container)Computes a new compressed bitmap containing the composition of the current bitmap with some other bitmap. |
| public void | |
| private int | |
| public boolean | equals(Object
the reference object with which to compare. o)Overrides java. Check to see whether the two compressed bitmaps contain the same set bits. |
| private void | |
| private void | fastaddStreamOfEmptyWords(final boolean
the boolean value v, int the number (must be greater than 0) number)For experts: You want to add many zeroes or ones faster? |
| public boolean | Returns: whether the bit is set to truethe bit we are interested in i)Query the value of a single bit. |
| public EWAHIterator32 | |
| public int | Returns: location of the first set bit or -1getFirstSetBit is a light-weight method that returns the location of the set bit (=1) or -1 if there is none. |
| public IteratingRLW32 | Returns: the IteratingRLW iterator corresponding to this bitmapGets an IteratingRLW to iterate over the data. |
| public List | |
| private ReverseEWAHIterator32 | Returns: the ReverseEWAHIterator32Gets a ReverseEWAHIterator32 over the data. |
| public int | hashCode()
Overrides java. Returns a customized hash code (based on Karp-Rabin). |
| private void | |
| private void | |
| public boolean | Returns: whether they intersectthe other bitmap (it will not be modified) a)Return true if the two EWAHCompressedBitmap have both at least one true bit in the same position. |
| public IntIterator | Returns: the int iteratorIterator over the set bits (this is what most people will want to use to browse the content if they want an iterator). |
| public boolean | Returns: true if no bit is setChecks whether this bitmap is empty (has a cardinality of zero). |
| public Iterator | Returns: the iteratorImplements java. Iterates over the positions of the true values. |
| private void | |
| pack-priv static int | |
| private boolean | |
| private boolean | |
| public void | |
| public EWAHCompressedBitmap32 | Returns: the EWAH compressed bitmapthe other bitmap (it will not be modified) a)Implements com. Returns a new compressed bitmap containing the bitwise OR values of the current bitmap with some other bitmap. |
| public static EWAHCompressedBitmap32 | Returns: result of the ORbitmaps to OR together bitmaps)Implements com. Returns a new compressed bitmap containing the bitwise OR values of the provided bitmaps. |
| public int | Returns: the cardinalitythe other bitmap (it will not be modified) a)Returns the cardinality of the result of a bitwise OR of the values of the current bitmap with some other bitmap. |
| public static int | Returns: the cardinalitybitmaps to OR bitmaps)Returns the cardinality of the result of a bitwise OR of the values of the provided bitmaps. |
| public void | orToContainer(final EWAHCompressedBitmap32
the other bitmap (it will not be modified) a, final BitmapStorage32 where we store the result container)Computes the bitwise or between the current bitmap and the bitmap "a". |
| public static void | orWithContainer(final BitmapStorage32
where store the result container, final EWAHCompressedBitmap32... to be aggregated bitmaps)For internal use. |
| public void | readExternal(ObjectInput
the stream to read data from in order to restore the object in)Implements java. The object implements the readExternal method to restore its contents by calling the methods of DataInput for primitive types and readObject for objects, strings and arrays. |
| public IntIterator | |
| public void | |
| public int | Returns: the size in bytesReport the number of bytes required to serialize this bitmap. |
| public boolean | |
| private boolean | |
| private void | |
| private void | |
| private void | |
| public boolean | Returns: true if the update was possiblethe size in bits size, final boolean the default boolean value defaultValue)Change the reported size in bits of the *uncompressed* bitmap represented by this compressed bitmap. |
| public void | setSizeInBitsWithinLastWord(final int
the size in bits size)Implements com. Set the size in bits. |
| public EWAHCompressedBitmap32 | Returns: new shifted bitmapnumber of bits b)Generates a new bitmap shifted by "b" bits. |
| public int | Returns: the size in bitsImplements com. Returns the size in bits of the *uncompressed* bitmap represented by this compressed bitmap. |
| public int | Returns: the size in bytesImplements com. Report the *compressed* size of the bitmap (equivalent to memory usage, after accounting for some overhead). |
| public void | swap(final EWAHCompressedBitmap32
bitmap to swap with other)swap the content of the bitmap with another. |
| public static EWAHCompressedBitmap32 | Returns: the aggregated bitmapthe threshold t, final EWAHCompressedBitmap32... input data bitmaps)Compute a Boolean threshold function: bits are true where at least T bitmaps have a true bit. |
| public static void | thresholdWithContainer(final BitmapStorage32
where we write the aggregated bitmap container, final int the threshold t, final EWAHCompressedBitmap32... input data bitmaps)Compute a Boolean threshold function: bits are true where at least T bitmaps have a true bit. |
| public int[] | Returns: the array containing the location of the set bitsPopulate an array of (sorted integers) corresponding to the location of the set bits. |
| public String | Returns: the stringA more detailed string describing the bitmap (useful for debugging). |
| public List | |
| public String | |
| public void | |
| public void | writeExternal(ObjectOutput
the stream to write the object to out)Implements java. The object implements the writeExternal method to save its contents by calling the methods of DataOutput for its primitive values or calling the writeObject method of ObjectOutput for objects, strings, and arrays. |
| public EWAHCompressedBitmap32 | Returns: the EWAH compressed bitmapthe other bitmap (it will not be modified) a)Implements com. Returns a new compressed bitmap containing the bitwise XOR values of the current bitmap with some other bitmap. |
| public static EWAHCompressedBitmap32 | Returns: result of the XORbitmaps to XOR together bitmaps)Implements com. Returns a new compressed bitmap containing the bitwise XOR values of the provided bitmaps. |
| public int | Returns: the cardinalitythe other bitmap (it will not be modified) a)Returns the cardinality of the result of a bitwise XOR of the values of the current bitmap with some other bitmap. |
| public void | xorToContainer(final EWAHCompressedBitmap32
the other bitmap (it will not be modified) a, final BitmapStorage32 where we store the result container)Computes a new compressed bitmap containing the bitwise XOR values of the current bitmap with some other bitmap. |
| public static void | xorWithContainer(final BitmapStorage32
where store the result container, final EWAHCompressedBitmap32... to be aggregated bitmaps)For internal use. |