Class OpenBitSet

An "open" BitSet implementation that allows direct access to the array of words storing the bits.

NOTE: This can be used in .NET any place where a java.util.BitSet is used in Java.

Unlike java.util.BitSet, the fact that bits are packed into an array of longs is part of the interface. This allows efficient implementation of other algorithms by someone other than the author. It also allows one to efficiently implement alternate serialization or interchange formats.

OpenBitSet is faster than java.util.BitSet in most operations and much faster at calculating cardinality of sets and results of set operations. It can also handle sets of larger cardinality (up to 64 * 2**32-1)

The goals of OpenBitSet are the fastest implementation possible, and maximum code reuse. Extra safety and encapsulation may always be built on top, but if that's built in, the cost can never be removed (and hence people re-implement their own version in order to get better performance).

Performance Results

Test system: Pentium 4, Sun Java 1.5_06 -server -Xbatch -Xmx64M

BitSet size = 1,000,000

Results are java.util.BitSet time divided by OpenBitSet time.

	cardinality	IntersectionCount	Union	NextSetBit	Get	GetIterator
50% full	3.36	3.96	1.44	1.46	1.99	1.58
1% full	3.31	3.90		1.04		0.99

Test system: AMD Opteron, 64 bit linux, Sun Java 1.5_06 -server -Xbatch -Xmx64M

BitSet size = 1,000,000

Results are java.util.BitSet time divided by OpenBitSet time.

	cardinality	IntersectionCount	Union	NextSetBit	Get	GetIterator
50% full	2.50	3.50	1.00	1.03	1.12	1.25
1% full	2.51	3.49		1.00		1.02

Inheritance

System.Object

DocIdSet

OpenBitSet

OpenBitSetDISI

Implements

IBits

Inherited Members

DocIdSet.NewAnonymous(Func<DocIdSetIterator>)

DocIdSet.NewAnonymous(Func<DocIdSetIterator>, Func<IBits>)

DocIdSet.NewAnonymous(Func<DocIdSetIterator>, Func<Boolean>)

DocIdSet.NewAnonymous(Func<DocIdSetIterator>, Func<IBits>, Func<Boolean>)

System.Object.Equals(System.Object, System.Object)

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: Lucene.Net.Util

Assembly: Lucene.Net.dll

Syntax

public class OpenBitSet : DocIdSet, IBits

Constructors

| Improve this Doc View Source

OpenBitSet()

Constructor: allocates enough space for 64 bits.

Declaration

public OpenBitSet()

| Improve this Doc View Source

OpenBitSet(Int64)

Constructs an OpenBitSet large enough to hold numBits.

Declaration

public OpenBitSet(long numBits)

Parameters

Type	Name	Description
System.Int64	numBits

| Improve this Doc View Source

OpenBitSet(Int64[], Int32)

Constructs an OpenBitSet from an existing long[].

The first 64 bits are in long[0], with bit index 0 at the least significant bit, and bit index 63 at the most significant. Given a bit index, the word containing it is long[index/64], and it is at bit number index%64 within that word.

numWords are the number of elements in the array that contain set bits (non-zero longs). numWords should be <= bits.Length, and any existing words in the array at position >= numWords should be zero.

Declaration

public OpenBitSet(long[] bits, int numWords)

Parameters

Type	Name	Description
System.Int64[]	bits
System.Int32	numWords

Fields

| Improve this Doc View Source

m_bits

Declaration

protected long[] m_bits

Field Value

Type	Description
System.Int64[]

| Improve this Doc View Source

m_wlen

Declaration

protected int m_wlen

Field Value

Type	Description
System.Int32

Properties

| Improve this Doc View Source

Bits

Declaration

public override IBits Bits { get; }

Property Value

Type	Description
IBits

Overrides

DocIdSet.Bits

| Improve this Doc View Source

Capacity

Returns the current capacity in bits (1 greater than the index of the last bit).

Declaration

public virtual long Capacity { get; }

Property Value

Type	Description
System.Int64

| Improve this Doc View Source

Cardinality

Gets the number of set bits.

Declaration

public virtual long Cardinality { get; }

Property Value

Type	Description
System.Int64	The number of set bits.

| Improve this Doc View Source

IsCacheable

This DocIdSet implementation is cacheable.

Declaration

public override bool IsCacheable { get; }

Property Value

Type	Description
System.Boolean

Overrides

DocIdSet.IsCacheable

| Improve this Doc View Source

IsEmpty

Returns true if there are no set bits

Declaration

public virtual bool IsEmpty { get; }

Property Value

Type	Description
System.Boolean

| Improve this Doc View Source

Length

Returns the current capacity of this set. This is not equal to Cardinality.

NOTE: This is equivalent to size() or length() in Lucene.

Declaration

public virtual int Length { get; }

Property Value

Type	Description
System.Int32

| Improve this Doc View Source

NumWords

Expert: gets the number of System.Int64s in the array that are in use.

Declaration

public virtual int NumWords { get; }

Property Value

Type	Description
System.Int32

Methods

| Improve this Doc View Source

And(OpenBitSet)

see Intersect(OpenBitSet)

Declaration

public virtual void And(OpenBitSet other)

Parameters

Type	Name	Description
OpenBitSet	other

| Improve this Doc View Source

AndNot(OpenBitSet)

see AndNot(OpenBitSet)

Declaration

public virtual void AndNot(OpenBitSet other)

Parameters

Type	Name	Description
OpenBitSet	other

| Improve this Doc View Source

AndNotCount(OpenBitSet, OpenBitSet)

Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified.

Declaration

public static long AndNotCount(OpenBitSet a, OpenBitSet b)

Parameters

Type	Name	Description
OpenBitSet	a
OpenBitSet	b

Returns

Type	Description
System.Int64

| Improve this Doc View Source

Bits2words(Int64)

Returns the number of 64 bit words it would take to hold numBits.

Declaration

public static int Bits2words(long numBits)

Parameters

Type	Name	Description
System.Int64	numBits

Returns

Type	Description
System.Int32

| Improve this Doc View Source

Clear(Int32, Int32)

Clears a range of bits. Clearing past the end does not change the size of the set.

Declaration

public virtual void Clear(int startIndex, int endIndex)

Parameters

Type	Name	Description
System.Int32	startIndex	Lower index
System.Int32	endIndex	One-past the last bit to clear

| Improve this Doc View Source

Clear(Int64)

Clears a bit, allowing access beyond the current set size without changing the size.

Declaration

public virtual void Clear(long index)

Parameters

Type	Name	Description
System.Int64	index

| Improve this Doc View Source

Clear(Int64, Int64)

Clears a range of bits. Clearing past the end does not change the size of the set.

Declaration

public virtual void Clear(long startIndex, long endIndex)

Parameters

Type	Name	Description
System.Int64	startIndex	Lower index
System.Int64	endIndex	One-past the last bit to clear

| Improve this Doc View Source

Clone()

Declaration

public object Clone()

Returns

Type	Description
System.Object

| Improve this Doc View Source

EnsureCapacity(Int64)

Ensure that the long[] is big enough to hold numBits, expanding it if necessary.

Declaration

public virtual void EnsureCapacity(long numBits)

Parameters

Type	Name	Description
System.Int64	numBits

| Improve this Doc View Source

EnsureCapacityWords(Int32)

Expand the long[] with the size given as a number of words (64 bit longs).

Declaration

public virtual void EnsureCapacityWords(int numWords)

Parameters

Type	Name	Description
System.Int32	numWords

| Improve this Doc View Source

Equals(Object)

Returns true if both sets have the same bits set.

Declaration

public override bool Equals(object o)

Parameters

Type	Name	Description
System.Object	o

Returns

Type	Description
System.Boolean

Overrides

System.Object.Equals(System.Object)

| Improve this Doc View Source

ExpandingWordNum(Int64)

Declaration

protected virtual int ExpandingWordNum(long index)

Parameters

Type	Name	Description
System.Int64	index

Returns

Type	Description
System.Int32

| Improve this Doc View Source

FastClear(Int32)

Clears a bit. The index should be less than the Length.

Declaration

public virtual void FastClear(int index)

Parameters

Type	Name	Description
System.Int32	index

| Improve this Doc View Source

FastClear(Int64)

Clears a bit. The index should be less than the Length.

Declaration

public virtual void FastClear(long index)

Parameters

Type	Name	Description
System.Int64	index

| Improve this Doc View Source

FastFlip(Int32)

Flips a bit. The index should be less than the Length.

Declaration

public virtual void FastFlip(int index)

Parameters

Type	Name	Description
System.Int32	index

| Improve this Doc View Source

FastFlip(Int64)

Flips a bit. The index should be less than the Length.

Declaration

public virtual void FastFlip(long index)

Parameters

Type	Name	Description
System.Int64	index

| Improve this Doc View Source

FastGet(Int32)

Returns true or false for the specified bit index. The index should be less than the Length.

Declaration

public virtual bool FastGet(int index)

Parameters

Type	Name	Description
System.Int32	index

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

FastGet(Int64)

Returns true or false for the specified bit index. The index should be less than the Length.

Declaration

public virtual bool FastGet(long index)

Parameters

Type	Name	Description
System.Int64	index

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

FastSet(Int32)

Sets the bit at the specified index. The index should be less than the Length.

Declaration

public virtual void FastSet(int index)

Parameters

Type	Name	Description
System.Int32	index

| Improve this Doc View Source

FastSet(Int64)

Sets the bit at the specified index. The index should be less than the Length.

Declaration

public virtual void FastSet(long index)

Parameters

Type	Name	Description
System.Int64	index

| Improve this Doc View Source

Flip(Int64)

Flips a bit, expanding the set size if necessary.

Declaration

public virtual void Flip(long index)

Parameters

Type	Name	Description
System.Int64	index

| Improve this Doc View Source

Flip(Int64, Int64)

Flips a range of bits, expanding the set size if necessary.

Declaration

public virtual void Flip(long startIndex, long endIndex)

Parameters

Type	Name	Description
System.Int64	startIndex	Lower index
System.Int64	endIndex	One-past the last bit to flip

| Improve this Doc View Source

FlipAndGet(Int32)

Flips a bit and returns the resulting bit value. The index should be less than the Length.

Declaration

public virtual bool FlipAndGet(int index)

Parameters

Type	Name	Description
System.Int32	index

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

FlipAndGet(Int64)

Flips a bit and returns the resulting bit value. The index should be less than the Length.

Declaration

public virtual bool FlipAndGet(long index)

Parameters

Type	Name	Description
System.Int64	index

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

Get(Int32)

Returns true or false for the specified bit index.

Declaration

public virtual bool Get(int index)

Parameters

Type	Name	Description
System.Int32	index

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

Get(Int64)

Returns true or false for the specified bit index.

Declaration

public virtual bool Get(long index)

Parameters

Type	Name	Description
System.Int64	index

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

GetAndSet(Int32)

Sets a bit and returns the previous value. The index should be less than the Length.

Declaration

public virtual bool GetAndSet(int index)

Parameters

Type	Name	Description
System.Int32	index

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

GetAndSet(Int64)

Sets a bit and returns the previous value. The index should be less than the Length.

Declaration

public virtual bool GetAndSet(long index)

Parameters

Type	Name	Description
System.Int64	index

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

GetBit(Int32)

Returns 1 if the bit is set, 0 if not. The index should be less than the Length.

Declaration

public virtual int GetBit(int index)

Parameters

Type	Name	Description
System.Int32	index

Returns

Type	Description
System.Int32

| Improve this Doc View Source

GetBits()

Expert: returns the long[] storing the bits.

Declaration

public virtual long[] GetBits()

Returns

Type	Description
System.Int64[]

| Improve this Doc View Source

GetHashCode()

Declaration

public override int GetHashCode()

Returns

Type	Description
System.Int32

Overrides

System.Object.GetHashCode()

| Improve this Doc View Source

GetIterator()

Declaration

public override DocIdSetIterator GetIterator()

Returns

Type	Description
DocIdSetIterator

Overrides

DocIdSet.GetIterator()

| Improve this Doc View Source

Intersect(OpenBitSet)

this = this AND other

Declaration

public virtual void Intersect(OpenBitSet other)

Parameters

Type	Name	Description
OpenBitSet	other

| Improve this Doc View Source

IntersectionCount(OpenBitSet, OpenBitSet)

Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified.

Declaration

public static long IntersectionCount(OpenBitSet a, OpenBitSet b)

Parameters

Type	Name	Description
OpenBitSet	a
OpenBitSet	b

Returns

Type	Description
System.Int64

| Improve this Doc View Source

Intersects(OpenBitSet)

returns true if the sets have any elements in common.

Declaration

public virtual bool Intersects(OpenBitSet other)

Parameters

Type	Name	Description
OpenBitSet	other

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

NextSetBit(Int32)

Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.

Declaration

public virtual int NextSetBit(int index)

Parameters

Type	Name	Description
System.Int32	index

Returns

Type	Description
System.Int32

| Improve this Doc View Source

NextSetBit(Int64)

Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.

Declaration

public virtual long NextSetBit(long index)

Parameters

Type	Name	Description
System.Int64	index

Returns

Type	Description
System.Int64

| Improve this Doc View Source

Or(OpenBitSet)

see Union(OpenBitSet)

Declaration

public virtual void Or(OpenBitSet other)

Parameters

Type	Name	Description
OpenBitSet	other

| Improve this Doc View Source

PrevSetBit(Int32)

Returns the index of the first set bit starting downwards at the index specified. -1 is returned if there are no more set bits.

Declaration

public virtual int PrevSetBit(int index)

Parameters

Type	Name	Description
System.Int32	index

Returns

Type	Description
System.Int32

| Improve this Doc View Source

PrevSetBit(Int64)

Returns the index of the first set bit starting downwards at the index specified. -1 is returned if there are no more set bits.

Declaration

public virtual long PrevSetBit(long index)

Parameters

Type	Name	Description
System.Int64	index

Returns

Type	Description
System.Int64

| Improve this Doc View Source

Remove(OpenBitSet)

Remove all elements set in other. this = this AND_NOT other.

Declaration

public virtual void Remove(OpenBitSet other)

Parameters

Type	Name	Description
OpenBitSet	other

| Improve this Doc View Source

Set(Int64)

Sets a bit, expanding the set size if necessary.

Declaration

public virtual void Set(long index)

Parameters

Type	Name	Description
System.Int64	index

| Improve this Doc View Source

Set(Int64, Int64)

Sets a range of bits, expanding the set size if necessary.

Declaration

public virtual void Set(long startIndex, long endIndex)

Parameters

Type	Name	Description
System.Int64	startIndex	Lower index
System.Int64	endIndex	One-past the last bit to set

| Improve this Doc View Source

TrimTrailingZeros()

Lowers numWords, the number of words in use, by checking for trailing zero words.

Declaration

public virtual void TrimTrailingZeros()

| Improve this Doc View Source

Union(OpenBitSet)

this = this OR other

Declaration

public virtual void Union(OpenBitSet other)

Parameters

Type	Name	Description
OpenBitSet	other

| Improve this Doc View Source

UnionCount(OpenBitSet, OpenBitSet)

Returns the popcount or cardinality of the union of the two sets. Neither set is modified.

Declaration

public static long UnionCount(OpenBitSet a, OpenBitSet b)

Parameters

Type	Name	Description
OpenBitSet	a
OpenBitSet	b

Returns

Type	Description
System.Int64

| Improve this Doc View Source

Xor(OpenBitSet)

this = this XOR other

Declaration

public virtual void Xor(OpenBitSet other)

Parameters

Type	Name	Description
OpenBitSet	other

| Improve this Doc View Source

XorCount(OpenBitSet, OpenBitSet)

Returns the popcount or cardinality of the exclusive-or of the two sets. Neither set is modified.

Declaration

public static long XorCount(OpenBitSet a, OpenBitSet b)

Parameters

Type	Name	Description
OpenBitSet	a
OpenBitSet	b

Returns

Type	Description
System.Int64

Explicit Interface Implementations

| Improve this Doc View Source

IBits.Length

Declaration

int IBits.Length { get; }

Returns

Type	Description
System.Int32

Implements

IBits