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 2014/11/14 22:33:01 UTC
[53/58] [abbrv] incubator-calcite git commit: [CALCITE-460] Add
ImmutableBitSet and replace uses of BitSet
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java b/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java
index cd70844..ce651bc 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java
@@ -26,6 +26,7 @@ import org.apache.calcite.rel.RelWriter;
import org.apache.calcite.rel.core.JoinRelType;
import org.apache.calcite.rel.type.RelDataType;
import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.ImmutableIntList;
import org.apache.calcite.util.ImmutableNullableList;
@@ -34,7 +35,6 @@ import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Lists;
import java.util.ArrayList;
-import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
@@ -52,7 +52,7 @@ public final class MultiJoin extends AbstractRelNode {
private final boolean isFullOuterJoin;
private final List<RexNode> outerJoinConditions;
private final ImmutableList<JoinRelType> joinTypes;
- private final List<BitSet> projFields;
+ private final List<ImmutableBitSet> projFields;
public final ImmutableMap<Integer, ImmutableIntList> joinFieldRefCountsMap;
private final RexNode postJoinFilter;
@@ -91,7 +91,7 @@ public final class MultiJoin extends AbstractRelNode {
boolean isFullOuterJoin,
List<RexNode> outerJoinConditions,
List<JoinRelType> joinTypes,
- List<BitSet> projFields,
+ List<ImmutableBitSet> projFields,
ImmutableMap<Integer, ImmutableIntList> joinFieldRefCountsMap,
RexNode postJoinFilter) {
super(cluster, cluster.traitSetOf(Convention.NONE));
@@ -214,7 +214,7 @@ public final class MultiJoin extends AbstractRelNode {
* @return bitmaps representing the fields projected from each input; if an
* entry is null, all fields are projected
*/
- public List<BitSet> getProjFields() {
+ public List<ImmutableBitSet> getProjFields() {
return projFields;
}
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java b/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java
index 62eef89..2e6667c 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java
@@ -30,7 +30,7 @@ import org.apache.calcite.rex.RexNode;
import org.apache.calcite.rex.RexPermuteInputsShuttle;
import org.apache.calcite.rex.RexUtil;
import org.apache.calcite.rex.RexVisitor;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Pair;
import org.apache.calcite.util.Util;
import org.apache.calcite.util.mapping.Mappings;
@@ -41,7 +41,6 @@ import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import java.io.PrintWriter;
-import java.util.BitSet;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
@@ -132,8 +131,7 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
if (edgeOrdinal == -1) {
// No more edges. Are there any un-joined vertexes?
final Vertex lastVertex = Util.last(vertexes);
- final int z =
- BitSets.previousClearBit(lastVertex.factors, lastVertex.id - 1);
+ final int z = lastVertex.factors.previousClearBit(lastVertex.id - 1);
if (z < 0) {
break;
}
@@ -147,7 +145,7 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
// Therefore, for now, the factors that are merged are exactly the
// factors on this edge.
assert bestEdge.factors.cardinality() == 2;
- factors = BitSets.toArray(bestEdge.factors);
+ factors = bestEdge.factors.toArray();
}
// Determine which factor is to be on the LHS of the join.
@@ -165,26 +163,29 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
// Find the join conditions. All conditions whose factors are now all in
// the join can now be used.
- final BitSet newFactors =
- BitSets.union(majorVertex.factors, minorVertex.factors);
+ final int v = vertexes.size();
+ final ImmutableBitSet newFactors =
+ ImmutableBitSet.builder(majorVertex.factors)
+ .addAll(minorVertex.factors)
+ .set(v)
+ .build();
+
final List<RexNode> conditions = Lists.newArrayList();
final Iterator<LoptMultiJoin.Edge> edgeIterator = unusedEdges.iterator();
while (edgeIterator.hasNext()) {
LoptMultiJoin.Edge edge = edgeIterator.next();
- if (BitSets.contains(newFactors, edge.factors)) {
+ if (newFactors.contains(edge.factors)) {
conditions.add(edge.condition);
edgeIterator.remove();
usedEdges.add(edge);
}
}
- final int v = vertexes.size();
double cost =
majorVertex.cost
* minorVertex.cost
* RelMdUtil.guessSelectivity(
RexUtil.composeConjunction(rexBuilder, conditions, false));
- newFactors.set(v);
final Vertex newVertex =
new JoinVertex(v, majorFactor, minorFactor, newFactors,
cost, ImmutableList.copyOf(conditions));
@@ -197,13 +198,16 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
// This vertex has fewer rows (1k rows) -- a fact that is critical to
// decisions made later. (Hence "greedy" algorithm not "simple".)
// The adjacent edges are modified.
- final BitSet merged = BitSets.of(minorFactor, majorFactor);
+ final ImmutableBitSet merged =
+ ImmutableBitSet.of(minorFactor, majorFactor);
for (int i = 0; i < unusedEdges.size(); i++) {
final LoptMultiJoin.Edge edge = unusedEdges.get(i);
if (edge.factors.intersects(merged)) {
- BitSet newEdgeFactors = (BitSet) edge.factors.clone();
- newEdgeFactors.andNot(newFactors);
- newEdgeFactors.set(v);
+ ImmutableBitSet newEdgeFactors =
+ ImmutableBitSet.builder(edge.factors)
+ .removeAll(newFactors)
+ .set(v)
+ .build();
assert newEdgeFactors.cardinality() == 2;
final LoptMultiJoin.Edge newEdge =
new LoptMultiJoin.Edge(edge.condition, newEdgeFactors,
@@ -251,7 +255,7 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
RexUtil.composeConjunction(rexBuilder, joinVertex.conditions,
false);
relNodes.add(
- Pair.of((RelNode)
+ Pair.of(
joinFactory.createJoin(left, right, condition.accept(shuttle),
JoinRelType.INNER, ImmutableSet.<String>of(), false),
mapping));
@@ -321,10 +325,10 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
abstract static class Vertex {
final int id;
- protected final BitSet factors;
+ protected final ImmutableBitSet factors;
final double cost;
- Vertex(int id, BitSet factors, double cost) {
+ Vertex(int id, ImmutableBitSet factors, double cost) {
this.id = id;
this.factors = factors;
this.cost = cost;
@@ -337,7 +341,7 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
final int fieldOffset;
LeafVertex(int id, RelNode rel, double cost, int fieldOffset) {
- super(id, BitSets.of(id), cost);
+ super(id, ImmutableBitSet.of(id), cost);
this.rel = rel;
this.fieldOffset = fieldOffset;
}
@@ -359,8 +363,8 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
* columns (not in terms of the outputs of left and right input factors). */
final ImmutableList<RexNode> conditions;
- JoinVertex(int id, int leftFactor, int rightFactor,
- BitSet factors, double cost, ImmutableList<RexNode> conditions) {
+ JoinVertex(int id, int leftFactor, int rightFactor, ImmutableBitSet factors,
+ double cost, ImmutableList<RexNode> conditions) {
super(id, factors, cost);
this.leftFactor = leftFactor;
this.rightFactor = rightFactor;
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java b/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java
index d317237..cfaf740 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java
@@ -31,6 +31,7 @@ import org.apache.calcite.rex.RexUtil;
import org.apache.calcite.rex.RexVisitorImpl;
import org.apache.calcite.sql.SqlOperator;
import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Pair;
import com.google.common.collect.ImmutableList;
@@ -88,14 +89,14 @@ public class PushProjector {
* pushed past, if the RelNode is not a join. If the RelNode is a join, then
* the fields correspond to the left hand side of the join.
*/
- final BitSet childBitmap;
+ final ImmutableBitSet childBitmap;
/**
* Bitmap containing the fields in the right hand side of a join, in the
* case where the projection is being pushed past a join. Not used
* otherwise.
*/
- final BitSet rightBitmap;
+ final ImmutableBitSet rightBitmap;
/**
* Number of fields in the RelNode that the projection is being pushed past,
@@ -215,13 +216,13 @@ public class PushProjector {
nFieldsRight = rightFields.size();
nSysFields = joinRel.getSystemFieldList().size();
childBitmap =
- BitSets.range(nSysFields, nFields + nSysFields);
+ ImmutableBitSet.range(nSysFields, nFields + nSysFields);
rightBitmap =
- BitSets.range(nFields + nSysFields, nChildFields);
+ ImmutableBitSet.range(nFields + nSysFields, nChildFields);
} else {
nFields = nChildFields;
nFieldsRight = 0;
- childBitmap = BitSets.range(nChildFields);
+ childBitmap = ImmutableBitSet.range(nChildFields);
rightBitmap = null;
nSysFields = 0;
}
@@ -574,16 +575,16 @@ public class PushProjector {
*/
private class InputSpecialOpFinder extends RexVisitorImpl<Void> {
private final BitSet rexRefs;
- private final BitSet leftFields;
- private final BitSet rightFields;
+ private final ImmutableBitSet leftFields;
+ private final ImmutableBitSet rightFields;
private final ExprCondition preserveExprCondition;
private final List<RexNode> preserveLeft;
private final List<RexNode> preserveRight;
public InputSpecialOpFinder(
BitSet rexRefs,
- BitSet leftFields,
- BitSet rightFields,
+ ImmutableBitSet leftFields,
+ ImmutableBitSet rightFields,
ExprCondition preserveExprCondition,
List<RexNode> preserveLeft,
List<RexNode> preserveRight) {
@@ -609,12 +610,12 @@ public class PushProjector {
// if the arguments of the expression only reference the
// left hand side, preserve it on the left; similarly, if
// it only references expressions on the right
- final BitSet exprArgs = RelOptUtil.InputFinder.bits(call);
+ final ImmutableBitSet exprArgs = RelOptUtil.InputFinder.bits(call);
if (exprArgs.cardinality() > 0) {
- if (BitSets.contains(leftFields, exprArgs)) {
+ if (leftFields.contains(exprArgs)) {
addExpr(preserveLeft, call);
return true;
- } else if (BitSets.contains(rightFields, exprArgs)) {
+ } else if (rightFields.contains(exprArgs)) {
assert preserveRight != null;
addExpr(preserveRight, call);
return true;
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java b/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java
index bedea88..28d9454 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java
@@ -26,13 +26,12 @@ import org.apache.calcite.rel.core.Join;
import org.apache.calcite.rel.core.JoinInfo;
import org.apache.calcite.rel.core.Project;
import org.apache.calcite.rel.core.SemiJoin;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.ImmutableIntList;
import org.apache.calcite.util.IntList;
import com.google.common.collect.Lists;
-import java.util.BitSet;
import java.util.List;
/**
@@ -56,21 +55,23 @@ public class SemiJoinRule extends RelOptRule {
final Join join = call.rel(1);
final RelNode left = call.rel(2);
final Aggregate aggregate = call.rel(3);
- final BitSet bits = RelOptUtil.InputFinder.bits(project.getProjects(),
- null);
- final BitSet rightBits = BitSets.range(left.getRowType().getFieldCount(),
- join.getRowType().getFieldCount());
+ final ImmutableBitSet bits =
+ RelOptUtil.InputFinder.bits(project.getProjects(), null);
+ final ImmutableBitSet rightBits =
+ ImmutableBitSet.range(left.getRowType().getFieldCount(),
+ join.getRowType().getFieldCount());
if (bits.intersects(rightBits)) {
return;
}
final JoinInfo joinInfo = join.analyzeCondition();
- if (!joinInfo.rightSet().equals(BitSets.range(aggregate.getGroupCount()))) {
+ if (!joinInfo.rightSet().equals(
+ ImmutableBitSet.range(aggregate.getGroupCount()))) {
// Rule requires that aggregate key to be the same as the join key.
// By the way, neither a super-set nor a sub-set would work.
return;
}
final List<Integer> newRightKeys = Lists.newArrayList();
- final IntList aggregateKeys = BitSets.toList(aggregate.getGroupSet());
+ final IntList aggregateKeys = aggregate.getGroupSet().toList();
for (int key : joinInfo.rightKeys) {
newRightKeys.add(aggregateKeys.get(key));
}
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/schema/Statistic.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/schema/Statistic.java b/core/src/main/java/org/apache/calcite/schema/Statistic.java
index fa907da..b725d4b 100644
--- a/core/src/main/java/org/apache/calcite/schema/Statistic.java
+++ b/core/src/main/java/org/apache/calcite/schema/Statistic.java
@@ -16,7 +16,7 @@
*/
package org.apache.calcite.schema;
-import java.util.BitSet;
+import org.apache.calcite.util.ImmutableBitSet;
/**
* Statistics about a {@link Table}.
@@ -32,7 +32,7 @@ public interface Statistic {
/** Returns whether the given set of columns is a unique key, or a superset
* of a unique key, of the table.
*/
- boolean isKey(BitSet columns);
+ boolean isKey(ImmutableBitSet columns);
}
// End Statistic.java
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/schema/Statistics.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/schema/Statistics.java b/core/src/main/java/org/apache/calcite/schema/Statistics.java
index 9712e7c..4b2611a 100644
--- a/core/src/main/java/org/apache/calcite/schema/Statistics.java
+++ b/core/src/main/java/org/apache/calcite/schema/Statistics.java
@@ -16,9 +16,8 @@
*/
package org.apache.calcite.schema;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
-import java.util.BitSet;
import java.util.List;
/**
@@ -35,21 +34,22 @@ public class Statistics {
return null;
}
- public boolean isKey(BitSet columns) {
+ public boolean isKey(ImmutableBitSet columns) {
return false;
}
};
/** Returns a statistic with a given row count and set of unique keys. */
- public static Statistic of(final double rowCount, final List<BitSet> keys) {
+ public static Statistic of(final double rowCount,
+ final List<ImmutableBitSet> keys) {
return new Statistic() {
public Double getRowCount() {
return rowCount;
}
- public boolean isKey(BitSet columns) {
- for (BitSet key : keys) {
- if (BitSets.contains(columns, key)) {
+ public boolean isKey(ImmutableBitSet columns) {
+ for (ImmutableBitSet key : keys) {
+ if (columns.contains(key)) {
return true;
}
}
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java b/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java
index 4da6445..6da2268 100644
--- a/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java
+++ b/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java
@@ -64,9 +64,9 @@ import org.apache.calcite.sql.SqlOperator;
import org.apache.calcite.sql.fun.SqlCountAggFunction;
import org.apache.calcite.sql.fun.SqlSingleValueAggFunction;
import org.apache.calcite.sql.fun.SqlStdOperatorTable;
-import org.apache.calcite.util.BitSets;
import org.apache.calcite.util.Bug;
import org.apache.calcite.util.Holder;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Pair;
import org.apache.calcite.util.ReflectUtil;
import org.apache.calcite.util.ReflectiveVisitDispatcher;
@@ -87,7 +87,6 @@ import com.google.common.collect.SortedSetMultimap;
import java.math.BigDecimal;
import java.util.ArrayList;
-import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
@@ -582,7 +581,7 @@ public class RelDecorrelator implements ReflectiveVisitor {
new LogicalAggregate(
rel.getCluster(),
newProjectRel,
- BitSets.range(newGroupKeyCount),
+ ImmutableBitSet.range(newGroupKeyCount),
newAggCalls);
mapOldToNewRel.put(rel, newAggregate);
@@ -2202,7 +2201,7 @@ public class RelDecorrelator implements ReflectiveVisitor {
}
int nFields = leftInputRel.getRowType().getFieldCount();
- BitSet allCols = BitSets.range(nFields);
+ ImmutableBitSet allCols = ImmutableBitSet.range(nFields);
// leftInputRel contains unique keys
// i.e. each row is distinct and can group by on all the left
@@ -2345,8 +2344,8 @@ public class RelDecorrelator implements ReflectiveVisitor {
aggRel.getGroupCount(), groupCount));
}
- BitSet groupSet =
- BitSets.range(groupCount);
+ ImmutableBitSet groupSet =
+ ImmutableBitSet.range(groupCount);
LogicalAggregate newAggRel =
new LogicalAggregate(
cluster,
@@ -2355,7 +2354,7 @@ public class RelDecorrelator implements ReflectiveVisitor {
newAggCalls);
List<RexNode> newAggOutputProjExprList = Lists.newArrayList();
- for (int i : BitSets.toIter(groupSet)) {
+ for (int i : groupSet) {
newAggOutputProjExprList.add(
rexBuilder.makeInputRef(newAggRel, i));
}
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java b/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java
index 075def1..c68273d 100644
--- a/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java
+++ b/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java
@@ -47,8 +47,8 @@ import org.apache.calcite.rex.RexPermuteInputsShuttle;
import org.apache.calcite.rex.RexUtil;
import org.apache.calcite.rex.RexVisitor;
import org.apache.calcite.sql.validate.SqlValidator;
-import org.apache.calcite.util.BitSets;
import org.apache.calcite.util.Bug;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Pair;
import org.apache.calcite.util.ReflectUtil;
import org.apache.calcite.util.ReflectiveVisitor;
@@ -63,7 +63,6 @@ import com.google.common.collect.ImmutableList;
import java.math.BigDecimal;
import java.util.ArrayList;
-import java.util.BitSet;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
@@ -144,7 +143,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
this,
"trimFields",
RelNode.class,
- BitSet.class,
+ ImmutableBitSet.class,
Set.class);
this.projectFactory = Preconditions.checkNotNull(projectFactory);
this.filterFactory = Preconditions.checkNotNull(filterFactory);
@@ -168,7 +167,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
*/
public RelNode trim(RelNode root) {
final int fieldCount = root.getRowType().getFieldCount();
- final BitSet fieldsUsed = BitSets.range(fieldCount);
+ final ImmutableBitSet fieldsUsed = ImmutableBitSet.range(fieldCount);
final Set<RelDataTypeField> extraFields = Collections.emptySet();
final TrimResult trimResult =
dispatchTrimFields(root, fieldsUsed, extraFields);
@@ -189,14 +188,14 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
protected TrimResult trimChild(
RelNode rel,
RelNode input,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
Util.discard(rel);
if (input.getClass().getName().endsWith("MedMdrClassExtentRel")) {
// MedMdrJoinRule cannot handle Join of Project of
// MedMdrClassExtentRel, only naked MedMdrClassExtentRel.
// So, disable trimming.
- fieldsUsed = BitSets.range(input.getRowType().getFieldCount());
+ fieldsUsed = ImmutableBitSet.range(input.getRowType().getFieldCount());
}
return dispatchTrimFields(input, fieldsUsed, extraFields);
}
@@ -217,7 +216,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
protected TrimResult trimChildRestore(
RelNode rel,
RelNode input,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
TrimResult trimResult = trimChild(rel, input, fieldsUsed, extraFields);
if (trimResult.right.isIdentity()) {
@@ -255,7 +254,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
*/
protected final TrimResult dispatchTrimFields(
RelNode rel,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final TrimResult trimResult =
trimFieldsDispatcher.invoke(rel, fieldsUsed, extraFields);
@@ -296,7 +295,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
*/
public TrimResult trimFields(
RelNode rel,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
// We don't know how to trim this kind of relational expression, so give
// it back intact.
@@ -308,12 +307,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.logical.LogicalProject}.
*/
public TrimResult trimFields(
Project project,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final RelDataType rowType = project.getRowType();
final int fieldCount = rowType.getFieldCount();
@@ -321,16 +320,16 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
final RelDataType inputRowType = input.getRowType();
// Which fields are required from the input?
- BitSet inputFieldsUsed = new BitSet(inputRowType.getFieldCount());
final Set<RelDataTypeField> inputExtraFields =
new LinkedHashSet<RelDataTypeField>(extraFields);
RelOptUtil.InputFinder inputFinder =
- new RelOptUtil.InputFinder(inputFieldsUsed, inputExtraFields);
+ new RelOptUtil.InputFinder(inputExtraFields);
for (Ord<RexNode> ord : Ord.zip(project.getProjects())) {
if (fieldsUsed.get(ord.i)) {
ord.e.accept(inputFinder);
}
}
+ ImmutableBitSet inputFieldsUsed = inputFinder.inputBitSet.build();
// Create input with trimmed columns.
TrimResult trimResult =
@@ -416,12 +415,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.logical.LogicalFilter}.
*/
public TrimResult trimFields(
Filter filter,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final RelDataType rowType = filter.getRowType();
final int fieldCount = rowType.getFieldCount();
@@ -430,12 +429,13 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
// We use the fields used by the consumer, plus any fields used in the
// filter.
- BitSet inputFieldsUsed = (BitSet) fieldsUsed.clone();
final Set<RelDataTypeField> inputExtraFields =
new LinkedHashSet<RelDataTypeField>(extraFields);
RelOptUtil.InputFinder inputFinder =
- new RelOptUtil.InputFinder(inputFieldsUsed, inputExtraFields);
+ new RelOptUtil.InputFinder(inputExtraFields);
+ inputFinder.inputBitSet.addAll(fieldsUsed);
conditionExpr.accept(inputFinder);
+ final ImmutableBitSet inputFieldsUsed = inputFinder.inputBitSet.build();
// Create input with trimmed columns.
TrimResult trimResult =
@@ -468,12 +468,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.core.Sort}.
*/
public TrimResult trimFields(
Sort sort,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final RelDataType rowType = sort.getRowType();
final int fieldCount = rowType.getFieldCount();
@@ -482,7 +482,8 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
// We use the fields used by the consumer, plus any fields used as sort
// keys.
- BitSet inputFieldsUsed = (BitSet) fieldsUsed.clone();
+ final ImmutableBitSet.Builder inputFieldsUsed =
+ ImmutableBitSet.builder(fieldsUsed);
for (RelFieldCollation field : collation.getFieldCollations()) {
inputFieldsUsed.set(field.getFieldIndex());
}
@@ -490,7 +491,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
// Create input with trimmed columns.
final Set<RelDataTypeField> inputExtraFields = Collections.emptySet();
TrimResult trimResult =
- trimChild(sort, input, inputFieldsUsed, inputExtraFields);
+ trimChild(sort, input, inputFieldsUsed.build(), inputExtraFields);
RelNode newInput = trimResult.left;
final Mapping inputMapping = trimResult.right;
@@ -517,12 +518,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.logical.LogicalJoin}.
*/
public TrimResult trimFields(
Join join,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final int fieldCount = join.getSystemFieldList().size()
+ join.getLeft().getRowType().getFieldCount()
@@ -531,13 +532,13 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
final int systemFieldCount = join.getSystemFieldList().size();
// Add in fields used in the condition.
- BitSet fieldsUsedPlus = (BitSet) fieldsUsed.clone();
final Set<RelDataTypeField> combinedInputExtraFields =
new LinkedHashSet<RelDataTypeField>(extraFields);
RelOptUtil.InputFinder inputFinder =
- new RelOptUtil.InputFinder(
- fieldsUsedPlus, combinedInputExtraFields);
+ new RelOptUtil.InputFinder(combinedInputExtraFields);
+ inputFinder.inputBitSet.addAll(fieldsUsed);
conditionExpr.accept(inputFinder);
+ final ImmutableBitSet fieldsUsedPlus = inputFinder.inputBitSet.build();
// If no system fields are used, we can remove them.
int systemFieldUsedCount = 0;
@@ -564,8 +565,8 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
final int inputFieldCount = inputRowType.getFieldCount();
// Compute required mapping.
- BitSet inputFieldsUsed = new BitSet(inputFieldCount);
- for (int bit : BitSets.toIter(fieldsUsedPlus)) {
+ ImmutableBitSet.Builder inputFieldsUsed = ImmutableBitSet.builder();
+ for (int bit : fieldsUsedPlus) {
if (bit >= offset && bit < offset + inputFieldCount) {
inputFieldsUsed.set(bit - offset);
}
@@ -573,11 +574,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
// If there are system fields, we automatically use the
// corresponding field in each input.
- if (newSystemFieldCount > 0) {
- // calling with newSystemFieldCount == 0 should be safe but hits
- // http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6222207
- inputFieldsUsed.set(0, newSystemFieldCount);
- }
+ inputFieldsUsed.set(0, newSystemFieldCount);
// FIXME: We ought to collect extra fields for each input
// individually. For now, we assume that just one input has
@@ -588,7 +585,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
: combinedInputExtraFields;
inputExtraFieldCounts.add(inputExtraFields.size());
TrimResult trimResult =
- trimChild(join, input, inputFieldsUsed, inputExtraFields);
+ trimChild(join, input, inputFieldsUsed.build(), inputExtraFields);
newInputs.add(trimResult.left);
if (trimResult.left != input) {
++changeCount;
@@ -662,12 +659,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.core.SetOp} (including UNION and UNION ALL).
*/
public TrimResult trimFields(
SetOp setOp,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final RelDataType rowType = setOp.getRowType();
final int fieldCount = rowType.getFieldCount();
@@ -677,7 +674,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
// wants the last field. (The last field is the least likely to be a
// system field.)
if (fieldsUsed.isEmpty()) {
- fieldsUsed.set(rowType.getFieldCount() - 1);
+ fieldsUsed = ImmutableBitSet.of(rowType.getFieldCount() - 1);
}
// Compute the desired field mapping. Give the consumer the fields they
@@ -730,12 +727,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.logical.LogicalAggregate}.
*/
public TrimResult trimFields(
Aggregate aggregate,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
// Fields:
//
@@ -753,11 +750,9 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
final RelDataType rowType = aggregate.getRowType();
// Compute which input fields are used.
- BitSet inputFieldsUsed = new BitSet();
// 1. group fields are always used
- for (int i : BitSets.toIter(aggregate.getGroupSet())) {
- inputFieldsUsed.set(i);
- }
+ final ImmutableBitSet.Builder inputFieldsUsed =
+ ImmutableBitSet.builder(aggregate.getGroupSet());
// 2. agg functions
for (AggregateCall aggCall : aggregate.getAggCallList()) {
for (int i : aggCall.getArgList()) {
@@ -769,14 +764,14 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
final RelNode input = aggregate.getInput(0);
final Set<RelDataTypeField> inputExtraFields = Collections.emptySet();
final TrimResult trimResult =
- trimChild(aggregate, input, inputFieldsUsed, inputExtraFields);
+ trimChild(aggregate, input, inputFieldsUsed.build(), inputExtraFields);
final RelNode newInput = trimResult.left;
final Mapping inputMapping = trimResult.right;
// If the input is unchanged, and we need to project all columns,
// there's nothing to do.
if (input == newInput
- && fieldsUsed.equals(BitSets.range(rowType.getFieldCount()))) {
+ && fieldsUsed.equals(ImmutableBitSet.range(rowType.getFieldCount()))) {
return new TrimResult(
aggregate,
Mappings.createIdentity(rowType.getFieldCount()));
@@ -800,7 +795,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
groupCount
+ usedAggCallCount);
- final BitSet newGroupSet =
+ final ImmutableBitSet newGroupSet =
Mappings.apply(inputMapping, aggregate.getGroupSet());
// Populate mapping of where to find the fields. System and grouping
@@ -840,12 +835,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.logical.LogicalTableModify}.
*/
public TrimResult trimFields(
LogicalTableModify modifier,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
// Ignore what consumer wants. We always project all columns.
Util.discard(fieldsUsed);
@@ -856,7 +851,8 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
// We want all fields from the child.
final int inputFieldCount = input.getRowType().getFieldCount();
- BitSet inputFieldsUsed = BitSets.range(inputFieldCount);
+ final ImmutableBitSet inputFieldsUsed =
+ ImmutableBitSet.range(inputFieldCount);
// Create input with trimmed columns.
final Set<RelDataTypeField> inputExtraFields = Collections.emptySet();
@@ -886,12 +882,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.logical.LogicalTableFunctionScan}.
*/
public TrimResult trimFields(
LogicalTableFunctionScan tabFun,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final RelDataType rowType = tabFun.getRowType();
final int fieldCount = rowType.getFieldCount();
@@ -899,7 +895,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
for (RelNode input : tabFun.getInputs()) {
final int inputFieldCount = input.getRowType().getFieldCount();
- BitSet inputFieldsUsed = BitSets.range(inputFieldCount);
+ ImmutableBitSet inputFieldsUsed = ImmutableBitSet.range(inputFieldCount);
// Create input with trimmed columns.
final Set<RelDataTypeField> inputExtraFields =
@@ -923,12 +919,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.logical.LogicalValues}.
*/
public TrimResult trimFields(
LogicalValues values,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final RelDataType rowType = values.getRowType();
final int fieldCount = rowType.getFieldCount();
@@ -937,11 +933,11 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
// because zero-column records are illegal. Give them the last field,
// which is unlikely to be a system field.
if (fieldsUsed.isEmpty()) {
- fieldsUsed = BitSets.range(fieldCount - 1, fieldCount);
+ fieldsUsed = ImmutableBitSet.range(fieldCount - 1, fieldCount);
}
// If all fields are used, return unchanged.
- if (fieldsUsed.equals(BitSets.range(fieldCount))) {
+ if (fieldsUsed.equals(ImmutableBitSet.range(fieldCount))) {
Mapping mapping = Mappings.createIdentity(fieldCount);
return new TrimResult(values, mapping);
}
@@ -949,7 +945,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
List<List<RexLiteral>> newTuples = new ArrayList<List<RexLiteral>>();
for (List<RexLiteral> tuple : values.getTuples()) {
List<RexLiteral> newTuple = new ArrayList<RexLiteral>();
- for (int field : BitSets.toIter(fieldsUsed)) {
+ for (int field : fieldsUsed) {
newTuple.add(tuple.get(field));
}
newTuples.add(newTuple);
@@ -964,29 +960,30 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
return new TrimResult(newValues, mapping);
}
- private Mapping createMapping(BitSet fieldsUsed, int fieldCount) {
+ private Mapping createMapping(ImmutableBitSet fieldsUsed, int fieldCount) {
final Mapping mapping =
Mappings.create(
MappingType.INVERSE_SURJECTION,
fieldCount,
fieldsUsed.cardinality());
int i = 0;
- for (int field : BitSets.toIter(fieldsUsed)) {
+ for (int field : fieldsUsed) {
mapping.set(field, i++);
}
return mapping;
}
/**
- * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+ * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
* {@link org.apache.calcite.rel.logical.LogicalTableScan}.
*/
public TrimResult trimFields(
final TableScan tableAccessRel,
- BitSet fieldsUsed,
+ ImmutableBitSet fieldsUsed,
Set<RelDataTypeField> extraFields) {
final int fieldCount = tableAccessRel.getRowType().getFieldCount();
- if (fieldsUsed.equals(BitSets.range(fieldCount)) && extraFields.isEmpty()) {
+ if (fieldsUsed.equals(ImmutableBitSet.range(fieldCount))
+ && extraFields.isEmpty()) {
// if there is nothing to project or if we are projecting everything
// then no need to introduce another RelNode
return trimFields(
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java b/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
index ce1cb4a..ceb6a1a 100644
--- a/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
+++ b/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
@@ -127,7 +127,7 @@ import org.apache.calcite.sql.validate.SqlValidatorImpl;
import org.apache.calcite.sql.validate.SqlValidatorNamespace;
import org.apache.calcite.sql.validate.SqlValidatorScope;
import org.apache.calcite.sql.validate.SqlValidatorUtil;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.ImmutableIntList;
import org.apache.calcite.util.NlsString;
import org.apache.calcite.util.NumberUtil;
@@ -148,7 +148,6 @@ import java.lang.reflect.Type;
import java.math.BigDecimal;
import java.util.AbstractList;
import java.util.ArrayList;
-import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.EnumSet;
@@ -714,7 +713,7 @@ public class SqlToRelConverter {
rel =
createAggregate(
bb,
- BitSets.range(rel.getRowType().getFieldCount()),
+ ImmutableBitSet.range(rel.getRowType().getFieldCount()),
ImmutableList.<AggregateCall>of());
bb.setRoot(
@@ -1033,7 +1032,7 @@ public class SqlToRelConverter {
final int keyCount = leftKeys.size();
final List<Integer> args = ImmutableIntList.range(0, keyCount);
LogicalAggregate aggregate =
- new LogicalAggregate(cluster, seek, BitSets.of(),
+ new LogicalAggregate(cluster, seek, ImmutableBitSet.of(),
ImmutableList.of(
new AggregateCall(SqlStdOperatorTable.COUNT, false,
ImmutableList.<Integer>of(), longType, null),
@@ -2276,7 +2275,7 @@ public class SqlToRelConverter {
case LITERAL:
return node;
default:
- BitSet bits = RelOptUtil.InputFinder.bits(node);
+ ImmutableBitSet bits = RelOptUtil.InputFinder.bits(node);
final int mid = leftCount + extraLeftExprs.size();
switch (Side.of(bits, mid)) {
case LEFT:
@@ -2312,7 +2311,7 @@ public class SqlToRelConverter {
enum Side {
LEFT, RIGHT, BOTH, EMPTY;
- static Side of(BitSet bitSet, int middle) {
+ static Side of(ImmutableBitSet bitSet, int middle) {
final int firstBit = bitSet.nextSetBit(0);
if (firstBit < 0) {
return EMPTY;
@@ -2646,7 +2645,7 @@ public class SqlToRelConverter {
bb.setRoot(
createAggregate(
bb,
- BitSets.range(aggConverter.groupExprs.size()),
+ ImmutableBitSet.range(aggConverter.groupExprs.size()),
aggConverter.getAggCalls()),
false);
@@ -2744,7 +2743,7 @@ public class SqlToRelConverter {
*/
protected RelNode createAggregate(
Blackboard bb,
- BitSet groupSet,
+ ImmutableBitSet groupSet,
List<AggregateCall> aggCalls) {
return new LogicalAggregate(
cluster,
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/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 0d79c85..bbab792 100644
--- a/core/src/main/java/org/apache/calcite/util/BitSets.java
+++ b/core/src/main/java/org/apache/calcite/util/BitSets.java
@@ -48,6 +48,24 @@ public final class BitSets {
}
/**
+ * 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.
@@ -86,6 +104,10 @@ public final class BitSets {
};
}
+ public static Iterable<Integer> toIter(final ImmutableBitSet bitSet) {
+ return bitSet;
+ }
+
/**
* Converts a bitset to a list.
*
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java b/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
index 8ad1742..20ecfa5 100644
--- a/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
+++ b/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
@@ -63,7 +63,6 @@ import java.lang.reflect.Method;
import java.sql.ResultSet;
import java.sql.Time;
import java.sql.Timestamp;
-import java.util.BitSet;
import java.util.Calendar;
import java.util.Collection;
import java.util.Collections;
@@ -265,14 +264,15 @@ public enum BuiltInMethod {
ELEMENT(SqlFunctions.class, "element", List.class),
SELECTIVITY(Selectivity.class, "getSelectivity", RexNode.class),
UNIQUE_KEYS(UniqueKeys.class, "getUniqueKeys", boolean.class),
- COLUMN_UNIQUENESS(ColumnUniqueness.class, "areColumnsUnique", BitSet.class,
- boolean.class),
+ COLUMN_UNIQUENESS(ColumnUniqueness.class, "areColumnsUnique",
+ ImmutableBitSet.class, boolean.class),
ROW_COUNT(RowCount.class, "getRowCount"),
DISTINCT_ROW_COUNT(DistinctRowCount.class, "getDistinctRowCount",
- BitSet.class, RexNode.class),
+ ImmutableBitSet.class, RexNode.class),
PERCENTAGE_ORIGINAL_ROWS(PercentageOriginalRows.class,
"getPercentageOriginalRows"),
- POPULATION_SIZE(PopulationSize.class, "getPopulationSize", BitSet.class),
+ POPULATION_SIZE(PopulationSize.class, "getPopulationSize",
+ ImmutableBitSet.class),
COLUMN_ORIGIN(ColumnOrigin.class, "getColumnOrigins", int.class),
CUMULATIVE_COST(CumulativeCost.class, "getCumulativeCost"),
NON_CUMULATIVE_COST(NonCumulativeCost.class, "getNonCumulativeCost"),
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/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
new file mode 100644
index 0000000..a757dd5
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
@@ -0,0 +1,882 @@
+/*
+ * 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 org.apache.calcite.runtime.Utilities;
+
+import com.google.common.base.Function;
+import com.google.common.collect.Maps;
+
+import java.io.Serializable;
+import java.util.AbstractList;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.SortedMap;
+
+/**
+ * An immutable list of bits.
+ */
+public class ImmutableBitSet
+ implements Iterable<Integer>, Serializable, Comparable<ImmutableBitSet> {
+ /** Compares bit sets topologically, so that enclosing bit sets come first,
+ * using natural ordering to break ties. */
+ public static final Comparator<ImmutableBitSet> COMPARATOR =
+ new Comparator<ImmutableBitSet>() {
+ public int compare(ImmutableBitSet o1, ImmutableBitSet o2) {
+ if (o1.equals(o2)) {
+ return 0;
+ }
+ if (o1.contains(o2)) {
+ return -1;
+ }
+ if (o2.contains(o1)) {
+ return 1;
+ }
+ return o1.compareTo(o2);
+ }
+ };
+
+ // BitSets are packed into arrays of "words." Currently a word is
+ // a long, which consists of 64 bits, requiring 6 address bits.
+ // The choice of word size is determined purely by performance concerns.
+ private static final int ADDRESS_BITS_PER_WORD = 6;
+ private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
+
+ /* Used to shift left or right for a partial word mask */
+ private static final long WORD_MASK = 0xffffffffffffffffL;
+
+ private static final long[] EMPTY_LONGS = new long[0];
+
+ private static final ImmutableBitSet EMPTY =
+ new ImmutableBitSet(EMPTY_LONGS);
+
+ public static final Function<? super BitSet, ImmutableBitSet> FROM_BIT_SET =
+ new Function<BitSet, ImmutableBitSet>() {
+ public ImmutableBitSet apply(BitSet input) {
+ return ImmutableBitSet.of(BitSets.toIter(input));
+ }
+ };
+
+ private final long[] words;
+
+ /** Private constructor. Does not copy the array. */
+ private ImmutableBitSet(long[] words) {
+ this.words = words;
+ assert words.length == 0
+ ? words == EMPTY_LONGS
+ : words[words.length - 1] != 0L;
+ }
+
+ /** Creates an ImmutableBitSet with no bits. */
+ public static ImmutableBitSet of() {
+ return EMPTY;
+ }
+
+ public static ImmutableBitSet of(int... bits) {
+ int max = -1;
+ for (int bit : bits) {
+ max = Math.max(bit, max);
+ }
+ if (max == -1) {
+ return EMPTY;
+ }
+ long[] words = new long[wordIndex(max) + 1];
+ for (int bit : bits) {
+ int wordIndex = wordIndex(bit);
+ words[wordIndex] |= 1L << bit;
+ }
+ return new ImmutableBitSet(words);
+ }
+
+ public static ImmutableBitSet of(Iterable<Integer> bits) {
+ if (bits instanceof ImmutableBitSet) {
+ return (ImmutableBitSet) bits;
+ }
+ int max = -1;
+ for (int bit : bits) {
+ max = Math.max(bit, max);
+ }
+ if (max == -1) {
+ return EMPTY;
+ }
+ long[] words = new long[wordIndex(max) + 1];
+ for (int bit : bits) {
+ int wordIndex = wordIndex(bit);
+ words[wordIndex] |= 1L << bit;
+ }
+ return new ImmutableBitSet(words);
+ }
+
+ /**
+ * Creates an ImmutableBitSet with given bits set.
+ *
+ * <p>For example, <code>of(ImmutableIntList.of(0, 3))</code> returns a bit
+ * set with bits {0, 3} set.
+ *
+ * @param bits Collection of bits to set
+ * @return Bit set
+ */
+ public static ImmutableBitSet of(ImmutableIntList bits) {
+ return builder().addAll(bits).build();
+ }
+
+ /**
+ * Creates an ImmutableBitSet 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 ImmutableBitSet range(int fromIndex, int toIndex) {
+ if (fromIndex > toIndex) {
+ throw new IllegalArgumentException();
+ }
+ if (toIndex < 0) {
+ throw new IllegalArgumentException();
+ }
+ if (fromIndex == toIndex) {
+ return EMPTY;
+ }
+ int startWordIndex = wordIndex(fromIndex);
+ int endWordIndex = wordIndex(toIndex - 1);
+ long[] words = new long[endWordIndex + 1];
+
+ long firstWordMask = WORD_MASK << fromIndex;
+ long lastWordMask = WORD_MASK >>> -toIndex;
+ if (startWordIndex == endWordIndex) {
+ // One word
+ words[startWordIndex] |= firstWordMask & lastWordMask;
+ } else {
+ // First word, middle words, last word
+ words[startWordIndex] |= firstWordMask;
+ for (int i = startWordIndex + 1; i < endWordIndex; i++) {
+ words[i] = WORD_MASK;
+ }
+ words[endWordIndex] |= lastWordMask;
+ }
+ return new ImmutableBitSet(words);
+ }
+
+ /** Creates an ImmutableBitSet with bits between 0 and {@code toIndex} set. */
+ public static ImmutableBitSet range(int toIndex) {
+ return range(0, toIndex);
+ }
+
+ /**
+ * Given a bit index, return word index containing it.
+ */
+ private static int wordIndex(int bitIndex) {
+ return bitIndex >> ADDRESS_BITS_PER_WORD;
+ }
+
+ /**
+ * Returns the value of the bit with the specified index. The value
+ * is {@code true} if the bit with the index {@code bitIndex}
+ * is currently set in this {@code ImmutableBitSet}; otherwise, the result
+ * is {@code false}.
+ *
+ * @param bitIndex the bit index
+ * @return the value of the bit with the specified index
+ * @throws IndexOutOfBoundsException if the specified index is negative
+ */
+ public boolean get(int bitIndex) {
+ if (bitIndex < 0) {
+ throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
+ }
+ int wordIndex = wordIndex(bitIndex);
+ return (wordIndex < words.length)
+ && ((words[wordIndex] & (1L << bitIndex)) != 0);
+ }
+
+ /**
+ * Returns a string representation of this bit set. For every index
+ * for which this {@code 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.
+ *
+ * <p>Example:
+ * <pre>
+ * BitSet drPepper = new BitSet();</pre>
+ * Now {@code drPepper.toString()} returns "{@code {}}".
+ * <pre>
+ * drPepper.set(2);</pre>
+ * Now {@code drPepper.toString()} returns "{@code {2}}".
+ * <pre>
+ * drPepper.set(4);
+ * drPepper.set(10);</pre>
+ * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
+ *
+ * @return a string representation of this bit set
+ */
+ public String toString() {
+ int numBits = words.length * BITS_PER_WORD;
+ StringBuilder b = new StringBuilder(6 * numBits + 2);
+ b.append('{');
+
+ int i = nextSetBit(0);
+ if (i != -1) {
+ b.append(i);
+ for (i = nextSetBit(i + 1); i >= 0; i = nextSetBit(i + 1)) {
+ int endOfRun = nextClearBit(i);
+ do { b.append(", ").append(i); }
+ while (++i < endOfRun);
+ }
+ }
+
+ b.append('}');
+ return b.toString();
+ }
+
+ /**
+ * Returns true if the specified {@code ImmutableBitSet} has any bits set to
+ * {@code true} that are also set to {@code true} in this
+ * {@code ImmutableBitSet}.
+ *
+ * @param set {@code ImmutableBitSet} to intersect with
+ * @return boolean indicating whether this {@code ImmutableBitSet} intersects
+ * the specified {@code ImmutableBitSet}
+ */
+ public boolean intersects(ImmutableBitSet set) {
+ for (int i = Math.min(words.length, set.words.length) - 1; i >= 0; i--) {
+ if ((words[i] & set.words[i]) != 0) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /** Returns the number of bits set to {@code true} in this
+ * {@code ImmutableBitSet}. */
+ public int cardinality() {
+ return countBits(words);
+ }
+
+ private static int countBits(long[] words) {
+ int sum = 0;
+ for (long word : words) {
+ sum += Long.bitCount(word);
+ }
+ return sum;
+ }
+
+ /**
+ * Returns the hash code value for this bit set. The hash code
+ * depends only on which bits are set within this {@code ImmutableBitSet}.
+ *
+ * <p>The hash code is defined using the same calculation as
+ * {@link java.util.BitSet#hashCode()}.
+ *
+ * @return the hash code value for this bit set
+ */
+ public int hashCode() {
+ long h = 1234;
+ for (int i = words.length; --i >= 0;) {
+ h ^= words[i] * (i + 1);
+ }
+ return (int) ((h >> 32) ^ h);
+ }
+
+ /**
+ * Returns the number of bits of space actually in use by this
+ * {@code ImmutableBitSet} to represent bit values.
+ * The maximum element in the set is the size - 1st element.
+ *
+ * @return the number of bits currently in this bit set
+ */
+ public int size() {
+ return words.length * BITS_PER_WORD;
+ }
+
+ /**
+ * Compares this object against the specified object.
+ * The result is {@code true} if and only if the argument is
+ * not {@code null} and is a {@code ImmutableBitSet} object that has
+ * exactly the same set of bits set to {@code true} as this bit
+ * set.
+ *
+ * @param obj the object to compare with
+ * @return {@code true} if the objects are the same;
+ * {@code false} otherwise
+ * @see #size()
+ */
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (!(obj instanceof ImmutableBitSet)) {
+ return false;
+ }
+ ImmutableBitSet set = (ImmutableBitSet) obj;
+ return Arrays.equals(words, set.words);
+ }
+
+ /** Compares this ImmutableBitSet with another, using a lexicographic
+ * ordering.
+ *
+ * <p>Bit sets {@code (), (0), (0, 1), (0, 1, 3), (1), (2, 3)} are in sorted
+ * order.</p>
+ */
+ public int compareTo(ImmutableBitSet o) {
+ int i = 0;
+ for (;;) {
+ int n0 = nextSetBit(i);
+ int n1 = o.nextSetBit(i);
+ int c = Utilities.compare(n0, n1);
+ if (c != 0 || n0 < 0) {
+ return c;
+ }
+ i = n0 + 1;
+ }
+ }
+
+ /**
+ * Returns the index of the first bit that is set to {@code true}
+ * that occurs on or after the specified starting index. If no such
+ * bit exists then {@code -1} is returned.
+ *
+ * <p>Based upon {@link BitSet#nextSetBit}.
+ *
+ * @param fromIndex the index to start checking from (inclusive)
+ * @return the index of the next set bit, or {@code -1} if there
+ * is no such bit
+ * @throws IndexOutOfBoundsException if the specified index is negative
+ */
+ public int nextSetBit(int fromIndex) {
+ if (fromIndex < 0) {
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+ }
+ int u = wordIndex(fromIndex);
+ if (u >= words.length) {
+ return -1;
+ }
+ long word = words[u] & (WORD_MASK << fromIndex);
+
+ while (true) {
+ if (word != 0) {
+ return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
+ }
+ if (++u == words.length) {
+ return -1;
+ }
+ word = words[u];
+ }
+ }
+
+ /**
+ * Returns the index of the first bit that is set to {@code false}
+ * that occurs on or after the specified starting index.
+ *
+ * @param fromIndex the index to start checking from (inclusive)
+ * @return the index of the next clear bit
+ * @throws IndexOutOfBoundsException if the specified index is negative
+ */
+ public int nextClearBit(int fromIndex) {
+ if (fromIndex < 0) {
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+ }
+ int u = wordIndex(fromIndex);
+ if (u >= words.length) {
+ return fromIndex;
+ }
+ long word = ~words[u] & (WORD_MASK << fromIndex);
+
+ while (true) {
+ if (word != 0) {
+ return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
+ }
+ if (++u == words.length) {
+ return words.length * BITS_PER_WORD;
+ }
+ word = ~words[u];
+ }
+ }
+
+ /**
+ * Returns the index of the nearest bit that is set to {@code false}
+ * that occurs on or before the specified starting index.
+ * If no such bit exists, or if {@code -1} is given as the
+ * starting index, then {@code -1} is returned.
+ *
+ * @param fromIndex the index to start checking from (inclusive)
+ * @return the index of the previous clear bit, or {@code -1} if there
+ * is no such bit
+ * @throws IndexOutOfBoundsException if the specified index is less
+ * than {@code -1}
+ */
+ public int previousClearBit(int fromIndex) {
+ if (fromIndex < 0) {
+ if (fromIndex == -1) {
+ return -1;
+ }
+ throw new IndexOutOfBoundsException("fromIndex < -1: " + fromIndex);
+ }
+
+ int u = wordIndex(fromIndex);
+ if (u >= words.length) {
+ return fromIndex;
+ }
+ long word = ~words[u] & (WORD_MASK >>> -(fromIndex + 1));
+
+ while (true) {
+ if (word != 0) {
+ return (u + 1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
+ }
+ if (u-- == 0) {
+ return -1;
+ }
+ word = ~words[u];
+ }
+ }
+
+ public Iterator<Integer> iterator() {
+ return new Iterator<Integer>() {
+ int i = nextSetBit(0);
+
+ public boolean hasNext() {
+ return i >= 0;
+ }
+
+ public Integer next() {
+ int prev = i;
+ i = nextSetBit(i + 1);
+ return prev;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
+
+ /** Converts this bit set to a list. */
+ public IntList toList() {
+ final IntList list = new IntList();
+ for (int i = nextSetBit(0); i >= 0; i = nextSetBit(i + 1)) {
+ list.add(i);
+ }
+ return list;
+ }
+
+ /** Creates a view onto this bit set as a list of integers.
+ *
+ * <p>The {@code cardinality} and {@code get} methods are both O(n), but
+ * the iterator is efficient. The list is memory efficient, and the CPU cost
+ * breaks even (versus {@link #toList}) if you intend to scan it only once. */
+ public List<Integer> asList() {
+ return new AbstractList<Integer>() {
+ @Override public Integer get(int index) {
+ return nth(index);
+ }
+
+ @Override public int size() {
+ return cardinality();
+ }
+
+ @Override public Iterator<Integer> iterator() {
+ return ImmutableBitSet.this.iterator();
+ }
+ };
+ }
+
+ /**
+ * Converts this bit set to an array.
+ *
+ * @return Array of set bits
+ */
+ public int[] toArray() {
+ final int[] integers = new int[cardinality()];
+ int j = 0;
+ for (int i = nextSetBit(0); i >= 0; i = nextSetBit(i + 1)) {
+ integers[j++] = i;
+ }
+ return integers;
+ }
+
+ /** Returns the union of this bit set with another. */
+ public ImmutableBitSet union(ImmutableBitSet other) {
+ return builder(this)
+ .addAll(other)
+ .build();
+ }
+
+ /** Returns the union of a number of bit sets. */
+ public static ImmutableBitSet union(
+ Iterable<? extends ImmutableBitSet> sets) {
+ final Builder builder = builder();
+ for (ImmutableBitSet set : sets) {
+ builder.addAll(set);
+ }
+ return builder.build();
+ }
+
+ /** Returns a bit set with all the bits in this set that are not in
+ * another.
+ *
+ * @see BitSet#andNot(java.util.BitSet) */
+ public ImmutableBitSet except(ImmutableBitSet that) {
+ final Builder builder = builder(this);
+ builder.removeAll(that);
+ return builder.build(this);
+ }
+
+ /** Returns a bit set with all the bits set in both this set and in
+ * another.
+ *
+ * @see BitSet#and */
+ public ImmutableBitSet intersect(ImmutableBitSet that) {
+ final Builder builder = builder(this);
+ builder.intersect(that);
+ return builder.build(this);
+ }
+
+ /**
+ * 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 set1 Bitmap to be checked
+ *
+ * @return Whether all bits in set1 are set in set0
+ */
+ public boolean contains(ImmutableBitSet set1) {
+ for (int i = set1.nextSetBit(0); i >= 0; i = set1.nextSetBit(i + 1)) {
+ if (!get(i)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The ordinal of a given bit, or -1 if it is not set.
+ */
+ public int indexOf(int bit) {
+ for (int i = nextSetBit(0), k = 0;; i = nextSetBit(i + 1), ++k) {
+ if (i < 0) {
+ return -1;
+ }
+ if (i == bit) {
+ return k;
+ }
+ }
+ }
+
+ /** 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. */
+ public static SortedMap<Integer, ImmutableBitSet> closure(
+ SortedMap<Integer, ImmutableBitSet> equivalence) {
+ final Closure closure = new Closure(equivalence);
+ return closure.closure;
+ }
+
+ /**
+ * Returns the "logical size" of this {@code ImmutableBitSet}: the index of
+ * the highest set bit in the {@code ImmutableBitSet} plus one. Returns zero
+ * if the {@code ImmutableBitSet} contains no set bits.
+ *
+ * @return the logical size of this {@code ImmutableBitSet}
+ */
+ public int length() {
+ if (words.length == 0) {
+ return 0;
+ }
+ return BITS_PER_WORD * (words.length - 1)
+ + (BITS_PER_WORD - Long.numberOfLeadingZeros(words[words.length - 1]));
+ }
+
+ /**
+ * Returns true if this {@code ImmutableBitSet} contains no bits that are set
+ * to {@code true}.
+ */
+ public boolean isEmpty() {
+ return words.length == 0;
+ }
+
+ public static Builder builder() {
+ return new Builder();
+ }
+
+ public static Builder builder(ImmutableBitSet bitSet) {
+ return new Builder(bitSet);
+ }
+
+ /** Returns the {@code n}th set bit.
+ *
+ * @throws java.lang.IndexOutOfBoundsException if n is less than 0 or greater
+ * than the number of bits set */
+ public int nth(int n) {
+ int start = 0;
+ for (long word : words) {
+ final int bitCount = Long.bitCount(word);
+ if (n < bitCount) {
+ while (word != 0) {
+ if ((word & 1) == 1) {
+ if (n == 0) {
+ return start;
+ }
+ --n;
+ }
+ word >>= 1;
+ ++start;
+ }
+ }
+ start += 64;
+ n -= bitCount;
+ }
+ throw new IndexOutOfBoundsException("index out of range: " + n);
+ }
+
+ /** Returns a bit set the same as this but with a given bit cleared. */
+ public ImmutableBitSet clear(int i) {
+ return except(ImmutableBitSet.of(i));
+ }
+
+ /** Returns a {@link BitSet} that has the same contents as this
+ * {@code ImmutableBitSet}. */
+ public BitSet toBitSet() {
+ return BitSets.of(this);
+ }
+
+ /**
+ * Setup equivalence Sets for each position. If i & 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 SortedMap<Integer, ImmutableBitSet> equivalence;
+ private final SortedMap<Integer, ImmutableBitSet> closure =
+ Maps.newTreeMap();
+
+ public Closure(SortedMap<Integer, ImmutableBitSet> equivalence) {
+ this.equivalence = equivalence;
+ final ImmutableIntList keys =
+ ImmutableIntList.copyOf(equivalence.keySet());
+ for (int pos : keys) {
+ computeClosure(pos);
+ }
+ }
+
+ private ImmutableBitSet computeClosure(int pos) {
+ ImmutableBitSet o = closure.get(pos);
+ if (o != null) {
+ return o;
+ }
+ final ImmutableBitSet b = equivalence.get(pos);
+ o = b;
+ int i = b.nextSetBit(pos + 1);
+ for (; i >= 0; i = b.nextSetBit(i + 1)) {
+ o = o.union(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;
+ }
+ }
+
+ /** Builder. */
+ public static class Builder {
+ private long[] words;
+
+ public Builder(ImmutableBitSet bitSet) {
+ words = bitSet.words.clone();
+ }
+
+ public Builder() {
+ words = EMPTY_LONGS;
+ }
+
+ /** Builds an ImmutableBitSet from the contents of this Builder.
+ *
+ * <p>After calling this method, the Builder cannot be used again. */
+ public ImmutableBitSet build() {
+ if (words.length == 0) {
+ return EMPTY;
+ }
+ long[] words = this.words;
+ this.words = null; // prevent re-use of builder
+ return new ImmutableBitSet(words);
+ }
+
+ /** Builds an ImmutableBitSet from the contents of this Builder, using
+ * an existing ImmutableBitSet if it happens to have the same contents.
+ *
+ * <p>Supplying the existing bit set if useful for set operations,
+ * where there is a significant chance that the original bit set is
+ * unchanged. We save memory because we use the same copy. For example:
+ *
+ * <blockquote><pre>
+ * ImmutableBitSet primeNumbers;
+ * ImmutableBitSet hundreds = ImmutableBitSet.of(100, 200, 300);
+ * return primeNumbers.except(hundreds);</pre></blockquote>
+ *
+ * <p>After calling this method, the Builder cannot be used again. */
+ public ImmutableBitSet build(ImmutableBitSet bitSet) {
+ if (wouldEqual(bitSet)) {
+ return bitSet;
+ }
+ return build();
+ }
+
+ public Builder set(int bit) {
+ if (words == null) {
+ throw new IllegalArgumentException("can only use builder once");
+ }
+ int wordIndex = wordIndex(bit);
+ if (wordIndex >= words.length) {
+ words = Arrays.copyOf(words, wordIndex + 1);
+ }
+ words[wordIndex] |= 1L << bit;
+ return this;
+ }
+
+ private void trim(int wordCount) {
+ while (wordCount > 0 && words[wordCount - 1] == 0L) {
+ --wordCount;
+ }
+ if (wordCount == words.length) {
+ return;
+ }
+ if (wordCount == 0) {
+ words = EMPTY_LONGS;
+ } else {
+ words = Arrays.copyOfRange(words, 0, wordCount);
+ }
+ }
+
+ public Builder clear(int bit) {
+ int wordIndex = wordIndex(bit);
+ if (wordIndex < words.length) {
+ words[wordIndex] &= ~(1L << bit);
+ trim(words.length);
+ }
+ return this;
+ }
+
+ /** Returns whether the bit set that would be created by this Builder would
+ * equal a given bit set. */
+ public boolean wouldEqual(ImmutableBitSet bitSet) {
+ if (words == null) {
+ throw new IllegalArgumentException("can only use builder once");
+ }
+ return Arrays.equals(words, bitSet.words);
+ }
+
+ /** Returns the number of set bits. */
+ public int cardinality() {
+ return countBits(words);
+ }
+
+ /** Sets all bits in a given bit set. */
+ public Builder addAll(ImmutableBitSet bitSet) {
+ for (Integer bit : bitSet) {
+ set(bit);
+ }
+ return this;
+ }
+
+ /** Sets all bits in a given list of bits. */
+ public Builder addAll(Iterable<Integer> integers) {
+ for (Integer integer : integers) {
+ set(integer);
+ }
+ return this;
+ }
+
+ /** Sets all bits in a given list of {@code int}s. */
+ public Builder addAll(ImmutableIntList integers) {
+ //noinspection ForLoopReplaceableByForEach
+ for (int i = 0; i < integers.size(); i++) {
+ set(integers.get(i));
+ }
+ return this;
+ }
+
+ /** Clears all bits in a given bit set. */
+ public Builder removeAll(ImmutableBitSet bitSet) {
+ for (Integer bit : bitSet) {
+ clear(bit);
+ }
+ return this;
+ }
+
+ /** Sets a range of bits, from {@code from} to {@code to} - 1. */
+ public Builder set(int fromIndex, int toIndex) {
+ if (fromIndex > toIndex) {
+ throw new IllegalArgumentException();
+ }
+ if (toIndex < 0) {
+ throw new IllegalArgumentException();
+ }
+ if (fromIndex < toIndex) {
+ // Increase capacity if necessary
+ int startWordIndex = wordIndex(fromIndex);
+ int endWordIndex = wordIndex(toIndex - 1);
+ if (endWordIndex >= words.length) {
+ words = Arrays.copyOf(words, endWordIndex + 1);
+ }
+
+ long firstWordMask = WORD_MASK << fromIndex;
+ long lastWordMask = WORD_MASK >>> -toIndex;
+ if (startWordIndex == endWordIndex) {
+ // One word
+ words[startWordIndex] |= firstWordMask & lastWordMask;
+ } else {
+ // First word, middle words, last word
+ words[startWordIndex] |= firstWordMask;
+ for (int i = startWordIndex + 1; i < endWordIndex; i++) {
+ words[i] = WORD_MASK;
+ }
+ words[endWordIndex] |= lastWordMask;
+ }
+ }
+ return this;
+ }
+
+ public boolean isEmpty() {
+ return words.length == 0;
+ }
+
+ public void intersect(ImmutableBitSet that) {
+ int x = Math.min(words.length, that.words.length);
+ for (int i = 0; i < x; i++) {
+ words[i] &= that.words[i];
+ }
+ trim(x);
+ }
+ }
+}
+
+// End ImmutableBitSet.java
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/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 8d9733b..8c16163 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
@@ -17,6 +17,7 @@
package org.apache.calcite.util.mapping;
import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.IntList;
import org.apache.calcite.util.Permutation;
import org.apache.calcite.util.Util;
@@ -188,6 +189,28 @@ public abstract class Mappings {
}
/**
+ * Applies a mapping to an {@code ImmutableBitSet}.
+ *
+ * <p>If the mapping does not affect the bit set, returns the original.
+ * Never changes the original.
+ *
+ * @param mapping Mapping
+ * @param bitSet Bit set
+ * @return Bit set with mapping applied
+ */
+ public static ImmutableBitSet apply(Mapping mapping, ImmutableBitSet bitSet) {
+ final ImmutableBitSet.Builder builder = ImmutableBitSet.builder();
+ for (int source : bitSet) {
+ final int target = mapping.getTarget(source);
+ builder.set(target);
+ }
+ if (builder.wouldEqual(bitSet)) {
+ return bitSet;
+ }
+ return builder.build();
+ }
+
+ /**
* Applies a mapping to a list.
*
* @param mapping Mapping
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java b/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java
index 5ef1877..6dc6aa4 100644
--- a/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java
+++ b/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java
@@ -32,7 +32,7 @@ import org.apache.calcite.sql.fun.SqlStdOperatorTable;
import org.apache.calcite.sql.type.SqlTypeName;
import org.apache.calcite.test.JdbcTest;
import org.apache.calcite.tools.Frameworks;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Util;
import com.google.common.collect.ImmutableList;
@@ -138,7 +138,7 @@ public class RelWriterTest {
final RelDataType bigIntType =
cluster.getTypeFactory().createSqlType(SqlTypeName.BIGINT);
LogicalAggregate aggregate =
- new LogicalAggregate(cluster, filter, BitSets.of(0),
+ new LogicalAggregate(cluster, filter, ImmutableBitSet.of(0),
ImmutableList.of(
new AggregateCall(SqlStdOperatorTable.COUNT,
true, ImmutableList.of(1), bigIntType, "c"),
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
index 3a3ec53..081ac93 100644
--- a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
+++ b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
@@ -33,6 +33,7 @@ import org.apache.calcite.tools.FrameworksTest;
import org.apache.calcite.tools.PlannerTest;
import org.apache.calcite.util.BitSetsTest;
import org.apache.calcite.util.ChunkListTest;
+import org.apache.calcite.util.ImmutableBitSetTest;
import org.apache.calcite.util.PartiallyOrderedSetTest;
import org.apache.calcite.util.PermutationTestCase;
import org.apache.calcite.util.ReflectVisitorTest;
@@ -57,6 +58,7 @@ import org.junit.runners.Suite;
// very fast tests (under 0.1s)
ArrayTableTest.class,
BitSetsTest.class,
+ ImmutableBitSetTest.class,
DirectedGraphTest.class,
ReflectVisitorTest.class,
RelOptUtilTest.class,
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java b/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java
index 7abe734..f915e1b 100644
--- a/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java
+++ b/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java
@@ -41,6 +41,7 @@ import org.apache.calcite.sql.validate.SqlMonikerType;
import org.apache.calcite.sql.validate.SqlMonotonicity;
import org.apache.calcite.sql.validate.SqlValidatorCatalogReader;
import org.apache.calcite.sql.validate.SqlValidatorUtil;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Pair;
import org.apache.calcite.util.Util;
@@ -49,7 +50,6 @@ import com.google.common.collect.Ordering;
import java.util.ArrayList;
import java.util.Arrays;
-import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
@@ -401,7 +401,7 @@ public class MockCatalogReader implements Prepare.CatalogReader {
return collationList;
}
- public boolean isKey(BitSet columns) {
+ public boolean isKey(ImmutableBitSet columns) {
return false;
}
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
index 41caea0..67b30de 100644
--- a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
@@ -30,6 +30,7 @@ import org.apache.calcite.rel.metadata.ReflectiveRelMetadataProvider;
import org.apache.calcite.rel.metadata.RelColumnOrigin;
import org.apache.calcite.rel.metadata.RelMetadataProvider;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.util.ImmutableBitSet;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
@@ -41,7 +42,6 @@ import org.junit.Test;
import java.lang.reflect.Method;
import java.util.ArrayList;
-import java.util.BitSet;
import java.util.List;
import java.util.Set;
@@ -539,7 +539,7 @@ public class RelMetadataTest extends SqlToRelTestBase {
@Test public void testDistinctRowCountTable() {
// no unique key information is available so return null
RelNode rel = convertSql("select * from emp where deptno = 10");
- BitSet groupKey = new BitSet();
+ ImmutableBitSet groupKey = ImmutableBitSet.of();
Double result =
RelMetadataQuery.getDistinctRowCount(
rel, groupKey, null);
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
index d1d0bae..aaa6b01 100644
--- a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
@@ -34,7 +34,7 @@ import org.apache.calcite.rex.RexProgramBuilder;
import org.apache.calcite.rex.RexUtil;
import org.apache.calcite.sql.fun.SqlStdOperatorTable;
import org.apache.calcite.sql.type.SqlTypeName;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.TestUtil;
import org.apache.calcite.util.Util;
@@ -46,7 +46,6 @@ import org.junit.Test;
import java.math.BigDecimal;
import java.util.Arrays;
-import java.util.BitSet;
import java.util.List;
import static org.hamcrest.CoreMatchers.equalTo;
@@ -322,7 +321,7 @@ public class RexProgramTest {
return builder;
}
- static boolean strongIf(RexNode e, BitSet b) {
+ static boolean strongIf(RexNode e, ImmutableBitSet b) {
return Strong.is(e, b);
}
@@ -330,11 +329,11 @@ public class RexProgramTest {
@Test public void testStrong() {
final RelDataType intType = typeFactory.createSqlType(SqlTypeName.INTEGER);
- final BitSet c = BitSets.of();
- final BitSet c0 = BitSets.of(0);
- final BitSet c1 = BitSets.of(1);
- final BitSet c01 = BitSets.of(0, 1);
- final BitSet c13 = BitSets.of(1, 3);
+ final ImmutableBitSet c = ImmutableBitSet.of();
+ final ImmutableBitSet c0 = ImmutableBitSet.of(0);
+ final ImmutableBitSet c1 = ImmutableBitSet.of(1);
+ final ImmutableBitSet c01 = ImmutableBitSet.of(0, 1);
+ final ImmutableBitSet c13 = ImmutableBitSet.of(1, 3);
// input ref
final RexInputRef aRef = rexBuilder.makeInputRef(intType, 0);
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java b/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java
index ab2cd05..1d88316 100644
--- a/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java
+++ b/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java
@@ -47,6 +47,7 @@ import org.apache.calcite.sql.validate.SqlValidatorTable;
import org.apache.calcite.sql2rel.RelFieldTrimmer;
import org.apache.calcite.sql2rel.SqlToRelConverter;
import org.apache.calcite.sql2rel.StandardConvertletTable;
+import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Util;
import com.google.common.base.Function;
@@ -54,7 +55,6 @@ import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import java.util.ArrayList;
-import java.util.BitSet;
import java.util.List;
import static org.junit.Assert.assertEquals;
@@ -353,7 +353,7 @@ public abstract class SqlToRelTestBase {
return collationList;
}
- public boolean isKey(BitSet columns) {
+ public boolean isKey(ImmutableBitSet columns) {
return false;
}
@@ -406,7 +406,7 @@ public abstract class SqlToRelTestBase {
return parent.getCollationList();
}
- public boolean isKey(BitSet columns) {
+ public boolean isKey(ImmutableBitSet columns) {
return parent.isKey(columns);
}
}