You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by jh...@apache.org on 2015/09/03 00:16:14 UTC
[26/50] incubator-calcite git commit: Various BitSet and
ImmutableBitSet utilities
Various BitSet and ImmutableBitSet utilities
* BitSets.closure does not alter its argument
* Add ImmutableBitSet.union(BitSet)
* Add ImmutableBitSet.shift(int)
* Add Mappings.apply2(Mapping, Iterable<ImmutableBitSet>)
Project: http://git-wip-us.apache.org/repos/asf/incubator-calcite/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-calcite/commit/41541d44
Tree: http://git-wip-us.apache.org/repos/asf/incubator-calcite/tree/41541d44
Diff: http://git-wip-us.apache.org/repos/asf/incubator-calcite/diff/41541d44
Branch: refs/heads/branch-release
Commit: 41541d44d458ec4e4c6067cb40aa68dd1f433bda
Parents: e27311e
Author: Julian Hyde <jh...@apache.org>
Authored: Thu Jul 23 12:30:11 2015 -0700
Committer: Julian Hyde <jh...@apache.org>
Committed: Thu Jul 23 12:30:11 2015 -0700
----------------------------------------------------------------------
.../java/org/apache/calcite/util/BitSets.java | 21 +++++++++-
.../apache/calcite/util/ImmutableBitSet.java | 44 +++++++++++++++++++-
.../apache/calcite/util/mapping/Mappings.java | 20 +++++++++
.../org/apache/calcite/util/BitSetsTest.java | 21 +++++++---
.../calcite/util/ImmutableBitSetTest.java | 34 +++++++++++++--
5 files changed, 127 insertions(+), 13 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/41541d44/core/src/main/java/org/apache/calcite/util/BitSets.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/BitSets.java b/core/src/main/java/org/apache/calcite/util/BitSets.java
index bbab792..daa174a 100644
--- a/core/src/main/java/org/apache/calcite/util/BitSets.java
+++ b/core/src/main/java/org/apache/calcite/util/BitSets.java
@@ -16,6 +16,8 @@
*/
package org.apache.calcite.util;
+import com.google.common.collect.ImmutableSortedMap;
+
import java.util.BitSet;
import java.util.Iterator;
import java.util.SortedMap;
@@ -275,6 +277,22 @@ public final class BitSets {
* <p>Does not modify the input map or its bit sets. */
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;
}
@@ -305,8 +323,7 @@ public final class BitSets {
*/
private static class Closure {
private SortedMap<Integer, BitSet> equivalence;
- private final SortedMap<Integer, BitSet> closure =
- new TreeMap<Integer, BitSet>();
+ private final SortedMap<Integer, BitSet> closure = new TreeMap<>();
public Closure(SortedMap<Integer, BitSet> equivalence) {
this.equivalence = equivalence;
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/41541d44/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java b/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
index d35a446..5e569e0 100644
--- a/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
+++ b/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
@@ -21,6 +21,7 @@ import org.apache.calcite.runtime.Utilities;
import com.google.common.base.Function;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSortedMap;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
@@ -36,6 +37,7 @@ import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
+import java.util.TreeMap;
import javax.annotation.Nonnull;
/**
@@ -347,7 +349,9 @@ public class ImmutableBitSet
}
/** Returns the number of bits set to {@code true} in this
- * {@code ImmutableBitSet}. */
+ * {@code ImmutableBitSet}.
+ *
+ * @see #size() */
public int cardinality() {
return countBits(words);
}
@@ -383,6 +387,8 @@ public class ImmutableBitSet
* The maximum element in the set is the size - 1st element.
*
* @return the number of bits currently in this bit set
+ *
+ * @see #cardinality()
*/
public int size() {
return words.length * BITS_PER_WORD;
@@ -603,6 +609,13 @@ public class ImmutableBitSet
return words.length == 0 ? words : words.clone();
}
+ /** Returns the union of this immutable bit set with a {@link BitSet}. */
+ public ImmutableBitSet union(BitSet other) {
+ return builder(this)
+ .addAll(BitSets.toIter(other))
+ .build();
+ }
+
/** Returns the union of this bit set with another. */
public ImmutableBitSet union(ImmutableBitSet other) {
return builder(this)
@@ -678,6 +691,22 @@ public class ImmutableBitSet
* <p>Does not modify the input map or its bit sets. */
public static SortedMap<Integer, ImmutableBitSet> closure(
SortedMap<Integer, ImmutableBitSet> equivalence) {
+ if (equivalence.isEmpty()) {
+ return ImmutableSortedMap.of();
+ }
+ int length = equivalence.lastKey();
+ for (ImmutableBitSet bitSet : equivalence.values()) {
+ length = Math.max(length, bitSet.length());
+ }
+ if (equivalence.size() < length
+ || equivalence.firstKey() != 0) {
+ SortedMap<Integer, ImmutableBitSet> old = equivalence;
+ equivalence = new TreeMap<>();
+ for (int i = 0; i < length; i++) {
+ final ImmutableBitSet bitSet = old.get(i);
+ equivalence.put(i, bitSet == null ? ImmutableBitSet.of() : bitSet);
+ }
+ }
final Closure closure = new Closure(equivalence);
return closure.closure;
}
@@ -788,6 +817,19 @@ public class ImmutableBitSet
});
}
+ /** Returns a bit set with every bit moved up {@code offset} positions.
+ * Offset may be negative, but throws if any bit ends up negative. */
+ public ImmutableBitSet shift(int offset) {
+ if (offset == 0) {
+ return this;
+ }
+ final Builder builder = builder();
+ for (int i = nextSetBit(0); i >= 0; i = nextSetBit(i + 1)) {
+ builder.set(i + offset);
+ }
+ return builder.build();
+ }
+
/**
* Setup equivalence Sets for each position. If i & j are equivalent then
* they will have the same equivalence Set. The algorithm computes the
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/41541d44/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java b/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java
index 556f090..dcacb56 100644
--- a/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java
+++ b/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java
@@ -23,6 +23,8 @@ import org.apache.calcite.util.Permutation;
import org.apache.calcite.util.Util;
import com.google.common.base.Function;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
import java.util.AbstractList;
import java.util.ArrayList;
@@ -208,6 +210,24 @@ public abstract class Mappings {
}
/**
+ * Applies a mapping to a collection of {@code ImmutableBitSet}s.
+ *
+ * @param mapping Mapping
+ * @param bitSets Collection of bit sets
+ * @return Bit sets with mapping applied
+ */
+ public static ImmutableList<ImmutableBitSet> apply2(final Mapping mapping,
+ Iterable<ImmutableBitSet> bitSets) {
+ return ImmutableList.copyOf(
+ Iterables.transform(bitSets,
+ new Function<ImmutableBitSet, ImmutableBitSet>() {
+ public ImmutableBitSet apply(ImmutableBitSet input1) {
+ return Mappings.apply(mapping, input1);
+ }
+ }));
+ }
+
+ /**
* Applies a mapping to a list.
*
* @param mapping Mapping
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/41541d44/core/src/test/java/org/apache/calcite/util/BitSetsTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/util/BitSetsTest.java b/core/src/test/java/org/apache/calcite/util/BitSetsTest.java
index 4e7cdb9..4581e9a 100644
--- a/core/src/test/java/org/apache/calcite/util/BitSetsTest.java
+++ b/core/src/test/java/org/apache/calcite/util/BitSetsTest.java
@@ -195,8 +195,7 @@ public class BitSetsTest {
final SortedMap<Integer, BitSet> empty = Maps.newTreeMap();
assertThat(BitSets.closure(empty), equalTo(empty));
- // Currently you need an entry for each position, otherwise you get an NPE.
- // We should fix that.
+ // Map with an an entry for each position.
final SortedMap<Integer, BitSet> map = Maps.newTreeMap();
map.put(0, BitSets.of(3));
map.put(1, BitSets.of());
@@ -211,11 +210,21 @@ public class BitSetsTest {
map.put(10, BitSets.of());
map.put(11, BitSets.of());
map.put(12, BitSets.of());
- String original = map.toString();
- assertThat(BitSets.closure(map).toString(),
- equalTo(
- "{0={3, 4, 12}, 1={}, 2={7}, 3={3, 4, 12}, 4={4, 12}, 5={}, 6={}, 7={7}, 8={}, 9={}, 10={}, 11={}, 12={4, 12}}"));
+ final String original = map.toString();
+ final String expected =
+ "{0={3, 4, 12}, 1={}, 2={7}, 3={3, 4, 12}, 4={4, 12}, 5={}, 6={}, 7={7}, 8={}, 9={}, 10={}, 11={}, 12={4, 12}}";
+ assertThat(BitSets.closure(map).toString(), equalTo(expected));
assertThat("argument modified", map.toString(), equalTo(original));
+
+ // Now a similar map with missing entries. Same result.
+ final SortedMap<Integer, BitSet> map2 = Maps.newTreeMap();
+ map2.put(0, BitSets.of(3));
+ map2.put(2, BitSets.of(7));
+ map2.put(3, BitSets.of(4, 12));
+ map2.put(9, BitSets.of());
+ final String original2 = map2.toString();
+ assertThat(BitSets.closure(map2).toString(), equalTo(expected));
+ assertThat("argument modified", map2.toString(), equalTo(original2));
}
}
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/41541d44/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java b/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java
index da34dc7..b04c12a 100644
--- a/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java
+++ b/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java
@@ -30,6 +30,7 @@ import java.util.List;
import java.util.SortedMap;
import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertThat;
@@ -374,11 +375,21 @@ public class ImmutableBitSetTest {
map.put(10, ImmutableBitSet.of());
map.put(11, ImmutableBitSet.of());
map.put(12, ImmutableBitSet.of());
- String original = map.toString();
- assertThat(ImmutableBitSet.closure(map).toString(),
- equalTo(
- "{0={3, 4, 12}, 1={}, 2={7}, 3={3, 4, 12}, 4={4, 12}, 5={}, 6={}, 7={7}, 8={}, 9={}, 10={}, 11={}, 12={4, 12}}"));
+ final String original = map.toString();
+ final String expected =
+ "{0={3, 4, 12}, 1={}, 2={7}, 3={3, 4, 12}, 4={4, 12}, 5={}, 6={}, 7={7}, 8={}, 9={}, 10={}, 11={}, 12={4, 12}}";
+ assertThat(ImmutableBitSet.closure(map).toString(), equalTo(expected));
assertThat("argument modified", map.toString(), equalTo(original));
+
+ // Now a similar map with missing entries. Same result.
+ final SortedMap<Integer, ImmutableBitSet> map2 = Maps.newTreeMap();
+ map2.put(0, ImmutableBitSet.of(3));
+ map2.put(2, ImmutableBitSet.of(7));
+ map2.put(3, ImmutableBitSet.of(4, 12));
+ map2.put(9, ImmutableBitSet.of());
+ final String original2 = map2.toString();
+ assertThat(ImmutableBitSet.closure(map2).toString(), equalTo(expected));
+ assertThat("argument modified", map2.toString(), equalTo(original2));
}
@Test public void testPowerSet() {
@@ -446,6 +457,21 @@ public class ImmutableBitSetTest {
assertThat(bitSet.clearIf(29, false), equalTo(bitSet));
assertThat(bitSet.clearIf(29, true), equalTo(bitSet2));
}
+
+ @Test public void testShift() {
+ final ImmutableBitSet bitSet = ImmutableBitSet.of(29, 4, 1969);
+ assertThat(bitSet.shift(0), is(bitSet));
+ assertThat(bitSet.shift(1), is(ImmutableBitSet.of(30, 5, 1970)));
+ assertThat(bitSet.shift(-4), is(ImmutableBitSet.of(25, 0, 1965)));
+ try {
+ final ImmutableBitSet x = bitSet.shift(-5);
+ fail("Expected error, got " + x);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ assertThat(e.getMessage(), is("-1"));
+ }
+ final ImmutableBitSet empty = ImmutableBitSet.of();
+ assertThat(empty.shift(-100), is(empty));
+ }
}
// End ImmutableBitSetTest.java