Lucene.Net  3.0.3
Lucene.Net is a port of the Lucene search engine library, written in C# and targeted at .NET runtime users.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Pages
Public Member Functions | Static Public Member Functions | Properties | List of all members
Lucene.Net.Util.OpenBitSet Class Reference

An "open" BitSet implementation that allows direct access to the array of words storing the bits. 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). If you want a "safe", totally encapsulated (and slower and limited) BitSet class, use java.util.BitSet. More...

Inherits DocIdSet, and ICloneable.

Inherited by Lucene.Net.Util.OpenBitSetDISI.

Public Member Functions

 OpenBitSet (long numBits)
 Constructs an OpenBitSet large enough to hold numBits.
 
 OpenBitSet ()
 
 OpenBitSet (long[] bits, int numWords)
 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.
 
override DocIdSetIterator Iterator ()
 
virtual long Capacity ()
 Returns the current capacity in bits (1 greater than the index of the last bit)
 
virtual long Size ()
 Returns the current capacity of this set. Included for compatibility. This is not equal to Cardinality
 
virtual bool IsEmpty ()
 Returns true if there are no set bits
 
virtual bool Get (int index)
 Returns true or false for the specified bit index.
 
virtual bool FastGet (int index)
 Returns true or false for the specified bit index. The index should be less than the OpenBitSet size
 
virtual bool Get (long index)
 Returns true or false for the specified bit index
 
virtual bool FastGet (long index)
 Returns true or false for the specified bit index. The index should be less than the OpenBitSet size.
 
virtual int GetBit (int index)
 returns 1 if the bit is set, 0 if not. The index should be less than the OpenBitSet size
 
virtual void Set (long index)
 sets a bit, expanding the set size if necessary
 
virtual void FastSet (int index)
 Sets the bit at the specified index. The index should be less than the OpenBitSet size.
 
virtual void FastSet (long index)
 Sets the bit at the specified index. The index should be less than the OpenBitSet size.
 
virtual void Set (long startIndex, long endIndex)
 Sets a range of bits, expanding the set size if necessary
 
virtual void FastClear (int index)
 clears a bit. The index should be less than the OpenBitSet size.
 
virtual void FastClear (long index)
 clears a bit. The index should be less than the OpenBitSet size.
 
virtual void Clear (long index)
 clears a bit, allowing access beyond the current set size without changing the size.
 
virtual void Clear (int startIndex, int endIndex)
 Clears a range of bits. Clearing past the end does not change the size of the set.
 
virtual void Clear (long startIndex, long endIndex)
 Clears a range of bits. Clearing past the end does not change the size of the set.
 
virtual bool GetAndSet (int index)
 Sets a bit and returns the previous value. The index should be less than the OpenBitSet size.
 
virtual bool GetAndSet (long index)
 Sets a bit and returns the previous value. The index should be less than the OpenBitSet size.
 
virtual void FastFlip (int index)
 flips a bit. The index should be less than the OpenBitSet size.
 
virtual void FastFlip (long index)
 flips a bit. The index should be less than the OpenBitSet size.
 
virtual void Flip (long index)
 flips a bit, expanding the set size if necessary
 
virtual bool FlipAndGet (int index)
 flips a bit and returns the resulting bit value. The index should be less than the OpenBitSet size.
 
virtual bool FlipAndGet (long index)
 flips a bit and returns the resulting bit value. The index should be less than the OpenBitSet size.
 
virtual void Flip (long startIndex, long endIndex)
 Flips a range of bits, expanding the set size if necessary
 
virtual long Cardinality ()
 
virtual int NextSetBit (int index)
 Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.
 
virtual long NextSetBit (long index)
 Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.
 
virtual System.Object Clone ()
 
virtual void Intersect (OpenBitSet other)
 this = this AND other
 
virtual void Union (OpenBitSet other)
 this = this OR other
 
virtual void Remove (OpenBitSet other)
 Remove all elements set in other. this = this AND_NOT other
 
virtual void Xor (OpenBitSet other)
 this = this XOR other
 
virtual void And (OpenBitSet other)
 
virtual void Or (OpenBitSet other)
 
virtual void AndNot (OpenBitSet other)
 
virtual bool Intersects (OpenBitSet other)
 returns true if the sets have any elements in common
 
virtual void EnsureCapacityWords (int numWords)
 Expand the long[] with the size given as a number of words (64 bit longs). getNumWords() is unchanged by this call.
 
virtual void EnsureCapacity (long numBits)
 Ensure that the long[] is big enough to hold numBits, expanding it if necessary. getNumWords() is unchanged by this call.
 
virtual void TrimTrailingZeros ()
 Lowers numWords, the number of words in use, by checking for trailing zero words.
 
override bool Equals (System.Object o)
 returns true if both sets have the same bits set
 
override int GetHashCode ()
 

Static Public Member Functions

static long IntersectionCount (OpenBitSet a, OpenBitSet b)
 Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified.
 
static long UnionCount (OpenBitSet a, OpenBitSet b)
 Returns the popcount or cardinality of the union of the two sets. Neither set is modified.
 
static long AndNotCount (OpenBitSet a, OpenBitSet b)
 Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified.
 
static long XorCount (OpenBitSet a, OpenBitSet b)
 Returns the popcount or cardinality of the exclusive-or of the two sets. Neither set is modified.
 
static int Bits2words (long numBits)
 returns the number of 64 bit words it would take to hold numBits
 

Properties

override bool IsCacheable [get]
 This DocIdSet implementation is cacheable.
 
virtual long[] Bits [get, set]
 Expert: Gets or sets the long[] storing the bits
 
virtual int NumWords [get, set]
 Expert: gets or sets the number of longs in the array that are in use
 

Detailed Description

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

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). If you want a "safe", totally encapsulated (and slower and limited) BitSet class, use java.util.BitSet.

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 intersect_count union nextSetBit get iterator
50% full 3.36 3.96 1.44 1.46 1.99 1.58
1% full 3.31 3.90 &#160; 1.04 &#160; 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 intersect_count union nextSetBit get iterator
50% full 2.50 3.50 1.00 1.03 1.12 1.25
1% full 2.51 3.49 &#160; 1.00 &#160; 1.02

<version> $Id$ </version>

Definition at line 81 of file OpenBitSet.cs.

Constructor & Destructor Documentation

Lucene.Net.Util.OpenBitSet.OpenBitSet ( long  numBits)

Constructs an OpenBitSet large enough to hold numBits.

Parameters
numBits

Definition at line 91 of file OpenBitSet.cs.

Lucene.Net.Util.OpenBitSet.OpenBitSet ( )

Definition at line 97 of file OpenBitSet.cs.

Lucene.Net.Util.OpenBitSet.OpenBitSet ( long[]  bits,
int  numWords 
)

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.

Definition at line 114 of file OpenBitSet.cs.

Member Function Documentation

virtual void Lucene.Net.Util.OpenBitSet.And ( OpenBitSet  other)
virtual

Definition at line 822 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.AndNot ( OpenBitSet  other)
virtual

Definition at line 834 of file OpenBitSet.cs.

static long Lucene.Net.Util.OpenBitSet.AndNotCount ( OpenBitSet  a,
OpenBitSet  b 
)
static

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

Definition at line 646 of file OpenBitSet.cs.

static int Lucene.Net.Util.OpenBitSet.Bits2words ( long  numBits)
static

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

Definition at line 886 of file OpenBitSet.cs.

virtual long Lucene.Net.Util.OpenBitSet.Capacity ( )
virtual

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

Definition at line 132 of file OpenBitSet.cs.

virtual long Lucene.Net.Util.OpenBitSet.Cardinality ( )
virtual
Returns
the number of set bits

Definition at line 612 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Clear ( long  index)
virtual

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

Definition at line 361 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Clear ( int  startIndex,
int  endIndex 
)
virtual

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

Parameters
startIndexlower index
endIndexone-past the last bit to clear

Definition at line 378 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Clear ( long  startIndex,
long  endIndex 
)
virtual

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

Parameters
startIndexlower index
endIndexone-past the last bit to clear

Definition at line 423 of file OpenBitSet.cs.

virtual System.Object Lucene.Net.Util.OpenBitSet.Clone ( )
virtual

Definition at line 729 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.EnsureCapacity ( long  numBits)
virtual

Ensure that the long[] is big enough to hold numBits, expanding it if necessary. getNumWords() is unchanged by this call.

Definition at line 869 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.EnsureCapacityWords ( int  numWords)
virtual

Expand the long[] with the size given as a number of words (64 bit longs). getNumWords() is unchanged by this call.

Definition at line 858 of file OpenBitSet.cs.

override bool Lucene.Net.Util.OpenBitSet.Equals ( System.Object  o)

returns true if both sets have the same bits set

Definition at line 893 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.FastClear ( int  index)
virtual

clears a bit. The index should be less than the OpenBitSet size.

Definition at line 334 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.FastClear ( long  index)
virtual

clears a bit. The index should be less than the OpenBitSet size.

Definition at line 352 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.FastFlip ( int  index)
virtual

flips a bit. The index should be less than the OpenBitSet size.

Definition at line 491 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.FastFlip ( long  index)
virtual

flips a bit. The index should be less than the OpenBitSet size.

Definition at line 502 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.FastGet ( int  index)
virtual

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

Definition at line 185 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.FastGet ( long  index)
virtual

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

Definition at line 211 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.FastSet ( int  index)
virtual

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

Definition at line 265 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.FastSet ( long  index)
virtual

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

Definition at line 276 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Flip ( long  index)
virtual

flips a bit, expanding the set size if necessary

Definition at line 511 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Flip ( long  startIndex,
long  endIndex 
)
virtual

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

Parameters
startIndexlower index
endIndexone-past the last bit to flip

Definition at line 550 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.FlipAndGet ( int  index)
virtual

flips a bit and returns the resulting bit value. The index should be less than the OpenBitSet size.

Definition at line 522 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.FlipAndGet ( long  index)
virtual

flips a bit and returns the resulting bit value. The index should be less than the OpenBitSet size.

Definition at line 534 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.Get ( int  index)
virtual

Returns true or false for the specified bit index.

Definition at line 168 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.Get ( long  index)
virtual

Returns true or false for the specified bit index

Definition at line 198 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.GetAndSet ( int  index)
virtual

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

Definition at line 465 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.GetAndSet ( long  index)
virtual

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

Definition at line 478 of file OpenBitSet.cs.

virtual int Lucene.Net.Util.OpenBitSet.GetBit ( int  index)
virtual

returns 1 if the bit is set, 0 if not. The index should be less than the OpenBitSet size

Definition at line 235 of file OpenBitSet.cs.

override int Lucene.Net.Util.OpenBitSet.GetHashCode ( )

Definition at line 927 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Intersect ( OpenBitSet  other)
virtual

this = this AND other

Definition at line 745 of file OpenBitSet.cs.

static long Lucene.Net.Util.OpenBitSet.IntersectionCount ( OpenBitSet  a,
OpenBitSet  b 
)
static

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

Definition at line 620 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.Intersects ( OpenBitSet  other)
virtual

returns true if the sets have any elements in common

Definition at line 840 of file OpenBitSet.cs.

virtual bool Lucene.Net.Util.OpenBitSet.IsEmpty ( )
virtual

Returns true if there are no set bits

Definition at line 146 of file OpenBitSet.cs.

override DocIdSetIterator Lucene.Net.Util.OpenBitSet.Iterator ( )

Definition at line 120 of file OpenBitSet.cs.

virtual int Lucene.Net.Util.OpenBitSet.NextSetBit ( int  index)
virtual

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

Definition at line 677 of file OpenBitSet.cs.

virtual long Lucene.Net.Util.OpenBitSet.NextSetBit ( long  index)
virtual

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

Definition at line 703 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Or ( OpenBitSet  other)
virtual

Definition at line 828 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Remove ( OpenBitSet  other)
virtual

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

Definition at line 787 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Set ( long  index)
virtual

sets a bit, expanding the set size if necessary

Definition at line 253 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Set ( long  startIndex,
long  endIndex 
)
virtual

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

Parameters
startIndexlower index
endIndexone-past the last bit to set

Definition at line 291 of file OpenBitSet.cs.

virtual long Lucene.Net.Util.OpenBitSet.Size ( )
virtual

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

Definition at line 140 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.TrimTrailingZeros ( )
virtual

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

Definition at line 877 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Union ( OpenBitSet  other)
virtual

this = this OR other

Definition at line 766 of file OpenBitSet.cs.

static long Lucene.Net.Util.OpenBitSet.UnionCount ( OpenBitSet  a,
OpenBitSet  b 
)
static

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

Definition at line 628 of file OpenBitSet.cs.

virtual void Lucene.Net.Util.OpenBitSet.Xor ( OpenBitSet  other)
virtual

this = this XOR other

Definition at line 799 of file OpenBitSet.cs.

static long Lucene.Net.Util.OpenBitSet.XorCount ( OpenBitSet  a,
OpenBitSet  b 
)
static

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

Definition at line 659 of file OpenBitSet.cs.

Property Documentation

virtual long [] Lucene.Net.Util.OpenBitSet.Bits
getset

Expert: Gets or sets the long[] storing the bits

Definition at line 154 of file OpenBitSet.cs.

override bool Lucene.Net.Util.OpenBitSet.IsCacheable
get

This DocIdSet implementation is cacheable.

Definition at line 127 of file OpenBitSet.cs.

virtual int Lucene.Net.Util.OpenBitSet.NumWords
getset

Expert: gets or sets the number of longs in the array that are in use

Definition at line 161 of file OpenBitSet.cs.


The documentation for this class was generated from the following file: