You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2016/01/19 18:36:58 UTC
incubator-tinkerpop git commit: fixed Order.shuffle so that it
doesn't violate contract. This required some refactoring. A little cleaner,
but I bet we could make it even nicer.
Repository: incubator-tinkerpop
Updated Branches:
refs/heads/TINKERPOP-1089 [created] ed66ee3e0
fixed Order.shuffle so that it doesn't violate contract. This required some refactoring. A little cleaner, but I bet we could make it even nicer.
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/ed66ee3e
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/ed66ee3e
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/ed66ee3e
Branch: refs/heads/TINKERPOP-1089
Commit: ed66ee3e027787a6c95c7ee9d5d1b09c155ed093
Parents: 1670e08
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Tue Jan 19 10:36:56 2016 -0700
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Tue Jan 19 10:36:56 2016 -0700
----------------------------------------------------------------------
.../traversal/step/map/OrderGlobalStep.java | 28 ++++-------
.../traversal/step/map/OrderLocalStep.java | 33 ++++++++-----
.../step/util/ComparatorTraverser.java | 52 ++++++++++++++++++++
.../traversal/traverser/util/TraverserSet.java | 9 +++-
.../util/function/ChainedComparator.java | 28 ++++++++++-
.../traversal/step/map/OrderGlobalStepTest.java | 18 +++++++
.../traversal/step/map/OrderLocalStepTest.java | 18 +++++++
7 files changed, 152 insertions(+), 34 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/ed66ee3e/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
index e7101c2..6b9a2cc 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
@@ -20,17 +20,16 @@ package org.apache.tinkerpop.gremlin.process.traversal.step.map;
import org.apache.tinkerpop.gremlin.process.traversal.Order;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
-import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.step.ComparatorHolder;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.CollectingBarrierStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.ComparatorTraverser;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.TraversalComparator;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
import org.apache.tinkerpop.gremlin.util.function.ChainedComparator;
-import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
@@ -44,6 +43,7 @@ import java.util.stream.Collectors;
public final class OrderGlobalStep<S> extends CollectingBarrierStep<S> implements ComparatorHolder<S>, TraversalParent {
private List<Comparator<S>> comparators = new ArrayList<>();
+ private ChainedComparator chainedComparator = null;
public OrderGlobalStep(final Traversal.Admin traversal) {
super(traversal);
@@ -51,7 +51,12 @@ public final class OrderGlobalStep<S> extends CollectingBarrierStep<S> implement
@Override
public void barrierConsumer(final TraverserSet<S> traverserSet) {
- traverserSet.sort(this.comparators.isEmpty() ? new ComparatorTraverser(Order.incr) : new ChainedComparator(ComparatorTraverser.convertComparator((List) this.comparators)));
+ if (null == this.chainedComparator)
+ this.chainedComparator = new ChainedComparator<>(ComparatorTraverser.convertComparator((List) this.getComparators()));
+ if (this.chainedComparator.isShuffle())
+ traverserSet.shuffle();
+ else
+ traverserSet.sort(this.chainedComparator);
}
@Override
@@ -105,26 +110,11 @@ public final class OrderGlobalStep<S> extends CollectingBarrierStep<S> implement
for (final Comparator<S> comparator : this.comparators) {
clone.addComparator(comparator instanceof TraversalComparator ? ((TraversalComparator) comparator).clone() : comparator);
}
+ clone.chainedComparator = null;
return clone;
}
/////
- private static class ComparatorTraverser<S> implements Comparator<Traverser<S>>, Serializable {
- private final Comparator<S> comparator;
-
- public ComparatorTraverser(final Comparator<S> comparator) {
- this.comparator = comparator;
- }
-
- @Override
- public int compare(final Traverser<S> traverserA, final Traverser<S> traverserB) {
- return this.comparator.compare(traverserA.get(), traverserB.get());
- }
-
- public static <S> List<ComparatorTraverser<S>> convertComparator(final List<Comparator<S>> comparators) {
- return comparators.stream().map(comparator -> new ComparatorTraverser<>(comparator)).collect(Collectors.toList());
- }
- }
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/ed66ee3e/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
index a39d6da..35493cf 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
@@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.TraversalComparator;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
+import org.apache.tinkerpop.gremlin.util.function.ChainedComparator;
import java.util.ArrayList;
import java.util.Collection;
@@ -43,7 +44,7 @@ import java.util.stream.Collectors;
public final class OrderLocalStep<S, M> extends MapStep<S, S> implements ComparatorHolder<M>, TraversalParent {
private List<Comparator<M>> comparators = new ArrayList<>();
- private Comparator<M> chainedComparator = null;
+ private ChainedComparator<M> chainedComparator = null;
public OrderLocalStep(final Traversal.Admin traversal) {
super(traversal);
@@ -51,6 +52,8 @@ public final class OrderLocalStep<S, M> extends MapStep<S, S> implements Compara
@Override
protected S map(final Traverser.Admin<S> traverser) {
+ if (null == this.chainedComparator)
+ this.chainedComparator = new ChainedComparator<>(this.getComparators());
final S start = traverser.get();
if (start instanceof Collection)
return (S) OrderLocalStep.sortCollection((Collection) start, this.chainedComparator);
@@ -65,12 +68,11 @@ public final class OrderLocalStep<S, M> extends MapStep<S, S> implements Compara
this.comparators.add(comparator);
if (comparator instanceof TraversalComparator)
this.integrateChild(((TraversalComparator) comparator).getTraversal());
- this.chainedComparator = this.comparators.stream().reduce((a, b) -> a.thenComparing(b)).get();
}
@Override
public List<Comparator<M>> getComparators() {
- return Collections.unmodifiableList(this.comparators);
+ return this.comparators.isEmpty() ? Collections.singletonList((Comparator) Order.incr) : Collections.unmodifiableList(this.comparators);
}
@Override
@@ -106,31 +108,36 @@ public final class OrderLocalStep<S, M> extends MapStep<S, S> implements Compara
}
@Override
- public OrderLocalStep<S,M> clone() {
- final OrderLocalStep<S,M> clone = (OrderLocalStep<S,M>) super.clone();
+ public OrderLocalStep<S, M> clone() {
+ final OrderLocalStep<S, M> clone = (OrderLocalStep<S, M>) super.clone();
clone.comparators = new ArrayList<>();
- for(final Comparator<M> comparator : this.comparators) {
+ for (final Comparator<M> comparator : this.comparators) {
clone.addComparator(comparator instanceof TraversalComparator ? ((TraversalComparator) comparator).clone() : comparator);
}
+ clone.chainedComparator = null;
return clone;
}
/////////////
- private static final <A> List<A> sortCollection(final Collection<A> collection, final Comparator<?> comparator) {
+ private static final <A> List<A> sortCollection(final Collection<A> collection, final ChainedComparator<?> comparator) {
if (collection instanceof List) {
- Collections.sort((List) collection, (Comparator) comparator);
+ if (comparator.isShuffle())
+ Collections.shuffle((List) collection);
+ else
+ Collections.sort((List) collection, (Comparator) comparator);
return (List<A>) collection;
} else {
- final List<A> list = new ArrayList<>(collection);
- Collections.sort(list, (Comparator) comparator);
- return list;
+ return sortCollection(new ArrayList<>(collection), comparator);
}
}
- private static final <K, V> Map<K, V> sortMap(final Map<K, V> map, final Comparator<?> comparator) {
+ private static final <K, V> Map<K, V> sortMap(final Map<K, V> map, final ChainedComparator<?> comparator) {
final List<Map.Entry<K, V>> entries = new ArrayList<>(map.entrySet());
- Collections.sort(entries, (Comparator) comparator);
+ if (comparator.isShuffle())
+ Collections.shuffle(entries);
+ else
+ Collections.sort(entries, (Comparator) comparator);
final LinkedHashMap<K, V> sortedMap = new LinkedHashMap<>();
entries.forEach(entry -> sortedMap.put(entry.getKey(), entry.getValue()));
return sortedMap;
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/ed66ee3e/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComparatorTraverser.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComparatorTraverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComparatorTraverser.java
new file mode 100644
index 0000000..437a01a
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComparatorTraverser.java
@@ -0,0 +1,52 @@
+/*
+ * 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.tinkerpop.gremlin.process.traversal.step.util;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+
+import java.io.Serializable;
+import java.util.Comparator;
+import java.util.List;
+import java.util.stream.Collectors;
+
+/**
+ * @author Marko A. Rodriguez (http://markorodriguez.com)
+ */
+public final class ComparatorTraverser<S> implements Comparator<Traverser<S>>, Serializable {
+
+ private final Comparator<S> comparator;
+
+ public ComparatorTraverser(final Comparator<S> comparator) {
+ this.comparator = comparator;
+ }
+
+ public Comparator<S> getComparator() {
+ return this.comparator;
+ }
+
+ @Override
+ public int compare(final Traverser<S> traverserA, final Traverser<S> traverserB) {
+ return this.comparator.compare(traverserA.get(), traverserB.get());
+ }
+
+ public static <S> List<ComparatorTraverser<S>> convertComparator(final List<Comparator<S>> comparators) {
+ return comparators.stream().map(comparator -> new ComparatorTraverser<>(comparator)).collect(Collectors.toList());
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/ed66ee3e/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
index 793457d..757bc32 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
@@ -18,8 +18,8 @@
*/
package org.apache.tinkerpop.gremlin.process.traversal.traverser.util;
-import org.apache.tinkerpop.gremlin.process.traversal.util.FastNoSuchElementException;
import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.util.FastNoSuchElementException;
import java.io.Serializable;
import java.util.AbstractSet;
@@ -146,4 +146,11 @@ public class TraverserSet<S> extends AbstractSet<Traverser.Admin<S>> implements
list.forEach(traverser -> this.map.put(traverser, traverser));
}
+ public void shuffle() {
+ final List<Traverser.Admin<S>> list = new ArrayList<>(this.map.values());
+ Collections.shuffle(list);
+ this.map.clear();
+ list.forEach(traverser -> this.map.put(traverser, traverser));
+ }
+
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/ed66ee3e/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/ChainedComparator.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/ChainedComparator.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/ChainedComparator.java
index 6068f10..8c69f1b 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/ChainedComparator.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/ChainedComparator.java
@@ -18,9 +18,15 @@
*/
package org.apache.tinkerpop.gremlin.util.function;
+import org.apache.tinkerpop.gremlin.process.traversal.Order;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.ComparatorTraverser;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.TraversalComparator;
+
import java.io.Serializable;
+import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
+import java.util.stream.Collectors;
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
@@ -29,11 +35,19 @@ public final class ChainedComparator<T> implements Comparator<T>, Serializable {
private final List<Comparator<T>> comparators;
private transient Comparator<T> chain;
+ private final boolean isShuffle;
public ChainedComparator(final List<Comparator<T>> comparators) {
if (comparators.isEmpty())
throw new IllegalArgumentException("A chained comparator requires at least one comparator");
- this.comparators = comparators;
+ this.comparators = new ArrayList<>(comparators);
+ this.isShuffle = ChainedComparator.testIsShuffle(this.comparators.get(this.comparators.size() - 1));
+ if (!this.isShuffle)
+ this.comparators.removeAll(this.comparators.stream().filter(ChainedComparator::testIsShuffle).collect(Collectors.toList()));
+ }
+
+ public boolean isShuffle() {
+ return this.isShuffle;
}
@Override
@@ -41,4 +55,16 @@ public final class ChainedComparator<T> implements Comparator<T>, Serializable {
if (null == this.chain) this.chain = this.comparators.stream().reduce((a, b) -> a.thenComparing(b)).get();
return this.chain.compare(objectA, objectB);
}
+
+ private static boolean testIsShuffle(final Comparator comparator) {
+ if (comparator.equals(Order.shuffle))
+ return true;
+ else if (comparator instanceof ComparatorTraverser)
+ return testIsShuffle(((ComparatorTraverser) comparator).getComparator());
+ else if (comparator instanceof TraversalComparator)
+ return testIsShuffle(((TraversalComparator) comparator).getComparator());
+ else
+ return false;
+ }
+
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/ed66ee3e/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStepTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStepTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStepTest.java
index 17697b7..5613bd8 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStepTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStepTest.java
@@ -23,7 +23,9 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
import org.apache.tinkerpop.gremlin.process.traversal.step.StepTest;
import org.junit.Ignore;
+import org.junit.Test;
+import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
@@ -51,4 +53,20 @@ public class OrderGlobalStepTest extends StepTest {
__.order().by(outE().count(), Order.incr).by("age", Order.incr)
);
}
+
+ @Test
+ public void shouldNotThrowContractException() {
+ for (int x = 0; x < 1000; x++) {
+ final List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 1000; i++) {
+ list.add(i);
+ }
+ __.inject(list).unfold().order().by(Order.shuffle).iterate();
+ __.inject(list).unfold().order().by().by(Order.shuffle).iterate();
+ __.inject(list).unfold().order().by(Order.shuffle).by().iterate();
+ __.inject(list).unfold().order().by(__.identity(), Order.shuffle).iterate();
+ __.inject(list).unfold().order().by().by(__.identity(), Order.shuffle).iterate();
+ __.inject(list).unfold().order().by(__.identity(), Order.shuffle).by().iterate();
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/ed66ee3e/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStepTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStepTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStepTest.java
index 5058572..30b96b0 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStepTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStepTest.java
@@ -24,7 +24,9 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
import org.apache.tinkerpop.gremlin.process.traversal.step.StepTest;
import org.junit.Ignore;
+import org.junit.Test;
+import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
@@ -52,4 +54,20 @@ public class OrderLocalStepTest extends StepTest {
__.order(Scope.local).by(outE().count(), Order.incr).by("age", Order.incr)
);
}
+
+ @Test
+ public void shouldNotThrowContractException() {
+ for (int x = 0; x < 1000; x++) {
+ final List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 1000; i++) {
+ list.add(i);
+ }
+ __.inject(list).order(Scope.local).by(Order.shuffle).iterate();
+ __.inject(list).order(Scope.local).by().by(Order.shuffle).iterate();
+ __.inject(list).order(Scope.local).by(Order.shuffle).by().iterate();
+ __.inject(list).order(Scope.local).by(__.identity(), Order.shuffle).iterate();
+ __.inject(list).order(Scope.local).by().by(__.identity(), Order.shuffle).iterate();
+ __.inject(list).order(Scope.local).by(__.identity(), Order.shuffle).by().iterate();
+ }
+ }
}