Top Description Inners Fields Constructors Methods
com.zaxxer.sparsebits

public Class SparseBitSet

extends Object
implements Cloneable, Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable, java.lang.Cloneable
Imports
java.io.IOException, .ObjectInputStream, .ObjectOutputStream, .Serializable
This class implements a set of bits that grows as needed. Each bit of the bit set represents a boolean value. The values of a SparseBitSet are indexed by non-negative integers. Individual indexed values may be examined, set, cleared, or modified by logical operations. One SparseBitSet or logical value may be used to modify the contents of (another) SparseBitSet through logical AND, logical inclusive OR, logical exclusive OR, and And NOT operations over all or part of the bit sets.

All values in a bit set initially have the value false.

Every bit set has a current size, which is the number of bits of space nominally in use by the bit set from the first set bit to just after the last set bit. The length of the bit set effectively tells the position available after the last bit of the SparseBitSet.

The maximum cardinality of a SparseBitSet is Integer.MAX_VALUE, which means the bits of a SparseBitSet are labelled 0 .. Integer.MAX_VALUE − 1. After the last set bit of a SparseBitSet, any attempt to find a subsequent bit (nextSetBit()), will return an value of −1. If an attempt is made to use nextClearBit(), and all the bits are set from the starting position of the search to the bit labelled Integer.MAX_VALUE − 1, then similarly −1 will be returned.

Unless otherwise noted, passing a null parameter to any of the methods in a SparseBitSet will result in a NullPointerException.

A SparseBitSet is not safe for multi-threaded use without external synchronization.

Authors
Bruce K. Haddon, Arthur van Hoff, Michael McCloskey, Martin Buchholz
Since
1.6
Version
1.0, 2009-03-17

Nested and Inner Type Summary

Modifier and TypeClass and Description
protected abstract static class
SparseBitSet.AbstractStrategy

This strategy class is used by the setScanner to carry out the a variety of operations on this set, and usually a second set.

protected static class
SparseBitSet.AndNotStrategy

AndNot of two sets.

protected static class
SparseBitSet.AndStrategy

And of two sets.

protected class
SparseBitSet.Cache

This class holds the values related to various statistics kept about the bit set.

protected static class
SparseBitSet.ClearStrategy

Clear clears bits in the a set.

protected static class
SparseBitSet.CopyStrategy

Copies the needed parts of the b set to the a set.

protected static class
SparseBitSet.EqualsStrategy

Equals compares bits in the a set with those in the b set.

protected static class
SparseBitSet.FlipStrategy

Flip inverts the bits of the a set within the given range.

protected static class
SparseBitSet.IntersectsStrategy

Intersect has a true result if any word in the a set has a bit in common with the b set.

protected static class
SparseBitSet.OrStrategy

Or of two sets.

protected static class
SparseBitSet.SetStrategy

Set creates entries everywhere within the range.

public static enum
SparseBitSet.Statistics

These enumeration values are used as labels for the values in the String created by the statistics() method.

protected class
SparseBitSet.UpdateStrategy

Update the seven statistics that are computed for each set.

protected static class
SparseBitSet.XorStrategy

The XOR of level3 blocks is computed.

Field Summary

Modifier and TypeField and Description
protected static final transient SparseBitSet.AndNotStrategy
andNotStrategy

Word and block andNot strategy.

protected static final transient SparseBitSet.AndStrategy
andStrategy

Word and block and strategy.

protected transient long[][][]
bits

The storage for this SparseBitSet.

protected transient int
bitsLength

For the current size of the bits array, this is the maximum possible length of the bit set, i.e., the index of the last possible bit, plus one.

protected transient SparseBitSet.Cache
cache

Holds reference to the cache of statistics values computed by the UpdateStrategy

protected static final transient SparseBitSet.ClearStrategy
clearStrategy

Word and block clear strategy.

protected transient int
compactionCount

This value controls for format of the toString() output.

pack-priv static int
compactionCountDefault

The compaction count default.

protected static final transient SparseBitSet.CopyStrategy
copyStrategy

Word and block copy strategy.

protected transient SparseBitSet.EqualsStrategy
equalsStrategy

Word and block equals strategy.

protected static final transient SparseBitSet.FlipStrategy
flipStrategy

Word and block flip strategy.

protected static final int
INDEX_SIZE

The number of bits in a positive integer, and the size of permitted index of a bit in the bit set.

protected static transient SparseBitSet.IntersectsStrategy
intersectsStrategy

Word and block intersects strategy.

protected static final int
LENGTH2

LENGTH2 is the number of entries in the any level2 area.

protected static final int
LENGTH2_SIZE

LENGTH2_SIZE is maximum index of a LEVEL2 page.

protected static final int
LENGTH3

LENGTH3 is the number of entries in the any level3 block.

protected static final int
LENGTH3_SIZE

LENGTH3_SIZE is maximum index of a LEVEL3 page.

protected static final int
LENGTH4

The number of bits in a long value.

protected static final int
LENGTH4_SIZE

LENGTH4_SIZE is maximum index of a bit in a LEVEL4 word.

protected static final int
LEVEL1

LEVEL1 is the number of bits of the level1 address.

protected static final int
LEVEL2

LEVEL2 is the number of bits of the level2 address.

protected static final int
LEVEL3

LEVEL3 is the number of bits of the level3 address.

protected static final int
LEVEL4

The label (index) of a bit in the bit set is essentially broken into 4 "levels".

protected static final int
MASK2

MASK2 is the mask to extract the LEVEL2 address from a word index (after shifting by SHIFT3 and SHIFT2).

protected static final int
MASK3

MASK3 is the mask to extract the LEVEL3 address from a word index (after shifting by SHIFT3).

protected static final int
MAX_LENGTH1

MAX_LENGTH1 is the maximum number of entries in the level1 set array.

protected static final transient SparseBitSet.OrStrategy
orStrategy

Word and block or strategy.

private static final long
serialVersionUID

serialVersionUID

protected static final transient SparseBitSet.SetStrategy
setStrategy

Word and block set strategy.

protected static final int
SHIFT1

SHIFT1 is the shift to bring the level1 address (from the word index) to the right end (i.e., after shifting by SHIFT3).

protected static final int
SHIFT2

SHIFT2 is the shift to bring the level2 address (from the word index) to the right end (i.e., after shifting by SHIFT3).

protected static final int
SHIFT3

The shift to create the word index.

protected transient long[]
spare

A spare level 3 block is kept for use when scanning.

protected static final int
UNIT

UNIT is the greatest number of bits that can be held in one level1 entry.

protected transient SparseBitSet.UpdateStrategy
updateStrategy

Word and block update strategy.

protected static final transient SparseBitSet.XorStrategy
xorStrategy

Word and block xor strategy.

pack-priv static final long[]
ZERO_BLOCK

An empty level 3 block is kept for use when scanning.

Constructor Summary

AccessConstructor and Description
protected
SparseBitSet(int
a size in terms of bits
capacity, int
the compactionCount to be inherited (for internal generation)
compactionCount)

Constructor for a new (sparse) bit set.

public
SparseBitSet()

Constructs an empty bit set with the default initial size.

public
SparseBitSet(int
the initial provisional length of the SparseBitSet
nbits)

Creates a bit set whose initial size is large enough to efficiently represent bits with indices in the range 0 through at least nbits-1.

Method Summary

Modifier and TypeMethod and Description
public void
and(int
a bit index
i, boolean
a boolean value to AND with that bit
value)

Performs a logical AND of the addressed target bit with the argument value.

public void
and(int
index of the first bit to be included in the operation
i, int
index after the last bit to included in the operation
j, SparseBitSet
a SparseBitSet
b)

Performs a logical AND of this target bit set with the argument bit set within the given range of bits.

public void
and(SparseBitSet
a SparseBitSet
b)

Performs a logical AND of this target bit set with the argument bit set.

public static SparseBitSet

Returns:

a new SparseBitSet representing the AND of the two sets
and(SparseBitSet
a SparseBitSet
a, SparseBitSet
another SparseBitSet
b)

Performs a logical AND of the two given SparseBitSets.

public void
andNot(int
a bit index
i, boolean
a boolean value to AndNOT with that bit
value)

Performs a logical AndNOT of the addressed target bit with the argument value.

public void
andNot(int
index of the first bit to be included in the operation
i, int
index after the last bit to included in the operation
j, SparseBitSet
the SparseBitSet with which to mask this SparseBitSet
b)

Performs a logical AndNOT of this target bit set with the argument bit set within the given range of bits.

public void
andNot(SparseBitSet
the SparseBitSet with which to mask this SparseBitSet
b)

Performs a logical AndNOT of this target bit set with the argument bit set.

public static SparseBitSet

Returns:

a new SparseBitSet representing the AndNOT of the two sets
andNot(SparseBitSet
a SparseBitSet
a, SparseBitSet
another SparseBitSet
b)

Creates a bit set from thie first SparseBitSet whose corresponding bits are cleared by the set bits of the second SparseBitSet.

public int

Returns:

the number of bits set to true in this SparseBitSet
cardinality()

Returns the number of bits set to true in this SparseBitSet.

public void
clear(int
a bit index.
i)

Sets the bit at the specified index to false.

public void
clear(int
index of the first bit to be cleared
i, int
index after the last bit to be cleared
j)

Sets the bits from the specified i (inclusive) to the specified j (exclusive) to false.

public void
clear()

Sets all of the bits in this SparseBitSet to false.

public SparseBitSet

Returns:

a clone of this SparseBitSet
clone()

Overrides java.lang.Object.clone.

Cloning this SparseBitSet produces a new SparseBitSet that is equal() to it.

protected final void
constructorHelper()

Intializes all the additional objects required for correct operation.

public boolean

Returns:

true if the objects are equivalent; false otherwise.
equals(Object
the Object with which to compare
obj)

Overrides java.lang.Object.equals.

Compares this object against the specified object.

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

Sets the bit at the specified index to the complement of its current value.

public void
flip(int
index of the first bit to flip
i, int
index after the last bit to flip
j)

Sets each bit from the specified i (inclusive) to the specified j (exclusive) to the complement of its current value.

public boolean

Returns:

the boolean value of the bit with the specified index.
get(int
the bit index
i)

Returns the value of the bit with the specified index.

public SparseBitSet

Returns:

a new SparseBitSet from a range of this SparseBitSet
get(int
index of the first bit to include
i, int
index after the last bit to include
j)

Returns a new SparseBitSet composed of bits from this SparseBitSet from i (inclusive) to j (exclusive).

public int

Returns:

a hash code value for this bit set
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for this bit set.

public boolean

Returns:

the boolean indicating whether this SparseBitSet intersects the specified SparseBitSet
intersects(int
index of the first bit to include
i, int
index after the last bit to include
j, SparseBitSet
the SparseBitSet with which to intersect
b)

Returns true if the specified SparseBitSet has any bits within the given range i (inclusive) to j (exclusive) set to true that are also set to true in the same range of this SparseBitSet.

public boolean

Returns:

boolean indicating whether this SparseBitSet intersects the specified SparseBitSet
intersects(SparseBitSet
a SparseBitSet with which to intersect
b)

Returns true if the specified SparseBitSet has any bits set to true that are also set to true in this SparseBitSet.

public boolean

Returns:

the boolean indicating whether this SparseBitSet is empty
isEmpty()

Returns true if this SparseBitSet contains no bits that are set to true.

public int

Returns:

the logical length of this SparseBitSet
length()

Returns the "logical length" of this SparseBitSet: the index of the highest set bit in the SparseBitSet plus one.

public int

Returns:

the index of the next clear bit, or -1 if there is no such bit
nextClearBit(int
the index to start checking from (inclusive)
i)

Returns the index of the first bit that is set to false that occurs on or after the specified starting index.

public int

Returns:

the index of the next set bit
nextSetBit(int
the index to start checking from (inclusive)
i)

Returns the index of the first bit that is set to true that occurs on or after the specified starting index.

protected final void
nullify(int
word index at which to start (inclusive)
start)

Clear out a part of the set array with nulls, from the given start to the end of the array.

public void
or(int
a bit index
i, boolean
a boolean value to OR with that bit
value)

Performs a logical OR of the addressed target bit with the argument value.

public void
or(int
index of the first bit to be included in the operation
i, int
index after the last bit to included in the operation
j, SparseBitSet
the SparseBitSet with which to perform the OR operation with this SparseBitSet
b)

Performs a logical OR of the addressed target bit with the argument value within the given range.

public void
or(SparseBitSet
the SparseBitSet with which to perform the OR operation with this SparseBitSet
b)

Performs a logical OR of this bit set with the bit set argument.

public static SparseBitSet

Returns:

new SparseBitSet representing the OR of the two sets
or(SparseBitSet
a SparseBitSet
a, SparseBitSet
another SparseBitSet
b)

Performs a logical OR of the two given SparseBitSets.

public int

Returns:

the index of the previous clear bit, or -1 if there is no such bit
previousClearBit(int
the index to start checking from (inclusive)
i)

Returns the index of the nearest bit that is set to false that occurs on or before the specified starting index.

public int

Returns:

the index of the previous set bit, or -1 if there is no such bit
previousSetBit(int
the index to start checking from (inclusive)
i)

Returns the index of the nearest bit that is set to true that occurs on or before the specified starting index.

private void
readObject(ObjectInputStream
the ObjectInputStream to use
s)

Reconstitute the SparseBitSet instance from a stream (i.e., deserialize it).

protected final void
resize(int
the desired address to be included in the set
index)

Resize the bit array.

public void
set(int
a bit index
i)

Sets the bit at the specified index.

public void
set(int
a bit index
i, boolean
a boolean value to set
value)

Sets the bit at the specified index to the specified value.

public void
set(int
index of the first bit to be set
i, int
index after the last bit to be se
j)

Sets the bits from the specified i (inclusive) to the specified j (exclusive) to true.

public void
set(int
index of the first bit to be set
i, int
index after the last bit to be set
j, boolean
to which to set the selected bits
value)

Sets the bits from the specified i (inclusive) to the specified j (exclusive) to the specified value.

protected final void
setScanner(int
the bit (inclusive) at which to start the scan
i, int
the bit (exclusive) at which to stop the scan
j, SparseBitSet
a SparseBitSet, if needed, the second SparseBitSet in the operation
b, SparseBitSet.AbstractStrategy
the AbstractStrategy class defining the operation to be executed
op)

Scans over the bit set (and a second bit set if part of the operation) are all performed by this method.

public int

Returns:

the number of bits (true and false) nominally in this bit set at this moment
size()

Returns the number of bits of space nominally in use by this SparseBitSet to represent bit values.

public String

Returns:

a String detailing the statistics of the bit set
statistics()

Convenience method for statistics if the individual results are not needed.

public String

Returns:

a String detailing the statistics of the bit set
statistics(String[]
an array for the individual results (if not null)
values)

Determine, and create a String with the bit set statistics.

protected final void
statisticsUpdate()

The entirety of the bit set is examined, and the various statistics of the bit set (size, length, cardinality, hashCode, etc.) are computed.

protected static void
throwIndexOutOfBoundsException(int
lower bound for a operation
i, int
upper bound for a operation
j)

Throw the exception to indicate a range error.

public String

Returns:

a String representation of this SparseBitSet
toString()

Overrides java.lang.Object.toString.

Returns a string representation of this bit set.

public void
toStringCompaction(int
the maximum count of a run of bits that are shown as individual entries in a toString() conversion. If 0, all bits are shown individually.
count)

Sequences of set bits longer than this value are shown by toString() as a "sub-sequence," in the form a..b.

public void
toStringCompaction(boolean
if true, change the default value
change)

If change is true, the current value of the toStringCompaction() value is made the default value for all SparseBitSets created from this point onward in this JVM.

private void
writeObject(ObjectOutputStream
the ObjectOutputStream to which to write the serialized object
s)

Save the state of the SparseBitSet instance to a stream (i.e., serialize it).

public void
xor(int
a bit index
i, boolean
a boolean value to XOR with that bit
value)

Performs a logical XOR of the addressed target bit with the argument value.

public void
xor(int
index of the first bit to be included in the operation
i, int
index after the last bit to included in the operation
j, SparseBitSet
the SparseBitSet with which to perform the XOR operation with this SparseBitSet
b)

Performs a logical XOR of this bit set with the bit set argument within the given range.

public void
xor(SparseBitSet
the SparseBitSet with which to perform the XOR operation with thisSparseBitSet
b)

Performs a logical XOR of this bit set with the bit set argument.

public static SparseBitSet

Returns:

a new SparseBitSet representing the XOR of the two sets
xor(SparseBitSet
a SparseBitSet
a, SparseBitSet
another SparseBitSet
b)

Performs a logical XOR of the two given SparseBitSets.

Inherited from java.lang.Object:
finalizegetClassnotifynotifyAllwaitwaitwait