BitSets.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to you under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.calcite.util;
import com.google.common.collect.ImmutableSortedMap;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.List;
import java.util.NavigableMap;
import java.util.SortedMap;
import java.util.TreeMap;
import static java.util.Objects.requireNonNull;
/**
* Utility functions for {@link BitSet}.
*/
public final class BitSets {
private BitSets() {
throw new AssertionError("no instances!");
}
/**
* 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.
*
* @param set0 Containing bitmap
* @param set1 Bitmap to be checked
*
* @return Whether all bits in set1 are set in set0
*/
public static boolean contains(BitSet set0, BitSet set1) {
for (int i = set1.nextSetBit(0); i >= 0; i = set1.nextSetBit(i + 1)) {
if (!set0.get(i)) {
return false;
}
}
return true;
}
/**
* 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.
*
* @param set0 Containing bitmap
* @param set1 Bitmap to be checked
*
* @return Whether all bits in set1 are set in set0
*/
public static boolean contains(BitSet set0, ImmutableBitSet set1) {
for (int i = set1.nextSetBit(0); i >= 0; i = set1.nextSetBit(i + 1)) {
if (!set0.get(i)) {
return false;
}
}
return true;
}
/**
* Returns an iterable over the bits in a bitmap that are set to '1'.
*
* <p>This allows you to iterate over a bit set using a 'foreach' construct.
* For instance:
*
* <blockquote><code>
* BitSet bitSet;<br>
* for (int i : Util.toIter(bitSet)) {<br>
* print(i);<br>
* }</code></blockquote>
*
* @param bitSet Bit set
* @return Iterable
*/
public static Iterable<Integer> toIter(final BitSet bitSet) {
return () -> new Iterator<Integer>() {
int i = bitSet.nextSetBit(0);
@Override public boolean hasNext() {
return i >= 0;
}
@Override public Integer next() {
int prev = i;
i = bitSet.nextSetBit(i + 1);
return prev;
}
@Override public void remove() {
throw new UnsupportedOperationException();
}
};
}
public static Iterable<Integer> toIter(final ImmutableBitSet bitSet) {
return bitSet;
}
/**
* Converts a bitset to a list.
*
* <p>The list is mutable, and future changes to the list do not affect the
* contents of the bit set.
*
* @param bitSet Bit set
* @return List of set bits
*/
public static List<Integer> toList(final BitSet bitSet) {
final List<Integer> list = new ArrayList<>();
for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
list.add(i);
}
return list;
}
/**
* Converts a BitSet to an array.
*
* @param bitSet Bit set
* @return Array of set bits
*/
public static int[] toArray(final BitSet bitSet) {
final int[] integers = new int[bitSet.cardinality()];
int j = 0;
for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
integers[j++] = i;
}
return integers;
}
/**
* Creates a bitset with given bits set.
*
* <p>For example, {@code of(0, 3)} returns a bit set with bits {0, 3}
* set.
*
* @param bits Array of bits to set
* @return Bit set
*/
public static BitSet of(int... bits) {
final BitSet bitSet = new BitSet();
for (int bit : bits) {
bitSet.set(bit);
}
return bitSet;
}
/**
* Creates a BitSet with given bits set.
*
* <p>For example, {@code of(new Integer[] {0, 3})} returns a bit set
* with bits {0, 3} set.
*
* @param bits Array of bits to set
* @return Bit set
*/
public static BitSet of(Integer[] bits) {
final BitSet bitSet = new BitSet();
for (int bit : bits) {
bitSet.set(bit);
}
return bitSet;
}
/**
* Creates a BitSet with given bits set.
*
* <p>For example, {@code of(Arrays.asList(0, 3)) } returns a bit set
* with bits {0, 3} set.
*
* @param bits Collection of bits to set
* @return Bit set
*/
public static BitSet of(Iterable<? extends Number> bits) {
final BitSet bitSet = new BitSet();
for (Number bit : bits) {
bitSet.set(bit.intValue());
}
return bitSet;
}
/**
* Creates a BitSet with given bits set.
*
* <p>For example, {@code of(ImmutableIntList.of(0, 3))} returns a bit set
* with bits {0, 3} set.
*
* @param bits Collection of bits to set
* @return Bit set
*/
public static BitSet of(ImmutableIntList bits) {
final BitSet bitSet = new BitSet();
for (int i = 0, n = bits.size(); i < n; i++) {
bitSet.set(bits.getInt(i));
}
return bitSet;
}
/**
* Creates a bitset with bits from {@code fromIndex} (inclusive) to
* specified {@code toIndex} (exclusive) set to {@code true}.
*
* <p>For example, {@code range(0, 3)} returns a bit set with bits
* {0, 1, 2} set.
*
* @param fromIndex Index of the first bit to be set.
* @param toIndex Index after the last bit to be set.
* @return Bit set
*/
public static BitSet range(int fromIndex, int toIndex) {
final BitSet bitSet = new BitSet();
if (toIndex > fromIndex) {
// Avoid http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6222207
// "BitSet internal invariants may be violated"
bitSet.set(fromIndex, toIndex);
}
return bitSet;
}
/** Creates a BitSet with bits between 0 and {@code toIndex} set. */
public static BitSet range(int toIndex) {
return range(0, toIndex);
}
/** Sets all bits in a given BitSet corresponding to integers from a list. */
public static void setAll(BitSet bitSet, Iterable<? extends Number> list) {
for (Number number : list) {
bitSet.set(number.intValue());
}
}
/** Returns a BitSet that is the union of the given BitSets. Does not modify
* any of the inputs. */
public static BitSet union(BitSet set0, BitSet... sets) {
final BitSet s = (BitSet) set0.clone();
for (BitSet set : sets) {
s.or(set);
}
return s;
}
/** Returns the previous clear bit.
*
* <p>Has same behavior as {@link BitSet#previousClearBit}, but that method
* does not exist before 1.7. */
public static int previousClearBit(BitSet bitSet, int fromIndex) {
if (fromIndex < -1) {
throw new IndexOutOfBoundsException();
}
while (fromIndex >= 0) {
if (!bitSet.get(fromIndex)) {
return fromIndex;
}
--fromIndex;
}
return -1;
}
/** Computes the closure of a map from integers to bits.
*
* <p>The input must have an entry for each position.
*
* <p>Does not modify the input map or its bit sets. */
@SuppressWarnings("JdkObsolete")
public static SortedMap<Integer, BitSet> closure(
SortedMap<Integer, BitSet> equivalence) {
if (equivalence.isEmpty()) {
return ImmutableSortedMap.of();
}
int length = equivalence.lastKey();
for (BitSet bitSet : equivalence.values()) {
length = Math.max(length, bitSet.length());
}
if (equivalence.size() < length
|| equivalence.firstKey() != 0) {
SortedMap<Integer, BitSet> old = equivalence;
equivalence = new TreeMap<>();
for (int i = 0; i < length; i++) {
final BitSet bitSet = old.get(i);
equivalence.put(i, bitSet == null ? new BitSet() : bitSet);
}
}
final Closure closure = new Closure(equivalence);
return closure.closure;
}
/** Populates a {@link BitSet} from an iterable, such as a list of integer. */
public static void populate(BitSet bitSet, Iterable<? extends Number> list) {
for (Number number : list) {
bitSet.set(number.intValue());
}
}
/** Populates a {@link BitSet} from an
* {@link ImmutableIntList}. */
public static void populate(BitSet bitSet, ImmutableIntList list) {
for (int i = 0; i < list.size(); i++) {
bitSet.set(list.getInt(i));
}
}
/**
* Setup equivalence Sets for each position. If i and j are equivalent then
* they will have the same equivalence Set. The algorithm computes the
* closure relation at each position for the position wrt to positions
* greater than it. Once a closure is computed for a position, the closure
* Set is set on all its descendants. So the closure computation bubbles up
* from lower positions and the final equivalence Set is propagated down
* from the lowest element in the Set.
*/
private static class Closure {
private final SortedMap<Integer, BitSet> equivalence;
private final NavigableMap<Integer, BitSet> closure = new TreeMap<>();
@SuppressWarnings({"JdkObsolete", "method.invocation.invalid"})
Closure(SortedMap<Integer, BitSet> equivalence) {
this.equivalence = equivalence;
final ImmutableIntList keys =
ImmutableIntList.copyOf(equivalence.keySet());
for (int pos : keys) {
computeClosure(pos);
}
}
@SuppressWarnings("JdkObsolete")
private BitSet computeClosure(int pos) {
BitSet o = closure.get(pos);
if (o != null) {
return o;
}
BitSet b =
requireNonNull(equivalence.get(pos),
() -> "equivalence.get(pos) for " + pos);
o = (BitSet) b.clone();
int i = b.nextSetBit(pos + 1);
for (; i >= 0; i = b.nextSetBit(i + 1)) {
o.or(computeClosure(i));
}
closure.put(pos, o);
i = o.nextSetBit(pos + 1);
for (; i >= 0; i = b.nextSetBit(i + 1)) {
closure.put(i, o);
}
return o;
}
}
}