Class AtomicFixedLengthBitVector

java.lang.Object
de.calamanari.pk.util.AtomicFixedLengthBitVector
All Implemented Interfaces:
java.io.Serializable

public class AtomicFixedLengthBitVector
extends java.lang.Object
implements java.io.Serializable
AtomicFixedLengthBitVector is a fixed-size bit-vector implementation for concurrent access.
Author:
Karl Eilebrecht
See Also:
Serialized Form
  • Constructor Summary

    Constructors
    Constructor Description
    AtomicFixedLengthBitVector​(long size)
    Creates a new bit vector of the given size aligned to multiples of 64.
    AtomicFixedLengthBitVector​(long[] longArray)
    Creates the bit vector from the given number of longs, see toLongArray()
  • Method Summary

    Modifier and Type Method Description
    void clear()
    Sets all bits in this vector to 0.
    long countNumberOfBitsSet()
    Counts the 1-bits in the vector from left to right.
    void flipBit​(long position)
    Flips the bit at the given position (0 -> 1 resp. 1 -> 0)
    int getBit​(long position)  
    long getSize()
    Returns the total capacity (always a multiple of 64)
    boolean isBitSet​(long position)  
    void setBit​(long position)
    Sets the bit at the given position to 1
    boolean setBitIfNotPresent​(long position)
    Sets the bit if it was not present before.
    long[] toLongArray()
    Returns the long-array representation of this bit vector
    java.lang.String toPaddedBinaryString()
    Only for debugging, for easier checking (single consistent vector) longs appear from right (LSB) to left
    java.lang.String toString()  
    void unsetBit​(int position)
    Sets the bit at the given position to 0
    boolean unsetBitIfPresent​(int position)
    Sets the bit at the given position to 0, if it was 0 before.

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Constructor Details

    • AtomicFixedLengthBitVector

      public AtomicFixedLengthBitVector​(long size)
      Creates a new bit vector of the given size aligned to multiples of 64.

      Thus getSize() may be greater than the specified size, max difference 63.

      Parameters:
      size - >=1
    • AtomicFixedLengthBitVector

      public AtomicFixedLengthBitVector​(long[] longArray)
      Creates the bit vector from the given number of longs, see toLongArray()
      Parameters:
      longArray - data
  • Method Details

    • setBit

      public void setBit​(long position)
      Sets the bit at the given position to 1
      Parameters:
      position - bit position in the vector
      Throws:
      java.lang.IndexOutOfBoundsException - if the position is negative or exceeds the capacity
    • setBitIfNotPresent

      public boolean setBitIfNotPresent​(long position)
      Sets the bit if it was not present before. In other words, the caller will know if it was already present in a single operation.

      Note: In any cases the bit in the vector will be 1 afterwards.

      Parameters:
      position - bit position in the vector
      Returns:
      true if the bit has been set or false if it was set before
      Throws:
      java.lang.IndexOutOfBoundsException - if the position is negative or exceeds the capacity
    • unsetBit

      public void unsetBit​(int position)
      Sets the bit at the given position to 0
      Parameters:
      position - bit position in the vector
      Throws:
      java.lang.IndexOutOfBoundsException - if the position is negative or exceeds the capacity
    • unsetBitIfPresent

      public boolean unsetBitIfPresent​(int position)
      Sets the bit at the given position to 0, if it was 0 before. In other words, the caller will know if the bit was present before in a single operation.

      Note: In any cases the bit in the vector will be 0 afterwards.

      Parameters:
      position - bit position in the vector
      Returns:
      true if the bit has been unset or false if the bit was 0 before
      Throws:
      java.lang.IndexOutOfBoundsException - if the position is negative or exceeds the capacity
    • flipBit

      public void flipBit​(long position)
      Flips the bit at the given position (0 -> 1 resp. 1 -> 0)
      Parameters:
      position - bit position in the vector
      Throws:
      java.lang.IndexOutOfBoundsException - if the position is negative or exceeds the capacity
    • isBitSet

      public boolean isBitSet​(long position)
      Parameters:
      position - bit position in the vector
      Returns:
      true if the bit was set, false otherwise
      Throws:
      java.lang.IndexOutOfBoundsException - if the position is negative or exceeds the capacity
    • getBit

      public int getBit​(long position)
      Parameters:
      position - bit position in the vector
      Returns:
      1 if the bit was set, 0 otherwise
      Throws:
      java.lang.IndexOutOfBoundsException - if the position is negative or exceeds the capacity
    • countNumberOfBitsSet

      public long countNumberOfBitsSet()
      Counts the 1-bits in the vector from left to right.

      Important: This operation is not atomic but subsequently counts the bits in the underlying long values. Thus calling setBit(long) or flipBit(long) concurrently is safe but may lead to unexpected results because the effect on the overall count will depend on the position the concurrent change happens.

      Returns:
      number of bits set to 1 in this vector
    • clear

      public void clear()
      Sets all bits in this vector to 0.

      Important: This operation is not atomic but consists on a sequence of updates. Calling it concurrently with other operations on this vector is safe but may lead to surprising results.

    • getSize

      public long getSize()
      Returns the total capacity (always a multiple of 64)
      Returns:
      number of bits the vector can store
    • toLongArray

      public long[] toLongArray()
      Returns the long-array representation of this bit vector

      Important:

      • Consider memory consumption, this operation will create a copy and thus double the required memory.
      • This operation is not atomic. It is still safe to be called concurrently with other operations on this bit vector, but this may lead to unexpected results.
      Returns:
      copy of the internal long array
    • toString

      public java.lang.String toString()
      Overrides:
      toString in class java.lang.Object
    • toPaddedBinaryString

      public java.lang.String toPaddedBinaryString()
      Only for debugging, for easier checking (single consistent vector) longs appear from right (LSB) to left
      Returns:
      a string composed of 0s and 1s, may be huge!