Package it.unimi.dsi.bits

Class LongBigArrayBitVector

java.lang.Object
java.util.AbstractCollection<Boolean>
it.unimi.dsi.fastutil.booleans.AbstractBooleanCollection
it.unimi.dsi.fastutil.booleans.AbstractBooleanBigList
it.unimi.dsi.bits.AbstractBitVector
it.unimi.dsi.bits.LongBigArrayBitVector
All Implemented Interfaces:
BitVector, BigList<Boolean>, BooleanBigList, BooleanCollection, BooleanIterable, BooleanStack, Size64, Stack<Boolean>, Serializable, Cloneable, Comparable<BigList<? extends Boolean>>, Iterable<Boolean>, Collection<Boolean>, RandomAccess
public class LongBigArrayBitVector extends AbstractBitVector implements Cloneable, Serializable
A bit vector implementation based on a big arrays of longs.

The main goal of this class is to be able to accommodate very large bit vectors. With respect to LongArrayBitVector, many optimized methods are missing and rely on the generic implementations in AbstractBitVector. Instances of this class represent a bit vector using a big array of longs that is enlarged as needed when new entries are created (using LongBigArrays.grow(long[][], long, long)), but is never made smaller (even on a clear()). Use trim() for that purpose.

Besides usual methods for setting and getting bits, this class provides views that make it possible to access comfortably the bit vector in different ways: for instance, asLongBigList(int) provide access as a list of longs, whereas AbstractBitVector.asLongSet() provides access in setwise form.

When enlarging the underlying array (e.g., for append(long, int) operations or add operations on the big list view), or when invoking ensureCapacity(long), this class calls LongBigArrays.grow(long[][], long, long), which could enlarge the array more than expected. On the contrary, length(long) (and the corresponding method in the big list view) sizes the underlying array in an exact manner.

Bit numbering follows the right-to-left convention: bit k (counted from the right) of word w is bit 64w + k of the overall bit vector.

If CHECKS is true at compile time, boundary checks for all bit operations will be compiled in. For maximum speed, you may want to recompile this class with CHECKS set to false. CHECKS is public, so you can check from your code whether you're being provided a version with checks or not. In any case, many checks happen when you enable assertions.

Warning: Several optional methods have still to be implemented (e.g., adding an element at an arbitrary position using the BooleanBigList methods).

Warning: The AbstractBitVector.bits() method uses the AbstractBitVector implementation, which will fail for bit vectors that cannot be stored in a single long array (i.e., more than Arrays.MAX_ARRAY_SIZE) * Long.SIZE).

See Also:

  • Field Details

    • CHECKS

      public static final boolean CHECKS
      Whether this class has been compiled with index checks or not.
      See Also:

    • length

      protected long length
      The number of bits in this vector.

    • bits

      protected transient long[][] bits
      The backing big array of this vector. Bit 0 of the first element of the first array contains bit 0 of the bit vector, bit 0 of the second element contains bit Long.SIZE of the bit vector and so on.

  • Constructor Details

    • LongBigArrayBitVector

      protected LongBigArrayBitVector(long capacity)

  • Method Details

    • words

      public static final long words(long size)
      Returns the number of words that are necessary to hold the given number of bits.
      Parameters:
      size - a number of bits.
      Returns:
      the number of words that are necessary to hold the given number of bits.

    • bits

      public static final long bits(long word)
      Returns the number of bits in the given number of words.
      Parameters:
      word - a word position.
      Returns:
      Long.SIZE * word.

    • word

      public static final long word(long index)
      Return the index of the word that holds a bit of specified index.
      Parameters:
      index - the index of a bit, or -1.
      Returns:
      the index of the word that holds the bit of given index, or -1 if index is -1.

    • getInstance

      public static LongBigArrayBitVector getInstance(long capacity)
      Creates a new empty bit vector of given capacity. The resulting vector will be able to contain capacity bits without reallocations of the backing array.

      Note that this constructor creates an empty bit vector. If you want a cleared bit vector of a specified size, please use the ofLength(long) factory method.

      Parameters:
      capacity - the capacity (in bits) of the new bit vector.
      Returns:
      a new bit vector of given capacity.

    • getInstance

      public static LongBigArrayBitVector getInstance()
      Creates a new empty bit vector. No allocation is actually performed.
      Returns:
      a new bit vector with no capacity.

    • ofLength

      public static LongBigArrayBitVector ofLength(long length)
      Creates a new empty bit vector of given length.
      Parameters:
      length - the size (in bits) of the new bit vector.

    • of

      public static LongBigArrayBitVector of(int... bit)
      Creates a new bit vector with given bits.
      Parameters:
      bit - a list of bits that will be set in the newly created bit vector.

    • length

      public long length()
      Description copied from interface: BitVector
      Returns the number of bits in this bit vector.

      If the number of bits in this bit vector is smaller than or equal to Integer.MAX_VALUE, this method is semantically equivalent to List.size(). In any case, this method is semantically equivalent to Size64.size64(), but it is prefererred.

      Specified by:
      length in interface BitVector
      Returns:
      the number of bits in this bit vector.

    • bigBits

      public long[][] bigBits()
      Returns the underlying big array.
      Returns:
      the underlying big array.

    • ensureCapacity

      public LongBigArrayBitVector ensureCapacity(long numBits)
      Ensures that this bit vector can hold the specified number of bits.

      This method uses LongBigArrays.grow(long[][], long, long) to ensure that there is enough space for the given number of bits. As a consequence, the actual length of the long array allocated might be larger than expected.

      Parameters:
      numBits - the number of bits that this vector must be able to contain.
      Returns:
      this bit vector.

    • length

      public LongBigArrayBitVector length(long newLength)
      Description copied from interface: BitVector
      Sets the number of bits in this bit vector.

      It is expected that this method will try to allocate exactly the necessary space.

      If the argument fits an integer, this method has the same side effects of BooleanList.size(int). In any case, this method has the same side effects of BigList.size(long), but it is preferred, as it has the advantage of returning this bit vector, thus making it possible to chain methods.

      Specified by:
      length in interface BitVector
      Overrides:
      length in class AbstractBitVector
      Parameters:
      newLength - the new length in bits for this bit vector.
      Returns:
      this bit vector.

    • fill

      public void fill(boolean value)
      Description copied from interface: BitVector
      Sets all bits this bit vector to the given boolean value (optional operation).
      Specified by:
      fill in interface BitVector
      Overrides:
      fill in class AbstractBitVector
      Parameters:
      value - the value (true or false).

    • trim

      public boolean trim()
      Reduces as must as possible the size of the backing array.
      Returns:
      true if some trimming was actually necessary.

    • clear

      public void clear()
      Sets the size of this bit vector to 0.

      Note that this method does not try to reallocate that backing array. If you want to force that behaviour, call trim() afterwards.

      Specified by:
      clear in interface Collection<Boolean>
      Overrides:
      clear in class AbstractBitVector

    • copy

      public LongBigArrayBitVector copy()
      Description copied from interface: BitVector
      Returns a copy of this bit vector.
      Specified by:
      copy in interface BitVector
      Overrides:
      copy in class AbstractBitVector
      Returns:
      a copy of this bit vector.

    • fast

      public LongBigArrayBitVector fast()
      Returns this bit vector.
      Specified by:
      fast in interface BitVector
      Overrides:
      fast in class AbstractBitVector
      Returns:
      this bit vector.

    • copy

      public static LongBigArrayBitVector copy(BitVector bv)
      Returns a copy of the given bit vector.

      This method uses BitVector.getLong(long, long) on Long.SIZE boundaries to copy at high speed.

      Parameters:
      bv - a bit vector.
      Returns:
      an instance of this class containing a copy of the given vector.

    • getBoolean

      public boolean getBoolean(long index)
      Specified by:
      getBoolean in interface BooleanBigList

    • set

      public boolean set(long index, boolean value)
      Specified by:
      set in interface BooleanBigList
      Overrides:
      set in class AbstractBitVector

    • set

      public void set(long index)
      Description copied from interface: BitVector
      Sets a bit in this bit vector (optional operation).
      Specified by:
      set in interface BitVector
      Overrides:
      set in class AbstractBitVector
      Parameters:
      index - the index of a bit.

    • clear

      public void clear(long index)
      Description copied from interface: BitVector
      Clears a bit in this bit vector (optional operation).
      Specified by:
      clear in interface BitVector
      Overrides:
      clear in class AbstractBitVector
      Parameters:
      index - the index of a bit.

    • append

      public LongBigArrayBitVector append(long value, int width)
      Description copied from interface: BitVector
      Appends the less significant bits of a long integer to this bit vector.
      Specified by:
      append in interface BitVector
      Overrides:
      append in class AbstractBitVector
      Parameters:
      value - a value to be appended
      width - the number of less significant bits to be added to this bit vector.
      Returns:
      this bit vector.

    • add

      public boolean add(boolean value)
      Specified by:
      add in interface BooleanCollection
      Overrides:
      add in class AbstractBitVector

    • getLong

      public long getLong(long from, long to)
      Description copied from interface: BitVector
      Returns the specified bit range as a long.

      Note that bit 0 of the returned long will be bit from of this bit vector.

      Implementations are invited to provide high-speed implementations for the case in which from is a multiple of Long.SIZE and to is from + Long.SIZE (or less, in case the vector length is exceeded). This behaviour make it possible to implement high-speed hashing, copies, etc.

      Specified by:
      getLong in interface BitVector
      Overrides:
      getLong in class AbstractBitVector
      Parameters:
      from - the starting bit (inclusive).
      to - the ending bit (exclusive).
      Returns:
      the long value contained in the specified bits.

    • wrap

      public static LongBigArrayBitVector wrap(long[][] array, long size)
      Wraps the given big array of longs in a bit vector for the given number of bits.

      Note that all bits in array beyond that of index size must be unset, or an exception will be thrown.

      Parameters:
      array - a big array of longs.
      size - the number of bits of the newly created bit vector.
      Returns:
      a bit vector of size size using array as backing big array.

    • wrap

      public static LongBigArrayBitVector wrap(long[][] array)
      Wraps the given array of longs in a bit vector.
      Parameters:
      array - an array of longs.
      Returns:
      a bit vector of size Long.SIZE times the length of array using array as backing array.

    • clone

      public LongBigArrayBitVector clone() throws CloneNotSupportedException
      Returns a cloned copy of this bit vector.

      This method is functionally equivalent to copy(), except that copy() trims the backing array.

      Overrides:
      clone in class Object
      Returns:
      a copy of this bit vector.
      Throws:
      CloneNotSupportedException

    • hashCode

      public int hashCode()
      Description copied from interface: BitVector
      Returns a hash code for this bit vector.

      Hash codes for bit vectors are defined as follows: 

       final long length = length();
 long fullLength = length & -Long.SIZE;
 long h = 0x9e3779b97f4a7c13L ^ length;
 for(long i = 0; i < fullLength; i += Long.SIZE) h ^= (h << 5) + getLong(i, i + Long.SIZE) + (h >>> 2);
 if (length != fullLength) h ^= (h << 5) + getLong(fullLength, length) + (h >>> 2);
 (int)((h >>> 32) ^ h);

      The last value is the hash code of the bit vector. This hashing is based on shift-add-xor hashing (M.V. Ramakrishna and Justin Zobel, “Performance in practice of string hashing functions”, Proc. of the Fifth International Conference on Database Systems for Advanced Applications, 1997, pages 215−223).

      The returned value is not a high-quality hash such as Jenkins's, but it can be computed very quickly; in any case, 32 bits are too few for a high-quality hash to be used in large-scale applications.

      Important: all bit vector implementations are required to return the value defined here. The simplest way to obtain this result is to subclass AbstractBitVector.

      Specified by:
      hashCode in interface BitVector
      Specified by:
      hashCode in interface Collection<Boolean>
      Overrides:
      hashCode in class AbstractBitVector
      Returns:
      a hash code for this bit vector.

    • equals

      public boolean equals(Object o)
      Specified by:
      equals in interface Collection<Boolean>
      Overrides:
      equals in class AbstractBitVector

    • equals

      public boolean equals(LongBigArrayBitVector v)

    • asLongBigList

      public LongBigList asLongBigList(int width)
      Description copied from interface: BitVector
      Returns a view of this bit vector as a list of nonnegative integers of specified width.

      More formally, getLong(p) will return the nonnegative integer defined by the bits starting at p * width (bit 0, inclusive) and ending at (p + 1) * width (bit width − 1, exclusive).

      Specified by:
      asLongBigList in interface BitVector
      Overrides:
      asLongBigList in class AbstractBitVector
      Parameters:
      width - a bit width.
      Returns:
      a view of this bit vector as a list of nonnegative integers of specified width.