Class BitSet
- java.lang.Object
-
- com.googlecode.javaewah.datastructure.BitSet
-
- All Implemented Interfaces:
WordArray
,java.io.Externalizable
,java.io.Serializable
,java.lang.Cloneable
,java.lang.Iterable<java.lang.Integer>
public class BitSet extends java.lang.Object implements java.lang.Cloneable, java.lang.Iterable<java.lang.Integer>, java.io.Externalizable, WordArray
This is an optimized version of Java's BitSet. In many cases, it can be used as a drop-in replacement.
It differs from the basic Java BitSet class in the following ways:
- You can iterate over set bits using a simpler syntax
for(int bs: myBitset)
. - You can compute the cardinality of an intersection and union without writing it out or modifying your BitSets (see methods such as andcardinality).
- You can recover wasted memory with trim().
- It does not implicitly expand: you have to explicitly call resize. This helps to keep memory usage in check.
- It supports memory-file mapping (see the ImmutableBitSet class).
- It supports faster and more efficient serialization functions (serialize and deserialize).
- Since:
- 0.8.0
- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description (package private) long[]
data
(package private) static long
serialVersionUID
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
and(WordArray bs)
Compute bitwise AND.int
andcardinality(WordArray bs)
Compute cardinality of bitwise AND.void
andNot(WordArray bs)
Compute bitwise AND NOT.int
andNotcardinality(WordArray bs)
Compute cardinality of bitwise AND NOT.static BitSet
bitmapOf(int... setBits)
Return a bitmap with the bit set to true at the given positions.int
cardinality()
Compute the number of bits set to 1void
clear()
Reset all bits to false.void
clear(int index)
Set the bit to false.void
clear(int start, int end)
Set the bits in the range of indexes to false.BitSet
clone()
void
deserialize(java.io.DataInput in)
Deserialize.boolean
empty()
Check whether a bitset contains a set bit.boolean
equals(java.lang.Object o)
void
flip(int i)
Flip the bit.void
flip(int start, int end)
Flip the bits in the range of indexes.boolean
get(int i)
Get the value of the bit.int
getNumberOfWords()
Get the total number of words contained in this data structure.long
getWord(int index)
Get the word at the given indexint
hashCode()
boolean
intersects(WordArray bs)
Checks whether two bitsets intersect.IntIterator
intIterator()
Iterate over the set bitsjava.util.Iterator<java.lang.Integer>
iterator()
int
nextSetBit(int i)
Usage: for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) { operate on index i here }int
nextUnsetBit(int i)
Usage: for(int i=bs.nextUnsetBit(0); i>=0; i=bs.nextUnsetBit(i+1)) { operate on index i here }void
or(WordArray bs)
Compute bitwise OR.int
orcardinality(WordArray bs)
Compute cardinality of bitwise OR.void
readExternal(java.io.ObjectInput in)
void
removeWord(int i)
Remove a word.void
resize(int sizeInBits)
Resize the bitsetvoid
serialize(java.io.DataOutput out)
Serialize.void
set(int i)
Set to true.void
set(int i, boolean b)
Set to some value.void
set(int start, int end)
Set the bits in the range of indexes true.void
set(int start, int end, boolean v)
Set the bits in the range of indexes to the specified Boolean value.int
size()
Query the sizejava.lang.String
toString()
void
trim()
Recovers wasted memoryvoid
unset(int i)
Set to falseIntIterator
unsetIntIterator()
Iterate over the unset bitsvoid
writeExternal(java.io.ObjectOutput out)
void
xor(WordArray bs)
Compute bitwise XOR.int
xorcardinality(WordArray bs)
Compute cardinality of bitwise XOR.
-
-
-
Field Detail
-
data
long[] data
-
serialVersionUID
static final long serialVersionUID
- See Also:
- Constant Field Values
-
-
Method Detail
-
and
public void and(WordArray bs)
Compute bitwise AND.- Parameters:
bs
- other bitset
-
andcardinality
public int andcardinality(WordArray bs)
Compute cardinality of bitwise AND. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.- Parameters:
bs
- other bitset- Returns:
- cardinality
-
andNot
public void andNot(WordArray bs)
Compute bitwise AND NOT. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.- Parameters:
bs
- other bitset
-
andNotcardinality
public int andNotcardinality(WordArray bs)
Compute cardinality of bitwise AND NOT.- Parameters:
bs
- other bitset- Returns:
- cardinality
-
cardinality
public int cardinality()
Compute the number of bits set to 1- Returns:
- the number of bits
-
clear
public void clear()
Reset all bits to false. This might be wasteful: a better approach is to create a new empty bitmap.
-
clear
public void clear(int index)
Set the bit to false. Seeunset(int)
- Parameters:
index
- location of the bit
-
clear
public void clear(int start, int end)
Set the bits in the range of indexes to false. This might throw an exception if size() is insufficient, consider calling resize().- Parameters:
start
- location of the first bit to set to zeroend
- location of the last bit to set to zero (not included)
-
clone
public BitSet clone()
- Overrides:
clone
in classjava.lang.Object
-
equals
public boolean equals(java.lang.Object o)
- Overrides:
equals
in classjava.lang.Object
-
empty
public boolean empty()
Check whether a bitset contains a set bit.- Returns:
- true if no set bit is found
-
flip
public void flip(int i)
Flip the bit. This might throw an exception if size() is insufficient, consider calling resize().- Parameters:
i
- index of the bit
-
flip
public void flip(int start, int end)
Flip the bits in the range of indexes. This might throw an exception if size() is insufficient, consider calling resize().- Parameters:
start
- location of the first bitend
- location of the last bit (not included)
-
get
public boolean get(int i)
Get the value of the bit. This might throw an exception if size() is insufficient, consider calling resize().- Parameters:
i
- index- Returns:
- value of the bit
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
intIterator
public IntIterator intIterator()
Iterate over the set bits- Returns:
- an iterator
-
iterator
public java.util.Iterator<java.lang.Integer> iterator()
- Specified by:
iterator
in interfacejava.lang.Iterable<java.lang.Integer>
-
intersects
public boolean intersects(WordArray bs)
Checks whether two bitsets intersect.- Parameters:
bs
- other bitset- Returns:
- true if they have a non-empty intersection (result of AND)
-
nextSetBit
public int nextSetBit(int i)
Usage: for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) { operate on index i here }- Parameters:
i
- current set bit- Returns:
- next set bit or -1
-
nextUnsetBit
public int nextUnsetBit(int i)
Usage: for(int i=bs.nextUnsetBit(0); i>=0; i=bs.nextUnsetBit(i+1)) { operate on index i here }- Parameters:
i
- current unset bit- Returns:
- next unset bit or -1
-
or
public void or(WordArray bs)
Compute bitwise OR. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.- Parameters:
bs
- other bitset
-
orcardinality
public int orcardinality(WordArray bs)
Compute cardinality of bitwise OR. BitSets are not modified.- Parameters:
bs
- other bitset- Returns:
- cardinality
-
removeWord
public void removeWord(int i)
Remove a word.- Parameters:
i
- index of the word to be removed.
-
resize
public void resize(int sizeInBits)
Resize the bitset- Parameters:
sizeInBits
- new number of bits
-
set
public void set(int i)
Set to true. This might throw an exception if size() is insufficient, consider calling resize().- Parameters:
i
- index of the bit
-
set
public void set(int i, boolean b)
Set to some value. This might throw an exception if size() is insufficient, consider calling resize().- Parameters:
i
- indexb
- value of the bit
-
set
public void set(int start, int end)
Set the bits in the range of indexes true. This might throw an exception if size() is insufficient, consider calling resize().- Parameters:
start
- location of the first bitend
- location of the last bit (not included)
-
set
public void set(int start, int end, boolean v)
Set the bits in the range of indexes to the specified Boolean value. This might throw an exception if size() is insufficient, consider calling resize().- Parameters:
start
- location of the first bitend
- location of the last bit (not included)v
- Boolean value
-
size
public int size()
Query the size- Returns:
- the size in bits.
-
trim
public void trim()
Recovers wasted memory
-
unset
public void unset(int i)
Set to false- Parameters:
i
- index of the bit
-
unsetIntIterator
public IntIterator unsetIntIterator()
Iterate over the unset bits- Returns:
- an iterator
-
writeExternal
public void writeExternal(java.io.ObjectOutput out) throws java.io.IOException
- Specified by:
writeExternal
in interfacejava.io.Externalizable
- Throws:
java.io.IOException
-
readExternal
public void readExternal(java.io.ObjectInput in) throws java.io.IOException, java.lang.ClassNotFoundException
- Specified by:
readExternal
in interfacejava.io.Externalizable
- Throws:
java.io.IOException
java.lang.ClassNotFoundException
-
serialize
public void serialize(java.io.DataOutput out) throws java.io.IOException
Serialize. The current bitmap is not modified.- Parameters:
out
- the DataOutput stream- Throws:
java.io.IOException
- Signals that an I/O exception has occurred.
-
deserialize
public void deserialize(java.io.DataInput in) throws java.io.IOException
Deserialize.- Parameters:
in
- the DataInput stream- Throws:
java.io.IOException
- Signals that an I/O exception has occurred.
-
xor
public void xor(WordArray bs)
Compute bitwise XOR. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.- Parameters:
bs
- other bitset
-
xorcardinality
public int xorcardinality(WordArray bs)
Compute cardinality of bitwise XOR. BitSets are not modified.- Parameters:
bs
- other bitset- Returns:
- cardinality
-
getNumberOfWords
public int getNumberOfWords()
Description copied from interface:WordArray
Get the total number of words contained in this data structure.- Specified by:
getNumberOfWords
in interfaceWordArray
- Returns:
- the number
-
getWord
public long getWord(int index)
Description copied from interface:WordArray
Get the word at the given index
-
bitmapOf
public static BitSet bitmapOf(int... setBits)
Return a bitmap with the bit set to true at the given positions. (This is a convenience method.)- Parameters:
setBits
- list of set bit positions- Returns:
- the bitmap
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-