Package org.apache.lucene.util

Class SparseFixedBitSet

java.lang.Object
org.apache.lucene.util.BitSet
org.apache.lucene.util.SparseFixedBitSet
All Implemented Interfaces:
Accountable, Bits
public class SparseFixedBitSet extends BitSet implements Bits, Accountable
A bit set that only stores longs that have at least one bit which is set. The way it works is that the space of bits is divided into blocks of 4096 bits, which is 64 longs. Then for each block, we have:
  • a long[] which stores the non-zero longs for that block
  • a long so that bit i being set means that the i-th long of the block is non-null, and its offset in the array of longs is the number of one bits on the right of the i-th bit.

  • Field Details

    • BASE_RAM_BYTES_USED

      private static final long BASE_RAM_BYTES_USED

    • SINGLE_ELEMENT_ARRAY_BYTES_USED

      private static final long SINGLE_ELEMENT_ARRAY_BYTES_USED

    • MASK_4096

      private static final int MASK_4096
      See Also:

    • indices

      final long[] indices

    • bits

      final long[][] bits

    • length

      final int length

    • nonZeroLongCount

      int nonZeroLongCount

    • ramBytesUsed

      long ramBytesUsed

  • Constructor Details

    • SparseFixedBitSet

      public SparseFixedBitSet(int length)
      Create a SparseFixedBitSet that can contain bits between 0 included and length excluded.

  • Method Details

    • blockCount

      private static int blockCount(int length)

    • length

      public int length()
      Description copied from interface: Bits
      Returns the number of bits in this set
      Specified by:
      length in interface Bits

    • consistent

      private boolean consistent(int index)

    • cardinality

      public int cardinality()
      Description copied from class: BitSet
      Return the number of bits that are set. NOTE: this method is likely to run in linear time
      Specified by:
      cardinality in class BitSet

    • approximateCardinality

      public int approximateCardinality()
      Description copied from class: BitSet
      Return an approximation of the cardinality of this set. Some implementations may trade accuracy for speed if they have the ability to estimate the cardinality of the set without iterating over all the data. The default implementation returns BitSet.cardinality().
      Overrides:
      approximateCardinality in class BitSet

    • get

      public boolean get(int i)
      Description copied from interface: Bits
      Returns the value of the bit with the specified index.
      Specified by:
      get in interface Bits
      Parameters:
      i - index, should be non-negative and < Bits.length(). The result of passing negative or out of bounds values is undefined by this interface, just don't do it!
      Returns:
      true if the bit is set, false otherwise.

    • oversize

      private static int oversize(int s)

    • set

      public void set(int i)
      Set the bit at index i.
      Specified by:
      set in class BitSet

    • insertBlock

      private void insertBlock(int i4096, int i64, int i)

    • insertLong

      private void insertLong(int i4096, int i64, int i, long index)

    • clear

      public void clear(int i)
      Clear the bit at index i.
      Specified by:
      clear in class BitSet

    • and

      private void and(int i4096, int i64, long mask)

    • removeLong

      private void removeLong(int i4096, int i64, long index, int o)

    • clear

      public void clear(int from, int to)
      Description copied from class: BitSet
      Clears a range of bits.
      Specified by:
      clear in class BitSet
      Parameters:
      from - lower index
      to - one-past the last bit to clear

    • mask

      private static long mask(int from, int to)

    • clearWithinBlock

      private void clearWithinBlock(int i4096, int from, int to)

    • firstDoc

      private int firstDoc(int i4096)
      Return the first document that occurs on or after the provided block index.

    • nextSetBit

      public int nextSetBit(int i)
      Description copied from class: BitSet
      Returns the index of the first set bit starting at the index specified. DocIdSetIterator.NO_MORE_DOCS is returned if there are no more set bits.
      Specified by:
      nextSetBit in class BitSet

    • lastDoc

      private int lastDoc(int i4096)
      Return the last document that occurs on or before the provided block index.

    • prevSetBit

      public int prevSetBit(int i)
      Description copied from class: BitSet
      Returns the index of the last set bit before or on the index specified. -1 is returned if there are no more set bits.
      Specified by:
      prevSetBit in class BitSet

    • longBits

      private long longBits(long index, long[] bits, int i64)
      Return the long bits at the given i64 index.

    • or

      private void or(int i4096, long index, long[] bits, int nonZeroLongCount)

    • or

      private void or(SparseFixedBitSet other)

    • orDense

      private void orDense(DocIdSetIterator it) throws IOException
      or(DocIdSetIterator) impl that works best when it is dense
      Throws:
      IOException

    • or

      public void or(DocIdSetIterator it) throws IOException
      Description copied from class: BitSet
      Does in-place OR of the bits provided by the iterator. The state of the iterator after this operation terminates is undefined.
      Overrides:
      or in class BitSet
      Throws:
      IOException

    • ramBytesUsed

      public long ramBytesUsed()
      Description copied from interface: Accountable
      Return the memory usage of this object in bytes. Negative values are illegal.
      Specified by:
      ramBytesUsed in interface Accountable

    • toString

      public String toString()
      Overrides:
      toString in class Object