Class SparseFixedBitSet

  • All Implemented Interfaces:
    Accountable, Bits

    public class SparseFixedBitSet
    extends BitSet
    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.
    • Constructor Summary

      Constructors 
      Constructor Description
      SparseFixedBitSet​(int length)
      Create a SparseFixedBitSet that can contain bits between 0 included and length excluded.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void and​(int i4096, int i64, long mask)  
      int approximateCardinality()
      Return an approximation of the cardinality of this set.
      private static int blockCount​(int length)  
      int cardinality()
      Return the number of bits that are set.
      void clear()
      Clear all the bits of the set.
      void clear​(int i)
      Clear the bit at index i.
      void clear​(int from, int to)
      Clears a range of bits.
      private void clearWithinBlock​(int i4096, int from, int to)  
      private boolean consistent​(int index)  
      private int firstDoc​(int i4096)
      Return the first document that occurs on or after the provided block index.
      boolean get​(int i)
      Returns the value of the bit with the specified index.
      boolean getAndSet​(int i)
      Set the bit at i, returning true if it was previously set.
      private void insertBlock​(int i4096, long i64bit, int i)  
      private void insertLong​(int i4096, long i64bit, int i, long index)  
      private int lastDoc​(int i4096)
      Return the last document that occurs on or before the provided block index.
      int length()
      Returns the number of bits in this set
      private long longBits​(long index, long[] bits, int i64)
      Return the long bits at the given i64 index.
      private static long mask​(int from, int to)  
      int nextSetBit​(int i)
      Returns the index of the first set bit starting at the index specified.
      private void or​(int i4096, long index, long[] bits, int nonZeroLongCount)  
      void or​(DocIdSetIterator it)
      Does in-place OR of the bits provided by the iterator.
      private void or​(SparseFixedBitSet other)  
      private void orDense​(DocIdSetIterator it)
      or(DocIdSetIterator) impl that works best when it is dense
      private static int oversize​(int s)  
      int prevSetBit​(int i)
      Returns the index of the last set bit before or on the index specified.
      long ramBytesUsed()
      Return the memory usage of this object in bytes.
      private void removeLong​(int i4096, int i64, long index, int o)  
      void set​(int i)
      Set the bit at index i.
      java.lang.String toString()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • 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
      • indices

        final long[] indices
      • bits

        final long[][] bits
      • length

        final int length
      • nonZeroLongCount

        int nonZeroLongCount
      • ramBytesUsed

        long ramBytesUsed
    • Constructor Detail

      • SparseFixedBitSet

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

      • blockCount

        private static int blockCount​(int length)
      • clear

        public void clear()
        Description copied from class: BitSet
        Clear all the bits of the set.

        Depending on the implementation, this may be significantly faster than clear(0, length).

        Overrides:
        clear in class BitSet
      • length

        public int length()
        Description copied from interface: Bits
        Returns the number of bits in this set
      • 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().
        Specified by:
        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.
        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.
      • getAndSet

        public boolean getAndSet​(int i)
        Description copied from class: BitSet
        Set the bit at i, returning true if it was previously set.
        Specified by:
        getAndSet in class BitSet
      • 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,
                                 long i64bit,
                                 int i)
      • insertLong

        private void insertLong​(int i4096,
                                long i64bit,
                                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

        public void or​(DocIdSetIterator it)
                throws java.io.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:
        java.io.IOException
      • ramBytesUsed

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

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