Class FixedBitSet

  • All Implemented Interfaces:
    Accountable, Bits

    public final class FixedBitSet
    extends BitSet
    BitSet of fixed length (numBits), backed by accessible (getBits()) long[], accessed with an int index, implementing Bits and DocIdSet. If you need to manage more than 2.1B bits, use LongBitSet.
    • Constructor Summary

      Constructors 
      Constructor Description
      FixedBitSet​(int numBits)
      Creates a new LongBitSet.
      FixedBitSet​(long[] storedBits, int numBits)
      Creates a new LongBitSet using the provided long[] array as backing store.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void and​(long[] otherArr, int otherNumWords)  
      void and​(FixedBitSet other)
      this = this AND other
      private void andNot​(int otherOffsetWords, long[] otherArr, int otherNumWords)  
      private void andNot​(int otherOffsetWords, FixedBitSet other)  
      void andNot​(DocIdSetIterator iter)  
      void andNot​(FixedBitSet other)
      this = this AND NOT other
      static long andNotCount​(FixedBitSet a, FixedBitSet b)
      Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))".
      int approximateCardinality()
      Return an approximation of the cardinality of this set.
      Bits asReadOnlyBits()
      Convert this instance to read-only Bits.
      static int bits2words​(int numBits)
      returns the number of 64 bit words it would take to hold numBits
      int cardinality()
      Returns number of set bits.
      void clear()
      Clear all the bits of the set.
      void clear​(int index)
      Clear the bit at i.
      void clear​(int startIndex, int endIndex)
      Clears a range of bits.
      FixedBitSet clone()  
      static FixedBitSet copyOf​(Bits bits)
      Make a copy of the given bits.
      static FixedBitSet ensureCapacity​(FixedBitSet bits, int numBits)
      If the given FixedBitSet is large enough to hold numBits+1, returns the given bits, otherwise returns a new FixedBitSet which can hold the requested number of bits.
      boolean equals​(java.lang.Object o)  
      void flip​(int index)
      Flip the bit at the provided index.
      void flip​(int startIndex, int endIndex)
      Flips a range of bits
      boolean get​(int index)
      Returns the value of the bit with the specified index.
      boolean getAndClear​(int index)  
      boolean getAndSet​(int index)
      Set the bit at i, returning true if it was previously set.
      long[] getBits()
      Expert.
      int hashCode()  
      static long intersectionCount​(FixedBitSet a, FixedBitSet b)
      Returns the popcount or cardinality of the intersection of the two sets.
      boolean intersects​(FixedBitSet other)
      returns true if the sets have any elements in common
      int length()
      Returns the number of bits in this set
      int nextSetBit​(int index)
      Returns the index of the first set bit starting at the index specified.
      private void or​(int otherOffsetWords, long[] otherArr, int otherNumWords)  
      private void or​(int otherOffsetWords, FixedBitSet other)  
      void or​(DocIdSetIterator iter)
      Does in-place OR of the bits provided by the iterator.
      void or​(FixedBitSet other)
      this = this OR other
      int prevSetBit​(int index)
      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.
      boolean scanIsEmpty()
      Scans the backing store to check if all bits are clear.
      void set​(int index)
      Set the bit at i.
      void set​(int startIndex, int endIndex)
      Sets a range of bits
      static long unionCount​(FixedBitSet a, FixedBitSet b)
      Returns the popcount or cardinality of the union of the two sets.
      private boolean verifyGhostBitsClear()
      Checks if the bits past numBits are clear.
      private void xor​(long[] otherBits, int otherNumWords)  
      void xor​(DocIdSetIterator iter)
      Does in-place XOR of the bits provided by the iterator.
      void xor​(FixedBitSet other)
      this = this XOR other
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • BASE_RAM_BYTES_USED

        private static final long BASE_RAM_BYTES_USED
      • bits

        private final long[] bits
      • numBits

        private final int numBits
      • numWords

        private final int numWords
    • Constructor Detail

      • FixedBitSet

        public FixedBitSet​(int numBits)
        Creates a new LongBitSet. The internally allocated long array will be exactly the size needed to accommodate the numBits specified.
        Parameters:
        numBits - the number of bits needed
      • FixedBitSet

        public FixedBitSet​(long[] storedBits,
                           int numBits)
        Creates a new LongBitSet using the provided long[] array as backing store. The storedBits array must be large enough to accommodate the numBits specified, but may be larger. In that case the 'extra' or 'ghost' bits must be clear (or they may provoke spurious side-effects)
        Parameters:
        storedBits - the array to use as backing store
        numBits - the number of bits actually needed
    • Method Detail

      • ensureCapacity

        public static FixedBitSet ensureCapacity​(FixedBitSet bits,
                                                 int numBits)
        If the given FixedBitSet is large enough to hold numBits+1, returns the given bits, otherwise returns a new FixedBitSet which can hold the requested number of bits.

        NOTE: the returned bitset reuses the underlying long[] of the given bits if possible. Also, calling length() on the returned bits may return a value greater than numBits.

      • bits2words

        public static int bits2words​(int numBits)
        returns the number of 64 bit words it would take to hold numBits
      • intersectionCount

        public static long intersectionCount​(FixedBitSet a,
                                             FixedBitSet b)
        Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified.
      • unionCount

        public static long unionCount​(FixedBitSet a,
                                      FixedBitSet b)
        Returns the popcount or cardinality of the union of the two sets. Neither set is modified.
      • andNotCount

        public static long andNotCount​(FixedBitSet a,
                                       FixedBitSet b)
        Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified.
      • 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
      • verifyGhostBitsClear

        private boolean verifyGhostBitsClear()
        Checks if the bits past numBits are clear. Some methods rely on this implicit assumption: search for "Depends on the ghost bits being clear!"
        Returns:
        true if the bits past numBits are clear.
      • length

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

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

        public long[] getBits()
        Expert.
      • cardinality

        public int cardinality()
        Returns number of set bits. NOTE: this visits every long in the backing bits array, and the result is not internally cached!
        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 index)
        Description copied from interface: Bits
        Returns the value of the bit with the specified index.
        Parameters:
        index - 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.
      • set

        public void set​(int index)
        Description copied from class: BitSet
        Set the bit at i.
        Specified by:
        set in class BitSet
      • getAndSet

        public boolean getAndSet​(int index)
        Description copied from class: BitSet
        Set the bit at i, returning true if it was previously set.
        Specified by:
        getAndSet in class BitSet
      • clear

        public void clear​(int index)
        Description copied from class: BitSet
        Clear the bit at i.
        Specified by:
        clear in class BitSet
      • getAndClear

        public boolean getAndClear​(int index)
      • nextSetBit

        public int nextSetBit​(int index)
        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
      • prevSetBit

        public int prevSetBit​(int index)
        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
      • or

        public void or​(DocIdSetIterator iter)
                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
      • or

        public void or​(FixedBitSet other)
        this = this OR other
      • or

        private void or​(int otherOffsetWords,
                        FixedBitSet other)
      • or

        private void or​(int otherOffsetWords,
                        long[] otherArr,
                        int otherNumWords)
      • xor

        public void xor​(FixedBitSet other)
        this = this XOR other
      • xor

        public void xor​(DocIdSetIterator iter)
                 throws java.io.IOException
        Does in-place XOR of the bits provided by the iterator.
        Throws:
        java.io.IOException
      • xor

        private void xor​(long[] otherBits,
                         int otherNumWords)
      • intersects

        public boolean intersects​(FixedBitSet other)
        returns true if the sets have any elements in common
      • and

        public void and​(FixedBitSet other)
        this = this AND other
      • and

        private void and​(long[] otherArr,
                         int otherNumWords)
      • andNot

        public void andNot​(DocIdSetIterator iter)
                    throws java.io.IOException
        Throws:
        java.io.IOException
      • andNot

        public void andNot​(FixedBitSet other)
        this = this AND NOT other
      • andNot

        private void andNot​(int otherOffsetWords,
                            FixedBitSet other)
      • andNot

        private void andNot​(int otherOffsetWords,
                            long[] otherArr,
                            int otherNumWords)
      • scanIsEmpty

        public boolean scanIsEmpty()
        Scans the backing store to check if all bits are clear. The method is deliberately not called "isEmpty" to emphasize it is not low cost (as isEmpty usually is).
        Returns:
        true if all bits are clear.
      • flip

        public void flip​(int startIndex,
                         int endIndex)
        Flips a range of bits
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to flip
      • flip

        public void flip​(int index)
        Flip the bit at the provided index.
      • set

        public void set​(int startIndex,
                        int endIndex)
        Sets a range of bits
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to set
      • clear

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

        public FixedBitSet clone()
        Overrides:
        clone in class java.lang.Object
      • equals

        public boolean equals​(java.lang.Object o)
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • copyOf

        public static FixedBitSet copyOf​(Bits bits)
        Make a copy of the given bits.
      • asReadOnlyBits

        public Bits asReadOnlyBits()
        Convert this instance to read-only Bits. This is useful in the case that this FixedBitSet is returned as a Bits instance, to make sure that consumers may not get write access back by casting to a FixedBitSet. NOTE: Changes to this FixedBitSet will be reflected on the returned Bits.