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 2015/05/07 16:52:41 UTC
incubator-tinkerpop git commit: Strategy sorting converted to
top-sort Added extra test to demonstrate previous sort was not working Added
some docs
Repository: incubator-tinkerpop
Updated Branches:
refs/heads/master 39364da3f -> e557d7c4f
Strategy sorting converted to top-sort
Added extra test to demonstrate previous sort was not working
Added some docs
https://issues.apache.org/jira/browse/TINKERPOP3-667
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/e557d7c4
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/e557d7c4
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/e557d7c4
Branch: refs/heads/master
Commit: e557d7c4fb9e8ebb39f7e6581362ac2b5dd3d5ee
Parents: 39364da
Author: Bryn Cooke <br...@gmail.com>
Authored: Thu May 7 13:18:49 2015 +0100
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Thu May 7 08:52:34 2015 -0600
----------------------------------------------------------------------
.../process/traversal/TraversalStrategies.java | 98 +++++++++++++-------
.../util/DefaultTraversalStrategies.java | 4 +-
.../process/TraversalStrategiesTest.java | 49 +++++++---
3 files changed, 106 insertions(+), 45 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e557d7c4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
index 1e7dbfd..6697f10 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
@@ -32,6 +32,7 @@ import org.apache.tinkerpop.gremlin.util.tools.MultiMap;
import java.io.Serializable;
import java.util.*;
+import java.util.stream.Collectors;
/**
* A {@link Traversal} maintains a set of {@link TraversalStrategy} instances within a TraversalStrategies object.
@@ -42,6 +43,8 @@ import java.util.*;
*/
public interface TraversalStrategies extends Serializable, Cloneable {
+ static List<Class<? extends TraversalStrategy>> strategyCategories = Collections.unmodifiableList(Arrays.asList(TraversalStrategy.DecorationStrategy.class, TraversalStrategy.OptimizationStrategy.class, TraversalStrategy.FinalizationStrategy.class, TraversalStrategy.VerificationStrategy.class));
+
/**
* Return all the {@link TraversalStrategy} singleton instances associated with this {@link TraversalStrategies}.
*/
@@ -97,52 +100,83 @@ public interface TraversalStrategies extends Serializable, Cloneable {
*
* @param strategies the traversal strategies to sort
*/
- public static void sortStrategies(final List<TraversalStrategy<?>> strategies) {
+ public static List<TraversalStrategy<?>> sortStrategies(final List<TraversalStrategy<?>> strategies) {
final Map<Class<? extends TraversalStrategy>, Set<Class<? extends TraversalStrategy>>> dependencyMap = new HashMap<>();
- final Set<Class<? extends TraversalStrategy>> strategyClass = new HashSet<>(strategies.size());
+ final Map<Class<? extends TraversalStrategy>, Set<Class<? extends TraversalStrategy>>> strategiesByCategory = new HashMap();
+ final Set<Class<? extends TraversalStrategy>> strategyClasses = new HashSet<>(strategies.size());
//Initialize data structure
- strategies.forEach(s -> strategyClass.add(s.getClass()));
+ strategies.forEach(s -> {
+ strategyClasses.add(s.getClass());
+ MultiMap.put(strategiesByCategory, s.getTraversalCategory(), s.getClass());
+ });
+
//Initialize all the dependencies
strategies.forEach(strategy -> {
strategy.applyPrior().forEach(s -> {
- if (strategyClass.contains(s)) MultiMap.put(dependencyMap, s, strategy.getClass());
+ if (strategyClasses.contains(s)) MultiMap.put(dependencyMap, strategy.getClass(), s);
});
strategy.applyPost().forEach(s -> {
- if (strategyClass.contains(s)) MultiMap.put(dependencyMap, strategy.getClass(), s);
+ if (strategyClasses.contains(s)) MultiMap.put(dependencyMap, s, strategy.getClass());
});
});
- //Now, compute transitive closure until convergence
- boolean updated;
- do {
- updated = false;
- for (final Class<? extends TraversalStrategy> sc : strategyClass) {
- List<Class<? extends TraversalStrategy>> toAdd = null;
- for (Class<? extends TraversalStrategy> before : MultiMap.get(dependencyMap, sc)) {
- final Set<Class<? extends TraversalStrategy>> beforeDep = MultiMap.get(dependencyMap, before);
- if (!beforeDep.isEmpty()) {
- if (toAdd == null) toAdd = new ArrayList<>(beforeDep.size());
- toAdd.addAll(beforeDep);
- }
+
+ //Add dependencies by category
+ List<Class<? extends TraversalStrategy>> strategiesInPreviousCategories = new ArrayList<>();
+ for(Class<? extends TraversalStrategy> category : strategyCategories) {
+ Set<Class<? extends TraversalStrategy>> strategiesInThisCategory = MultiMap.get(strategiesByCategory, category);
+ for(Class<? extends TraversalStrategy> strategy : strategiesInThisCategory) {
+ for(Class<? extends TraversalStrategy> previousStrategy : strategiesInPreviousCategories) {
+ MultiMap.put(dependencyMap, strategy, previousStrategy);
}
- if (toAdd != null && MultiMap.putAll(dependencyMap, sc, toAdd)) updated = true;
}
- } while (updated);
- Collections.sort(strategies, (strategy1, strategy2) -> {
- int categoryComparison = strategy1.compareTo(strategy2.getTraversalCategory());
- if (categoryComparison != 0) return categoryComparison;
-
- boolean s1Before = MultiMap.containsEntry(dependencyMap, strategy1.getClass(), strategy2.getClass());
- boolean s2Before = MultiMap.containsEntry(dependencyMap, strategy2.getClass(), strategy1.getClass());
- if (s1Before && s2Before)
- throw new IllegalStateException("Cyclic dependency between traversal strategies: ["
- + strategy1.getClass().getName() + ", " + strategy2.getClass().getName() + ']');
- if (s1Before) return -1;
- else if (s2Before) return 1;
- else return 0;
- });
+ strategiesInPreviousCategories.addAll(strategiesInThisCategory);
+ }
+
+ //Finally sort via t-sort
+ List<Class<? extends TraversalStrategy>> unprocessedStrategyClasses = new ArrayList<>(strategies.stream().map(s->s.getClass()).collect(Collectors.toSet()));
+ List<Class<? extends TraversalStrategy>> sortedStrategyClasses = new ArrayList<>();
+ Set<Class<? extends TraversalStrategy>> seenStrategyClasses = new HashSet<>();
+
+ while(!unprocessedStrategyClasses.isEmpty()) {
+ Class<? extends TraversalStrategy> strategy = unprocessedStrategyClasses.get(0);
+ visit(dependencyMap, sortedStrategyClasses, seenStrategyClasses, unprocessedStrategyClasses, strategy);
+ }
+
+ List<TraversalStrategy<?>> sortedStrategies = new ArrayList<>();
+ //We now have a list of sorted strategy classes
+ for(Class<? extends TraversalStrategy> strategyClass : sortedStrategyClasses) {
+ for(TraversalStrategy strategy : strategies) {
+ if(strategy.getClass().equals(strategyClass)) {
+ sortedStrategies.add(strategy);
+ }
+ }
+ }
+
+
+ return sortedStrategies;
+ }
+
+
+ static void visit(Map<Class<? extends TraversalStrategy>, Set<Class<? extends TraversalStrategy>>> dependencyMap, List<Class<? extends TraversalStrategy>> sortedStrategyClasses, Set<Class<? extends TraversalStrategy>> seenStrategyClases, List<Class<? extends TraversalStrategy>> unprocessedStrategyClasses, Class<? extends TraversalStrategy> strategyClass) {
+ if(seenStrategyClases.contains(strategyClass)) {
+ throw new IllegalStateException("Cyclic dependency between traversal strategies: ["
+ + seenStrategyClases + ']');
+ }
+
+
+ if(unprocessedStrategyClasses.contains(strategyClass)) {
+ seenStrategyClases.add(strategyClass);
+ for (Class<? extends TraversalStrategy> dependency : MultiMap.get(dependencyMap, strategyClass)) {
+ visit(dependencyMap, sortedStrategyClasses, seenStrategyClases, unprocessedStrategyClasses, dependency);
+ }
+ seenStrategyClases.remove(strategyClass);
+ unprocessedStrategyClasses.remove(strategyClass);
+ sortedStrategyClasses.add(strategyClass);
+ }
}
+
public static final class GlobalCache {
private static final Map<Class<? extends Graph>, TraversalStrategies> CACHE = new HashMap<>();
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e557d7c4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalStrategies.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalStrategies.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalStrategies.java
index 0dd0cd2..eb5a9c7 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalStrategies.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalStrategies.java
@@ -47,7 +47,7 @@ public class DefaultTraversalStrategies implements TraversalStrategies {
added = true;
}
}
- if (added) TraversalStrategies.sortStrategies(this.traversalStrategies);
+ if (added) this.traversalStrategies = TraversalStrategies.sortStrategies(this.traversalStrategies);
return this;
}
@@ -62,7 +62,7 @@ public class DefaultTraversalStrategies implements TraversalStrategies {
removed = true;
}
}
- if (removed) TraversalStrategies.sortStrategies(this.traversalStrategies);
+ if (removed) this.traversalStrategies = TraversalStrategies.sortStrategies(this.traversalStrategies);
return this;
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e557d7c4/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/TraversalStrategiesTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/TraversalStrategiesTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/TraversalStrategiesTest.java
index 0beaa37..f200552 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/TraversalStrategiesTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/TraversalStrategiesTest.java
@@ -25,7 +25,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversal
import org.junit.Test;
import java.util.Arrays;
-import java.util.Collections;
+import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
@@ -51,27 +51,29 @@ public class TraversalStrategiesTest {
c = new StrategyC(),
d = new StrategyD(),
e = new StrategyE(),
- k = new StrategyK();
+ k = new StrategyK(),
+ l = new StrategyL(),
+ m = new StrategyM(),
+ n = new StrategyN(),
+ o = new StrategyO();
List<TraversalStrategy<?>> s;
//Dependency well defined
s = Arrays.asList(b, a);
- TraversalStrategies.sortStrategies(s);
+ s = TraversalStrategies.sortStrategies(s);
assertEquals(2, s.size());
assertEquals(a, s.get(0));
assertEquals(b, s.get(1));
//No dependency
s = Arrays.asList(c, a);
- TraversalStrategies.sortStrategies(s);
+ s = TraversalStrategies.sortStrategies(s);
assertEquals(2, s.size());
- assertEquals(c, s.get(0));
- assertEquals(a, s.get(1));
//Dependency well defined
s = Arrays.asList(c, a, b);
- TraversalStrategies.sortStrategies(s);
+ s = TraversalStrategies.sortStrategies(s);
assertEquals(3, s.size());
assertEquals(a, s.get(0));
assertEquals(b, s.get(1));
@@ -88,7 +90,7 @@ public class TraversalStrategiesTest {
//Dependency well defined
s = Arrays.asList(d, c, a, e, b);
- TraversalStrategies.sortStrategies(s);
+ s = TraversalStrategies.sortStrategies(s);
assertEquals(5, s.size());
assertEquals(a, s.get(0));
assertEquals(b, s.get(1));
@@ -104,6 +106,12 @@ public class TraversalStrategiesTest {
} catch (IllegalStateException ex) {
assertTrue(ex.getMessage().toLowerCase().contains("cyclic"));
}
+
+ //Lots of strategies
+ s = Arrays.asList(b, l, m, n, o, a);
+ s = TraversalStrategies.sortStrategies(s);
+ assertTrue(s.indexOf(a) < s.indexOf(b));
+
}
@@ -171,6 +179,25 @@ public class TraversalStrategiesTest {
}
+ public static class StrategyL extends DummyStrategy {
+
+ }
+
+
+ public static class StrategyM extends DummyStrategy {
+
+ }
+
+ public static class StrategyN extends DummyStrategy {
+
+ }
+
+ public static class StrategyO extends DummyStrategy {
+
+ }
+
+
+
private static class DummyStrategy<S extends TraversalStrategy> extends AbstractTraversalStrategy<S> {
@Override
@@ -197,14 +224,14 @@ public class TraversalStrategiesTest {
//in category sorting
s = Arrays.asList(b, a);
- TraversalStrategies.sortStrategies(s);
+ s = TraversalStrategies.sortStrategies(s);
assertEquals(2, s.size());
assertEquals(a, s.get(0));
assertEquals(b, s.get(1));
//mixed category sorting
s = Arrays.asList(a, e, b, d);
- TraversalStrategies.sortStrategies(s);
+ s = TraversalStrategies.sortStrategies(s);
assertEquals(4, s.size());
assertEquals(a, s.get(0));
assertEquals(b, s.get(1));
@@ -213,7 +240,7 @@ public class TraversalStrategiesTest {
//full reverse sorting
s = Arrays.asList(k,e,d,c,b,a);
- TraversalStrategies.sortStrategies(s);
+ s = TraversalStrategies.sortStrategies(s);
assertEquals(6, s.size());
assertEquals(a, s.get(0));
assertEquals(b, s.get(1));