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
implements Bits, Accountable

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.Bits

EMPTY_ARRAY

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

NULL_ACCOUNTABLE

Constructor Summary

Constructors

Constructor and 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

Modifier and Type	Method and Description
void	and(FixedBitSet other) this = this AND other
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))".
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(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
boolean	get(int index) Returns the value of the bit with the specified index.
boolean	getAndClear(int index)
boolean	getAndSet(int index)
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.
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.
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

approximateCardinality, 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 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.

length

public int length()

Description copied from interface: Bits

Returns the number of bits in this set

Specified by:

length in interface Bits

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

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

get

public boolean get(int index)

Description copied from interface: Bits

Returns the value of the bit with the specified index.

Specified by:

get in interface Bits

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)

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

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(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.