sparsebitmap
Class SparseBitmap

java.lang.Object
  sparsebitmap.SparseBitmap

All Implemented Interfaces:

Externalizable, Serializable, Cloneable, Iterable<Integer>, BitmapContainer

public class SparseBitmap
extends Object
implements Iterable<Integer>, BitmapContainer, Cloneable, Externalizable

The purpose of this class is to provide a compressed alternative to the Java BitSet class that can scale to much larger bit ranges. It also offers good processing performance while remaining simple.

Author:

Daniel Lemire

See Also:

Serialized Form

Field Summary

IntArray	buffer buffer is where the data is store.
int	sizeinwords sizeinwords*32 is the the number of bits represented by this bitmap.
static int	WORDSIZE We have a 32-bit implementation (ints are 32-bit in Java).

Constructor Summary

SparseBitmap()
Constructs a SparseBitmap object with default parameters.

SparseBitmap(int expectedstoragesize)
Constructs a SparseBitmap object.

Method Summary

void	add(int wo, int off) For expert use: add a literal bitmap word so that the resulting bitmap will cover off+1 words.
static SkippableIterator	and(SkippableIterator... bitmap) And.
static SparseBitmap	and(SparseBitmap... bitmaps) Computes the bit-wise and aggregate over several bitmaps.
SparseBitmap	and(SparseBitmap o) Compute the bit-wise logical and with another bitmap.
static void	and2by2(BitmapContainer container, SparseBitmap bitmap1, SparseBitmap bitmap2) Computes the bit-wise logical exclusive and of two bitmaps.
static SkippableIterator	and2by2(SkippableIterator bitmap1, SkippableIterator bitmap2) And2by2.
static SparseBitmap	bitmapOf(int... k) Convenience method: will construct a bitmap with the specified bit sets.
int	cardinality() Compute the cardinality.
static int	cardinality(SkippableIterator i) Cardinality.
void	clear() Reinitialize this bitmap.
Object	clone()
void	deserialize(DataInput in) Deserialize.
boolean	equals(Object o) Checks whether two SparseBitmap have the same bit sets.
static SkippableIterator	fastand(SkippableIterator... bitmap) Fastand.
static SkippableIterator	fastand(SparseBitmap... bitmaps)
static SkippableIterator	flatand(SkippableIterator... bitmap) Flatand.
IntIterator	getIntIterator() Build a fast iterator over the set bits.
SkippableIterator	getSkippableIterator() Gets the skippable iterator.
int	hashCode() Return a hash value for this object.
Iterator<Integer>	iterator() Allow you to iterate over the set bits.
static boolean	match(SkippableIterator o1, SkippableIterator o2) Synchronize two iterators
static SparseBitmap	materialize(SkippableIterator i) Materialize.
static SparseBitmap	or(SparseBitmap... bitmaps) Computes the bit-wise or aggregate over several bitmaps.
SparseBitmap	or(SparseBitmap o) Computes the bit-wise logical or with another bitmap.
static void	or2by2(BitmapContainer container, SparseBitmap bitmap1, SparseBitmap bitmap2) Computes the bit-wise logical or of two bitmaps.
void	readExternal(ObjectInput in)
static SkippableIterator	reverseflatand(SkippableIterator... bitmap) Reverseflatand.
void	serialize(DataOutput out) Serialize.
void	set(int i) Set the bit at position i to true.
int	sizeInBytes() Return how much space is used by data (in bytes).
int[]	toArray() Convenience method: returns an array containing the set bits.
String	toString() A string describing the bitmap.
static SkippableIterator	treeand(SkippableIterator... bitmap) Treeand.
int	trim() Minimizes the memory usage by copying over the data on a smaller array.
void	writeExternal(ObjectOutput out)
static SparseBitmap	xor(SparseBitmap... bitmaps) Computes the bit-wise exclusive or aggregate over several bitmaps.
SparseBitmap	xor(SparseBitmap o) Computes the bit-wise logical exclusive or with another bitmap.
static void	xor2by2(BitmapContainer container, SparseBitmap bitmap1, SparseBitmap bitmap2) Computes the bit-wise logical exclusive or of two bitmaps.

Methods inherited from class java.lang.Object

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

Field Detail

sizeinwords

public int sizeinwords

sizeinwords*32 is the the number of bits represented by this bitmap.

buffer

public IntArray buffer

buffer is where the data is store. The format is 32-bit for the offset, 32-bit for a literal bitmap

WORDSIZE

public static final int WORDSIZE

We have a 32-bit implementation (ints are 32-bit in Java).

See Also:

Constant Field Values

Constructor Detail

SparseBitmap

public SparseBitmap()

Constructs a SparseBitmap object with default parameters.

SparseBitmap

public SparseBitmap(int expectedstoragesize)

Constructs a SparseBitmap object.

Parameters:

expectedstoragesize - this parameter corresponds to the initial memory allocation

Method Detail

add

public void add(int wo,
                int off)

For expert use: add a literal bitmap word so that the resulting bitmap will cover off+1 words. This function does minimal checking: to input data in the bitmap, you might be better off with the set method.

Specified by:

add in interface BitmapContainer

Parameters:

wo - literal bitmap word to add

off - position at (total size will be off+1)

equals

public boolean equals(Object o)

Checks whether two SparseBitmap have the same bit sets. Return true if so.

Overrides:

equals in class Object

Parameters:

o - the o

Returns:

whether the two objects have the same set bits

hashCode

public int hashCode()

Return a hash value for this object. Uses a Karp-Rabin hash function.

Overrides:

hashCode in class Object

Returns:

the hash value

toArray

public int[] toArray()

Convenience method: returns an array containing the set bits.

Returns:

array corresponding to the position of the set bits.

toString

public String toString()

A string describing the bitmap.

Overrides:

toString in class Object

Returns:

the string

bitmapOf

public static SparseBitmap bitmapOf(int... k)

Convenience method: will construct a bitmap with the specified bit sets. Note that the list of integers should be sorted in increasing order.

Parameters:

k - the list of bits to set

Returns:

the corresponding SparseBitmap object.

set

public void set(int i)

Set the bit at position i to true. The SparseBitmap will automatically expand. Note that you need to set the bits in sorted order (e.g., 1,2,5,6 and not 6,4,1,2). If the bit cannot be set, an IllegalArgumentException is thrown.

Parameters:

i - the i

iterator

public Iterator<Integer> iterator()

Allow you to iterate over the set bits.

Specified by:

iterator in interface Iterable<Integer>

Returns:

Iterator over the set bits

getIntIterator

public IntIterator getIntIterator()

Build a fast iterator over the set bits.

Returns:

the iterator over the set bits

and

public SparseBitmap and(SparseBitmap o)

Compute the bit-wise logical and with another bitmap.

Parameters:

o - another bitmap

Returns:

the result of the bit-wise logical and

and2by2

public static void and2by2(BitmapContainer container,
                           SparseBitmap bitmap1,
                           SparseBitmap bitmap2)

Computes the bit-wise logical exclusive and of two bitmaps.

Parameters:

container - where the data will be stored

bitmap1 - the first bitmap

bitmap2 - the second bitmap

and

public static SkippableIterator and(SkippableIterator... bitmap)

And.

Parameters:

bitmap - the bitmap

Returns:

the skippable iterator

fastand

public static SkippableIterator fastand(SkippableIterator... bitmap)

Fastand.

Parameters:

bitmap - the bitmap

Returns:

the skippable iterator

treeand

public static SkippableIterator treeand(SkippableIterator... bitmap)

Treeand.

Parameters:

bitmap - the bitmap

Returns:

the skippable iterator

flatand

public static SkippableIterator flatand(SkippableIterator... bitmap)

Flatand.

Parameters:

bitmap - the bitmap

Returns:

the skippable iterator

reverseflatand

public static SkippableIterator reverseflatand(SkippableIterator... bitmap)

Reverseflatand.

Parameters:

bitmap - the bitmap

Returns:

the skippable iterator

materialize

public static SparseBitmap materialize(SkippableIterator i)

Materialize.

Parameters:

i - the i

Returns:

the sparse bitmap

cardinality

public static int cardinality(SkippableIterator i)

Cardinality.

Parameters:

i - the i

Returns:

the int

and2by2

public static SkippableIterator and2by2(SkippableIterator bitmap1,
                                        SkippableIterator bitmap2)

And2by2.

Parameters:

bitmap1 - the bitmap1

bitmap2 - the bitmap2

Returns:

the skippable iterator

or

public SparseBitmap or(SparseBitmap o)

Computes the bit-wise logical or with another bitmap.

Parameters:

o - another bitmap

Returns:

the result of the bit-wise logical or

or2by2

public static void or2by2(BitmapContainer container,
                          SparseBitmap bitmap1,
                          SparseBitmap bitmap2)

Computes the bit-wise logical or of two bitmaps.

Parameters:

container - where the data will be stored

bitmap1 - the first bitmap

bitmap2 - the second bitmap

xor

public SparseBitmap xor(SparseBitmap o)

Computes the bit-wise logical exclusive or with another bitmap.

Parameters:

o - another bitmap

Returns:

the result of the bti-wise logical exclusive or

xor2by2

public static void xor2by2(BitmapContainer container,
                           SparseBitmap bitmap1,
                           SparseBitmap bitmap2)

Computes the bit-wise logical exclusive or of two bitmaps.

Parameters:

container - where the data will be stored

bitmap1 - the first bitmap

bitmap2 - the second bitmap

and

public static SparseBitmap and(SparseBitmap... bitmaps)

Computes the bit-wise and aggregate over several bitmaps.

Parameters:

bitmaps - the bitmaps to aggregate

Returns:

the resulting bitmap

fastand

public static SkippableIterator fastand(SparseBitmap... bitmaps)

or

public static SparseBitmap or(SparseBitmap... bitmaps)

Computes the bit-wise or aggregate over several bitmaps.

Parameters:

bitmaps - the bitmaps to aggregate

Returns:

the resulting bitmap

xor

public static SparseBitmap xor(SparseBitmap... bitmaps)

Computes the bit-wise exclusive or aggregate over several bitmaps.

Parameters:

bitmaps - the bitmaps to aggregate

Returns:

the resulting bitmap

sizeInBytes

public int sizeInBytes()

Return how much space is used by data (in bytes).

Returns:

the

trim

public int trim()

Minimizes the memory usage by copying over the data on a smaller array.

Returns:

new memory usage for the internal array (in bytes)

getSkippableIterator

public SkippableIterator getSkippableIterator()

Gets the skippable iterator.

Returns:

the skippable iterator

match

public static boolean match(SkippableIterator o1,
                            SkippableIterator o2)

Synchronize two iterators

Parameters:

o1 - the first iterator

o2 - the second iterator

Returns:

true, if successful

readExternal

public void readExternal(ObjectInput in)
                  throws IOException,
                         ClassNotFoundException

Specified by:

readExternal in interface Externalizable

Throws:

IOException

ClassNotFoundException

writeExternal

public void writeExternal(ObjectOutput out)
                   throws IOException

Specified by:

writeExternal in interface Externalizable

Throws:

IOException

serialize

public void serialize(DataOutput out)
               throws IOException

Serialize.

Parameters:

out - the stream

Throws:

IOException - Signals that an I/O exception has occurred.

deserialize

public void deserialize(DataInput in)
                 throws IOException

Deserialize.

Parameters:

in - the stream

Throws:

IOException - Signals that an I/O exception has occurred.

cardinality

public int cardinality()

Compute the cardinality.

Returns:

the cardinality

clear

public void clear()

Reinitialize this bitmap.

clone

public Object clone()
             throws CloneNotSupportedException

Overrides:

clone in class Object

Throws:

CloneNotSupportedException