Class SparseBitSet
- java.lang.Object
-
- com.zaxxer.sparsebits.SparseBitSet
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Cloneable
public class SparseBitSet extends java.lang.Object implements java.lang.Cloneable, java.io.Serializable
This class implements a set of bits that grows as needed. Each bit of the bit set represents aboolean
value. The values of aSparseBitSet
are indexed by non-negative integers. Individual indexed values may be examined, set, cleared, or modified by logical operations. OneSparseBitSet
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
isInteger.MAX_VALUE
, which means the bits of aSparseBitSet
are labelled0
..Integer.MAX_VALUE − 1
. After the last set bit of aSparseBitSet
, 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 labelledInteger.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 aNullPointerException
.A
SparseBitSet
is not safe for multi-threaded use without external synchronization.- Since:
- 1.6
- Version:
- 1.0, 2009-03-17
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected 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.static class
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
Fields Modifier and Type Field Description protected static SparseBitSet.AndNotStrategy
andNotStrategy
Word and block andNot strategy.protected static SparseBitSet.AndStrategy
andStrategy
Word and block and strategy.protected long[][][]
bits
The storage for this SparseBitSet.protected 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 SparseBitSet.Cache
cache
Holds reference to the cache of statistics values computed by the UpdateStrategyprotected static SparseBitSet.ClearStrategy
clearStrategy
Word and block clear strategy.protected int
compactionCount
This value controls for format of the toString() output.(package private) static int
compactionCountDefault
The compaction count default.protected static SparseBitSet.CopyStrategy
copyStrategy
Word and block copy strategy.protected SparseBitSet.EqualsStrategy
equalsStrategy
Word and block equals strategy.protected static SparseBitSet.FlipStrategy
flipStrategy
Word and block flip strategy.protected static 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 SparseBitSet.IntersectsStrategy
intersectsStrategy
Word and block intersects strategy.protected static int
LENGTH2
LENGTH2 is the number of entries in the any level2 area.protected static int
LENGTH2_SIZE
LENGTH2_SIZE is maximum index of a LEVEL2 page.protected static int
LENGTH3
LENGTH3 is the number of entries in the any level3 block.protected static int
LENGTH3_SIZE
LENGTH3_SIZE is maximum index of a LEVEL3 page.protected static int
LENGTH4
The number of bits in a long value.protected static int
LENGTH4_SIZE
LENGTH4_SIZE is maximum index of a bit in a LEVEL4 word.protected static int
LEVEL1
LEVEL1 is the number of bits of the level1 address.protected static int
LEVEL2
LEVEL2 is the number of bits of the level2 address.protected static int
LEVEL3
LEVEL3 is the number of bits of the level3 address.protected static int
LEVEL4
The label (index) of a bit in the bit set is essentially broken into 4 "levels".protected static int
MASK2
MASK2 is the mask to extract the LEVEL2 address from a word index (after shifting by SHIFT3 and SHIFT2).protected static int
MASK3
MASK3 is the mask to extract the LEVEL3 address from a word index (after shifting by SHIFT3).protected static int
MAX_LENGTH1
MAX_LENGTH1 is the maximum number of entries in the level1 set array.protected static SparseBitSet.OrStrategy
orStrategy
Word and block or strategy.private static long
serialVersionUID
serialVersionUIDprotected static SparseBitSet.SetStrategy
setStrategy
Word and block set strategy.protected static 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 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 int
SHIFT3
The shift to create the word index.protected long[]
spare
A spare level 3 block is kept for use when scanning.protected static int
UNIT
UNIT is the greatest number of bits that can be held in one level1 entry.protected SparseBitSet.UpdateStrategy
updateStrategy
Word and block update strategy.protected static SparseBitSet.XorStrategy
xorStrategy
Word and block xor strategy.(package private) static long[]
ZERO_BLOCK
An empty level 3 block is kept for use when scanning.
-
Constructor Summary
Constructors Modifier Constructor Description SparseBitSet()
Constructs an empty bit set with the default initial size.SparseBitSet(int nbits)
Creates a bit set whose initial size is large enough to efficiently represent bits with indices in the range0
through at leastnbits-1
.protected
SparseBitSet(int capacity, int compactionCount)
Constructor for a new (sparse) bit set.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
and(int i, boolean value)
Performs a logical AND of the addressed target bit with the argument value.void
and(int i, int j, SparseBitSet b)
Performs a logical AND of this target bit set with the argument bit set within the given range of bits.void
and(SparseBitSet b)
Performs a logical AND of this target bit set with the argument bit set.static SparseBitSet
and(SparseBitSet a, SparseBitSet b)
Performs a logical AND of the two givenSparseBitSet
s.void
andNot(int i, boolean value)
Performs a logical AndNOT of the addressed target bit with the argument value.void
andNot(int i, int j, SparseBitSet b)
Performs a logical AndNOT of this target bit set with the argument bit set within the given range of bits.void
andNot(SparseBitSet b)
Performs a logical AndNOT of this target bit set with the argument bit set.static SparseBitSet
andNot(SparseBitSet a, SparseBitSet b)
Creates a bit set from thie firstSparseBitSet
whose corresponding bits are cleared by the set bits of the secondSparseBitSet
.int
cardinality()
Returns the number of bits set totrue
in thisSparseBitSet
.void
clear()
Sets all of the bits in thisSparseBitSet
tofalse
.void
clear(int i)
Sets the bit at the specified index tofalse
.void
clear(int i, int j)
Sets the bits from the specifiedi
(inclusive) to the specifiedj
(exclusive) tofalse
.SparseBitSet
clone()
Cloning thisSparseBitSet
produces a newSparseBitSet
that is equal() to it.protected void
constructorHelper()
Intializes all the additional objects required for correct operation.boolean
equals(java.lang.Object obj)
Compares this object against the specified object.void
flip(int i)
Sets the bit at the specified index to the complement of its current value.void
flip(int i, int j)
Sets each bit from the specifiedi
(inclusive) to the specifiedj
(exclusive) to the complement of its current value.boolean
get(int i)
Returns the value of the bit with the specified index.SparseBitSet
get(int i, int j)
Returns a newSparseBitSet
composed of bits from thisSparseBitSet
fromi
(inclusive) toj
(exclusive).int
hashCode()
Returns a hash code value for this bit set.boolean
intersects(int i, int j, SparseBitSet b)
Returns true if the specifiedSparseBitSet
has any bits within the given rangei
(inclusive) toj
(exclusive) set totrue
that are also set totrue
in the same range of thisSparseBitSet
.boolean
intersects(SparseBitSet b)
Returns true if the specifiedSparseBitSet
has any bits set totrue
that are also set totrue
in thisSparseBitSet
.boolean
isEmpty()
Returns true if thisSparseBitSet
contains no bits that are set totrue
.int
length()
Returns the "logical length" of thisSparseBitSet
: the index of the highest set bit in theSparseBitSet
plus one.int
nextClearBit(int i)
Returns the index of the first bit that is set tofalse
that occurs on or after the specified starting index.int
nextSetBit(int i)
Returns the index of the first bit that is set totrue
that occurs on or after the specified starting index.protected void
nullify(int start)
Clear out a part of the set array with nulls, from the given start to the end of the array.void
or(int i, boolean value)
Performs a logical OR of the addressed target bit with the argument value.void
or(int i, int j, SparseBitSet b)
Performs a logical OR of the addressed target bit with the argument value within the given range.void
or(SparseBitSet b)
Performs a logical OR of this bit set with the bit set argument.static SparseBitSet
or(SparseBitSet a, SparseBitSet b)
Performs a logical OR of the two givenSparseBitSet
s.int
previousClearBit(int i)
Returns the index of the nearest bit that is set tofalse
that occurs on or before the specified starting index.int
previousSetBit(int i)
Returns the index of the nearest bit that is set totrue
that occurs on or before the specified starting index.private void
readObject(java.io.ObjectInputStream s)
Reconstitute theSparseBitSet
instance from a stream (i.e., deserialize it).protected void
resize(int index)
Resize the bit array.void
set(int i)
Sets the bit at the specified index.void
set(int i, boolean value)
Sets the bit at the specified index to the specified value.void
set(int i, int j)
Sets the bits from the specifiedi
(inclusive) to the specifiedj
(exclusive) totrue
.void
set(int i, int j, boolean value)
Sets the bits from the specifiedi
(inclusive) to the specifiedj
(exclusive) to the specified value.protected void
setScanner(int i, int j, SparseBitSet b, SparseBitSet.AbstractStrategy op)
Scans over the bit set (and a second bit set if part of the operation) are all performed by this method.int
size()
Returns the number of bits of space nominally in use by thisSparseBitSet
to represent bit values.java.lang.String
statistics()
Convenience method for statistics if the individual results are not needed.java.lang.String
statistics(java.lang.String[] values)
Determine, and create a String with the bit set statistics.protected 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 i, int j)
Throw the exception to indicate a range error.java.lang.String
toString()
Returns a string representation of this bit set.void
toStringCompaction(boolean change)
If change istrue
, the current value of the toStringCompaction() value is made the default value for allSparseBitSet
s created from this point onward in this JVM.void
toStringCompaction(int count)
Sequences of set bits longer than this value are shown bytoString()
as a "sub-sequence," in the forma..b
.private void
writeObject(java.io.ObjectOutputStream s)
Save the state of theSparseBitSet
instance to a stream (i.e., serialize it).void
xor(int i, boolean value)
Performs a logical XOR of the addressed target bit with the argument value.void
xor(int i, int j, SparseBitSet b)
Performs a logical XOR of this bit set with the bit set argument within the given range.void
xor(SparseBitSet b)
Performs a logical XOR of this bit set with the bit set argument.static SparseBitSet
xor(SparseBitSet a, SparseBitSet b)
Performs a logical XOR of the two givenSparseBitSet
s.
-
-
-
Field Detail
-
compactionCount
protected transient int compactionCount
This value controls for format of the toString() output.- See Also:
toStringCompaction(int)
-
compactionCountDefault
static int compactionCountDefault
The compaction count default.
-
bits
protected transient long[][][] bits
The storage for this SparseBitSet. The ith bit is stored in a word represented by a long value, and is at bit positioni % 64
within that word (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).The words are organized into blocks, and the blocks are accessed by two additional levels of array indexing.
-
bitsLength
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. Note: this not the value returned by length().- See Also:
resize(int)
,length()
-
LENGTH4
protected static final int LENGTH4
The number of bits in a long value.- See Also:
- Constant Field Values
-
INDEX_SIZE
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.- See Also:
- Constant Field Values
-
LEVEL4
protected static final int LEVEL4
The label (index) of a bit in the bit set is essentially broken into 4 "levels". Respectively (from the least significant end), level4, the address within word, the address within a level3 block, the address within a level2 area, and the level1 address of that area within the set. LEVEL4 is the number of bits of the level4 address (number of bits need to address the bits in a long)- See Also:
- Constant Field Values
-
LEVEL3
protected static final int LEVEL3
LEVEL3 is the number of bits of the level3 address.- See Also:
- Constant Field Values
-
LEVEL2
protected static final int LEVEL2
LEVEL2 is the number of bits of the level2 address.- See Also:
- Constant Field Values
-
LEVEL1
protected static final int LEVEL1
LEVEL1 is the number of bits of the level1 address.- See Also:
- Constant Field Values
-
MAX_LENGTH1
protected static final int MAX_LENGTH1
MAX_LENGTH1 is the maximum number of entries in the level1 set array.- See Also:
- Constant Field Values
-
LENGTH2
protected static final int LENGTH2
LENGTH2 is the number of entries in the any level2 area.- See Also:
- Constant Field Values
-
LENGTH3
protected static final int LENGTH3
LENGTH3 is the number of entries in the any level3 block.- See Also:
- Constant Field Values
-
SHIFT3
protected static final int SHIFT3
The shift to create the word index. (I.e., move it to the right end)- See Also:
- Constant Field Values
-
MASK3
protected static final int MASK3
MASK3 is the mask to extract the LEVEL3 address from a word index (after shifting by SHIFT3).- See Also:
- Constant Field Values
-
SHIFT2
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).- See Also:
- Constant Field Values
-
UNIT
protected static final int UNIT
UNIT is the greatest number of bits that can be held in one level1 entry. That is, bits per word by words per level3 block by blocks per level2 area.- See Also:
- Constant Field Values
-
MASK2
protected static final int MASK2
MASK2 is the mask to extract the LEVEL2 address from a word index (after shifting by SHIFT3 and SHIFT2).- See Also:
- Constant Field Values
-
SHIFT1
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).- See Also:
- Constant Field Values
-
LENGTH2_SIZE
protected static final int LENGTH2_SIZE
LENGTH2_SIZE is maximum index of a LEVEL2 page.- See Also:
- Constant Field Values
-
LENGTH3_SIZE
protected static final int LENGTH3_SIZE
LENGTH3_SIZE is maximum index of a LEVEL3 page.- See Also:
- Constant Field Values
-
LENGTH4_SIZE
protected static final int LENGTH4_SIZE
LENGTH4_SIZE is maximum index of a bit in a LEVEL4 word.- See Also:
- Constant Field Values
-
cache
protected transient SparseBitSet.Cache cache
Holds reference to the cache of statistics values computed by the UpdateStrategy- See Also:
SparseBitSet.Cache
,SparseBitSet.UpdateStrategy
-
spare
protected transient long[] spare
A spare level 3 block is kept for use when scanning. When a target block is needed, and there is not already one in the bit set, the spare is provided. If non-zero values are placed into this block, it is moved to the resulting set, and a new spare is acquired. Note: a new spare needs to be allocated when the set is cloned (so that the spare is not shared between two sets).
-
ZERO_BLOCK
static final long[] ZERO_BLOCK
An empty level 3 block is kept for use when scanning. When a source block is needed, and there is not already one in the corresponding bit set, the ZERO_BLOCK is used (as a read-only block). It is a source of zero values so that code does not have to test for a null level3 block. This is a static block shared everywhere.
-
serialVersionUID
private static final long serialVersionUID
serialVersionUID- See Also:
- Constant Field Values
-
andStrategy
protected static final transient SparseBitSet.AndStrategy andStrategy
Word and block and strategy.
-
andNotStrategy
protected static final transient SparseBitSet.AndNotStrategy andNotStrategy
Word and block andNot strategy.
-
clearStrategy
protected static final transient SparseBitSet.ClearStrategy clearStrategy
Word and block clear strategy.
-
copyStrategy
protected static final transient SparseBitSet.CopyStrategy copyStrategy
Word and block copy strategy.
-
equalsStrategy
protected transient SparseBitSet.EqualsStrategy equalsStrategy
Word and block equals strategy.
-
flipStrategy
protected static final transient SparseBitSet.FlipStrategy flipStrategy
Word and block flip strategy.
-
intersectsStrategy
protected static transient SparseBitSet.IntersectsStrategy intersectsStrategy
Word and block intersects strategy.
-
orStrategy
protected static final transient SparseBitSet.OrStrategy orStrategy
Word and block or strategy.
-
setStrategy
protected static final transient SparseBitSet.SetStrategy setStrategy
Word and block set strategy.
-
updateStrategy
protected transient SparseBitSet.UpdateStrategy updateStrategy
Word and block update strategy.
-
xorStrategy
protected static final transient SparseBitSet.XorStrategy xorStrategy
Word and block xor strategy.
-
-
Constructor Detail
-
SparseBitSet
protected SparseBitSet(int capacity, int compactionCount) throws java.lang.NegativeArraySizeException
Constructor for a new (sparse) bit set. All bits initially are effectivelyfalse
. This is a internal constructor that collects all the needed actions to initialise the bit set.The capacity is taken to be a suggestion for a size of the bit set, in bits. An appropiate table size (a power of two) is then determined and used. The size will be grown as needed to accomodate any bits addressed during the use of the bit set.
- Parameters:
capacity
- a size in terms of bitscompactionCount
- the compactionCount to be inherited (for internal generation)- Throws:
java.lang.NegativeArraySizeException
- if the specified initial size is negative- Since:
- 1.6
-
SparseBitSet
public SparseBitSet()
Constructs an empty bit set with the default initial size. Initially all bits are effectivelyfalse
.- Since:
- 1.6
-
SparseBitSet
public SparseBitSet(int nbits) throws java.lang.NegativeArraySizeException
Creates a bit set whose initial size is large enough to efficiently represent bits with indices in the range0
through at leastnbits-1
. Initially all bits are effectivelyfalse
.No guarantees are given for how large or small the actual object will be. The setting of bits above the given range is permitted (and will perhaps eventually cause resizing).
- Parameters:
nbits
- the initial provisional length of the SparseBitSet- Throws:
java.lang.NegativeArraySizeException
- if the specified initial length is negative- Since:
- 1.6
- See Also:
SparseBitSet()
-
-
Method Detail
-
and
public void and(int i, boolean value) throws java.lang.IndexOutOfBoundsException
Performs a logical AND of the addressed target bit with the argument value. This bit set is modified so that the addressed bit has the valuetrue
if and only if it both initially had the valuetrue
and the argument value is alsotrue
.- Parameters:
i
- a bit indexvalue
- a boolean value to AND with that bit- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE- Since:
- 1.6
-
and
public void and(int i, int j, SparseBitSet b) throws java.lang.IndexOutOfBoundsException
Performs a logical AND of this target bit set with the argument bit set within the given range of bits. Within the range, this bit set is modified so that each bit in it has the valuetrue
if and only if it both initially had the valuetrue
and the corresponding bit in the bit set argument also had the valuetrue
. Outside the range, this set is not changed.- Parameters:
i
- index of the first bit to be included in the operationj
- index after the last bit to included in the operationb
- a SparseBitSet- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
-
and
public void and(SparseBitSet b)
Performs a logical AND of this target bit set with the argument bit set. This bit set is modified so that each bit in it has the valuetrue
if and only if it both initially had the valuetrue
and the corresponding bit in the bit set argument also had the valuetrue
.- Parameters:
b
- a SparseBitSet- Since:
- 1.6
-
and
public static SparseBitSet and(SparseBitSet a, SparseBitSet b)
Performs a logical AND of the two givenSparseBitSet
s. The returnedSparseBitSet
is created so that each bit in it has the valuetrue
if and only if both the given sets initially had the corresponding bitstrue
, otherwisefalse
.- Parameters:
a
- a SparseBitSetb
- another SparseBitSet- Returns:
- a new SparseBitSet representing the AND of the two sets
- Since:
- 1.6
-
andNot
public void andNot(int i, boolean value)
Performs a logical AndNOT of the addressed target bit with the argument value. This bit set is modified so that the addressed bit has the valuetrue
if and only if it both initially had the valuetrue
and the argument value isfalse
.- Parameters:
i
- a bit indexvalue
- a boolean value to AndNOT with that bit- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE- Since:
- 1.6
-
andNot
public void andNot(int i, int j, SparseBitSet b) throws java.lang.IndexOutOfBoundsException
Performs a logical AndNOT of this target bit set with the argument bit set within the given range of bits. Within the range, this bit set is modified so that each bit in it has the valuetrue
if and only if it both initially had the valuetrue
and the corresponding bit in the bit set argument has the valuefalse
. Outside the range, this set is not changed.- Parameters:
i
- index of the first bit to be included in the operationj
- index after the last bit to included in the operationb
- the SparseBitSet with which to mask this SparseBitSet- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
-
andNot
public void andNot(SparseBitSet b)
Performs a logical AndNOT of this target bit set with the argument bit set. This bit set is modified so that each bit in it has the valuetrue
if and only if it both initially had the valuetrue
and the corresponding bit in the bit set argument has the valuefalse
.- Parameters:
b
- the SparseBitSet with which to mask this SparseBitSet- Since:
- 1.6
-
andNot
public static SparseBitSet andNot(SparseBitSet a, SparseBitSet b)
Creates a bit set from thie firstSparseBitSet
whose corresponding bits are cleared by the set bits of the secondSparseBitSet
. The resulting bit set is created so that a bit in it has the valuetrue
if and only if the corresponding bit in theSparseBitSet
of the first is set, and that same corresponding bit is not set in theSparseBitSet
of the second argument.- Parameters:
a
- a SparseBitSetb
- another SparseBitSet- Returns:
- a new SparseBitSet representing the AndNOT of the two sets
- Since:
- 1.6
-
cardinality
public int cardinality()
Returns the number of bits set totrue
in thisSparseBitSet
.- Returns:
- the number of bits set to true in this SparseBitSet
- Since:
- 1.6
-
clear
public void clear(int i)
Sets the bit at the specified index tofalse
.- Parameters:
i
- a bit index.- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE.- Since:
- 1.6
-
clear
public void clear(int i, int j) throws java.lang.IndexOutOfBoundsException
Sets the bits from the specifiedi
(inclusive) to the specifiedj
(exclusive) tofalse
.- Parameters:
i
- index of the first bit to be clearedj
- index after the last bit to be cleared- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
-
clear
public void clear()
Sets all of the bits in thisSparseBitSet
tofalse
.- Since:
- 1.6
-
clone
public SparseBitSet clone()
Cloning thisSparseBitSet
produces a newSparseBitSet
that is equal() to it. The clone of the bit set is another bit set that has exactly the same bits set totrue
as this bit set.Note: the actual space allocated to the clone tries to minimise the actual amount of storage allocated to hold the bits, while still trying to keep access to the bits being a rapid as possible. Since the space allocated to a
SparseBitSet
is not normally decreased, replacing a bit set by its clone may be a way of both managing memory consumption and improving the rapidity of access.- Overrides:
clone
in classjava.lang.Object
- Returns:
- a clone of this SparseBitSet
- Since:
- 1.6
-
equals
public boolean equals(java.lang.Object obj)
Compares this object against the specified object. The result istrue
if and only if the argument is notnull
and is aSparseBitSet
object that has exactly the same bits set totrue
as this bit set. That is, for every nonnegativei
indexing a bit in the set,((SparseBitSet)obj).get(i) == this.get(i)
must be true.- Overrides:
equals
in classjava.lang.Object
- Parameters:
obj
- the Object with which to compare- Returns:
true
if the objects are equivalent;false
otherwise.- Since:
- 1.6
-
flip
public void flip(int i)
Sets the bit at the specified index to the complement of its current value.- Parameters:
i
- the index of the bit to flip- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE- Since:
- 1.6
-
flip
public void flip(int i, int j) throws java.lang.IndexOutOfBoundsException
Sets each bit from the specifiedi
(inclusive) to the specifiedj
(exclusive) to the complement of its current value.- Parameters:
i
- index of the first bit to flipj
- index after the last bit to flip- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or is equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
-
get
public boolean get(int i)
Returns the value of the bit with the specified index. The value istrue
if the bit with the indexi
is currently set in thisSparseBitSet
; otherwise, the result isfalse
.- Parameters:
i
- the bit index- Returns:
- the boolean value of the bit with the specified index.
- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE- Since:
- 1.6
-
get
public SparseBitSet get(int i, int j) throws java.lang.IndexOutOfBoundsException
Returns a newSparseBitSet
composed of bits from thisSparseBitSet
fromi
(inclusive) toj
(exclusive).- Parameters:
i
- index of the first bit to includej
- index after the last bit to include- Returns:
- a new SparseBitSet from a range of this SparseBitSet
- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or is equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
-
hashCode
public int hashCode()
Returns a hash code value for this bit set. The hash code depends only on which bits have been set within thisSparseBitSet
. The algorithm used to compute it may be described as follows.Suppose the bits in the
SparseBitSet
were to be stored in an array oflong
integers called, say,bits
, in such a manner that biti
is set in theSparseBitSet
(for nonnegative values ofi
) if and only if the expression((i>>6) < bits.length) && ((bits[i>>6] & (1L << (bit & 0x3F))) != 0)
is true. Then the following definition of thehashCode
method would be a correct implementation of the actual algorithm:public int hashCode() { long hash = 1234L; for( int i = bits.length; --i >= 0; ) hash ^= bits[i] * (i + 1); return (int)((h >> 32) ^ h); }
Note that the hash code values change if the set of bits is altered.- Overrides:
hashCode
in classjava.lang.Object
- Returns:
- a hash code value for this bit set
- Since:
- 1.6
- See Also:
Object.equals(Object)
,Hashtable
-
intersects
public boolean intersects(int i, int j, SparseBitSet b) throws java.lang.IndexOutOfBoundsException
Returns true if the specifiedSparseBitSet
has any bits within the given rangei
(inclusive) toj
(exclusive) set totrue
that are also set totrue
in the same range of thisSparseBitSet
.- Parameters:
i
- index of the first bit to includej
- index after the last bit to includeb
- the SparseBitSet with which to intersect- Returns:
- the boolean indicating whether this SparseBitSet intersects the specified SparseBitSet
- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
-
intersects
public boolean intersects(SparseBitSet b)
Returns true if the specifiedSparseBitSet
has any bits set totrue
that are also set totrue
in thisSparseBitSet
.- Parameters:
b
- a SparseBitSet with which to intersect- Returns:
- boolean indicating whether this SparseBitSet intersects the specified SparseBitSet
- Since:
- 1.6
-
isEmpty
public boolean isEmpty()
Returns true if thisSparseBitSet
contains no bits that are set totrue
.- Returns:
- the boolean indicating whether this SparseBitSet is empty
- Since:
- 1.6
-
length
public int length()
Returns the "logical length" of thisSparseBitSet
: the index of the highest set bit in theSparseBitSet
plus one. Returns zero if theSparseBitSet
contains no set bits.- Returns:
- the logical length of this SparseBitSet
- Since:
- 1.6
-
nextClearBit
public int nextClearBit(int i)
Returns the index of the first bit that is set tofalse
that occurs on or after the specified starting index.- Parameters:
i
- the index to start checking from (inclusive)- Returns:
- the index of the next clear bit, or -1 if there is no such bit
- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative- Since:
- 1.6
-
nextSetBit
public int nextSetBit(int i)
Returns the index of the first bit that is set totrue
that occurs on or after the specified starting index. If no such it exists then -1 is returned.To iterate over the
true
bits in aSparseBitSet sbs
, use the following loop:for( int i = sbbits.nextSetBit(0); i >= 0; i = sbbits.nextSetBit(i+1) ) { // operate on index i here }
- Parameters:
i
- the index to start checking from (inclusive)- Returns:
- the index of the next set bit
- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative- Since:
- 1.6
-
previousClearBit
public int previousClearBit(int i)
Returns the index of the nearest bit that is set tofalse
that occurs on or before the specified starting index. If no such bit exists, or if-1
is given as the starting index, then-1
is returned.- Parameters:
i
- the index to start checking from (inclusive)- Returns:
- the index of the previous clear bit, or
-1
if there is no such bit - Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is less than-1
- Since:
- 1.2
- See Also:
BitSet.previousClearBit(int)
-
previousSetBit
public int previousSetBit(int i)
Returns the index of the nearest bit that is set totrue
that occurs on or before the specified starting index. If no such bit exists, or if-1
is given as the starting index, then-1
is returned.- Parameters:
i
- the index to start checking from (inclusive)- Returns:
- the index of the previous set bit, or
-1
if there is no such bit - Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is less than-1
- Since:
- 1.2
- See Also:
BitSet.previousSetBit(int)
-
or
public void or(int i, boolean value)
Performs a logical OR of the addressed target bit with the argument value. This bit set is modified so that the addressed bit has the valuetrue
if and only if it both initially had the valuetrue
or the argument value istrue
.- Parameters:
i
- a bit indexvalue
- a boolean value to OR with that bit- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE- Since:
- 1.6
-
or
public void or(int i, int j, SparseBitSet b) throws java.lang.IndexOutOfBoundsException
Performs a logical OR of the addressed target bit with the argument value within the given range. This bit set is modified so that within the range a bit in it has the valuetrue
if and only if it either already had the valuetrue
or the corresponding bit in the bit set argument has the valuetrue
. Outside the range this set is not changed.- Parameters:
i
- index of the first bit to be included in the operationj
- index after the last bit to included in the operationb
- the SparseBitSet with which to perform the OR operation with this SparseBitSet- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
-
or
public void or(SparseBitSet b)
Performs a logical OR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the valuetrue
if and only if it either already had the valuetrue
or the corresponding bit in the bit set argument has the valuetrue
.- Parameters:
b
- the SparseBitSet with which to perform the OR operation with this SparseBitSet- Since:
- 1.6
-
or
public static SparseBitSet or(SparseBitSet a, SparseBitSet b)
Performs a logical OR of the two givenSparseBitSet
s. The returnedSparseBitSet
is created so that a bit in it has the valuetrue
if and only if it either had the valuetrue
in the set given by the first arguemetn or had the valuetrue
in the second argument, otherwisefalse
.- Parameters:
a
- a SparseBitSetb
- another SparseBitSet- Returns:
- new SparseBitSet representing the OR of the two sets
- Since:
- 1.6
-
set
public void set(int i)
Sets the bit at the specified index.- Parameters:
i
- a bit index- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE- Since:
- 1.6
-
set
public void set(int i, boolean value)
Sets the bit at the specified index to the specified value.- Parameters:
i
- a bit indexvalue
- a boolean value to set- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE- Since:
- 1.6
-
set
public void set(int i, int j) throws java.lang.IndexOutOfBoundsException
Sets the bits from the specifiedi
(inclusive) to the specifiedj
(exclusive) totrue
.- Parameters:
i
- index of the first bit to be setj
- index after the last bit to be se- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or is equal to Integer.MAX_INT, orj
is negative, ori
is larger thanj
.- Since:
- 1.6
-
set
public void set(int i, int j, boolean value)
Sets the bits from the specifiedi
(inclusive) to the specifiedj
(exclusive) to the specified value.- Parameters:
i
- index of the first bit to be setj
- index after the last bit to be setvalue
- to which to set the selected bits- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or is equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
-
size
public int size()
Returns the number of bits of space nominally in use by thisSparseBitSet
to represent bit values. The count of bits in the set is the (label of the last set bit) + 1 - (the label of the first set bit).- Returns:
- the number of bits (true and false) nominally in this bit set at this moment
- Since:
- 1.6
-
statistics
public java.lang.String statistics()
Convenience method for statistics if the individual results are not needed.- Returns:
- a String detailing the statistics of the bit set
- Since:
- 1.6
- See Also:
statistics(String[])
-
statistics
public java.lang.String statistics(java.lang.String[] values)
Determine, and create a String with the bit set statistics. The statistics include: Size, Length, Cardinality, Total words (i.e., the total number of 64-bit "words"), Set array length (i.e., the number of references that can be held by the top level array, Level2 areas in use, Level3 blocks in use,, Level2 pool size, Level3 pool size, and the Compaction count.This method is intended for diagnostic use (as it is relatively expensive in time), but can be useful in understanding an application's use of a
SparseBitSet
.- Parameters:
values
- an array for the individual results (if not null)- Returns:
- a String detailing the statistics of the bit set
- Since:
- 1.6
-
toString
public java.lang.String toString()
Returns a string representation of this bit set. For every index for which thisSparseBitSet
contains a bit in the set state, the decimal representation of that index is included in the result. Such indices are listed in order from lowest to highest. If there is a subsequence of set bits longer than the value given by toStringCompaction, the subsequence is represented by the value for the first and the last values, with ".." between them. The individual bits, or the representation of sub-sequences are separated by ", " (a comma and a space) and surrounded by braces, resulting in a compact string showing (a variant of) the usual mathematical notation for a set of integers.
Example (with the default value of 2 for subsequences):SparseBitSet drPepper = new SparseBitSet();
NowdrPepper.toString()
returns "{}
".
drPepper.set(2);
NowdrPepper.toString()
returns "{2}
".
drPepper.set(3, 4); drPepper.set(10);
NowdrPepper.toString()
returns "{2..4, 10}
".
This method is intended for diagnostic use (as it is relatively expensive in time), but can be useful in interpreting problems in an application's use of aSparseBitSet
.- Overrides:
toString
in classjava.lang.Object
- Returns:
- a String representation of this SparseBitSet
- Since:
- 1.6
- See Also:
toStringCompaction(int length)
-
toStringCompaction
public void toStringCompaction(int count)
Sequences of set bits longer than this value are shown bytoString()
as a "sub-sequence," in the forma..b
. Setting this value to zero causes each set bit to be listed individually. The default default value is 2 (which means sequences of three or more bits set are shown as a subsequence, and all other set bits are listed individually).Note: this value will be passed to
SparseBitSet
s that may be created within or as a result of the operations on this bit set, or, for static methods, from the value belonging to the first parameter.- Parameters:
count
- the maximum count of a run of bits that are shown as individual entries in atoString
() conversion. If 0, all bits are shown individually.- Since:
- 1.6
- See Also:
toString()
-
toStringCompaction
public void toStringCompaction(boolean change)
If change istrue
, the current value of the toStringCompaction() value is made the default value for allSparseBitSet
s created from this point onward in this JVM.- Parameters:
change
- if true, change the default value- Since:
- 1.6
-
xor
public void xor(int i, boolean value)
Performs a logical XOR of the addressed target bit with the argument value. This bit set is modified so that the addressed bit has the valuetrue
if and only one of the following statements holds:- The addressed bit initially had the value
true
, and the value of the argument isfalse
. - The bit initially had the value
false
, and the value of the argument istrue
.
- Parameters:
i
- a bit indexvalue
- a boolean value to XOR with that bit- Throws:
java.lang.IndexOutOfBoundsException
- if the specified index is negative or equal to Integer.MAX_VALUE- Since:
- 1.6
- The addressed bit initially had the value
-
xor
public void xor(int i, int j, SparseBitSet b) throws java.lang.IndexOutOfBoundsException
Performs a logical XOR of this bit set with the bit set argument within the given range. This resulting bit set is computed so that a bit within the range in it has the valuetrue
if and only if one of the following statements holds:- The bit initially had the value
true
, and the corresponding bit in the argument set has the valuefalse
. - The bit initially had the value
false
, and the corresponding bit in the argument set has the valuetrue
.
- Parameters:
i
- index of the first bit to be included in the operationj
- index after the last bit to included in the operationb
- the SparseBitSet with which to perform the XOR operation with this SparseBitSet- Throws:
java.lang.IndexOutOfBoundsException
- ifi
is negative or equal to Integer.MAX_VALUE, orj
is negative, ori
is larger thanj
- Since:
- 1.6
- The bit initially had the value
-
xor
public void xor(SparseBitSet b)
Performs a logical XOR of this bit set with the bit set argument. This resulting bit set is computed so that a bit in it has the valuetrue
if and only if one of the following statements holds:- The bit initially had the value
true
, and the corresponding bit in the argument set has the valuefalse
. - The bit initially had the value
false
, and the corresponding bit in the argument set has the valuetrue
.
- Parameters:
b
- the SparseBitSet with which to perform the XOR operation with thisSparseBitSet- Since:
- 1.6
- The bit initially had the value
-
xor
public static SparseBitSet xor(SparseBitSet a, SparseBitSet b)
Performs a logical XOR of the two givenSparseBitSet
s. The resulting bit set is created so that a bit in it has the valuetrue
if and only if one of the following statements holds:- A bit in the first argument has the value
true
, and the corresponding bit in the second argument has the valuefalse
. - A bit in the first argument has the value
false
, and the corresponding bit in the second argument has the valuetrue
.
- Parameters:
a
- a SparseBitSetb
- another SparseBitSet- Returns:
- a new SparseBitSet representing the XOR of the two sets
- Since:
- 1.6
- A bit in the first argument has the value
-
throwIndexOutOfBoundsException
protected static void throwIndexOutOfBoundsException(int i, int j) throws java.lang.IndexOutOfBoundsException
Throw the exception to indicate a range error. TheString
constructed reports all the possible errors in one message.- Parameters:
i
- lower bound for a operationj
- upper bound for a operation- Throws:
java.lang.IndexOutOfBoundsException
- indicating the range is not valid- Since:
- 1.6
-
constructorHelper
protected final void constructorHelper()
Intializes all the additional objects required for correct operation.- Since:
- 1.6
-
nullify
protected final void nullify(int start)
Clear out a part of the set array with nulls, from the given start to the end of the array. If the given parameter is beyond the end of the bits array, nothing is changed.- Parameters:
start
- word index at which to start (inclusive)- Since:
- 1.6
-
resize
protected final void resize(int index)
Resize the bit array. Moves the entries in the the bits array of this SparseBitSet into an array whose size (which may be larger or smaller) is the given bit size (i.e., includes the bit whose index is one less that the given value). If the new array is smaller, the excess entries in the set array are discarded. If the new array is bigger, it is filled with nulls.- Parameters:
index
- the desired address to be included in the set- Since:
- 1.6
-
setScanner
protected final void setScanner(int i, int j, SparseBitSet b, SparseBitSet.AbstractStrategy op) throws java.lang.IndexOutOfBoundsException
Scans over the bit set (and a second bit set if part of the operation) are all performed by this method. The properties and the operation executed are defined by a given strategy, which must be derived from theAbstractStrategy
. The strategy defines how to operate on a single word, and on whole words that may or may not constitute a full block of words.- Parameters:
i
- the bit (inclusive) at which to start the scanj
- the bit (exclusive) at which to stop the scanb
- a SparseBitSet, if needed, the second SparseBitSet in the operationop
- the AbstractStrategy class defining the operation to be executed- Throws:
java.lang.IndexOutOfBoundsException
- Since:
- 1.6
- See Also:
SparseBitSet.AbstractStrategy
-
statisticsUpdate
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. Level arrays that are empty (i.e., all zero at level 3, all null at level 2) are replaced by null references, ensuring a normalized representation.- Since:
- 1.6
-
writeObject
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException, java.lang.InternalError
Save the state of theSparseBitSet
instance to a stream (i.e., serialize it).- Parameters:
s
- the ObjectOutputStream to which to write the serialized object- Throws:
java.io.IOException
- if an io error occursjava.lang.InternalError
- if the SparseBitSet representation is inconsistent- Since:
- 1.6
-
readObject
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, java.lang.ClassNotFoundException
Reconstitute theSparseBitSet
instance from a stream (i.e., deserialize it).- Parameters:
s
- the ObjectInputStream to use- Throws:
java.io.IOException
- if there is an io errorjava.lang.ClassNotFoundException
- if the stream contains an unidentified class- Since:
- 1.6
-
-