Top Description Fields Constructors Methods
com.googlecode.javaewah.datastructure

public Class BitSet

extends Object
implements Cloneable, Iterable<Integer>, Externalizable, WordArray
Class Inheritance
All Implemented Interfaces
com.googlecode.javaewah.datastructure.WordArray, java.io.Externalizable, java.io.Serializable, java.lang.Iterable, java.lang.Cloneable
Imports
com.googlecode.javaewah.IntIterator, java.io.DataInput, .DataOutput, .Externalizable, .IOException, .ObjectInput, .ObjectOutput, java.util.Arrays, .Iterator

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:

Author
Daniel Lemire
Since
0.8.0

Field Summary

Modifier and TypeField and Description
pack-priv long[]
pack-priv static final long

Constructor Summary

AccessConstructor and Description
public
BitSet(final int
the size in bits
sizeInBits
)

Construct a bitset with the specified number of bits (initially all false).

public

Method Summary

Modifier and TypeMethod and Description
public void
and(WordArray
other bitset
bs
)

Compute bitwise AND.

public int

Returns:

cardinality
andcardinality
(WordArray
other bitset
bs
)

Compute cardinality of bitwise AND.

public void
andNot(WordArray
other bitset
bs
)

Compute bitwise AND NOT.

public int

Returns:

cardinality
andNotcardinality
(WordArray
other bitset
bs
)

Compute cardinality of bitwise AND NOT.

public static BitSet

Returns:

the bitmap
bitmapOf
(int...
list of set bit positions
setBits
)

Return a bitmap with the bit set to true at the given positions.

public int

Returns:

the number of bits
cardinality
()

Compute the number of bits set to 1

public void
clear()

Reset all bits to false.

public void
clear(int
location of the bit
index
)

Set the bit to false.

public void
clear(int
location of the first bit to set to zero
start
,
int
location of the last bit to set to zero (not included)
end
)

Set the bits in the range of indexes to false.

public BitSet
clone()

Overrides java.lang.Object.clone.

Creates and returns a copy of this object.

public void
deserialize(DataInput
the DataInput stream
in
)

Deserialize.

public boolean

Returns:

true if no set bit is found
empty
()

Check whether a bitset contains a set bit.

public boolean
equals(Object
the reference object with which to compare.
o
)

Overrides java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

public void
flip(final int
index of the bit
i
)

Flip the bit.

public void
flip(int
location of the first bit
start
,
int
location of the last bit (not included)
end
)

Flip the bits in the range of indexes.

public boolean

Returns:

value of the bit
get
(final int
index
i
)

Get the value of the bit.

public int
getNumberOfWords()

Implements com.googlecode.javaewah.datastructure.WordArray.getNumberOfWords.

Get the total number of words contained in this data structure.

public long
getWord(int
the index
index
)

Implements com.googlecode.javaewah.datastructure.WordArray.getWord.

Get the word at the given index

public int
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for this object.

public boolean

Returns:

true if they have a non-empty intersection (result of AND)
intersects
(WordArray
other bitset
bs
)

Checks whether two bitsets intersect.

public IntIterator

Returns:

an iterator
intIterator
()

Iterate over the set bits

public Iterator<Integer>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public int

Returns:

next set bit or -1
nextSetBit
(final int
current set bit
i
)

Usage: for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) { operate on index i here }

public int

Returns:

next unset bit or -1
nextUnsetBit
(final int
current unset bit
i
)

Usage: for(int i=bs.nextUnsetBit(0); i>=0; i=bs.nextUnsetBit(i+1)) { operate on index i here }

public void
or(WordArray
other bitset
bs
)

Compute bitwise OR.

public int

Returns:

cardinality
orcardinality
(WordArray
other bitset
bs
)

Compute cardinality of bitwise OR.

public void
readExternal(ObjectInput
the stream to read data from in order to restore the object
in
)

Implements java.io.Externalizable.readExternal.

The object implements the readExternal method to restore its contents by calling the methods of DataInput for primitive types and readObject for objects, strings and arrays.

public void
removeWord(int
index of the word to be removed.
i
)

Remove a word.

public void
resize(int
new number of bits
sizeInBits
)

Resize the bitset

public void
serialize(DataOutput
the DataOutput stream
out
)

Serialize.

public void
set(final int
index of the bit
i
)

Set to true.

public void
set(final int
index
i
,
final boolean
value of the bit
b
)

Set to some value.

public void
set(int
location of the first bit
start
,
int
location of the last bit (not included)
end
)

Set the bits in the range of indexes true.

public void
set(int
location of the first bit
start
,
int
location of the last bit (not included)
end
,
boolean
Boolean value
v
)

Set the bits in the range of indexes to the specified Boolean value.

public int

Returns:

the size in bits.
size
()

Query the size

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

public void
trim()

Recovers wasted memory

public void
unset(final int
index of the bit
i
)

Set to false

public IntIterator

Returns:

an iterator
unsetIntIterator
()

Iterate over the unset bits

public void
writeExternal(ObjectOutput
the stream to write the object to
out
)

Implements java.io.Externalizable.writeExternal.

The object implements the writeExternal method to save its contents by calling the methods of DataOutput for its primitive values or calling the writeObject method of ObjectOutput for objects, strings, and arrays.

public void
xor(WordArray
other bitset
bs
)

Compute bitwise XOR.

public int

Returns:

cardinality
xorcardinality
(WordArray
other bitset
bs
)

Compute cardinality of bitwise XOR.

Inherited from java.lang.Object:
finalizegetClassnotifynotifyAllwaitwaitwait

Field Detail

databack to summary
pack-priv long[] data
serialVersionUIDback to summary
pack-priv static final long serialVersionUID

Constructor Detail

BitSetback to summary
public BitSet(final 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:int

the size in bits

BitSetback to summary
public BitSet()

Method Detail

andback to summary
public void and(WordArray bs)

Compute bitwise AND.

Parameters
bs:WordArray

other bitset

andcardinalityback to summary
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:WordArray

other bitset

Returns:int

cardinality

andNotback to summary
public void andNot(WordArray bs)

Compute bitwise AND NOT. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.

Parameters
bs:WordArray

other bitset

andNotcardinalityback to summary
public int andNotcardinality(WordArray bs)

Compute cardinality of bitwise AND NOT.

Parameters
bs:WordArray

other bitset

Returns:int

cardinality

bitmapOfback to summary
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:int[]

list of set bit positions

Returns:BitSet

the bitmap

cardinalityback to summary
public int cardinality()

Compute the number of bits set to 1

Returns:int

the number of bits

clearback to summary
public void clear()

Reset all bits to false. This might be wasteful: a better approach is to create a new empty bitmap.

clearback to summary
public void clear(int index)

Set the bit to false. See unset(int)

Parameters
index:int

location of the bit

clearback to summary
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:int

location of the first bit to set to zero

end:int

location of the last bit to set to zero (not included)

cloneback to summary
public BitSet clone()

Overrides java.lang.Object.clone.

Doc from java.lang.Object.clone.

Creates and returns a copy of this object. The precise meaning of "copy" may depend on the class of the object. The general intent is that, for any object x, the expression:

x.clone() != x
will be true, and that the expression:
x.clone().getClass() == x.getClass()
will be true, but these are not absolute requirements. While it is typically the case that:
x.clone().equals(x)
will be true, this is not an absolute requirement.

By convention, the returned object should be obtained by calling super.clone. If a class and all of its superclasses (except Object) obey this convention, it will be the case that x.clone().getClass() == x.getClass().

By convention, the object returned by this method should be independent of this object (which is being cloned). To achieve this independence, it may be necessary to modify one or more fields of the object returned by super.clone before returning it. Typically, this means copying any mutable objects that comprise the internal "deep structure" of the object being cloned and replacing the references to these objects with references to the copies. If a class contains only primitive fields or references to immutable objects, then it is usually the case that no fields in the object returned by super.clone need to be modified.

Returns:BitSet

a clone of this instance.

Annotations
@Override
deserializeback to summary
public void deserialize(DataInput in) throws IOException

Deserialize.

Parameters
in:DataInput

the DataInput stream

Exceptions
IOException:
Signals that an I/O exception has occurred.
emptyback to summary
public boolean empty()

Check whether a bitset contains a set bit.

Returns:boolean

true if no set bit is found

equalsback to summary
public boolean equals(Object o)

Overrides java.lang.Object.equals.

Doc from java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

The equals method implements an equivalence relation on non-null object references:

  • It is reflexive: for any non-null reference value x, x.equals(x) should return true.
  • It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
  • It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
  • It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
  • For any non-null reference value x, x.equals(null) should return false.

An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes.

Parameters
o:Object

the reference object with which to compare.

Returns:boolean

true if this object is the same as the obj argument; false otherwise.

Annotations
@Override
flipback to summary
public void flip(final int i)

Flip the bit. This might throw an exception if size() is insufficient, consider calling resize().

Parameters
i:int

index of the bit

flipback to summary
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:int

location of the first bit

end:int

location of the last bit (not included)

getback to summary
public boolean get(final int i)

Get the value of the bit. This might throw an exception if size() is insufficient, consider calling resize().

Parameters
i:int

index

Returns:boolean

value of the bit

getNumberOfWordsback to summary
public int getNumberOfWords()

Implements com.googlecode.javaewah.datastructure.WordArray.getNumberOfWords.

Doc from com.googlecode.javaewah.datastructure.WordArray.getNumberOfWords.

Get the total number of words contained in this data structure.

Returns:int

the number

Annotations
@Override
getWordback to summary
public long getWord(int index)

Implements com.googlecode.javaewah.datastructure.WordArray.getWord.

Doc from com.googlecode.javaewah.datastructure.WordArray.getWord.

Get the word at the given index

Parameters
index:int

the index

Returns:long

the word

Annotations
@Override
hashCodeback to summary
public int hashCode()

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for this object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

  • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
  • It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
Returns:int

a hash code value for this object

Annotations
@Override
intersectsback to summary
public boolean intersects(WordArray bs)

Checks whether two bitsets intersect.

Parameters
bs:WordArray

other bitset

Returns:boolean

true if they have a non-empty intersection (result of AND)

intIteratorback to summary
public IntIterator intIterator()

Iterate over the set bits

Returns:IntIterator

an iterator

iteratorback to summary
public Iterator<Integer> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

Returns:Iterator<Integer>

an Iterator.

Annotations
@Override
nextSetBitback to summary
public int nextSetBit(final int i)

Usage: for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) { operate on index i here }

Parameters
i:int

current set bit

Returns:int

next set bit or -1

nextUnsetBitback to summary
public int nextUnsetBit(final int i)

Usage: for(int i=bs.nextUnsetBit(0); i>=0; i=bs.nextUnsetBit(i+1)) { operate on index i here }

Parameters
i:int

current unset bit

Returns:int

next unset bit or -1

orback to summary
public void or(WordArray bs)

Compute bitwise OR. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.

Parameters
bs:WordArray

other bitset

orcardinalityback to summary
public int orcardinality(WordArray bs)

Compute cardinality of bitwise OR. BitSets are not modified.

Parameters
bs:WordArray

other bitset

Returns:int

cardinality

readExternalback to summary
public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException

Implements java.io.Externalizable.readExternal.

Doc from java.io.Externalizable.readExternal.

The object implements the readExternal method to restore its contents by calling the methods of DataInput for primitive types and readObject for objects, strings and arrays. The readExternal method must read the values in the same sequence and with the same types as were written by writeExternal.

Parameters
in:ObjectInput

the stream to read data from in order to restore the object

Annotations
@Override
Exceptions
IOException:
if I/O errors occur
ClassNotFoundException:
If the class for an object being restored cannot be found.
removeWordback to summary
public void removeWord(int i)

Remove a word.

Parameters
i:int

index of the word to be removed.

resizeback to summary
public void resize(int sizeInBits)

Resize the bitset

Parameters
sizeInBits:int

new number of bits

serializeback to summary
public void serialize(DataOutput out) throws IOException

Serialize. The current bitmap is not modified.

Parameters
out:DataOutput

the DataOutput stream

Exceptions
IOException:
Signals that an I/O exception has occurred.
setback to summary
public void set(final int i)

Set to true. This might throw an exception if size() is insufficient, consider calling resize().

Parameters
i:int

index of the bit

setback to summary
public void set(final int i, final boolean b)

Set to some value. This might throw an exception if size() is insufficient, consider calling resize().

Parameters
i:int

index

b:boolean

value of the bit

setback to summary
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:int

location of the first bit

end:int

location of the last bit (not included)

setback to summary
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:int

location of the first bit

end:int

location of the last bit (not included)

v:boolean

Boolean value

sizeback to summary
public int size()

Query the size

Returns:int

the size in bits.

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

Returns:String

a string representation of the object

Annotations
@Override
trimback to summary
public void trim()

Recovers wasted memory

unsetback to summary
public void unset(final int i)

Set to false

Parameters
i:int

index of the bit

unsetIntIteratorback to summary
public IntIterator unsetIntIterator()

Iterate over the unset bits

Returns:IntIterator

an iterator

writeExternalback to summary
public void writeExternal(ObjectOutput out) throws IOException

Implements java.io.Externalizable.writeExternal.

Doc from java.io.Externalizable.writeExternal.

The object implements the writeExternal method to save its contents by calling the methods of DataOutput for its primitive values or calling the writeObject method of ObjectOutput for objects, strings, and arrays.

Parameters
out:ObjectOutput

the stream to write the object to

Annotations
@Override
Exceptions
IOException:
Includes any I/O exceptions that may occur
xorback to summary
public void xor(WordArray bs)

Compute bitwise XOR. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.

Parameters
bs:WordArray

other bitset

xorcardinalityback to summary
public int xorcardinality(WordArray bs)

Compute cardinality of bitwise XOR. BitSets are not modified.

Parameters
bs:WordArray

other bitset

Returns:int

cardinality