Class LongBitSet

  • All Implemented Interfaces:
    Accountable

    public final class LongBitSet
    extends java.lang.Object
    implements Accountable
    BitSet of fixed length (numBits), backed by accessible (getBits()) long[], accessed with a long index. Use it only if you intend to store more than 2.1B bits, otherwise you should use FixedBitSet.
    • Constructor Summary

      Constructors 
      Constructor Description
      LongBitSet​(long numBits)
      Creates a new LongBitSet.
      LongBitSet​(long[] storedBits, long numBits)
      Creates a new LongBitSet using the provided long[] array as backing store.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void and​(LongBitSet other)
      this = this AND other
      void andNot​(LongBitSet other)
      this = this AND NOT other
      static int bits2words​(long numBits)
      Returns the number of 64 bit words it would take to hold numBits
      long cardinality()
      Returns number of set bits.
      void clear​(long index)  
      void clear​(long startIndex, long endIndex)
      Clears a range of bits.
      LongBitSet clone()  
      static LongBitSet ensureCapacity​(LongBitSet bits, long numBits)
      If the given LongBitSet is large enough to hold numBits+1, returns the given bits, otherwise returns a new LongBitSet which can hold the requested number of bits.
      boolean equals​(java.lang.Object o)
      returns true if both sets have the same bits set
      void flip​(long index)
      Flip the bit at the provided index.
      void flip​(long startIndex, long endIndex)
      Flips a range of bits
      boolean get​(long index)  
      boolean getAndClear​(long index)  
      boolean getAndSet​(long index)  
      long[] getBits()
      Expert.
      int hashCode()  
      boolean intersects​(LongBitSet other)
      returns true if the sets have any elements in common
      long length()
      Returns the number of bits stored in this bitset.
      long nextSetBit​(long index)
      Returns the index of the first set bit starting at the index specified.
      void or​(LongBitSet other)
      this = this OR other
      long prevSetBit​(long 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​(long index)  
      void set​(long startIndex, long endIndex)
      Sets a range of bits
      private boolean verifyGhostBitsClear()
      Checks if the bits past numBits are clear.
      void xor​(LongBitSet other)
      this = this XOR other
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • BASE_RAM_BYTES

        private static final long BASE_RAM_BYTES
      • bits

        private final long[] bits
      • numBits

        private final long numBits
      • numWords

        private final int numWords
      • MAX_NUM_BITS

        public static final long MAX_NUM_BITS
        The maximum numBits supported.
    • Constructor Detail

      • LongBitSet

        public LongBitSet​(long 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
      • LongBitSet

        public LongBitSet​(long[] storedBits,
                          long 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 LongBitSet ensureCapacity​(LongBitSet bits,
                                                long numBits)
        If the given LongBitSet is large enough to hold numBits+1, returns the given bits, otherwise returns a new LongBitSet 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​(long numBits)
        Returns the number of 64 bit words it would take to hold numBits
      • verifyGhostBitsClear

        private boolean verifyGhostBitsClear()
        Checks if the bits past numBits are clear. Some methods rely on this implicit assumption: search for "Depends on the ghost bits being clear!"
        Returns:
        true if the bits past numBits are clear.
      • length

        public long length()
        Returns the number of bits stored in this bitset.
      • getBits

        public long[] getBits()
        Expert.
      • cardinality

        public long cardinality()
        Returns number of set bits. NOTE: this visits every long in the backing bits array, and the result is not internally cached!
      • get

        public boolean get​(long index)
      • set

        public void set​(long index)
      • getAndSet

        public boolean getAndSet​(long index)
      • clear

        public void clear​(long index)
      • getAndClear

        public boolean getAndClear​(long index)
      • nextSetBit

        public 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.
      • prevSetBit

        public long prevSetBit​(long index)
        Returns the index of the last set bit before or on the index specified. -1 is returned if there are no more set bits.
      • or

        public void or​(LongBitSet other)
        this = this OR other
      • xor

        public void xor​(LongBitSet other)
        this = this XOR other
      • intersects

        public boolean intersects​(LongBitSet other)
        returns true if the sets have any elements in common
      • and

        public void and​(LongBitSet other)
        this = this AND other
      • andNot

        public void andNot​(LongBitSet 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​(long startIndex,
                         long endIndex)
        Flips a range of bits
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to flip
      • flip

        public void flip​(long index)
        Flip the bit at the provided index.
      • set

        public void set​(long startIndex,
                        long endIndex)
        Sets a range of bits
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to set
      • clear

        public void clear​(long startIndex,
                          long endIndex)
        Clears a range of bits.
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to clear
      • clone

        public LongBitSet clone()
        Overrides:
        clone in class java.lang.Object
      • equals

        public boolean equals​(java.lang.Object o)
        returns true if both sets have the same bits set
        Overrides:
        equals in class java.lang.Object
      • hashCode

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