Show / Hide Table of Contents

    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.

    cardinalityIntersectionCountUnionNextSetBitGetGetIterator
    50% full3.363.961.441.461.991.58
    1% full3.313.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.

    cardinalityIntersectionCountUnionNextSetBitGetGetIterator
    50% full2.503.501.001.031.121.25
    1% full2.513.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>)
    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

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

    Cardinality()

    Get the number of set bits.

    Declaration
    public virtual long Cardinality()
    Returns
    Type Description
    System.Int64

    The number of set bits.

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

    Implements

    IBits
    • Improve this Doc
    • View Source
    Back to top Copyright © 2020 Licensed to the Apache Software Foundation (ASF)