edu.northwestern.at.utils

## Class SparseBitSet

- java.lang.Object
- - edu.northwestern.at.utils.SparseBitSet

- All Implemented Interfaces:
    XCloneable, java.io.Serializable, java.lang.Cloneable

      public class SparseBitSet
      extends java.lang.Object
      implements XCloneable, java.io.Serializable

  A set of bits. The set automatically grows as more bits are needed.
  Version:
    1.00, 25 Jul 1999
  Author:
    C. Scott Ananian

    Modications by Philip R. "Pib" Burns to add missing BitSet methods.

  See Also:
    Serialized Form

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `protected static interface` | `SparseBitSet.BinOp`

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected static SparseBitSet.BinOp` | `AND`
    `protected static SparseBitSet.BinOp` | `ANDNOT`
    `protected long[]` | `bits` Array of bit-blocks; each holding BITS bits.
    `protected static int` | `BITS` Number of bits in a block.
    `protected static int` | `BITS_M1` BITS-1, using the identity: x % BITS == x & (BITS-1)
    `protected static int` | `LG_BITS` log base 2 of BITS, for the identity: x/BITS == x >> LG_BITS
    `protected int[]` | `offs` Sorted array of bit-block offsets.
    `protected static SparseBitSet.BinOp` | `OR`
    `protected int` | `size` Number of blocks currently in use.
    `protected static SparseBitSet.BinOp` | `XOR`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `SparseBitSet()` Create an empty set.
    `SparseBitSet(int nbits)` Create an empty set with the specified size.
    `SparseBitSet(SparseBitSet set)` Create an empty set with the same size as the given set.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `and(SparseBitSet otherSet)` Logically AND this bit set with another.
    `void` | `andNot(SparseBitSet otherSet)` Logically ANDNOT this bit set with another.
    `protected static void` | `binop(SparseBitSet a, SparseBitSet b, SparseBitSet.BinOp op)`
    `protected int` | `bsearch(int bnum)`
    `int` | `cardinality()` Return cardinality (# of bits set on) in this bit set.
    `void` | `clear()` Clear all bits.
    `void` | `clear(int bit)` Clear a bit.
    `void` | `clear(int fromIndex, int toIndex)` Clears a range of bits.
    `java.lang.Object` | `clone()` Clone this set.
    `java.util.Enumeration` | `elements()` Return an `Enumeration` of `Integer`s indices of bits set on in this SparseBitSet.
    `boolean` | `equals(java.lang.Object object)` Compare this set against another.
    `static boolean` | `equals(SparseBitSet a, SparseBitSet b)` Compare two SparseBitSets for equality.
    `void` | `flip(int bit)` Flip a bit value.
    `void` | `flip(int fromIndex, int toIndex)` Flips a range of bits.
    `boolean` | `get(int bit)` Get bit value.
    `int` | `hashCode()` Return hash code for set.
    `protected void` | `insert_block(int idx, int bnum)`
    `boolean` | `intersects(SparseBitSet otherSet)` Check if this set and another share at least one set bit.
    `protected boolean` | `isValid()` Check validity.
    `int` | `length()` Returns index of highest set bit in this set plus one.
    `protected void` | `new_block(int bnum)`
    `protected void` | `new_block(int idx, int bnum)`
    `int` | `nextClearBit(int fromIndex)` Returns index of first bit set to false that occurs on or after specified starting index.
    `int` | `nextSetBit(int fromIndex)` Returns index of first bit set to true that occurs on or after specified starting index.
    `void` | `or(SparseBitSet otherSet)` Logically OR this bit set with another.
    `void` | `set(int bit)` Set a bit.
    `int` | `size()` Return set's size.
    `java.lang.String` | `toString()` Converts the SparseBitSet to a String.
    `void` | `xor(SparseBitSet otherSet)` Logically XOR this bit set with another.

    - ### Methods inherited from class java.lang.Object

      `finalize, getClass, notify, notifyAll, wait, wait, wait`

- - ### Field Detail

    - #### offs

          protected int[] offs

      Sorted array of bit-block offsets.

    - #### bits

          protected long[] bits

      Array of bit-blocks; each holding BITS bits.

    - #### size

          protected int size

      Number of blocks currently in use.

    - #### LG_BITS

          protected static final int LG_BITS

      log base 2 of BITS, for the identity: x/BITS == x >> LG_BITS
      See Also:
        Constant Field Values

    - #### BITS

          protected static final int BITS

      Number of bits in a block.
      See Also:
        Constant Field Values

    - #### BITS_M1

          protected static final int BITS_M1

      BITS-1, using the identity: x % BITS == x & (BITS-1)
      See Also:
        Constant Field Values

    - #### AND

          protected static final SparseBitSet.BinOp AND

    - #### OR

          protected static final SparseBitSet.BinOp OR

    - #### XOR

          protected static final SparseBitSet.BinOp XOR

    - #### ANDNOT

          protected static final SparseBitSet.BinOp ANDNOT

  - ### Constructor Detail

    - #### SparseBitSet

          public SparseBitSet()

      Create an empty set.

    - #### SparseBitSet

          public SparseBitSet(int nbits)

      Create an empty set with the specified size.
      Parameters:
        `nbits` - The size of the set.

    - #### SparseBitSet

          public SparseBitSet(SparseBitSet set)

      Create an empty set with the same size as the given set.

  - ### Method Detail

    - #### new_block

          protected void new_block(int bnum)

    - #### new_block

          protected void new_block(int idx,
                       int bnum)

    - #### insert_block

          protected void insert_block(int idx,
                          int bnum)

    - #### bsearch

          protected int bsearch(int bnum)

    - #### set

          public void set(int bit)

      Set a bit.
      Parameters:
        `bit` - The bit to set.

    - #### clear

          public void clear(int bit)

      Clear a bit.
      Parameters:
        `bit` - The bit to be cleared.

    - #### clear

          public void clear()

      Clear all bits.

    - #### clear

          public void clear(int fromIndex,
                   int toIndex)

      Clears a range of bits.
      Parameters:
        `fromIndex` - Index of first bit to be cleared.
        `toIndex` - Index + 1 of last bit to be cleared.

    - #### flip

          public void flip(int bit)

      Flip a bit value.
      Parameters:
        `bit` - Bit to flip.

    - #### flip

          public void flip(int fromIndex,
                  int toIndex)

      Flips a range of bits.
      Parameters:
        `fromIndex` - Index of first bit to be flipped.
        `toIndex` - Index + 1 of last bit to be flipped.

    - #### get

          public boolean get(int bit)

      Get bit value.
      Parameters:
        `bit` - Bit whose value is to be retrieved.
      Returns:
        true if bit set, false otherwise.

    - #### and

          public void and(SparseBitSet otherSet)

      Logically AND this bit set with another.
      Parameters:
        `otherSet` - The other bit set to AND against.

    - #### or

          public void or(SparseBitSet otherSet)

      Logically OR this bit set with another.
      Parameters:
        `otherSet` - The other bit set to be ORed against.

    - #### xor

          public void xor(SparseBitSet otherSet)

      Logically XOR this bit set with another.
      Parameters:
        `otherSet` - The other bit set to be XORed against.

    - #### andNot

          public void andNot(SparseBitSet otherSet)

      Logically ANDNOT this bit set with another.
      Parameters:
        `otherSet` - The other bit set to be ANDNOTed against.

    - #### binop

          protected static final void binop(SparseBitSet a,
                   SparseBitSet b,
                   SparseBitSet.BinOp op)

    - #### hashCode

          public int hashCode()

      Return hash code for set.
      Overrides:
        `hashCode` in class `java.lang.Object`
      Returns:
        The hash code.

    - #### size

          public int size()

      Return set's size.

    - #### equals

          public boolean equals(java.lang.Object object)

      Compare this set against another.
      Overrides:
        `equals` in class `java.lang.Object`
      Parameters:
        `object` - The object to compare against.
      Returns:
        true the objects are equal, false otherwise.

    - #### equals

          public static boolean equals(SparseBitSet a,
                       SparseBitSet b)

      Compare two SparseBitSets for equality.
      Returns:
        true if sets are equal, false otherwise.

    - #### cardinality

          public int cardinality()

      Return cardinality (# of bits set on) in this bit set.
      Returns:
        Cardinality of this bit set.

    - #### intersects

          public boolean intersects(SparseBitSet otherSet)

      Check if this set and another share at least one set bit.
      Parameters:
        `otherSet` - The other set to check for intersection
      Returns:
        true If this set and the other intersect.

    - #### length

          public int length()

      Returns index of highest set bit in this set plus one.
      Returns:
        The logical size of this set.

    - #### nextSetBit

          public int nextSetBit(int fromIndex)

      Returns index of first bit set to true that occurs on or after specified starting index.
      Parameters:
        `fromIndex` - Index to start checking from (inclusive).
      Returns:
        Index of next bit set.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if specified index is negative.

        If no such bit exists then -1 is returned. To iterate over the true bits in a BitSet, use the following loop:

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

    - #### nextClearBit

          public int nextClearBit(int fromIndex)

      Returns index of first bit set to false that occurs on or after specified starting index.
      Parameters:
        `fromIndex` - Index to start checking from (inclusive).
      Returns:
        Index of next clear bit.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if specified index is negative.

        If no such bit exists then -1 is returned. To iterate over the false bits in a BitSet, use the following loop:

        `for (int i = bs.nextClearBit(0); i >= 0; i = bs.nextClearBit(i+1)) { // operate on index i here }`

    - #### clone

          public java.lang.Object clone()

      Clone this set.
      Specified by:
        `clone` in interface `XCloneable`
      Overrides:
        `clone` in class `java.lang.Object`
      Returns:
        Clone of this bit set.

    - #### elements

          public java.util.Enumeration elements()

      Return an `Enumeration` of `Integer`s indices of bits set on in this SparseBitSet.

    - #### toString

          public java.lang.String toString()

      Converts the SparseBitSet to a String.
      Overrides:
        `toString` in class `java.lang.Object`

    - #### isValid

          protected boolean isValid()

      Check validity.