sparsebitmap
Class SparseBitmap

java.lang.Object
  sparsebitmap.SparseBitmap

All Implemented Interfaces:

Iterable<Integer>, BitmapContainer

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

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

Field Summary

int[]	buffer buffer is where the data is store.
int	cardinality Number of bits set to true.
static int	MINSTORAGEUSAGE MINSTORAGEUSAGE determines how big the initial array is, by default.
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).
int	wordusage How many words in buffer do we actually use?

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 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 SparseBitmap	bitmapOf(int... k) Convenience method: will construct a bitmap with the specified bit sets.
int	compact() Minimizes the memory usage by copying over the data on a smaller array.
boolean	equals(Object o) Checks whether two SparseBitmap have the same bit sets.
IntIterator	getIntIterator() Build a fast iterator over the set bits
int	hashCode() Return a hash value for this object.
Iterator<Integer>	iterator() Allow you to iterate over the set bits
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	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.
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

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Field Detail

sizeinwords

public int sizeinwords

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

cardinality

public int cardinality

Number of bits set to true.

MINSTORAGEUSAGE

public static final int MINSTORAGEUSAGE

MINSTORAGEUSAGE determines how big the initial array is, by default.

See Also:

Constant Field Values

buffer

public int[] buffer

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

wordusage

public int wordusage

How many words in buffer do we actually use?

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

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.

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 -

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

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

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).

Specified by:

sizeInBytes in interface BitmapContainer

Returns:

the

compact

public int compact()

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

Returns:

new memory usage for the internal array (in bytes)