Class ImmutableBitSet

java.lang.Object
org.apache.calcite.util.ImmutableBitSet
All Implemented Interfaces:
Serializable, Comparable<ImmutableBitSet>, Iterable<Integer>

public class ImmutableBitSet
extends Object
implements Iterable<Integer>, Serializable, Comparable<ImmutableBitSet>
An immutable list of bits.
See Also:
Serialized Form
  • Field Details

  • Method Details

    • of

      public static ImmutableBitSet of()
      Creates an ImmutableBitSet with no bits.
    • of

      public static ImmutableBitSet of​(int... bits)
    • of

      public static ImmutableBitSet of​(Iterable<Integer> bits)
    • of

      public static ImmutableBitSet of​(ImmutableIntList bits)
      Creates an ImmutableBitSet with given bits set.

      For example, of(ImmutableIntList.of(0, 3)) returns a bit set with bits {0, 3} set.

      Parameters:
      bits - Collection of bits to set
      Returns:
      Bit set
    • valueOf

      public static ImmutableBitSet valueOf​(long... longs)
      Returns a new immutable bit set containing all the bits in the given long array.

      More precisely,

      ImmutableBitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)

      for all n < 64 * longs.length.

      This method is equivalent to ImmutableBitSet.valueOf(LongBuffer.wrap(longs)).

      Parameters:
      longs - a long array containing a little-endian representation of a sequence of bits to be used as the initial bits of the new bit set
      Returns:
      a ImmutableBitSet containing all the bits in the long array
    • valueOf

      public static ImmutableBitSet valueOf​(LongBuffer longs)
      Returns a new immutable bit set containing all the bits in the given long buffer.
    • fromBitSet

      public static ImmutableBitSet fromBitSet​(BitSet input)
      Returns a new immutable bit set containing all the bits in the given BitSet.
    • range

      public static ImmutableBitSet range​(int fromIndex, int toIndex)
      Creates an ImmutableBitSet with bits from fromIndex (inclusive) to specified toIndex (exclusive) set to true.

      For example, range(0, 3) returns a bit set with bits {0, 1, 2} set.

      Parameters:
      fromIndex - Index of the first bit to be set.
      toIndex - Index after the last bit to be set.
      Returns:
      Bit set
    • range

      public static ImmutableBitSet range​(int toIndex)
      Creates an ImmutableBitSet with bits between 0 and toIndex set.
    • toImmutableBitSet

      public static Collector<Integer,​ImmutableBitSet.Builder,​ImmutableBitSet> toImmutableBitSet()
      Creates a Collector.
    • powerSet

      public Iterable<ImmutableBitSet> powerSet()
      Computes the power set (set of all sets) of this bit set.
    • get

      public 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 ImmutableBitSet; 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
    • get

      public ImmutableBitSet get​(int fromIndex, int toIndex)
      Returns a new ImmutableBitSet composed of bits from this ImmutableBitSet from fromIndex (inclusive) to toIndex (exclusive).
      Parameters:
      fromIndex - index of the first bit to include
      toIndex - index after the last bit to include
      Returns:
      a new ImmutableBitSet from a range of this ImmutableBitSet
      Throws:
      IndexOutOfBoundsException - if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex
    • toString

      public String toString()
      Returns a string representation of this bit set. For every index for which this BitSet contains a bit in the set state, the decimal representation of that index is included in the result. Such indices are listed in order from lowest to highest, separated by ", " (a comma and a space) and surrounded by braces, resulting in the usual mathematical notation for a set of integers.

      Example:

       BitSet drPepper = new BitSet();
      Now drPepper.toString() returns "{}".
       drPepper.set(2);
      Now drPepper.toString() returns "{2}".
       drPepper.set(4);
       drPepper.set(10);
      Now drPepper.toString() returns "{2, 4, 10}".
      Overrides:
      toString in class Object
      Returns:
      a string representation of this bit set
    • intersects

      public boolean intersects​(ImmutableBitSet set)
      Returns true if the specified ImmutableBitSet has any bits set to true that are also set to true in this ImmutableBitSet.
      Parameters:
      set - ImmutableBitSet to intersect with
      Returns:
      boolean indicating whether this ImmutableBitSet intersects the specified ImmutableBitSet
    • cardinality

      public int cardinality()
      Returns the number of bits set to true in this ImmutableBitSet.
      See Also:
      size()
    • hashCode

      public int hashCode()
      Returns the hash code value for this bit set. The hash code depends only on which bits are set within this ImmutableBitSet.

      The hash code is defined using the same calculation as BitSet.hashCode().

      Overrides:
      hashCode in class Object
      Returns:
      the hash code value for this bit set
    • size

      public int size()
      Returns the number of bits of space actually in use by this ImmutableBitSet 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
      See Also:
      cardinality()
    • equals

      public boolean equals​(Object obj)
      Compares this object against the specified object. The result is true if and only if the argument is not null and is a ImmutableBitSet object that has exactly the same set of bits set to true as this bit set.
      Overrides:
      equals in class Object
      Parameters:
      obj - the object to compare with
      Returns:
      true if the objects are the same; false otherwise
      See Also:
      size()
    • compareTo

      public int compareTo​(@Nonnull ImmutableBitSet o)
      Compares this ImmutableBitSet with another, using a lexicographic ordering.

      Bit sets (), (0), (0, 1), (0, 1, 3), (1), (2, 3) are in sorted order.

      Specified by:
      compareTo in interface Comparable<ImmutableBitSet>
    • nextSetBit

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

      Based upon BitSet.nextSetBit(int).

      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

      public 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
    • previousClearBit

      public 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
    • iterator

      public Iterator<Integer> iterator()
      Specified by:
      iterator in interface Iterable<Integer>
    • toList

      public List<Integer> toList()
      Converts this bit set to a list.
    • asList

      public List<Integer> asList()
      Creates a view onto this bit set as a list of integers.

      The cardinality and get methods are both O(n), but the iterator is efficient. The list is memory efficient, and the CPU cost breaks even (versus toList()) if you intend to scan it only once.

    • asSet

      public Set<Integer> asSet()
      Creates a view onto this bit set as a set of integers.

      The size and contains methods are both O(n), but the iterator is efficient.

    • toArray

      public int[] toArray()
      Converts this bit set to an array.

      Each entry of the array is the ordinal of a set bit. The array is sorted.

      Returns:
      Array of set bits
    • toLongArray

      public long[] toLongArray()
      Converts this bit set to an array of little-endian words.
    • union

      public ImmutableBitSet union​(BitSet other)
      Returns the union of this immutable bit set with a BitSet.
    • union

      public ImmutableBitSet union​(ImmutableBitSet other)
      Returns the union of this bit set with another.
    • union

      public static ImmutableBitSet union​(Iterable<? extends ImmutableBitSet> sets)
      Returns the union of a number of bit sets.
    • except

      public ImmutableBitSet except​(ImmutableBitSet that)
      Returns a bit set with all the bits in this set that are not in another.
      See Also:
      BitSet.andNot(java.util.BitSet)
    • intersect

      public ImmutableBitSet intersect​(ImmutableBitSet that)
      Returns a bit set with all the bits set in both this set and in another.
      See Also:
      BitSet.and(java.util.BitSet)
    • contains

      public boolean contains​(ImmutableBitSet set1)
      Returns true if all bits set in the second parameter are also set in the first. In other words, whether x is a super-set of y.
      Parameters:
      set1 - Bitmap to be checked
      Returns:
      Whether all bits in set1 are set in set0
    • indexOf

      public int indexOf​(int bit)
      The ordinal of a given bit, or -1 if it is not set.
    • closure

      public static SortedMap<Integer,​ImmutableBitSet> closure​(SortedMap<Integer,​ImmutableBitSet> equivalence)
      Computes the closure of a map from integers to bits.

      The input must have an entry for each position.

      Does not modify the input map or its bit sets.

    • length

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

      public boolean isEmpty()
      Returns true if this ImmutableBitSet contains no bits that are set to true.
    • builder

      public static ImmutableBitSet.Builder builder()
      Creates an empty Builder.
    • builder

      @Deprecated public static ImmutableBitSet.Builder builder​(ImmutableBitSet bitSet)
      Deprecated.
    • rebuild

      public ImmutableBitSet.Builder rebuild()
      Creates a Builder whose initial contents are the same as this ImmutableBitSet.
    • nth

      public int nth​(int n)
      Returns the nth set bit.
      Throws:
      IndexOutOfBoundsException - if n is less than 0 or greater than the number of bits set
    • set

      public ImmutableBitSet set​(int i)
      Returns a bit set the same as this but with a given bit set.
    • set

      public ImmutableBitSet set​(int i, boolean b)
      Returns a bit set the same as this but with a given bit set (if b is true) or unset (if b is false).
    • setIf

      public ImmutableBitSet setIf​(int bit, boolean condition)
      Returns a bit set the same as this but with a given bit set if condition is true.
    • clear

      public ImmutableBitSet clear​(int i)
      Returns a bit set the same as this but with a given bit cleared.
    • clearIf

      public ImmutableBitSet clearIf​(int i, boolean condition)
      Returns a bit set the same as this but with a given bit cleared if condition is true.
    • toBitSet

      public BitSet toBitSet()
      Returns a BitSet that has the same contents as this ImmutableBitSet.
    • permute

      public ImmutableBitSet permute​(Map<Integer,​Integer> map)
      Permutes a bit set according to a given mapping.
    • permute

      public static Iterable<ImmutableBitSet> permute​(Iterable<ImmutableBitSet> bitSets, Map<Integer,​Integer> map)
      Permutes a collection of bit sets according to a given mapping.
    • shift

      public ImmutableBitSet shift​(int offset)
      Returns a bit set with every bit moved up offset positions. Offset may be negative, but throws if any bit ends up negative.
    • allContain

      public static boolean allContain​(Collection<ImmutableBitSet> bitSets, int bit)
      Checks if all bit sets contain a particular bit.