Class BitSet
java.lang.Object
com.googlecode.javaewah.datastructure.BitSet
- All Implemented Interfaces:
WordArray
,Externalizable
,Serializable
,Cloneable
,Iterable<Integer>
public class BitSet
extends Object
implements Cloneable, Iterable<Integer>, 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:
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) long[]
(package private) static final long
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
Compute bitwise AND.int
Compute cardinality of bitwise AND.void
Compute bitwise AND NOT.int
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
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.clone()
void
deserialize
(DataInput in) Deserialize.boolean
empty()
Check whether a bitset contains a set bit.boolean
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
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.Iterate over the set bitsiterator()
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
Compute bitwise OR.int
Compute cardinality of bitwise OR.void
void
resize
(int sizeInBits) Resize the bitsetvoid
serialize
(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 sizetoString()
void
trim()
Recovers wasted memoryvoid
unset
(int i) Set to falseIterate over the unset bitsvoid
void
Compute bitwise XOR.int
Compute cardinality of bitwise XOR.Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Field Details
-
data
long[] data -
serialVersionUID
static final long serialVersionUID- See Also:
-
-
Constructor Details
-
BitSet
public BitSet(int sizeInBits) Construct a bitset with the specified number of bits (initially all false). The number of bits is rounded up to the nearest multiple of 64.- Parameters:
sizeInBits
- the size in bits
-
BitSet
public BitSet()
-
-
Method Details
-
and
Compute bitwise AND.- Parameters:
bs
- other bitset
-
andcardinality
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
Compute bitwise AND NOT. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.- Parameters:
bs
- other bitset
-
andNotcardinality
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
-
equals
-
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() -
intIterator
Iterate over the set bits- Returns:
- an iterator
-
iterator
-
intersects
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
Compute bitwise OR. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.- Parameters:
bs
- other bitset
-
orcardinality
Compute cardinality of bitwise OR. BitSets are not modified.- Parameters:
bs
- other bitset- Returns:
- cardinality
-
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
Iterate over the unset bits- Returns:
- an iterator
-
writeExternal
- Specified by:
writeExternal
in interfaceExternalizable
- Throws:
IOException
-
readExternal
- Specified by:
readExternal
in interfaceExternalizable
- Throws:
IOException
ClassNotFoundException
-
serialize
Serialize. The current bitmap is not modified.- Parameters:
out
- the DataOutput stream- Throws:
IOException
- Signals that an I/O exception has occurred.
-
deserialize
Deserialize.- Parameters:
in
- the DataInput stream- Throws:
IOException
- Signals that an I/O exception has occurred.
-
xor
Compute bitwise XOR. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.- Parameters:
bs
- other bitset
-
xorcardinality
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
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
-