com.zaxxer.sparsebits.SparseBitSet

All Implemented Interfaces:: Serializable, Cloneable

public class SparseBitSet extends Object implements Cloneable, 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.

Since:

1.6

Version:

1.0, 2009-03-17

See Also:

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 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

Fields

Modifier and Type

Field

Description

protected static final SparseBitSet.AndNotStrategy

andNotStrategy

Word and block andNot strategy.

protected static final 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 UpdateStrategy

protected static final 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 final SparseBitSet.CopyStrategy

copyStrategy

Word and block copy strategy.

protected SparseBitSet.EqualsStrategy

equalsStrategy

Word and block equals strategy.

protected static final 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 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 SparseBitSet.OrStrategy

orStrategy

Word and block or strategy.

private static final long

serialVersionUID

serialVersionUID

protected static final 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 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 SparseBitSet.UpdateStrategy

updateStrategy

Word and block update strategy.

protected static final SparseBitSet.XorStrategy

xorStrategy

Word and block xor strategy.

(package private) static final 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 range 0 through at least nbits-1.

protected

SparseBitSet(int capacity, int compactionCount)

Constructor for a new (sparse) bit set.
Method Summary

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 given SparseBitSets.

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 first SparseBitSet whose corresponding bits are cleared by the set bits of the second SparseBitSet.

int

cardinality()

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

void

clear()

Sets all of the bits in this SparseBitSet to false.

void

clear(int i)

Sets the bit at the specified index to false.

void

clear(int i, int j)

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

SparseBitSet

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.

boolean

equals(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 specified i (inclusive) to the specified j (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 new SparseBitSet composed of bits from this SparseBitSet from i (inclusive) to j (exclusive).

int

hashCode()

Returns a hash code value for this bit set.

boolean

intersects(int i, int j, SparseBitSet 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.

boolean

intersects(SparseBitSet b)

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

boolean

isEmpty()

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

int

length()

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

int

nextClearBit(int i)

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

int

nextSetBit(int 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 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 given SparseBitSets.

int

previousClearBit(int i)

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

int

previousSetBit(int 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 s)

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

protected final 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 specified i (inclusive) to the specified j (exclusive) to true.

void

set(int i, int j, boolean value)

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

protected final 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 this SparseBitSet to represent bit values.

String

statistics()

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

String

statistics(String[] 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 i, int j)

Throw the exception to indicate a range error.

String

toString()

Returns a string representation of this bit set.

void

toStringCompaction(boolean 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.

void

toStringCompaction(int count)

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

private void

writeObject(ObjectOutputStream s)

Save the state of the SparseBitSet 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 given SparseBitSets.

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

Field Details
- 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 position i % 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 Details
- SparseBitSet
  
  protected SparseBitSet(int capacity, int compactionCount) throws NegativeArraySizeException
  
  Constructor for a new (sparse) bit set. All bits initially are effectively false. 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 bits
  
  compactionCount - the compactionCount to be inherited (for internal generation)
  
  Throws:
  
  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 effectively false.
  
  Since:
  
  1.6
- SparseBitSet
  
  public SparseBitSet(int nbits) throws NegativeArraySizeException
  
  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. Initially all bits are effectively false.
  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:
  
  NegativeArraySizeException - if the specified initial length is negative
  
  Since:
  
  1.6
  
  See Also:
  
  SparseBitSet()
Method Details
- and
  
  public void and(int i, boolean value) throws 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 value true if and only if it both initially had the value true and the argument value is also true.
  
  Parameters:
  
  i - a bit index
  
  value - a boolean value to AND with that bit
  
  Throws:
  
  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 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 value true if and only if it both initially had the value true and the corresponding bit in the bit set argument also had the value true. Outside the range, this set is not changed.
  
  Parameters:
  
  i - index of the first bit to be included in the operation
  
  j - index after the last bit to included in the operation
  
  b - a SparseBitSet
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  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 value true if and only if it both initially had the value true and the corresponding bit in the bit set argument also had the value true.
  
  Parameters:
  
  b - a SparseBitSet
  
  Since:
  
  1.6
- and
  
  public static SparseBitSet and(SparseBitSet a, SparseBitSet b)
  
  Performs a logical AND of the two given SparseBitSets. The returned SparseBitSet is created so that each bit in it has the value true if and only if both the given sets initially had the corresponding bits true, otherwise false.
  
  Parameters:
  
  a - a SparseBitSet
  
  b - 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 value true if and only if it both initially had the value true and the argument value is false.
  
  Parameters:
  
  i - a bit index
  
  value - a boolean value to AndNOT with that bit
  
  Throws:
  
  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 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 value true if and only if it both initially had the value true and the corresponding bit in the bit set argument has the value false. Outside the range, this set is not changed.
  
  Parameters:
  
  i - index of the first bit to be included in the operation
  
  j - index after the last bit to included in the operation
  
  b - the SparseBitSet with which to mask this SparseBitSet
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  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 value true if and only if it both initially had the value true and the corresponding bit in the bit set argument has the value false.
  
  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 first SparseBitSet whose corresponding bits are cleared by the set bits of the second SparseBitSet. The resulting bit set is created so that a bit in it has the value true if and only if the corresponding bit in the SparseBitSet of the first is set, and that same corresponding bit is not set in the SparseBitSet of the second argument.
  
  Parameters:
  
  a - a SparseBitSet
  
  b - 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 to true in this SparseBitSet.
  
  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 to false.
  
  Parameters:
  
  i - a bit index.
  
  Throws:
  
  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 IndexOutOfBoundsException
  
  Sets the bits from the specified i (inclusive) to the specified j (exclusive) to false.
  
  Parameters:
  
  i - index of the first bit to be cleared
  
  j - index after the last bit to be cleared
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  Since:
  
  1.6
- clear
  
  public void clear()
  
  Sets all of the bits in this SparseBitSet to false.
  
  Since:
  
  1.6
- clone
  
  public SparseBitSet clone()
  
  Cloning this SparseBitSet produces a new SparseBitSet that is equal() to it. The clone of the bit set is another bit set that has exactly the same bits set to true 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 class Object
  
  Returns:
  
  a clone of this SparseBitSet
  
  Since:
  
  1.6
- equals
  
  public boolean equals(Object obj)
  Compares this object against the specified object. The result is true if and only if the argument is not null and is a SparseBitSet object that has exactly the same bits set to true as this bit set. That is, for every nonnegative i indexing a bit in the set,
  ((SparseBitSet)obj).get(i) == this.get(i)
  must be true.
  Overrides:
  
  equals in class 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:
  
  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 IndexOutOfBoundsException
  
  Sets each bit from the specified i (inclusive) to the specified j (exclusive) to the complement of its current value.
  
  Parameters:
  
  i - index of the first bit to flip
  
  j - index after the last bit to flip
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or is equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  Since:
  
  1.6
- get
  
  public boolean get(int i)
  
  Returns the value of the bit with the specified index. The value is true if the bit with the index i is currently set in this SparseBitSet; otherwise, the result is false.
  
  Parameters:
  
  i - the bit index
  
  Returns:
  
  the boolean value of the bit with the specified index.
  
  Throws:
  
  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 IndexOutOfBoundsException
  
  Returns a new SparseBitSet composed of bits from this SparseBitSet from i (inclusive) to j (exclusive).
  
  Parameters:
  
  i - index of the first bit to include
  
  j - index after the last bit to include
  
  Returns:
  
  a new SparseBitSet from a range of this SparseBitSet
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or is equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  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 this SparseBitSet. The algorithm used to compute it may be described as follows.
  Suppose the bits in the SparseBitSet were to be stored in an array of long integers called, say, bits, in such a manner that bit i is set in the SparseBitSet (for nonnegative values of i) if and only if the expression
  ((i>>6) < bits.length) && ((bits[i>>6] & (1L << (bit & 0x3F))) != 0)
  is true. Then the following definition of the hashCode 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 class 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 IndexOutOfBoundsException
  
  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.
  
  Parameters:
  
  i - index of the first bit to include
  
  j - index after the last bit to include
  
  b - the SparseBitSet with which to intersect
  
  Returns:
  
  the boolean indicating whether this SparseBitSet intersects the specified SparseBitSet
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  Since:
  
  1.6
- intersects
  
  public boolean intersects(SparseBitSet b)
  
  Returns true if the specified SparseBitSet has any bits set to true that are also set to true in this SparseBitSet.
  
  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 this SparseBitSet contains no bits that are set to true.
  
  Returns:
  
  the boolean indicating whether this SparseBitSet is empty
  
  Since:
  
  1.6
- length
  
  public int length()
  
  Returns the "logical length" of this SparseBitSet: the index of the highest set bit in the SparseBitSet plus one. Returns zero if the SparseBitSet 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 to false 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:
  
  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 to true 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 a SparseBitSet 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:
  
  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 to false 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:
  
  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 to true 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:
  
  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 value true if and only if it both initially had the value true or the argument value is true.
  
  Parameters:
  
  i - a bit index
  
  value - a boolean value to OR with that bit
  
  Throws:
  
  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 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 value true if and only if it either already had the value true or the corresponding bit in the bit set argument has the value true. Outside the range this set is not changed.
  
  Parameters:
  
  i - index of the first bit to be included in the operation
  
  j - index after the last bit to included in the operation
  
  b - the SparseBitSet with which to perform the OR operation with this SparseBitSet
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  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 value true if and only if it either already had the value true or the corresponding bit in the bit set argument has the value true.
  
  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 given SparseBitSets. The returned SparseBitSet is created so that a bit in it has the value true if and only if it either had the value true in the set given by the first arguemetn or had the value true in the second argument, otherwise false.
  
  Parameters:
  
  a - a SparseBitSet
  
  b - 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:
  
  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 index
  
  value - a boolean value to set
  
  Throws:
  
  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 IndexOutOfBoundsException
  
  Sets the bits from the specified i (inclusive) to the specified j (exclusive) to true.
  
  Parameters:
  
  i - index of the first bit to be set
  
  j - index after the last bit to be se
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or is equal to Integer.MAX_INT, or j is negative, or i is larger than j.
  
  Since:
  
  1.6
- set
  
  public void set(int i, int j, boolean value)
  
  Sets the bits from the specified i (inclusive) to the specified j (exclusive) to the specified value.
  
  Parameters:
  
  i - index of the first bit to be set
  
  j - index after the last bit to be set
  
  value - to which to set the selected bits
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or is equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  Since:
  
  1.6
- size
  
  public int size()
  
  Returns the number of bits of space nominally in use by this SparseBitSet 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 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 String statistics(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 String toString()
  Returns a string representation of this bit set. For every index for which this SparseBitSet 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();
  Now drPepper.toString() returns "{}".
  
  drPepper.set(2);
  Now drPepper.toString() returns "{2}".
  
  drPepper.set(3, 4); drPepper.set(10);
  Now drPepper.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 a SparseBitSet.
  Overrides:
  
  toString in class 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 by toString() as a "sub-sequence," in the form a..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 SparseBitSets 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 a toString() conversion. If 0, all bits are shown individually.
  
  Since:
  
  1.6
  
  See Also:
  
  toString()
- toStringCompaction
  
  public void toStringCompaction(boolean 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.
  
  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 value true if and only one of the following statements holds:
  
  The addressed bit initially had the value true, and the value of the argument is false.
  The bit initially had the value false, and the value of the argument is true.
  Parameters:
  
  i - a bit index
  
  value - a boolean value to XOR with that bit
  
  Throws:
  
  IndexOutOfBoundsException - if the specified index is negative or equal to Integer.MAX_VALUE
  
  Since:
  
  1.6
- xor
  
  public void xor(int i, int j, SparseBitSet b) throws 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 value true 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 value false.
  The bit initially had the value false, and the corresponding bit in the argument set has the value true.
  Outside the range this set is not changed.
  Parameters:
  
  i - index of the first bit to be included in the operation
  
  j - index after the last bit to included in the operation
  
  b - the SparseBitSet with which to perform the XOR operation with this SparseBitSet
  
  Throws:
  
  IndexOutOfBoundsException - if i is negative or equal to Integer.MAX_VALUE, or j is negative, or i is larger than j
  
  Since:
  
  1.6
- 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 value true 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 value false.
  The bit initially had the value false, and the corresponding bit in the argument set has the value true.
  Parameters:
  
  b - the SparseBitSet with which to perform the XOR operation with thisSparseBitSet
  
  Since:
  
  1.6
- xor
  
  public static SparseBitSet xor(SparseBitSet a, SparseBitSet b)
  Performs a logical XOR of the two given SparseBitSets. The resulting bit set is created so that a bit in it has the value true 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 value false.
  
  A bit in the first argument has the value false, and the corresponding bit in the second argument has the value true.
  Parameters:
  
  a - a SparseBitSet
  
  b - another SparseBitSet
  
  Returns:
  
  a new SparseBitSet representing the XOR of the two sets
  
  Since:
  
  1.6
- throwIndexOutOfBoundsException
  
  protected static void throwIndexOutOfBoundsException(int i, int j) throws IndexOutOfBoundsException
  
  Throw the exception to indicate a range error. The String constructed reports all the possible errors in one message.
  
  Parameters:
  
  i - lower bound for a operation
  
  j - upper bound for a operation
  
  Throws:
  
  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 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 the AbstractStrategy. 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 scan
  
  j - the bit (exclusive) at which to stop the scan
  
  b - a SparseBitSet, if needed, the second SparseBitSet in the operation
  
  op - the AbstractStrategy class defining the operation to be executed
  
  Throws:
  
  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(ObjectOutputStream s) throws IOException, InternalError
  
  Save the state of the SparseBitSet instance to a stream (i.e., serialize it).
  
  Parameters:
  
  s - the ObjectOutputStream to which to write the serialized object
  
  Throws:
  
  IOException - if an io error occurs
  
  InternalError - if the SparseBitSet representation is inconsistent
  
  Since:
  
  1.6
- readObject
  
  private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException
  
  Reconstitute the SparseBitSet instance from a stream (i.e., deserialize it).
  
  Parameters:
  
  s - the ObjectInputStream to use
  
  Throws:
  
  IOException - if there is an io error
  
  ClassNotFoundException - if the stream contains an unidentified class
  
  Since:
  
  1.6

Class SparseBitSet

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Details

compactionCount

compactionCountDefault

bits

bitsLength

LENGTH4

INDEX_SIZE

LEVEL4

LEVEL3

LEVEL2

LEVEL1

MAX_LENGTH1

LENGTH2

LENGTH3

SHIFT3

MASK3

SHIFT2

UNIT

MASK2

SHIFT1

LENGTH2_SIZE

LENGTH3_SIZE

LENGTH4_SIZE

cache

spare

ZERO_BLOCK

serialVersionUID

andStrategy

andNotStrategy

clearStrategy

copyStrategy

equalsStrategy

flipStrategy

intersectsStrategy

orStrategy

setStrategy

updateStrategy

xorStrategy

Constructor Details

SparseBitSet

SparseBitSet

SparseBitSet

Method Details

and

and

and

and

andNot

andNot

andNot

andNot

cardinality

clear

clear

clear

clone

equals

flip

flip

get

get

hashCode

intersects

intersects

isEmpty

length

nextClearBit

nextSetBit

previousClearBit

previousSetBit

or

or

or

or