org.qtunes.db.spi.simple
Class WAHBitSet

java.lang.Object
  extended by org.qtunes.db.spi.simple.WAHBitSet
All Implemented Interfaces:
Serializable

public class WAHBitSet
extends Object
implements Serializable

WAHBitSet implements the Word-Aligned Hybrid compressed BitSet. Using WAH as the compression scheme the class achieves both compressaion and performance on bitset operations.

See Also:
Serialized Form

Nested Class Summary
 class WAHBitSet.IndexSet
          The IndexSet stores positions of bits that are one.
 
Constructor Summary
WAHBitSet()
          Create an empty bitset.
WAHBitSet(BitSet set)
          Initialize the compressed bitset withn an uncompressed bitset.
 
Method Summary
 WAHBitSet and(WAHBitSet other)
          Returns a new WAH compressed bitset after anding the current bitset with the other bitset.
 int andSize(WAHBitSet other)
          This is an optimization over the and function.
 int cardinality()
          Returns the number of 1 bits in the bitset.
 boolean get(int i)
          Checks if the bit is set in the compressed bitset.
 BitSet getBitSet(BitSet set)
          Return a BitSet which has the same values set as this WAHBitSet
 WAHBitSet.IndexSet getIndexSet()
          Returns an index set for the set bits in the bitset.
 Iterator iterator()
          Returns an iterator for the set bits in the bitset.
 long memSize()
          Returns the amount of memory used by the compressed bit set
 WAHBitSet or(WAHBitSet other)
          Returns a new WAH compressed bitset after oring the current bitset with the other bitset.
 void set(int i)
          Sets the index i to one. expands the bitset if required.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

WAHBitSet

public WAHBitSet()
Create an empty bitset.


WAHBitSet

public WAHBitSet(BitSet set)
Initialize the compressed bitset withn an uncompressed bitset.

Parameters:
set - the uncompressed bitset.
Method Detail

getBitSet

public BitSet getBitSet(BitSet set)
Return a BitSet which has the same values set as this WAHBitSet

Parameters:
set - the Set to populate and return - if null, a new BitSet is created

set

public void set(int i)
Sets the index i to one. expands the bitset if required. Note: currently we are going to support only increasing the indexes.

Parameters:
i - the index to set as 1.

get

public boolean get(int i)
Checks if the bit is set in the compressed bitset. This operation is considerably slower than the uncompressed version. Use it with care.

Parameters:
i - the index where bit is checked.
Returns:
true if the index is set, false otherwise.

cardinality

public int cardinality()
Returns the number of 1 bits in the bitset.

Returns:
the number of 1 bits in the bitset.

iterator

public Iterator iterator()
Returns an iterator for the set bits in the bitset.

Returns:
an iterator for the set bits in the bitset

getIndexSet

public WAHBitSet.IndexSet getIndexSet()
Returns an index set for the set bits in the bitset. IndexSet is an easier way to get the set bits in the compressed bitset. IndexSet is lighter weight interface than iterator, and should be used when the performance is important.

Returns:
an index set for the set bits in the bitset

memSize

public long memSize()
Returns the amount of memory used by the compressed bit set

Returns:
the amount of memory used by the compressed bit set

and

public WAHBitSet and(WAHBitSet other)
Returns a new WAH compressed bitset after anding the current bitset with the other bitset.

Parameters:
other - the bitset to and with
Returns:
The resulting bitset

or

public WAHBitSet or(WAHBitSet other)
Returns a new WAH compressed bitset after oring the current bitset with the other bitset. This function is not as optimized as and

Parameters:
other - the bitset to or with
Returns:
The resulting bitset

andSize

public int andSize(WAHBitSet other)
This is an optimization over the and function. This does not create new bitset. This just counts the number of 1 bits common between the two bitsets.

Parameters:
other - the bitset to and with.
Returns:
the number of 1s common between two bitsets.