Top Description Fields Constructors Methods
com.carrotsearch.hppc

public Class BitSet

extends Object
implements Cloneable
Class Inheritance
All Implemented Interfaces
java.lang.Cloneable
Imports
com.carrotsearch.hppc.cursors.IntCursor, .LongCursor, com.carrotsearch.hppc.predicates.IntPredicate, .LongPredicate, com.carrotsearch.hppc.procedures.IntProcedure, .LongProcedure, java.util.*
An "open" BitSet implementation that allows direct access to the array of words storing the bits.

Unlike java.util.BitSet, the fact that bits are packed into an array of longs is part of the interface. This allows efficient implementation of other algorithms by someone other than the author. It also allows one to efficiently implement alternate serialization or interchange formats.

The index range for a bitset can easily exceed positive int range in Java (0x7fffffff), so many methods in this class accept or return a long. There are adapter methods that return views compatible with LongLookupContainer and IntLookupContainer interfaces.

See Also
asIntLookupContainer(), asLongLookupContainer()

Field Summary

Modifier and TypeField and Description
public long[]
bits

Internal representation of bits in this bit set.

private static final long
DEFAULT_NUM_BITS

The initial default number of bits.

public int
wlen

The number of words (longs) used in the bits array.

Constructor Summary

AccessConstructor and Description
public
BitSet()

Constructs a bit set with the default capacity.

public
BitSet(long
Number of bits
numBits)

Constructs an BitSet large enough to hold numBits.

public
BitSet(long[]
underlying bits buffer
bits, int
the number of elements in the array that contain set bits
numWords)

Constructs an BitSet from an existing long[].

Method Summary

Modifier and TypeMethod and Description
public void
and(BitSet other)

public void
andNot(BitSet other)

public static long

Returns:

Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified.
andNotCount(BitSet
The first set
a, BitSet
The second set
b)

public IntLookupContainer

Returns:

The view of this bitset as IntLookupContainer.
asIntLookupContainer()

Returns a view over this bitset data compatible with IntLookupContainer.

public LongLookupContainer

Returns:

The view of this bitset as LongLookupContainer.
asLongLookupContainer()

Returns a view over this bitset data compatible with LongLookupContainer.

public static int
bits2words(long numBits)

public long

Returns:

Returns the current capacity in bits (1 greater than the index of the last bit).
capacity()

public long

Returns:

the number of set bits
cardinality()

public void
clear()

Clears all bits.

public void
clear(long
the index to clear
index)

clears a bit, allowing access beyond the current set size without changing the size.

public void
clear(int
lower index
startIndex, int
one-past the last bit to clear
endIndex)

Clears a range of bits.

public void
clear(long
lower index
startIndex, long
one-past the last bit to clear
endIndex)

Clears a range of bits.

public Object
clone()

Overrides java.lang.Object.clone.

Creates and returns a copy of this object.

public void
ensureCapacity(long
The number of bits to expand to
numBits)

Ensure that the long[] is big enough to hold numBits, expanding it if necessary.

public void
ensureCapacityWords(int
The size to expand to (64-bit long words)
numWords)

Expand the long[] with the size given as a number of words (64 bit longs).

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.

protected int
expandingWordNum(long index)

public void
flip(long
the index to flip
index)

Flips a bit, expanding the set size if necessary.

public void
flip(long
lower index
startIndex, long
one-past the last bit to flip
endIndex)

Flips a range of bits, expanding the set size if necessary

public boolean

Returns:

previous state of the index
flipAndGet(int
the index to flip
index)

flips a bit and returns the resulting bit value.

public boolean

Returns:

previous state of the index
flipAndGet(long
the index to flip
index)

flips a bit and returns the resulting bit value.

public boolean

Returns:

Returns true or false for the specified bit index.
get(int
The index.
index)

public boolean

Returns:

Returns true or false for the specified bit index.
get(long
The index.
index)

public boolean

Returns:

previous state of the index
getAndSet(int
the index to set
index)

Sets a bit and returns the previous value.

public boolean

Returns:

previous state of the index
getAndSet(long
the index to set
index)

Sets a bit and returns the previous value.

public static int
getNextSize(int targetSize)

public static long[]
grow(long[] array, int minSize)

public int
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for this object.

public void
intersect(BitSet
The bitset to intersect with.
other)

this = this AND other

public static long

Returns:

Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified.
intersectionCount(BitSet
The first set
a, BitSet
The second set
b)

public boolean

Returns:

true if the sets have any elements in common
intersects(BitSet
The other bitset.
other)

public boolean

Returns:

Returns true if there are no set bits
isEmpty()

public BitSetIterator

Returns:

Returns an iterator over all set bits of this bitset. The iterator should be faster than using a loop around nextSetBit(int).
iterator()

public long

Returns:

Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one.
length()

public static BitSet

Returns:

New instance.
newInstance()

Static constructor-like method similar to other (generic) collections.

public int

Returns:

Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.
nextSetBit(int
The index to start scanning from, inclusive.
index)

public long

Returns:

Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.
nextSetBit(long
The index to start scanning from, inclusive.
index)

public void
or(BitSet other)

public void
remove(BitSet
The other bitset.
other)

Remove all elements set in other: this = this AND_NOT other

public void
set(long
the index to set
index)

Sets a bit, expanding the set size if necessary.

public void
set(long
lower index
startIndex, long
one-past the last bit to set
endIndex)

Sets a range of bits, expanding the set size if necessary

public long

Returns:

Returns the current capacity of this set. Included for compatibility. This is not equal to cardinality.
size()

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

public void
trimTrailingZeros()

Lowers wlen, the number of words in use, by checking for trailing zero words.

public void
union(BitSet
The bitset to union with.
other)

this = this OR other

public static long

Returns:

Returns the popcount or cardinality of the union of the two sets. Neither set is modified.
unionCount(BitSet
The first set
a, BitSet
The second set
b)

public void
xor(BitSet
The other bitset.
other)

this = this XOR other

public static long

Returns:

Returns the popcount or cardinality of the exclusive-or of the two sets. Neither set is modified.
xorCount(BitSet
The first set
a, BitSet
The second set
b)

Inherited from java.lang.Object:
finalizegetClassnotifynotifyAllwaitwaitwait

Field Detail

bitsback to summary
public long[] bits

Internal representation of bits in this bit set.

DEFAULT_NUM_BITSback to summary
private static final long DEFAULT_NUM_BITS

The initial default number of bits.

wlenback to summary
public int wlen

The number of words (longs) used in the bits array.

Constructor Detail

BitSetback to summary
public BitSet()

Constructs a bit set with the default capacity.

BitSetback to summary
public BitSet(long numBits)

Constructs an BitSet large enough to hold numBits.

Parameters
numBits:long

Number of bits

BitSetback to summary
public BitSet(long[] bits, int numWords)

Constructs an BitSet from an existing long[].

The first 64 bits are in long[0], with bit index 0 at the least significant bit, and bit index 63 at the most significant. Given a bit index, the word containing it is long[index/64], and it is at bit number index%64 within that word.

numWords are the number of elements in the array that contain set bits (non-zero longs). numWords should be <= bits.length, and any existing words in the array at position >= numWords should be zero.

Parameters
bits:long[]

underlying bits buffer

numWords:int

the number of elements in the array that contain set bits

Method Detail

andback to summary
public void and(BitSet other)
andNotback to summary
public void andNot(BitSet other)
andNotCountback to summary
public static long andNotCount(BitSet a, BitSet b)
Parameters
a:BitSet

The first set

b:BitSet

The second set

Returns:long

Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified.

asIntLookupContainerback to summary
public IntLookupContainer asIntLookupContainer()

Returns a view over this bitset data compatible with IntLookupContainer. A new object is always returned, but its methods reflect the current state of the bitset (the view is not a snapshot).

Methods of the returned IntLookupContainer may throw a RuntimeException if the cardinality of this bitset exceeds the int range.

Returns:IntLookupContainer

The view of this bitset as IntLookupContainer.

asLongLookupContainerback to summary
public LongLookupContainer asLongLookupContainer()

Returns a view over this bitset data compatible with LongLookupContainer. A new object is always returned, but its methods reflect the current state of the bitset (the view is not a snapshot).

Returns:LongLookupContainer

The view of this bitset as LongLookupContainer.

bits2wordsback to summary
public static int bits2words(long numBits)
capacityback to summary
public long capacity()
Returns:long

Returns the current capacity in bits (1 greater than the index of the last bit).

cardinalityback to summary
public long cardinality()
Returns:long

the number of set bits

clearback to summary
public void clear()

Clears all bits.

clearback to summary
public void clear(long index)

clears a bit, allowing access beyond the current set size without changing the size.

Parameters
index:long

the index to clear

clearback to summary
public void clear(int startIndex, int endIndex)

Clears a range of bits. Clearing past the end does not change the size of the set.

Parameters
startIndex:int

lower index

endIndex:int

one-past the last bit to clear

clearback to summary
public void clear(long startIndex, long endIndex)

Clears a range of bits. Clearing past the end does not change the size of the set.

Parameters
startIndex:long

lower index

endIndex:long

one-past the last bit to clear

cloneback to summary
public Object 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:Object

a clone of this instance.

Annotations
@Override
ensureCapacityback to summary
public void ensureCapacity(long numBits)

Ensure that the long[] is big enough to hold numBits, expanding it if necessary. getNumWords() is unchanged by this call.

Parameters
numBits:long

The number of bits to expand to

ensureCapacityWordsback to summary
public void ensureCapacityWords(int numWords)

Expand the long[] with the size given as a number of words (64 bit longs). getNumWords() is unchanged by this call.

Parameters
numWords:int

The size to expand to (64-bit long words)

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
expandingWordNumback to summary
protected int expandingWordNum(long index)
flipback to summary
public void flip(long index)

Flips a bit, expanding the set size if necessary.

Parameters
index:long

the index to flip

flipback to summary
public void flip(long startIndex, long endIndex)

Flips a range of bits, expanding the set size if necessary

Parameters
startIndex:long

lower index

endIndex:long

one-past the last bit to flip

flipAndGetback to summary
public boolean flipAndGet(int index)

flips a bit and returns the resulting bit value. The index should be less than the BitSet size.

Parameters
index:int

the index to flip

Returns:boolean

previous state of the index

flipAndGetback to summary
public boolean flipAndGet(long index)

flips a bit and returns the resulting bit value. The index should be less than the BitSet size.

Parameters
index:long

the index to flip

Returns:boolean

previous state of the index

getback to summary
public boolean get(int index)
Parameters
index:int

The index.

Returns:boolean

Returns true or false for the specified bit index.

getback to summary
public boolean get(long index)
Parameters
index:long

The index.

Returns:boolean

Returns true or false for the specified bit index.

getAndSetback to summary
public boolean getAndSet(int index)

Sets a bit and returns the previous value. The index should be less than the BitSet size.

Parameters
index:int

the index to set

Returns:boolean

previous state of the index

getAndSetback to summary
public boolean getAndSet(long index)

Sets a bit and returns the previous value. The index should be less than the BitSet size.

Parameters
index:long

the index to set

Returns:boolean

previous state of the index

getNextSizeback to summary
public static int getNextSize(int targetSize)
growback to summary
public static long[] grow(long[] array, int minSize)
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
intersectback to summary
public void intersect(BitSet other)

this = this AND other

Parameters
other:BitSet

The bitset to intersect with.

intersectionCountback to summary
public static long intersectionCount(BitSet a, BitSet b)
Parameters
a:BitSet

The first set

b:BitSet

The second set

Returns:long

Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified.

intersectsback to summary
public boolean intersects(BitSet other)
Parameters
other:BitSet

The other bitset.

Returns:boolean

true if the sets have any elements in common

isEmptyback to summary
public boolean isEmpty()
Returns:boolean

Returns true if there are no set bits

iteratorback to summary
public BitSetIterator iterator()
Returns:BitSetIterator

Returns an iterator over all set bits of this bitset. The iterator should be faster than using a loop around nextSetBit(int).

lengthback to summary
public long length()
Returns:long

Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one.

See Also
java.util.BitSet#length()
newInstanceback to summary
public static BitSet newInstance()

Static constructor-like method similar to other (generic) collections.

Returns:BitSet

New instance.

nextSetBitback to summary
public int nextSetBit(int index)
Parameters
index:int

The index to start scanning from, inclusive.

Returns:int

Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.

nextSetBitback to summary
public long nextSetBit(long index)
Parameters
index:long

The index to start scanning from, inclusive.

Returns:long

Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.

orback to summary
public void or(BitSet other)
removeback to summary
public void remove(BitSet other)

Remove all elements set in other: this = this AND_NOT other

Parameters
other:BitSet

The other bitset.

setback to summary
public void set(long index)

Sets a bit, expanding the set size if necessary.

Parameters
index:long

the index to set

setback to summary
public void set(long startIndex, long endIndex)

Sets a range of bits, expanding the set size if necessary

Parameters
startIndex:long

lower index

endIndex:long

one-past the last bit to set

sizeback to summary
public long size()
Returns:long

Returns the current capacity of this set. Included for compatibility. This is not equal to cardinality.

See Also
cardinality(), java.util.BitSet#size()
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
trimTrailingZerosback to summary
public void trimTrailingZeros()

Lowers wlen, the number of words in use, by checking for trailing zero words.

unionback to summary
public void union(BitSet other)

this = this OR other

Parameters
other:BitSet

The bitset to union with.

unionCountback to summary
public static long unionCount(BitSet a, BitSet b)
Parameters
a:BitSet

The first set

b:BitSet

The second set

Returns:long

Returns the popcount or cardinality of the union of the two sets. Neither set is modified.

xorback to summary
public void xor(BitSet other)

this = this XOR other

Parameters
other:BitSet

The other bitset.

xorCountback to summary
public static long xorCount(BitSet a, BitSet b)
Parameters
a:BitSet

The first set

b:BitSet

The second set

Returns:long

Returns the popcount or cardinality of the exclusive-or of the two sets. Neither set is modified.