cern.colt.bitvector

## Class BitVector

- java.lang.Object
- - cern.colt.PersistentObject
  - - cern.colt.bitvector.BitVector

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

      public class BitVector
      extends PersistentObject

  Fixed sized (non resizable) bitvector. Upon instance construction a bitvector is told to hold a fixed number of bits - it's size. The size can be any number (need not be a power of 2 or so). The bits of a `BitVector` are indexed by nonnegative integers. Any attempt to access a bit at an `index<0 || index>=size()` will throw an `IndexOutOfBoundsException`.

  Individual indexed bits can be examined, set, or cleared. Subranges can quickly be extracted, copied and replaced. Quick iteration over subranges is provided by optimized internal iterators (`forEach()` methods). One `BitVector` may be used to modify the contents of another `BitVector` through logical AND, OR, XOR and other similar operations.

  All operations consider the bits `0..size()-1` and nothing else. Operations involving two bitvectors (like AND, OR, XOR, etc.) will throw an `IllegalArgumentException` if the secondary bit vector has a size smaller than the receiver.

  A `BitVector` is never automatically resized, but it can manually be grown or shrinked via `setSize(...)`.

  For use cases that need to store several bits per information entity, quick accessors are provided that interpret subranges as 64 bit `long` integers.

  Why this class? Fist, `boolean[]` take one byte per stored bit. This class takes one bit per stored bit. Second, many applications find the semantics of `java.util.BitSet` not particularly helpful for their needs. Third, operations working on all bits of a bitvector are extremely quick. For example, on NT, Pentium Pro 200 Mhz, SunJDK1.2.2, java -classic, for two bitvectors A,B (both much larger than processor cache), the following results are obtained.

  - `A.and(B)` i.e. A = A & B --> runs at about 35 MB/sec
  - `A.cardinality()`, i.e. determining the selectivity, the number of bits in state "true" --> runs at about 80 MB/sec
  - Similar performance for `or, xor, andNot, not, copy, replace, partFromTo, indexOf, clear` etc.
  If you need extremely quick access to individual bits: Although getting and setting individual bits with methods `get(...)`, `set(...)` and `put(...)`is quick, it is even quicker (but not safe) to use `getQuick(...)` and `putQuick(...)` or even `QuickBitVector`.

  Note that this implementation is not synchronized.

  Version:
    1.01, 11/10/99
  See Also:
    `QuickBitVector`, `BitMatrix`, `BitSet`, Serialized Form

- - ### Field Summary

    - ### Fields inherited from class cern.colt.PersistentObject

      `serialVersionUID`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `BitVector(int size)` Constructs a bit vector that holds `size` bits.
    `BitVector(long[] bits, int size)` You normally need not use this method.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `and(BitVector other)` Performs a logical AND of the receiver with another bit vector (A = A & B).
    `void` | `andNot(BitVector other)` Clears all of the bits in receiver whose corresponding bit is set in the other bitvector (A = A \ B).
    `int` | `cardinality()` Returns the number of bits currently in the `true` state.
    `void` | `clear()` Clears all bits of the receiver.
    `void` | `clear(int bitIndex)` Changes the bit with index `bitIndex` to the "clear" (`false`) state.
    `java.lang.Object` | `clone()` Cloning this `BitVector` produces a new `BitVector` that is equal to it.
    `BitVector` | `copy()` Returns a deep copy of the receiver; calls `clone()` and casts the result.
    `long[]` | `elements()` You normally need not use this method.
    `void` | `elements(long[] bits, int size)` You normally need not use this method.
    `boolean` | `equals(java.lang.Object obj)` Compares this object against the specified object.
    `boolean` | `forEachIndexFromToInState(int from, int to, boolean state, IntProcedure procedure)` Applies a procedure to each bit index within the specified range that holds a bit in the given state.
    `boolean` | `get(int bitIndex)` Returns from the bitvector the value of the bit with the specified index.
    `long` | `getLongFromTo(int from, int to)` Returns a long value representing bits of the receiver from index `from` to index `to`.
    `boolean` | `getQuick(int bitIndex)` Returns from the bitvector the value of the bit with the specified index; WARNING: Does not check preconditions.
    `int` | `hashCode()` Returns a hash code value for the receiver.
    `int` | `indexOfFromTo(int from, int to, boolean state)` Returns the index of the first occurrence of the specified state.
    `void` | `not()` Performs a logical NOT on the bits of the receiver (A = ~A).
    `void` | `or(BitVector other)` Performs a logical OR of the receiver with another bit vector (A = A | B).
    `BitVector` | `partFromTo(int from, int to)` Constructs and returns a new bit vector which is a copy of the given range.
    `void` | `put(int bitIndex, boolean value)` Sets the bit with index `bitIndex` to the state specified by `value`.
    `void` | `putLongFromTo(long value, int from, int to)` Sets bits of the receiver from index `from` to index `to` to the bits of `value`.
    `void` | `putQuick(int bitIndex, boolean value)` Sets the bit with index `bitIndex` to the state specified by `value`; WARNING: Does not check preconditions.
    `void` | `replaceFromToWith(int from, int to, BitVector source, int sourceFrom)` Replaces the bits of the receiver in the given range with the bits of another bit vector.
    `void` | `replaceFromToWith(int from, int to, boolean value)` Sets the bits in the given range to the state specified by `value`.
    `void` | `set(int bitIndex)` Changes the bit with index `bitIndex` to the "set" (`true`) state.
    `void` | `setSize(int newSize)` Shrinks or expands the receiver so that it holds `newSize` bits.
    `int` | `size()` Returns the size of the receiver.
    `java.lang.String` | `toString()` Returns a string representation of the receiver.
    `void` | `xor(BitVector other)` Performs a logical XOR of the receiver with another bit vector (A = A ^ B).

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

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

- - ### Constructor Detail

    - #### BitVector

          public BitVector(long[] bits,
                   int size)

      You normally need not use this method. Use this method only if performance is critical. Constructs a bit vector with the given backing bits and size. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.

      A bitvector is modelled as a long array, i.e. `long[] bits` holds bits of a bitvector. Each long value holds 64 bits. The i-th bit is stored in bits[i/64] at bit position i % 64 (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).

      Throws:
        `java.lang.IllegalArgumentException` - if `size < 0 || size > bits.length*64`.

    - #### BitVector

          public BitVector(int size)

      Constructs a bit vector that holds `size` bits. All bits are initially `false`.
      Parameters:
        `size` - the number of bits the bit vector shall have.
      Throws:
        `java.lang.IllegalArgumentException` - if `size < 0`.

  - ### Method Detail

    - #### and

          public void and(BitVector other)

      Performs a logical AND of the receiver with another bit vector (A = A & B). The receiver is modified so that a bit in it has the value `true` if and only if it already had the value `true` and the corresponding bit in the other bit vector argument has the value `true`.
      Parameters:
        `other` - a bit vector.
      Throws:
        `java.lang.IllegalArgumentException` - if `size() > other.size()`.

    - #### andNot

          public void andNot(BitVector other)

      Clears all of the bits in receiver whose corresponding bit is set in the other bitvector (A = A \ B). In other words, determines the difference (A=A\B) between two bitvectors.
      Parameters:
        `other` - a bitvector with which to mask the receiver.
      Throws:
        `java.lang.IllegalArgumentException` - if `size() > other.size()`.

    - #### cardinality

          public int cardinality()

      Returns the number of bits currently in the `true` state. Optimized for speed. Particularly quick if the receiver is either sparse or dense.

    - #### clear

          public void clear()

      Clears all bits of the receiver.

    - #### clear

          public void clear(int bitIndex)

      Changes the bit with index `bitIndex` to the "clear" (`false`) state.
      Parameters:
        `bitIndex` - the index of the bit to be cleared.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `bitIndex<0 || bitIndex>=size()`

    - #### clone

          public java.lang.Object clone()

      Cloning this `BitVector` produces a new `BitVector` that is equal to it. The clone of the bit vector is another bit vector that has exactly the same bits set to `true` as this bit vector and the same current size, but independent state.
      Overrides:
        `clone` in class `PersistentObject`
      Returns:
        a deep copy of this bit vector.

    - #### copy

          public BitVector copy()

      Returns a deep copy of the receiver; calls `clone()` and casts the result.
      Returns:
        a deep copy of the receiver.

    - #### elements

          public long[] elements()

      You normally need not use this method. Use this method only if performance is critical. Returns the bit vector's backing bits. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the returned array directly via the [] operator, be sure you know what you're doing.

      A bitvector is modelled as a long array, i.e. `long[] bits` holds bits of a bitvector. Each long value holds 64 bits. The i-th bit is stored in bits[i/64] at bit position i % 64 (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).

    - #### elements

          public void elements(long[] bits,
                      int size)

      You normally need not use this method. Use this method only if performance is critical. Sets the bit vector's backing bits and size. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.

      A bitvector is modelled as a long array, i.e. `long[] bits` holds bits of a bitvector. Each long value holds 64 bits. The i-th bit is stored in bits[i/64] at bit position i % 64 (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).

      Parameters:
        `bits` - the backing bits of the bit vector.
        `size` - the number of bits the bit vector shall hold.
      Throws:
        `java.lang.IllegalArgumentException` - if `size < 0 || size > bits.length*64`.

    - #### 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 `BitVector` object that has the same size as the receiver and the same bits set to `true` as the receiver. That is, for every nonnegative `int` index `k`,

          ((BitVector)obj).get(k) == this.get(k)

      must be true.
      Overrides:
        `equals` in class `java.lang.Object`
      Parameters:
        `obj` - the object to compare with.
      Returns:
        `true` if the objects are the same; `false` otherwise.

    - #### forEachIndexFromToInState

          public boolean forEachIndexFromToInState(int from,
                                          int to,
                                          boolean state,
                                          IntProcedure procedure)

      Applies a procedure to each bit index within the specified range that holds a bit in the given state. Starts at index `from`, moves rightwards to `to`. Useful, for example, if you want to copy bits into an image or somewhere else.

      Optimized for speed. Particularly quick if one of the following conditions holds

      - `state==true` and the receiver is sparse (`cardinality()` is small compared to `size()`).
      - `state==false` and the receiver is dense (`cardinality()` is large compared to `size()`).
      Parameters:
        `from` - the leftmost search position, inclusive.
        `to` - the rightmost search position, inclusive.
        `state` - element to search for.
        `procedure` - a procedure object taking as argument the current bit index. Stops iteration if the procedure returns `false`, otherwise continues.
      Returns:
        `false` if the procedure stopped before all elements where iterated over, `true` otherwise.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if (`size()>0 && (from<0 || from>to || to>=size())`).

    - #### get

          public boolean get(int bitIndex)

      Returns from the bitvector the value of the bit with the specified index. The value is `true` if the bit with the index `bitIndex` is currently set; otherwise, returns `false`.
      Parameters:
        `bitIndex` - the bit index.
      Returns:
        the value of the bit with the specified index.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `bitIndex<0 || bitIndex>=size()`

    - #### getLongFromTo

          public long getLongFromTo(int from,
                           int to)

      Returns a long value representing bits of the receiver from index `from` to index `to`. Bits are returned as a long value with the return value having bit 0 set to bit `from`, ..., bit `to-from` set to bit `to`. All other bits of the return value are set to 0. If `to-from+1==0` then returns zero (`0L`).
      Parameters:
        `from` - index of start bit (inclusive).
        `to` - index of end bit (inclusive).
      Returns:
        the specified bits as long value.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `from<0 || from>=size() || to<0 || to>=size() || to-from+1<0 || to-from+1>64`

    - #### getQuick

          public boolean getQuick(int bitIndex)

      Returns from the bitvector the value of the bit with the specified index; WARNING: Does not check preconditions. The value is `true` if the bit with the index `bitIndex` is currently set; otherwise, returns `false`.

      Provided with invalid parameters this method may return invalid values without throwing any exception. You should only use this method when you are absolutely sure that the index is within bounds. Precondition (unchecked): `bitIndex >= 0 && bitIndex < size()`.

      Parameters:
        `bitIndex` - the bit index.
      Returns:
        the value of the bit with the specified index.

    - #### hashCode

          public int hashCode()

      Returns a hash code value for the receiver. The hash code depends only on which bits have been set within the receiver. The algorithm used to compute it may be described as follows.

      Suppose the bits in the receiver were to be stored in an array of `long` integers called, say, `bits`, in such a manner that bit `k` is set in the receiver (for nonnegative values of `k`) if and only if the expression

          ((k>>6) < bits.length) && ((bits[k>>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 h = 1234;
                for (int i = bits.length; --i >= 0; ) {
                     h ^= 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 `java.lang.Object`
      Returns:
        a hash code value for the receiver.

    - #### indexOfFromTo

          public int indexOfFromTo(int from,
                          int to,
                          boolean state)

      Returns the index of the first occurrence of the specified state. Returns `-1` if the receiver does not contain this state. Searches between `from`, inclusive and `to`, inclusive.

      Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): size=10^6, from=0, to=size-1, receiver contains matching state in the very end --> 0.002 seconds elapsed time.

      Parameters:
        `state` - state to search for.
        `from` - the leftmost search position, inclusive.
        `to` - the rightmost search position, inclusive.
      Returns:
        the index of the first occurrence of the element in the receiver; returns `-1` if the element is not found.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if (`size()>0 && (from<0 || from>to || to>=size())`).

    - #### not

          public void not()

      Performs a logical NOT on the bits of the receiver (A = ~A).

    - #### or

          public void or(BitVector other)

      Performs a logical OR of the receiver with another bit vector (A = A | B). The receiver 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 other bit vector argument has the value `true`.
      Parameters:
        `other` - a bit vector.
      Throws:
        `java.lang.IllegalArgumentException` - if `size() > other.size()`.

    - #### partFromTo

          public BitVector partFromTo(int from,
                             int to)

      Constructs and returns a new bit vector which is a copy of the given range. The new bitvector has `size()==to-from+1`.
      Parameters:
        `from` - the start index within the receiver, inclusive.
        `to` - the end index within the receiver, inclusive.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `size()>0 && (from<0 || from>to || to>=size()))`.

    - #### put

          public void put(int bitIndex,
                 boolean value)

      Sets the bit with index `bitIndex` to the state specified by `value`.
      Parameters:
        `bitIndex` - the index of the bit to be changed.
        `value` - the value to be stored in the bit.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `bitIndex<0 || bitIndex>=size()`

    - #### putLongFromTo

          public void putLongFromTo(long value,
                           int from,
                           int to)

      Sets bits of the receiver from index `from` to index `to` to the bits of `value`. Bit `from` is set to bit 0 of `value`, ..., bit `to` is set to bit `to-from` of `value`. All other bits stay unaffected. If `to-from+1==0` then does nothing.
      Parameters:
        `value` - the value to be copied into the receiver.
        `from` - index of start bit (inclusive).
        `to` - index of end bit (inclusive).
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `from<0 || from>=size() || to<0 || to>=size() || to-from+1<0 || to-from+1>64`.

    - #### putQuick

          public void putQuick(int bitIndex,
                      boolean value)

      Sets the bit with index `bitIndex` to the state specified by `value`; WARNING: Does not check preconditions.

      Provided with invalid parameters this method may set invalid values without throwing any exception. You should only use this method when you are absolutely sure that the index is within bounds. Precondition (unchecked): `bitIndex >= 0 && bitIndex < size()`.

      Parameters:
        `bitIndex` - the index of the bit to be changed.
        `value` - the value to be stored in the bit.

    - #### replaceFromToWith

          public void replaceFromToWith(int from,
                               int to,
                               BitVector source,
                               int sourceFrom)

      Replaces the bits of the receiver in the given range with the bits of another bit vector. Replaces the range `[from,to]` with the contents of the range `[sourceFrom,sourceFrom+to-from]`, all inclusive. If `source==this` and the source and destination range intersect in an ambiguous way, then replaces as if using an intermediate auxiliary copy of the receiver.

      Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): replace 10^6 ill aligned bits --> 0.02 seconds elapsed time.

      Parameters:
        `from` - the start index within the receiver, inclusive.
        `to` - the end index within the receiver, inclusive.
        `source` - the source bitvector to copy from.
        `sourceFrom` - the start index within `source`, inclusive.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `size()>0 && (from<0 || from>to || to>=size() || sourceFrom<0 || sourceFrom+to-from+1>source.size()))`.

    - #### replaceFromToWith

          public void replaceFromToWith(int from,
                               int to,
                               boolean value)

      Sets the bits in the given range to the state specified by `value`.

      Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): replace 10^6 ill aligned bits --> 0.002 seconds elapsed time.

      Parameters:
        `from` - the start index, inclusive.
        `to` - the end index, inclusive.
        `value` - the value to be stored in the bits of the range.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `size()>0 && (from<0 || from>to || to>=size())`.

    - #### set

          public void set(int bitIndex)

      Changes the bit with index `bitIndex` to the "set" (`true`) state.
      Parameters:
        `bitIndex` - the index of the bit to be set.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `bitIndex<0 || bitIndex>=size()`

    - #### setSize

          public void setSize(int newSize)

      Shrinks or expands the receiver so that it holds `newSize` bits. If the receiver is expanded, additional `false` bits are added to the end. If the receiver is shrinked, all bits between the old size and the new size are lost; their memory is subject to garbage collection. (This method introduces a new backing array of elements. WARNING: if you have more than one BitVector or BitMatrix sharing identical backing elements, be sure you know what you are doing.)
      Parameters:
        `newSize` - the number of bits the bit vector shall have.
      Throws:
        `java.lang.IllegalArgumentException` - if `size < 0`.

    - #### size

          public int size()

      Returns the size of the receiver.

    - #### toString

          public java.lang.String toString()

      Returns a string representation of the receiver. For every index for which the receiver contains a bit in the "set" (`true`) state, the decimal representation of that index is included in the result. Such indeces are listed in order from lowest to highest, separated by ", " (a comma and a space) and surrounded by braces.
      Overrides:
        `toString` in class `java.lang.Object`
      Returns:
        a string representation of this bit vector.

    - #### xor

          public void xor(BitVector other)

      Performs a logical XOR of the receiver with another bit vector (A = A ^ B). The receiver 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:
        `other` - a bit vector.
      Throws:
        `java.lang.IllegalArgumentException` - if `size() > other.size()`.

Jump to the Colt Homepage