Package org.apache.lucene.util

Class FixedBitSet

java.lang.Object
org.apache.lucene.util.BitSet
org.apache.lucene.util.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.
NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

  • Nested Class Summary

    Nested classes/interfaces inherited from interface org.apache.lucene.util.Bits

    Bits.MatchAllBits, Bits.MatchNoBits

  • Field Summary

    Fields inherited from interface org.apache.lucene.util.Accountable

    NULL_ACCOUNTABLE

    Fields inherited from interface org.apache.lucene.util.Bits

    EMPTY_ARRAY

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    and(FixedBitSet other)
    this = this AND 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))".
    static void
    andRange(FixedBitSet source, int sourceFrom, FixedBitSet dest, int destFrom, int length)
    And length bits starting at sourceFrom from source into dest starting at destFrom.
    void
    applyMask(FixedBitSet bitSet, int offset)
    Apply this Bits instance to the given FixedBitSet, which starts at the given offset.
    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.
    int
    cardinality(int from, int to)
    Return the number of set bits between indexes from inclusive and to exclusive.
    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(Object o)
     
    void
    flip(int index)
    Flip the bit at the provided index.
    void
    flip(int startIndex, int endIndex)
    Flips a range of bits
    void
    forEach(int from, int to, int base, CheckedIntConsumer<IOException> consumer)
    For each set bit from from inclusive to to exclusive, add base to the bit index and call consumer on it.
    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.
    int
    nextSetBit(int start, int upperBound)
    Returns the index of the first set bit from start (inclusive) until end (exclusive).
    void
    or(DocIdSetIterator iter)
    Does in-place OR of the bits provided by the iterator.
    void
    or(FixedBitSet other)
    this = this OR other
    static void
    orRange(FixedBitSet source, int sourceFrom, FixedBitSet dest, int destFrom, int length)
    Or length bits starting at sourceFrom from source into dest starting at destFrom.
    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.
    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 org.apache.lucene.util.BitSet

    checkUnpositioned, of

    Methods inherited from class java.lang.Object

    finalize, getClass, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface org.apache.lucene.util.Accountable

    getChildResources

  • Constructor Details

    • FixedBitSet

      public FixedBitSet(int numBits)
      Creates a new FixedBitSet. 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 FixedBitSet 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 Details

    • 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

    • 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

    • cardinality

      public int cardinality(int from, int to)
      Return the number of set bits between indexes from inclusive and to exclusive.

    • 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.
      Overrides:
      nextSetBit in class BitSet

    • nextSetBit

      public int nextSetBit(int start, int upperBound)
      Description copied from class: BitSet
      Returns the index of the first set bit from start (inclusive) until end (exclusive). 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 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

    • orRange

      public static void orRange(FixedBitSet source, int sourceFrom, FixedBitSet dest, int destFrom, int length)
      Or length bits starting at sourceFrom from source into dest starting at destFrom.

    • andRange

      public static void andRange(FixedBitSet source, int sourceFrom, FixedBitSet dest, int destFrom, int length)
      And length bits starting at sourceFrom from source into dest starting at destFrom.

    • or

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

    • xor

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

    • xor

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

    • 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

    • andNot

      public void andNot(DocIdSetIterator iter) throws IOException
      Throws:
      IOException

    • andNot

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

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

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class 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.

    • applyMask

      public void applyMask(FixedBitSet bitSet, int offset)
      Description copied from interface: Bits
      Apply this Bits instance to the given FixedBitSet, which starts at the given offset.

      This should behave the same way as the default implementation, which does the following: 

       for (int i = bitSet.nextSetBit(0);
     i != DocIdSetIterator.NO_MORE_DOCS;
     i = i + 1 >= bitSet.length() ? DocIdSetIterator.NO_MORE_DOCS : bitSet.nextSetBit(i + 1)) {
   if (get(offset + i) == false) {
     bitSet.clear(i);
   }
 }

    • forEach

      public void forEach(int from, int to, int base, CheckedIntConsumer<IOException> consumer) throws IOException
      For each set bit from from inclusive to to exclusive, add base to the bit index and call consumer on it. This is internally used by queries that use bit sets as intermediate representations of their matches.
      Throws:
      IOException