BiggerBitSet

java.lang.Object
- frink.graphics.BiggerBitSet

All Implemented Interfaces:

java.lang.Cloneable
```
public class BiggerBitSet
extends java.lang.Object
implements java.lang.Cloneable
```
BiggerBitSet is an improvement on Java's BitSet class in a few ways: 1.) BiggerBitSet uses long instead of int to address bits in its API which greatly increases the size of bits addresable. The implementation of BitSet allows a maximum number of pixels of (2^31 - 1) or 2147483647, which is about 2 billion pixels. If 3-D printing at a resolution of 0.1 mm/pixel, this gives a maximum size of about 5.07 inches on a side. ((2^31-1))^(1/3) 0.1 mm -> in This is not quite big enough to fit a modern 3-D printer's bed. With this class's API, the number of pixels is increased by a factor of 64, giving over 137 billion pixels. The calculation is: ((2^31-1) * 64)^(1/3) 0.1 mm -> in which gives a cube of about 20 inches on a side. This is enough of an improvement to warrant the class. 2.) BiggerBitSet does not allow itself to be dynamically resized; this should give a performance improvement over BitSet. BitSet takes a lot of effort to validate invariants and resize with every set. 3.) BiggerBitSet is constant across Java releases and implements functions (especially those to set a range of values quickly and efficiently) which did not exist in earlier versions of Java's BitSet.

Field Summary

Fields
Modifier and Type	Field and Description
`private static int`	`ADDRESS_BITS_PER_WORD`
`private static int`	`BIT_INDEX_MASK`
`private static int`	`BITS_PER_WORD`
`private static long`	`WORD_MASK`
`private long[]`	`words` The internal field corresponding to the serialField "bits".

Constructor Summary

Constructors
Constructor and Description
`BiggerBitSet(long nbits)` Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range `0` through `nbits-1`.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`and(BiggerBitSet set)` Performs a logical AND of this target bit set with the argument bit set.
`void`	`andNot(BiggerBitSet set)` Clears all of the bits in this `BiggerBitSet` whose corresponding bit is set in the specified `BiggerBitSet`.
`static int`	`bitCountLong(long i)` Returns the number of one-bits in the two's complement binary representation of the specified `long` value.
`long`	`cardinality()` Returns the number of bits set to `true` in this `BiggerBitSet`.
`private static void`	`checkRange(long fromIndex, long toIndex)` Checks that fromIndex ...
`void`	`clear()` Sets all of the bits in this BiggerBitSet to `false`.
`void`	`clear(long bitIndex)` Sets the bit specified by the index to `false`.
`void`	`clearRange(long fromIndex, long toIndex)` Sets the bits from the specified `fromIndex` (inclusive) to the specified `toIndex` (exclusive) to `false`.
`java.lang.Object`	`clone()` Cloning this `BiggerBitSet` produces a new `BiggerBitSet` that is equal to it.
`boolean`	`equals(java.lang.Object obj)` Compares this object against the specified object.
`void`	`flip(long bitIndex)` Sets the bit at the specified index to the complement of its current value.
`void`	`flip(long fromIndex, long toIndex)` Sets each bit from the specified `fromIndex` (inclusive) to the specified `toIndex` (exclusive) to the complement of its current value.
`boolean`	`get(long bitIndex)` Returns the value of the bit with the specified index.
`int`	`hashCode()` Returns the hash code value for this bit set.
`private void`	`initWords(long nbits)` Create the array of words.
`boolean`	`intersects(BiggerBitSet set)` Returns true if the specified `BiggerBitSet` has any bits set to `true` that are also set to `true` in this `BiggerBitSet`.
`boolean`	`isEmpty()` Returns true if this `BiggerBitSet` contains no bits that are set to `true`.
`long`	`length()` Returns the "logical size" of this `BiggerBitSet`: the index of the highest set bit in the `BiggerBitSet` plus one.
`long`	`nextClearBit(long fromIndex)` Returns the index of the first bit that is set to `false` that occurs on or after the specified starting index.
`long`	`nextSetBit(long fromIndex)` Returns the index of the first bit that is set to `true` that occurs on or after the specified starting index.
`private long`	`nextSetBit(long fromIndex, long toWordIndex)` Returns the index of the first bit that is set to `true` that occurs on or after the specified starting index and up to and including the specified word index If no such bit exists then `-1` is returned.
`static int`	`numberOfLeadingZerosInt(int i)` Returns the number of zero bits preceding the highest-order ("leftmost") one-bit in the two's complement binary representation of the specified `int` value.
`static int`	`numberOfLeadingZerosLong(long i)` Returns the number of zero bits preceding the highest-order ("leftmost") one-bit in the two's complement binary representation of the specified `long` value.
`static int`	`numberOfTrailingZerosInt(int i)` Returns the number of zero bits following the lowest-order ("rightmost") one-bit in the two's complement binary representation of the specified `int` value.
`static int`	`numberOfTrailingZerosLong(long i)` Returns the number of zero bits following the lowest-order ("rightmost") one-bit in the two's complement binary representation of the specified `long` value.
`void`	`or(BiggerBitSet set)` Performs a logical OR of this bit set with the bit set argument.
`long`	`previousClearBit(long fromIndex)` Returns the index of the nearest bit that is set to `false` that occurs on or before the specified starting index.
`long`	`previousSetBit(long fromIndex)` Returns the index of the nearest bit that is set to `true` that occurs on or before the specified starting index.
`void`	`set(long bitIndex)` Sets the bit at the specified index to `true`.
`void`	`set(long bitIndex, boolean value)` Sets the bit at the specified index to the specified value.
`void`	`setRange(long fromIndex, long toIndex)` Sets the bits from the specified `fromIndex` (inclusive) to the specified `toIndex` (exclusive) to `true`.
`void`	`setRange(long fromIndex, long toIndex, boolean value)` Sets the bits from the specified `fromIndex` (inclusive) to the specified `toIndex` (exclusive) to the specified value.
`long`	`size()` Returns the number of bits of space actually in use by this `BiggerBitSet` to represent bit values.
`private static int`	`wordIndex(long bitIndex)` Given a bit index, return word index containing it.
`void`	`xor(BiggerBitSet set)` Performs a logical XOR of this bit set with the bit set argument.

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

- Field Detail
  - ADDRESS_BITS_PER_WORD
```
private static final int ADDRESS_BITS_PER_WORD
```
    See Also:
    
    Constant Field Values
  - BITS_PER_WORD
```
private static final int BITS_PER_WORD
```
    See Also:
    
    Constant Field Values
  - BIT_INDEX_MASK
```
private static final int BIT_INDEX_MASK
```
    See Also:
    
    Constant Field Values
  - WORD_MASK
```
private static final long WORD_MASK
```
    See Also:
    
    Constant Field Values
  - words
```
private long[] words
```
    The internal field corresponding to the serialField "bits".
- Constructor Detail
  - BiggerBitSet
```
public BiggerBitSet(long nbits)
```
    Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1. All bits are initially false.
    
    Parameters:
    
    nbits - the size of the bit set
    
    Throws:
    
    java.lang.NegativeArraySizeException - if the specified initial size is negative
- Method Detail
  - wordIndex
```
private static int wordIndex(long bitIndex)
```
    Given a bit index, return word index containing it.
  - initWords
```
private void initWords(long nbits)
```
    Create the array of words. TODO: This should check limits. The maximum should be (2^31-1) * 64 or 137438953408
  - checkRange
```
private static void checkRange(long fromIndex,
                               long toIndex)
```
    Checks that fromIndex ... toIndex is a valid range of bit indices.
  - flip
```
public void flip(long bitIndex)
```
    Sets the bit at the specified index to the complement of its current value.
    
    Parameters:
    
    bitIndex - the index of the bit to flip
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if the specified index is negative
  - flip
```
public void flip(long fromIndex,
                 long toIndex)
```
    Sets each bit from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to the complement of its current value.
    
    Parameters:
    
    fromIndex - index of the first bit to flip
    
    toIndex - index after the last bit to flip
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex
  - set
```
public void set(long bitIndex)
```
    Sets the bit at the specified index to true.
    
    Parameters:
    
    bitIndex - a bit index
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if the specified index is negative
  - set
```
public void set(long bitIndex,
                boolean value)
```
    Sets the bit at the specified index to the specified value.
    
    Parameters:
    
    bitIndex - a bit index
    
    value - a boolean value to set
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if the specified index is negative
  - setRange
```
public void setRange(long fromIndex,
                     long toIndex)
```
    Sets the bits from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to true.
    
    Parameters:
    
    fromIndex - index of the first bit to be set
    
    toIndex - index after the last bit to be set
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex
  - setRange
```
public void setRange(long fromIndex,
                     long toIndex,
                     boolean value)
```
    Sets the bits from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to the specified value.
    
    Parameters:
    
    fromIndex - index of the first bit to be set
    
    toIndex - index after the last bit to be set
    
    value - value to set the selected bits to
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex
  - clear
```
public void clear(long bitIndex)
```
    Sets the bit specified by the index to false.
    
    Parameters:
    
    bitIndex - the index of the bit to be cleared
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if the specified index is negative
  - clearRange
```
public void clearRange(long fromIndex,
                       long toIndex)
```
    Sets the bits from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to false.
    
    Parameters:
    
    fromIndex - index of the first bit to be cleared
    
    toIndex - index after the last bit to be cleared
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex
  - clear
```
public void clear()
```
    Sets all of the bits in this BiggerBitSet to false.
  - get
```
public boolean get(long bitIndex)
```
    Returns the value of the bit with the specified index. The value is true if the bit with the index bitIndex is currently set in this BiggerBitSet; otherwise, the result is false.
    
    Parameters:
    
    bitIndex - the bit index
    
    Returns:
    
    the value of the bit with the specified index
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if the specified index is negative
  - nextSetBit
```
public long nextSetBit(long fromIndex)
```
    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 BiggerBitSet, use the following loop:
```
 
      for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
          // operate on index i here
          if (i == Integer.MAX_VALUE) {
              break; // or (i+1) would overflow
          }
      }
```
    Parameters:
    
    fromIndex - the index to start checking from (inclusive)
    
    Returns:
    
    the index of the next set bit, or -1 if there is no such bit
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if the specified index is negative
  - nextClearBit
```
public long nextClearBit(long fromIndex)
```
    Returns the index of the first bit that is set to false that occurs on or after the specified starting index.
    
    Parameters:
    
    fromIndex - the index to start checking from (inclusive)
    
    Returns:
    
    the index of the next clear bit
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if the specified index is negative
  - previousSetBit
```
public long previousSetBit(long fromIndex)
```
    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 a negative index is given as the starting index, then -1 is returned.
    To iterate over the true bits in a BiggerBitSet, use the following loop:
```
 
      for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
          // operate on index i here
      }
```
    Parameters:
    
    fromIndex - 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
  - previousClearBit
```
public long previousClearBit(long fromIndex)
```
    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:
    
    fromIndex - 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
  - length
```
public long length()
```
    Returns the "logical size" of this BiggerBitSet: the index of the highest set bit in the BiggerBitSet plus one. Returns zero if the BiggerBitSet contains no set bits.
    
    Returns:
    
    the logical size of this BiggerBitSet
  - isEmpty
```
public boolean isEmpty()
```
    Returns true if this BiggerBitSet contains no bits that are set to true.
    
    Returns:
    
    boolean indicating whether this BiggerBitSet is empty
  - intersects
```
public boolean intersects(BiggerBitSet set)
```
    Returns true if the specified BiggerBitSet has any bits set to true that are also set to true in this BiggerBitSet.
    
    Parameters:
    
    set - BiggerBitSet to intersect with
    
    Returns:
    
    boolean indicating whether this BiggerBitSet intersects the specified BiggerBitSet
  - cardinality
```
public long cardinality()
```
    Returns the number of bits set to true in this BiggerBitSet.
    
    Returns:
    
    the number of bits set to true in this BiggerBitSet
  - and
```
public void and(BiggerBitSet set)
```
    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:
    
    set - a bit set
  - or
```
public void or(BiggerBitSet set)
```
    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:
    
    set - a bit set
  - xor
```
public void xor(BiggerBitSet set)
```
    Performs a logical XOR 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 one of the following statements holds:
    - The bit initially has the value true, and the corresponding bit in the argument has the value false.
    - The bit initially has the value false, and the corresponding bit in the argument has the value true.
    Parameters:
    
    set - a bit set
  - andNot
```
public void andNot(BiggerBitSet set)
```
    Clears all of the bits in this BiggerBitSet whose corresponding bit is set in the specified BiggerBitSet.
    
    Parameters:
    
    set - the BiggerBitSet with which to mask this BiggerBitSet
  - hashCode
```
public int hashCode()
```
    Returns the hash code value for this bit set. The hash code depends only on which bits are set within this BiggerBitSet.
    The hash code is defined to be the result of the following calculation:
```
 
      public int hashCode() {
          long h = 1234;
          long[] words = toLongArray();
          for (int i = words.length; --i >= 0; )
              h ^= words[i] * (i + 1);
          return (int)((h >> 32) ^ h);
      }
```
    Note that the hash code changes if the set of bits is altered.
    Overrides:
    
    hashCode in class java.lang.Object
    
    Returns:
    
    the hash code value for this bit set
  - size
```
public long size()
```
    Returns the number of bits of space actually in use by this BiggerBitSet to represent bit values. The maximum element in the set is the size - 1st element.
    
    Returns:
    
    the number of bits currently in this bit set
  - equals
```
public boolean equals(java.lang.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 Bitset object that has exactly the same set of bits set to true as this bit set. That is, for every nonnegative int index k,
```
((BiggerBitSet)obj).get(k) == this.get(k)
```
    must be true. The current sizes of the two bit sets are not compared.
    Overrides:
    
    equals in class java.lang.Object
    
    Parameters:
    
    obj - the object to compare with
    
    Returns:
    
    true if the objects are the same; false otherwise
    
    See Also:
    
    size()
  - clone
```
public java.lang.Object clone()
```
    Cloning this BiggerBitSet produces a new BiggerBitSet 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.
    
    Overrides:
    
    clone in class java.lang.Object
    
    Returns:
    
    a clone of this bit set
    
    See Also:
    
    size()
  - nextSetBit
```
private long nextSetBit(long fromIndex,
                        long toWordIndex)
```
    Returns the index of the first bit that is set to true that occurs on or after the specified starting index and up to and including the specified word index If no such bit exists then -1 is returned.
    
    Parameters:
    
    fromIndex - the index to start checking from (inclusive)
    
    toWordIndex - the last word index to check (inclusive)
    
    Returns:
    
    the index of the next set bit, or -1 if there is no such bit
  - numberOfLeadingZerosInt
```
public static int numberOfLeadingZerosInt(int i)
```
    Returns the number of zero bits preceding the highest-order ("leftmost") one-bit in the two's complement binary representation of the specified int value. Returns 32 if the specified value has no one-bits in its two's complement representation, in other words if it is equal to zero.
    Note that this method is closely related to the logarithm base 2. For all positive int values x:
    - floor(log₂(x)) = 31 - numberOfLeadingZeros(x)
    - ceil(log₂(x)) = 32 - numberOfLeadingZeros(x - 1)
    Parameters:
    
    i - the value whose number of leading zeros is to be computed
    
    Returns:
    
    the number of zero bits preceding the highest-order ("leftmost") one-bit in the two's complement binary representation of the specified int value, or 32 if the value is equal to zero. TODO: Replace this with Integer.numberOfTrailingZeros when migrating to Java 1.5 or later.
  - numberOfTrailingZerosInt
```
public static int numberOfTrailingZerosInt(int i)
```
    Returns the number of zero bits following the lowest-order ("rightmost") one-bit in the two's complement binary representation of the specified int value. Returns 32 if the specified value has no one-bits in its two's complement representation, in other words if it is equal to zero.
    
    Parameters:
    
    i - the value whose number of trailing zeros is to be computed
    
    Returns:
    
    the number of zero bits following the lowest-order ("rightmost") one-bit in the two's complement binary representation of the specified int value, or 32 if the value is equal to zero. TODO: Replace this with Integer.numberOfTrailingZeros when migrating to Java 1.5 or later.
  - numberOfLeadingZerosLong
```
public static int numberOfLeadingZerosLong(long i)
```
    Returns the number of zero bits preceding the highest-order ("leftmost") one-bit in the two's complement binary representation of the specified long value. Returns 64 if the specified value has no one-bits in its two's complement representation, in other words if it is equal to zero.
    Note that this method is closely related to the logarithm base 2. For all positive long values x:
    - floor(log₂(x)) = 63 - numberOfLeadingZeros(x)
    - ceil(log₂(x)) = 64 - numberOfLeadingZeros(x - 1)
    Parameters:
    
    i - the value whose number of leading zeros is to be computed
    
    Returns:
    
    the number of zero bits preceding the highest-order ("leftmost") one-bit in the two's complement binary representation of the specified long value, or 64 if the value is equal to zero. TODO: Replace this with Long.numberOfLeadingZeros when migrating to Java 1.5 or later.
  - numberOfTrailingZerosLong
```
public static int numberOfTrailingZerosLong(long i)
```
    Returns the number of zero bits following the lowest-order ("rightmost") one-bit in the two's complement binary representation of the specified long value. Returns 64 if the specified value has no one-bits in its two's complement representation, in other words if it is equal to zero.
    
    Parameters:
    
    i - the value whose number of trailing zeros is to be computed
    
    Returns:
    
    the number of zero bits following the lowest-order ("rightmost") one-bit in the two's complement binary representation of the specified long value, or 64 if the value is equal to zero. TODO: Replace this with Long.numberOfTrailingZeros when migrating to Java 1.5 or later.
  - bitCountLong
```
public static int bitCountLong(long i)
```
    Returns the number of one-bits in the two's complement binary representation of the specified long value. This function is sometimes referred to as the population count.
    
    Parameters:
    
    i - the value whose bits are to be counted
    
    Returns:
    
    the number of one-bits in the two's complement binary representation of the specified long value. TODO: Replace this with Long.bitCount when migrating to Java 1.5 or later.

Class BiggerBitSet

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

ADDRESS_BITS_PER_WORD

BITS_PER_WORD

BIT_INDEX_MASK

WORD_MASK

words

Constructor Detail

BiggerBitSet

Method Detail

wordIndex

initWords

checkRange

flip

flip

set

set

setRange

setRange

clear

clearRange

clear

get

nextSetBit

nextClearBit

previousSetBit

previousClearBit

length

isEmpty

intersects

cardinality

and

or

xor

andNot

hashCode

size

equals

clone

nextSetBit

numberOfLeadingZerosInt

numberOfTrailingZerosInt

numberOfLeadingZerosLong

numberOfTrailingZerosLong

bitCountLong