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 2016/04/22 10:07:31 UTC
[02/13] calcite git commit: Add class ConsList
Add class ConsList
Project: http://git-wip-us.apache.org/repos/asf/calcite/repo
Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/80f8922b
Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/80f8922b
Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/80f8922b
Branch: refs/heads/master
Commit: 80f8922bd5ccf77d79b488f5eb8ff08d51d871da
Parents: 578fb2c
Author: Julian Hyde <jh...@apache.org>
Authored: Tue Apr 19 11:10:40 2016 -0700
Committer: Julian Hyde <jh...@apache.org>
Committed: Tue Apr 19 11:11:12 2016 -0700
----------------------------------------------------------------------
.../calcite/runtime/AbstractImmutableList.java | 107 ++++++++++++++
.../org/apache/calcite/runtime/ConsList.java | 146 +++++++++++++++++++
.../org/apache/calcite/runtime/FlatLists.java | 78 +---------
.../org/apache/calcite/util/graph/Graphs.java | 15 +-
.../java/org/apache/calcite/util/UtilTest.java | 107 ++++++++++++++
.../calcite/adapter/mongodb/MongoTable.java | 4 +-
6 files changed, 371 insertions(+), 86 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/calcite/blob/80f8922b/core/src/main/java/org/apache/calcite/runtime/AbstractImmutableList.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/runtime/AbstractImmutableList.java b/core/src/main/java/org/apache/calcite/runtime/AbstractImmutableList.java
new file mode 100644
index 0000000..ff7b48e
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/runtime/AbstractImmutableList.java
@@ -0,0 +1,107 @@
+/*
+ * 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.runtime;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import javax.annotation.Nonnull;
+
+/**
+ * Base class for lists whose contents are constant after creation.
+ *
+ * @param <E> Element type
+ */
+abstract class AbstractImmutableList<E> implements List<E> {
+ protected abstract List<E> toList();
+
+ @Nonnull public Iterator<E> iterator() {
+ return toList().iterator();
+ }
+
+ @Nonnull public ListIterator<E> listIterator() {
+ return toList().listIterator();
+ }
+
+ public boolean isEmpty() {
+ return false;
+ }
+
+ public boolean add(E t) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean addAll(@Nonnull Collection<? extends E> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean addAll(int index, @Nonnull Collection<? extends E> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean removeAll(@Nonnull Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean retainAll(@Nonnull Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+
+ public E set(int index, E element) {
+ throw new UnsupportedOperationException();
+ }
+
+ public void add(int index, E element) {
+ throw new UnsupportedOperationException();
+ }
+
+ public E remove(int index) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Nonnull public ListIterator<E> listIterator(int index) {
+ return toList().listIterator(index);
+ }
+
+ @Nonnull public List<E> subList(int fromIndex, int toIndex) {
+ return toList().subList(fromIndex, toIndex);
+ }
+
+ public boolean contains(Object o) {
+ return indexOf(o) >= 0;
+ }
+
+ public boolean containsAll(@Nonnull Collection<?> c) {
+ for (Object o : c) {
+ if (!contains(o)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public boolean remove(Object o) {
+ throw new UnsupportedOperationException();
+ }
+}
+
+// End AbstractImmutableList.java
http://git-wip-us.apache.org/repos/asf/calcite/blob/80f8922b/core/src/main/java/org/apache/calcite/runtime/ConsList.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/runtime/ConsList.java b/core/src/main/java/org/apache/calcite/runtime/ConsList.java
new file mode 100644
index 0000000..a30af84
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/runtime/ConsList.java
@@ -0,0 +1,146 @@
+/*
+ * 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.runtime;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import javax.annotation.Nonnull;
+
+/**
+ * List that consists of a head element and an immutable non-empty list.
+ *
+ * @param <E> Element type
+ */
+public class ConsList<E> extends AbstractImmutableList<E> {
+ private final E first;
+ private final List<E> rest;
+
+ /** Creates a ConsList.
+ * It consists of an element pre-pended to another list.
+ * If the other list is mutable, creates an immutable copy. */
+ public static <E> List<E> of(E first, List<E> rest) {
+ if (rest instanceof ConsList
+ || rest instanceof ImmutableList
+ && !rest.isEmpty()) {
+ return new ConsList<>(first, rest);
+ } else {
+ return ImmutableList.<E>builder().add(first).addAll(rest).build();
+ }
+ }
+
+ private ConsList(E first, List<E> rest) {
+ this.first = first;
+ this.rest = rest;
+ }
+
+ public E get(int index) {
+ for (ConsList<E> c = this;; c = (ConsList<E>) c.rest) {
+ if (index == 0) {
+ return c.first;
+ }
+ --index;
+ if (!(c.rest instanceof ConsList)) {
+ return c.rest.get(index);
+ }
+ }
+ }
+
+ public int size() {
+ int s = 1;
+ for (ConsList c = this;; c = (ConsList) c.rest, ++s) {
+ if (!(c.rest instanceof ConsList)) {
+ return s + c.rest.size();
+ }
+ }
+ }
+
+ @Override public int hashCode() {
+ return toList().hashCode();
+ }
+
+ @Override public boolean equals(Object o) {
+ return o == this
+ || o instanceof List
+ && toList().equals(o);
+ }
+
+ @Override public String toString() {
+ return toList().toString();
+ }
+
+ protected final List<E> toList() {
+ final List<E> list = new ArrayList<>();
+ for (ConsList<E> c = this;; c = (ConsList<E>) c.rest) {
+ list.add(c.first);
+ if (!(c.rest instanceof ConsList)) {
+ list.addAll(c.rest);
+ return list;
+ }
+ }
+ }
+
+ @Override @Nonnull public ListIterator<E> listIterator() {
+ return toList().listIterator();
+ }
+
+ @Override @Nonnull public Iterator<E> iterator() {
+ return toList().iterator();
+ }
+
+ @Override @Nonnull public ListIterator<E> listIterator(int index) {
+ return toList().listIterator(index);
+ }
+
+ @Nonnull public Object[] toArray() {
+ return toList().toArray();
+ }
+
+ @Nonnull public <T> T[] toArray(@Nonnull T[] a) {
+ final int s = size();
+ if (s > a.length) {
+ a = Arrays.copyOf(a, s);
+ } else if (s < a.length) {
+ a[s] = null;
+ }
+ int i = 0;
+ for (ConsList c = this;; c = (ConsList) c.rest) {
+ //noinspection unchecked
+ a[i++] = (T) c.first;
+ if (!(c.rest instanceof ConsList)) {
+ Object[] a2 = c.rest.toArray();
+ //noinspection SuspiciousSystemArraycopy
+ System.arraycopy(a2, 0, a, i, a2.length);
+ return a;
+ }
+ }
+ }
+
+ public int indexOf(Object o) {
+ return toList().indexOf(o);
+ }
+
+ public int lastIndexOf(Object o) {
+ return toList().lastIndexOf(o);
+ }
+}
+
+// End ConsList.java
http://git-wip-us.apache.org/repos/asf/calcite/blob/80f8922b/core/src/main/java/org/apache/calcite/runtime/FlatLists.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/runtime/FlatLists.java b/core/src/main/java/org/apache/calcite/runtime/FlatLists.java
index bf0c4f2..5e8d046 100644
--- a/core/src/main/java/org/apache/calcite/runtime/FlatLists.java
+++ b/core/src/main/java/org/apache/calcite/runtime/FlatLists.java
@@ -20,11 +20,9 @@ import org.apache.calcite.util.ImmutableNullableList;
import java.util.AbstractList;
import java.util.Arrays;
-import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
-import java.util.ListIterator;
import java.util.Objects;
import java.util.RandomAccess;
@@ -232,84 +230,12 @@ public class FlatLists {
/** Base class for flat lists. */
public abstract static class AbstractFlatList<T>
- implements List<T>, RandomAccess {
- protected final List<T> asArrayList() {
+ extends AbstractImmutableList<T> implements RandomAccess {
+ protected final List<T> toList() {
//noinspection unchecked
return Arrays.asList((T[]) toArray());
}
- public Iterator<T> iterator() {
- return asArrayList().iterator();
- }
-
- public ListIterator<T> listIterator() {
- return asArrayList().listIterator();
- }
-
- public boolean isEmpty() {
- return false;
- }
-
- public boolean add(T t) {
- throw new UnsupportedOperationException();
- }
-
- public boolean addAll(Collection<? extends T> c) {
- throw new UnsupportedOperationException();
- }
-
- public boolean addAll(int index, Collection<? extends T> c) {
- throw new UnsupportedOperationException();
- }
-
- public boolean removeAll(Collection<?> c) {
- throw new UnsupportedOperationException();
- }
-
- public boolean retainAll(Collection<?> c) {
- throw new UnsupportedOperationException();
- }
-
- public void clear() {
- throw new UnsupportedOperationException();
- }
-
- public T set(int index, T element) {
- throw new UnsupportedOperationException();
- }
-
- public void add(int index, T element) {
- throw new UnsupportedOperationException();
- }
-
- public T remove(int index) {
- throw new UnsupportedOperationException();
- }
-
- public ListIterator<T> listIterator(int index) {
- return asArrayList().listIterator(index);
- }
-
- public List<T> subList(int fromIndex, int toIndex) {
- return asArrayList().subList(fromIndex, toIndex);
- }
-
- public boolean contains(Object o) {
- return indexOf(o) >= 0;
- }
-
- public boolean containsAll(Collection<?> c) {
- for (Object o : c) {
- if (!contains(o)) {
- return false;
- }
- }
- return true;
- }
-
- public boolean remove(Object o) {
- throw new UnsupportedOperationException();
- }
}
/**
http://git-wip-us.apache.org/repos/asf/calcite/blob/80f8922b/core/src/main/java/org/apache/calcite/util/graph/Graphs.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/graph/Graphs.java b/core/src/main/java/org/apache/calcite/util/graph/Graphs.java
index c1b94a6..fd32f22 100644
--- a/core/src/main/java/org/apache/calcite/util/graph/Graphs.java
+++ b/core/src/main/java/org/apache/calcite/util/graph/Graphs.java
@@ -16,6 +16,7 @@
*/
package org.apache.calcite.util.graph;
+import org.apache.calcite.runtime.ConsList;
import org.apache.calcite.util.Pair;
import com.google.common.collect.ImmutableList;
@@ -54,7 +55,7 @@ public class Graphs {
public static <V, E extends DefaultEdge> FrozenGraph<V, E> makeImmutable(
DirectedGraph<V, E> graph) {
DefaultDirectedGraph<V, E> graph1 = (DefaultDirectedGraph<V, E>) graph;
- Map<Pair<V, V>, List<V>> shortestPaths = new HashMap<Pair<V, V>, List<V>>();
+ Map<Pair<V, V>, List<V>> shortestPaths = new HashMap<>();
for (DefaultDirectedGraph.VertexInfo<V, E> arc
: graph1.vertexMap.values()) {
for (E edge : arc.outEdges) {
@@ -78,10 +79,8 @@ public class Graphs {
List<V> arc2Path = shortestPaths.get(edge2);
if ((bestPath == null)
|| (bestPath.size() > (arc2Path.size() + 1))) {
- ImmutableList.Builder<V> newPath = ImmutableList.builder();
- newPath.add(graph1.source(edge));
- newPath.addAll(arc2Path);
- shortestPaths.put(key, newPath.build());
+ shortestPaths.put(key,
+ ConsList.of(graph1.source(edge), arc2Path));
changeCount++;
}
}
@@ -91,7 +90,7 @@ public class Graphs {
break;
}
}
- return new FrozenGraph<V, E>(graph1, shortestPaths);
+ return new FrozenGraph<>(graph1, shortestPaths);
}
/**
@@ -117,7 +116,7 @@ public class Graphs {
* <p>The current implementation is not optimal.</p>
*/
public List<List<V>> getPaths(V from, V to) {
- List<List<V>> list = new ArrayList<List<V>>();
+ List<List<V>> list = new ArrayList<>();
findPaths(from, to, list);
return list;
}
@@ -146,7 +145,7 @@ public class Graphs {
// if (edge != null) {
// list.add(ImmutableList.of(from, to));
// }
- final List<V> prefix = new ArrayList<V>();
+ final List<V> prefix = new ArrayList<>();
prefix.add(from);
findPathsExcluding(from, to, list, new HashSet<V>(), prefix);
}
http://git-wip-us.apache.org/repos/asf/calcite/blob/80f8922b/core/src/test/java/org/apache/calcite/util/UtilTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/util/UtilTest.java b/core/src/test/java/org/apache/calcite/util/UtilTest.java
index 285cbc9..548b538 100644
--- a/core/src/test/java/org/apache/calcite/util/UtilTest.java
+++ b/core/src/test/java/org/apache/calcite/util/UtilTest.java
@@ -22,6 +22,7 @@ import org.apache.calcite.examples.RelBuilderExample;
import org.apache.calcite.linq4j.Ord;
import org.apache.calcite.linq4j.function.Function1;
import org.apache.calcite.linq4j.function.Parameter;
+import org.apache.calcite.runtime.ConsList;
import org.apache.calcite.runtime.FlatLists;
import org.apache.calcite.runtime.Resources;
import org.apache.calcite.runtime.Utilities;
@@ -75,6 +76,8 @@ import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.CoreMatchers.isA;
import static org.hamcrest.CoreMatchers.not;
import static org.hamcrest.CoreMatchers.nullValue;
+import static org.hamcrest.CoreMatchers.sameInstance;
+import static org.hamcrest.CoreMatchers.startsWith;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNull;
@@ -392,6 +395,110 @@ public class UtilTest {
}
}
+ @Test public void testCons() {
+ final List<String> abc0 = Arrays.asList("a", "b", "c");
+
+ final List<String> abc = ConsList.of("a", ImmutableList.of("b", "c"));
+ assertThat(abc.size(), is(3));
+ assertThat(abc, is(abc0));
+
+ final List<String> bc = Lists.newArrayList("b", "c");
+ final List<String> abc2 = ConsList.of("a", bc);
+ assertThat(abc2.size(), is(3));
+ assertThat(abc2, is(abc0));
+ bc.set(0, "z");
+ assertThat(abc2, is(abc0));
+
+ final List<String> bc3 = ConsList.of("b", Collections.singletonList("c"));
+ final List<String> abc3 = ConsList.of("a", bc3);
+ assertThat(abc3.size(), is(3));
+ assertThat(abc3, is(abc0));
+ assertThat(abc3.indexOf("b"), is(1));
+ assertThat(abc3.indexOf("z"), is(-1));
+ assertThat(abc3.lastIndexOf("b"), is(1));
+ assertThat(abc3.lastIndexOf("z"), is(-1));
+ assertThat(abc3.hashCode(), is(abc0.hashCode()));
+
+ assertThat(abc3.get(0), is("a"));
+ assertThat(abc3.get(1), is("b"));
+ assertThat(abc3.get(2), is("c"));
+ try {
+ final String z = abc3.get(3);
+ fail("expected error, got " + z);
+ } catch (IndexOutOfBoundsException e) {
+ // ok
+ }
+ try {
+ final String z = abc3.get(-3);
+ fail("expected error, got " + z);
+ } catch (IndexOutOfBoundsException e) {
+ // ok
+ }
+ try {
+ final String z = abc3.get(30);
+ fail("expected error, got " + z);
+ } catch (IndexOutOfBoundsException e) {
+ // ok
+ }
+
+ final List<String> a = ConsList.of("a", ImmutableList.<String>of());
+ assertThat(a.size(), is(1));
+ assertThat(a, is(Collections.singletonList("a")));
+ }
+
+ @Test public void testConsPerformance() {
+ final int n = 2000000;
+ final int start = 10;
+ List<Integer> list = makeConsList(start, n + start);
+ assertThat(list.size(), is(n));
+ assertThat(list.toString(), startsWith("[10, 11, 12, "));
+ assertThat(list.contains(n / 2 + start), is(true));
+ assertThat(list.contains(n * 2 + start), is(false));
+ assertThat(list.indexOf(n / 2 + start), is(n / 2));
+ assertThat(list.containsAll(Arrays.asList(n - 1, n - 10, n / 2, start)),
+ is(true));
+ long total = 0;
+ for (Integer i : list) {
+ total += i - start;
+ }
+ assertThat(total, is((long) n * (n - 1) / 2));
+
+ final Object[] objects = list.toArray();
+ assertThat(objects.length, is(n));
+ final Integer[] integers = new Integer[n - 1];
+ assertThat(integers.length, is(n - 1));
+ final Integer[] integers2 = list.toArray(integers);
+ assertThat(integers2.length, is(n));
+ assertThat(integers2[0], is(start));
+ assertThat(integers2[integers2.length - 1], is(n + start - 1));
+ final Integer[] integers3 = list.toArray(integers2);
+ assertThat(integers2, sameInstance(integers3));
+ final Integer[] integers4 = new Integer[n + 1];
+ final Integer[] integers5 = list.toArray(integers4);
+ assertThat(integers5, sameInstance(integers4));
+ assertThat(integers5.length, is(n + 1));
+ assertThat(integers5[0], is(start));
+ assertThat(integers5[n - 1], is(n + start - 1));
+ assertThat(integers5[n], nullValue());
+
+ assertThat(list.hashCode(), is(Arrays.hashCode(integers3)));
+ assertThat(list, is(Arrays.asList(integers3)));
+ assertThat(list, is(list));
+ assertThat(Arrays.asList(integers3), is(list));
+ }
+
+ private List<Integer> makeConsList(int start, int end) {
+ List<Integer> list = null;
+ for (int i = end - 1; i >= start; i--) {
+ if (i == end - 1) {
+ list = Collections.singletonList(i);
+ } else {
+ list = ConsList.of(i, list);
+ }
+ }
+ return list;
+ }
+
@Test public void testIterableProperties() {
Properties properties = new Properties();
properties.put("foo", "george");
http://git-wip-us.apache.org/repos/asf/calcite/blob/80f8922b/mongodb/src/main/java/org/apache/calcite/adapter/mongodb/MongoTable.java
----------------------------------------------------------------------
diff --git a/mongodb/src/main/java/org/apache/calcite/adapter/mongodb/MongoTable.java b/mongodb/src/main/java/org/apache/calcite/adapter/mongodb/MongoTable.java
index 78e1898..96ca921 100644
--- a/mongodb/src/main/java/org/apache/calcite/adapter/mongodb/MongoTable.java
+++ b/mongodb/src/main/java/org/apache/calcite/adapter/mongodb/MongoTable.java
@@ -28,6 +28,7 @@ import org.apache.calcite.plan.RelOptTable;
import org.apache.calcite.rel.RelNode;
import org.apache.calcite.rel.type.RelDataType;
import org.apache.calcite.rel.type.RelDataTypeFactory;
+import org.apache.calcite.runtime.ConsList;
import org.apache.calcite.schema.SchemaPlus;
import org.apache.calcite.schema.TranslatableTable;
import org.apache.calcite.schema.impl.AbstractTableQueryable;
@@ -213,8 +214,7 @@ public class MongoTable extends AbstractQueryableTable
*/
private AggregationOutput aggregateOldWay(DBCollection dbCollection,
DBObject first, List<DBObject> rest) {
- return dbCollection.aggregate(first,
- rest.toArray(new DBObject[rest.size()]));
+ return dbCollection.aggregate(ConsList.of(first, rest));
}
/** Implementation of {@link org.apache.calcite.linq4j.Queryable} based on