Package pascal.taie.util.collection

Interface IBitSet

All Superinterfaces:
Copyable<IBitSet>, Serializable
All Known Implementing Classes:
AbstractBitSet, RegularBitSet, SparseBitSet
public interface IBitSet extends Copyable<IBitSet>, Serializable
Interface for different bit set implementations.

This interface is similar to Set. The main motivation to reinvent a bit set is that the APIs of Set do not fulfill the requirements of program analysis.

For APIs that may modify a bit set, such set(int), and(IBitSet), and or(IBitSet), this implementation returns whether the bit set changed. In addition, it provides some useful operations that are absent in Set.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static interface 
    IBitSet.Action<R>
    Action on set bits.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    and(IBitSet set)
    Performs a logical AND of this target bit set with the argument bit set.
    boolean
    andNot(IBitSet set)
    Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet.
    int
    cardinality()
    Returns the number of bits set to true in this BitSet.
    void
    clear()
    Sets all of the bits in this BitSet to false.
    boolean
    clear(int bitIndex)
    Sets the bit specified by the index to false.
    boolean
    contains(IBitSet set)
    Returns true if this BitSet contains all set bits in the specified BitSet.
    boolean
    disjoints(IBitSet set)
    Returns false if the specified BitSet has any bits set to true that are also set to true in this BitSet.
    void
    flip(int bitIndex)
    Sets the bit at the specified index to the complement of its current value.
    boolean
    get(int bitIndex)
    Returns the value of the bit with the specified index.
    boolean
    intersects(IBitSet set)
    Returns true if the specified BitSet has any bits set to true that are also set to true in this BitSet.
    boolean
    isEmpty()
    Returns true if this BitSet contains no bits that are set to true.
    static boolean
    isSparse(IBitSet set)
     
    default <R> R
    iterateBits(IBitSet.Action<R> action)
    Iterates all set bits in this set and takes action on them.
    int
    length()
    Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one.
    static IBitSet
    newBitSet(boolean isSparse)
    Creates a new set.
    int
    nextClearBit(int fromIndex)
    Returns the index of the first bit that is set to false that occurs on or after the specified starting index.
    int
    nextSetBit(int fromIndex)
    Returns the index of the first bit that is set to true that occurs on or after the specified starting index.
    static IBitSet
    of(int... bits)
    Creates a bit set that contains given bits.
    boolean
    or(IBitSet set)
    Performs a logical OR of this bit set with the bit set argument.
    IBitSet
    orDiff(IBitSet set)
    Performs a logical OR of this bit set with the bit set argument, computes and returns the difference set between given bit set and this set (before performing logical OR).
    int
    previousClearBit(int fromIndex)
    Returns the index of the nearest bit that is set to false that occurs on or before the specified starting index.
    int
    previousSetBit(int fromIndex)
    Returns the index of the nearest bit that is set to true that occurs on or before the specified starting index.
    boolean
    set(int bitIndex)
    Sets the bit at the specified index to true.
    boolean
    set(int bitIndex, boolean value)
    Sets the bit at the specified index to the specified value.
    void
    setTo(IBitSet set)
    Sets the content of this bit set to the same as specified bit set.
    int
    size()
    Returns the number of bits of space actually in use by this BitSet to represent bit values.
    boolean
    xor(IBitSet set)
    Performs a logical XOR of this bit set with the bit set argument.

    Methods inherited from interface pascal.taie.util.Copyable

    copy

  • Method Details

    • set

      boolean set(int bitIndex)
      Sets the bit at the specified index to true.
      Parameters:
      bitIndex - a bit index
      Returns:
      true if this BitSet changed as a result of the call
      Throws:
      IndexOutOfBoundsException - if the specified index is negative

    • set

      boolean set(int bitIndex, boolean value)
      Sets the bit at the specified index to the specified value.
      Parameters:
      bitIndex - a bit index
      value - a boolean value to set
      Returns:
      true if this BitSet changed as a result of the call
      Throws:
      IndexOutOfBoundsException - if the specified index is negative

    • clear

      boolean clear(int bitIndex)
      Sets the bit specified by the index to false.
      Parameters:
      bitIndex - the index of the bit to be cleared
      Returns:
      true if this BitSet changed as a result of the call
      Throws:
      IndexOutOfBoundsException - if the specified index is negative

    • get

      boolean get(int bitIndex)
      Returns the value of the bit with the specified index. The value is true if the bit with the index bitIndex is currently set in this BitSet; otherwise, the result is false.
      Parameters:
      bitIndex - the bit index
      Returns:
      the value of the bit with the specified index
      Throws:
      IndexOutOfBoundsException - if the specified index is negative

    • flip

      void flip(int bitIndex)
      Sets the bit at the specified index to the complement of its current value. This operation must modify the BitSet.
      Parameters:
      bitIndex - the index of the bit to flip
      Throws:
      IndexOutOfBoundsException - if the specified index is negative

    • nextSetBit

      int nextSetBit(int fromIndex)
      Returns the index of the first bit that is set to true that occurs on or after the specified starting index. If no such bit exists then -1 is returned.

      To iterate over the true bits in a BitSet, use the following loop: 

       
 for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
     // operate on index i here
     if (i == Integer.MAX_VALUE) {
         break; // or (i+1) would overflow
     }
 }
      Parameters:
      fromIndex - the index to start checking from (inclusive)
      Returns:
      the index of the next set bit, or -1 if there is no such bit
      Throws:
      IndexOutOfBoundsException - if the specified index is negative

    • nextClearBit

      int nextClearBit(int fromIndex)
      Returns the index of the first bit that is set to false that occurs on or after the specified starting index.
      Parameters:
      fromIndex - the index to start checking from (inclusive)
      Returns:
      the index of the next clear bit
      Throws:
      IndexOutOfBoundsException - if the specified index is negative

    • previousSetBit

      int previousSetBit(int fromIndex)
      Returns the index of the nearest bit that is set to true that occurs on or before the specified starting index. If no such bit exists, or if -1 is given as the starting index, then -1 is returned.

      To iterate over the true bits in a BitSet, use the following loop: 

       
 for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
     // operate on index i here
 }
      Parameters:
      fromIndex - the index to start checking from (inclusive)
      Returns:
      the index of the previous set bit, or -1 if there is no such bit
      Throws:
      IndexOutOfBoundsException - if the specified index is less than -1

    • previousClearBit

      int previousClearBit(int fromIndex)
      Returns the index of the nearest bit that is set to false that occurs on or before the specified starting index. If no such bit exists, or if -1 is given as the starting index, then -1 is returned.
      Parameters:
      fromIndex - the index to start checking from (inclusive)
      Returns:
      the index of the previous clear bit, or -1 if there is no such bit
      Throws:
      IndexOutOfBoundsException - if the specified index is less than -1

    • intersects

      boolean intersects(IBitSet set)
      Returns true if the specified BitSet has any bits set to true that are also set to true in this BitSet.
      Parameters:
      set - BitSet to intersect with
      Returns:
      boolean indicating whether this BitSet intersects the specified BitSet

    • disjoints

      boolean disjoints(IBitSet set)
      Returns false if the specified BitSet has any bits set to true that are also set to true in this BitSet.
      Parameters:
      set - BitSet to disjoint with
      Returns:
      boolean indicating whether this BitSet disjoints the specified BitSet

    • contains

      boolean contains(IBitSet set)
      Returns true if this BitSet contains all set bits in the specified BitSet.
      Parameters:
      set - bit set to be checked for containment in this set.
      Returns:
      boolean indicating whether this BitSet contains all set bits in the specified BitSet

    • and

      boolean and(IBitSet set)
      Performs a logical AND of this target bit set with the argument bit set. This bit set is modified so that each bit in it has the value true if and only if it both initially had the value true and the corresponding bit in the bit set argument also had the value true.
      Parameters:
      set - a bit set
      Returns:
      true if this bit set changed as a result of the call

    • andNot

      boolean andNot(IBitSet set)
      Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet.
      Parameters:
      set - the BitSet with which to mask this BitSet
      Returns:
      true if this bit set changed as a result of the call

    • or

      boolean or(IBitSet set)
      Performs a logical OR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if it either already had the value true or the corresponding bit in the bit set argument has the value true.
      Parameters:
      set - a bit set
      Returns:
      true if this bit set changed as a result of the call

    • orDiff

      IBitSet orDiff(IBitSet set)
      Performs a logical OR of this bit set with the bit set argument, computes and returns the difference set between given bit set and this set (before performing logical OR).
      Parameters:
      set - a bit set.
      Returns:
      a new bit set of bit values that are present in the bit set argument and were absent in this bit set before.

    • xor

      boolean xor(IBitSet set)
      Performs a logical XOR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if one of the following statements holds:
      • The bit initially has the value true, and the corresponding bit in the argument has the value false.
      • The bit initially has the value false, and the corresponding bit in the argument has the value true.
      Parameters:
      set - a bit set
      Returns:
      true if this bit set changed as a result of the call

    • setTo

      void setTo(IBitSet set)
      Sets the content of this bit set to the same as specified bit set.
      Parameters:
      set - a bit set

    • clear

      void clear()
      Sets all of the bits in this BitSet to false.

    • iterateBits

      default <R> R iterateBits(IBitSet.Action<R> action)
      Iterates all set bits in this set and takes action on them.

    • isEmpty

      boolean isEmpty()
      Returns true if this BitSet contains no bits that are set to true.
      Returns:
      boolean indicating whether this BitSet is empty

    • length

      int length()
      Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one. Returns zero if the BitSet contains no set bits.
      Returns:
      the logical size of this BitSet

    • size

      int size()
      Returns the number of bits of space actually in use by this BitSet to represent bit values. The maximum element in the set is the size - 1st element.
      Returns:
      the number of bits currently in this bit set

    • cardinality

      int cardinality()
      Returns the number of bits set to true in this BitSet.
      Returns:
      the number of bits set to true in this BitSet

    • newBitSet

      static IBitSet newBitSet(boolean isSparse)
      Creates a new set.

    • isSparse

      static boolean isSparse(IBitSet set)
      Returns:
      true if the given bit set is sparse.

    • of

      static IBitSet of(int... bits)
      Creates a bit set that contains given bits.