Package org.ka2ddo.util

Class HugeBitSet

java.lang.Object
org.ka2ddo.util.HugeBitSet
public final class HugeBitSet extends Object
This class implements a BitSet using a segmented array, so that growth to unreasonably huge sizes will not require having enough heap space for two contiguous copies of the bitset (to handle copying upon array growth). Instead, this class adds more segments, so existing segment data does not have to be copied and the size of contiguous heap allocations remains constant instead of growing.

Note that the maximum size of a HugeBitSet is 2**32 - 1 bits.

Author:
Andrew Pavlin, KA2DDO

  • Constructor Summary

    Constructors
    Constructor
    Description
    HugeBitSet()
    Create a HugeBitSet with no preallocated blocks.
    HugeBitSet(int prealloc)
    Create a HugeBitSet with memory allocated for up to the specific bit number,

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Clear all the bits in the HugeBitSet.
    boolean
    clear(int index)
    Clear the specified bit in the HugeBitSet.
    boolean
    get(int index)
    Test if the specified bit is set in the HugeBitSet.
    boolean
    isSet(int index)
    Test if the specified bit is set in the HugeBitSet.
    void
    justSet(int index)
    Set the specified bit in the HugeBitSet without returning the former state.
    int
    length()
    Get the maximum number of bits currently allocated in this HugeBitSet.
    int
    nextClearBit(int index)
    Returns the index of the first bit that is set to false that occurs on or after the specified starting index.
    int
    nextSetBit(int index)
    Returns the index of the first bit that is set to true that occurs on or after the specified starting index.
    void
    preallocate(int numBits)
    Ensure that enough storage has been allocated in the HugeBitSet to hold at least the specified range of bits.
    int
    previousClearBit(int index)
    Returns the index of the first bit that is set to false that occurs on or prior the specified starting index.
    int
    previousSetBit(int index)
    Returns the index of the first bit that is set to true that occurs on or before the specified starting index.
    boolean
    set(int index)
    Set the specified bit in the HugeBitSet.
    boolean
    setIfNot(int index)
    Set the specified bit in the HugeBitSet and indicate whether this was a change.
    String
    toString()
    Generate a String describing this HugeBitSet.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • HugeBitSet

      public HugeBitSet()
      Create a HugeBitSet with no preallocated blocks.

    • HugeBitSet

      public HugeBitSet(int prealloc)
      Create a HugeBitSet with memory allocated for up to the specific bit number,
      Parameters:
      prealloc - highest bit number to preallocate for

  • Method Details

    • set

      public boolean set(int index)
      Set the specified bit in the HugeBitSet.
      Parameters:
      index - zero-based int index of the bit to set
      Returns:
      boolean true if the bit was set prior to this call, false if clear

    • justSet

      public void justSet(int index)
      Set the specified bit in the HugeBitSet without returning the former state.
      Parameters:
      index - zero-based int index of the bit to set

    • setIfNot

      public boolean setIfNot(int index)
      Set the specified bit in the HugeBitSet and indicate whether this was a change.
      Parameters:
      index - zero-based int index of the bit to set
      Returns:
      boolean true if bit was formerly clear (freshly set), false otherwise

    • clear

      public boolean clear(int index)
      Clear the specified bit in the HugeBitSet.
      Parameters:
      index - zero-based int index of the bit to set
      Returns:
      boolean true if the bit was set prior to this call, false if clear

    • clear

      public void clear()
      Clear all the bits in the HugeBitSet. Note that this does not free any storage blocks allocated by previous calls to set() or justSet().

    • preallocate

      public void preallocate(int numBits)
      Ensure that enough storage has been allocated in the HugeBitSet to hold at least the specified range of bits.
      Parameters:
      numBits - highest bit number for which storage should be allocated when this method returns

    • get

      public boolean get(int index)
      Test if the specified bit is set in the HugeBitSet.
      Parameters:
      index - zero-based index of bit to test
      Returns:
      boolean true if bit is set, or false if bit is clear

    • isSet

      public boolean isSet(int index)
      Test if the specified bit is set in the HugeBitSet.
      Parameters:
      index - zero-based index of bit to test
      Returns:
      boolean true if bit is set, or false if bit is clear

    • toString

      public String toString()
      Generate a String describing this HugeBitSet.
      Overrides:
      toString in class Object
      Returns:
      descriptive String

    • length

      public int length()
      Get the maximum number of bits currently allocated in this HugeBitSet.
      Returns:
      maximum bit index + 1 currently allocated

    • nextSetBit

      public int nextSetBit(int index)
      Returns the index of the first bit that is set to true that occurs on or after the specified starting index. 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 }
      Parameters:
      index - the index to start checking from (inclusive).
      Returns:
      the index of the next set bit.
      Throws:
      IndexOutOfBoundsException - if the specified index is negative.

    • nextClearBit

      public int nextClearBit(int index)
      Returns the index of the first bit that is set to false that occurs on or after the specified starting index. 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 }
      Parameters:
      index - the index to start checking from (inclusive).
      Returns:
      the index of the next clear bit.
      Throws:
      IndexOutOfBoundsException - if the specified index is negative.

    • previousSetBit

      public int previousSetBit(int index)
      Returns the index of the first bit that is set to true that occurs on or before the specified starting index. 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.previousSetBit(Integer.MAX_VALUE); i >= 0; i = bs.previousSetBit(i-1)) { // operate on index i here }
      Parameters:
      index - the index to start checking from (inclusive).
      Returns:
      the index of the previous set bit.
      Throws:
      IndexOutOfBoundsException - if the specified index is negative.

    • previousClearBit

      public int previousClearBit(int index)
      Returns the index of the first bit that is set to false that occurs on or prior the specified starting index. 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.previousClearBit(Integer.MAX_VALUE); i >= 0; i = bs.previousClearBit(i+1)) { // operate on index i here }
      Parameters:
      index - the index to start checking from (inclusive).
      Returns:
      the index of the previous clear bit.
      Throws:
      IndexOutOfBoundsException - if the specified index is negative.