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/06/11 22:53:59 UTC
incubator-tinkerpop git commit: XMatchStep now has a pluggable
MatchAlgorithm. GreedMatchAlgorithm is provided as a public static class and,
for now, is hard coded as the MatchAlgorithm to use.
Repository: incubator-tinkerpop
Updated Branches:
refs/heads/xmatch 5d351f918 -> 9c213574b
XMatchStep now has a pluggable MatchAlgorithm. GreedMatchAlgorithm is provided as a public static class and, for now, is hard coded as the MatchAlgorithm to use.
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/9c213574
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/9c213574
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/9c213574
Branch: refs/heads/xmatch
Commit: 9c213574b7bc436269b4e4caf8af0b98803447e0
Parents: 5d351f9
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Thu Jun 11 14:53:54 2015 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Thu Jun 11 14:53:54 2015 -0600
----------------------------------------------------------------------
.../traversal/step/filter/exp/XMatchStep.java | 92 +++++++++++++-------
1 file changed, 62 insertions(+), 30 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/9c213574/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java
index 5524ee0..be0d94b 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java
@@ -41,7 +41,9 @@ import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
+import java.util.Optional;
import java.util.Set;
+import java.util.function.Function;
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
@@ -49,17 +51,16 @@ import java.util.Set;
public final class XMatchStep<S> extends ComputerAwareStep<S, S> implements TraversalParent {
private List<Traversal.Admin<Object, Object>> andTraversals = new ArrayList<>();
- private final List<String> traversalLabels = new ArrayList<>();
- private final List<String> startLabels = new ArrayList<>();
private boolean first = true;
+ private final MatchAlgorithm matchAlgorithm = new GreedyMatchAlgorithm();
+
public XMatchStep(final Traversal.Admin traversal, final Traversal... andTraversals) {
super(traversal);
int counter = 0;
for (final Traversal andTraversal : andTraversals) {
- final String traversalLabel = "t" + counter++;
- this.traversalLabels.add(traversalLabel);
+ final String traversalLabel = "t" + counter++; // TODO: this should be specified in a finalization strategy and based on the traversal then static id
//// START STEP
final Step<?, ?> startStep = andTraversal.asAdmin().getStartStep();
if (startStep instanceof StartStep && !startStep.getLabels().isEmpty()) {
@@ -68,7 +69,6 @@ public final class XMatchStep<S> extends ComputerAwareStep<S, S> implements Trav
final String startLabel = startStep.getLabels().iterator().next();
final Step<?, ?> selectOneStep = new SelectOneStep<>(andTraversal.asAdmin(), Scope.global, Pop.head, startLabel);
selectOneStep.addLabel(traversalLabel);
- this.startLabels.add(startLabel);
TraversalHelper.replaceStep(andTraversal.asAdmin().getStartStep(), selectOneStep, andTraversal.asAdmin());
}
//// END STEP
@@ -78,7 +78,7 @@ public final class XMatchStep<S> extends ComputerAwareStep<S, S> implements Trav
throw new IllegalArgumentException("The end step of a match()-traversal can only have one label: " + endStep);
final String label = endStep.getLabels().iterator().next();
endStep.removeLabel(label);
- final Step<?, ?> isOrAllowStep = new IsOrAllowStep<>(andTraversal.asAdmin(), label);
+ final Step<?, ?> isOrAllowStep = new IsOrAllowStep<>(andTraversal.asAdmin(), label); // TODO: perhaps just have a XMatchEndStep private static?
isOrAllowStep.addLabel(label);
andTraversal.asAdmin().addStep(isOrAllowStep);
andTraversal.asAdmin().addStep(new EndStep(andTraversal.asAdmin(), true));
@@ -110,49 +110,48 @@ public final class XMatchStep<S> extends ComputerAwareStep<S, S> implements Trav
for (final Traversal.Admin<Object, Object> traversal : this.andTraversals) {
clone.andTraversals.add(clone.integrateChild(traversal.clone()));
}
+ // TODO: does it need to clone the match algorithm?
return clone;
}
@Override
protected Iterator<Traverser<S>> standardAlgorithm() throws NoSuchElementException {
while (true) {
- if (!this.first) {
+ if (this.first) {
+ this.matchAlgorithm.initialize(this.andTraversals);
+ this.first = false;
+ } else {
for (final Traversal.Admin<?, ?> andTraversal : this.andTraversals) {
if (andTraversal.hasNext())
this.starts.add((Traverser.Admin) andTraversal.getEndStep().next().asAdmin());
}
}
- this.first = false;
- final Traverser<S> traverser = this.starts.next();
- final Path path = traverser.path();
- boolean traverserPassed = true;
- for (int i = 0; i < this.andTraversals.size(); i++) {
- if (path.hasLabel(this.startLabels.get(i)) && !path.hasLabel(this.traversalLabels.get(i))) {
- traverserPassed = false;
- this.andTraversals.get(i).addStart((Traverser) traverser);
- break;
- }
- }
- if (traverserPassed) {
+ final Traverser.Admin traverser = this.starts.next();
+ final Optional<Traversal.Admin<Object, Object>> optional = this.matchAlgorithm.apply(traverser);
+ if (optional.isPresent())
+ optional.get().addStart(traverser);
+ else
// TODO: trim off internal traversal labels from path
return IteratorUtils.of(traverser);
- }
}
}
@Override
protected Iterator<Traverser<S>> computerAlgorithm() throws NoSuchElementException {
- final Traverser<S> traverser = this.starts.next();
- final Path path = traverser.path();
- for (int i = 0; i < this.andTraversals.size(); i++) {
- if (path.hasLabel(this.startLabels.get(i)) && !path.hasLabel(this.traversalLabels.get(i))) {
- traverser.asAdmin().setStepId(this.andTraversals.get(i).getStartStep().getId());
- return IteratorUtils.of(traverser);
- }
+ if (this.first) {
+ this.matchAlgorithm.initialize(this.andTraversals);
+ this.first = false;
+ }
+ final Traverser.Admin traverser = this.starts.next();
+ final Optional<Traversal.Admin<Object, Object>> optional = this.matchAlgorithm.apply(traverser);
+ if (optional.isPresent()) {
+ traverser.asAdmin().setStepId(optional.get().getStartStep().getId());
+ return IteratorUtils.of(traverser);
+ } else {
+ // TODO: trim off internal traversal labels from path
+ traverser.asAdmin().setStepId(this.getNextStep().getId());
+ return IteratorUtils.of(traverser);
}
- // TODO: trim off internal traversal labels from path
- traverser.asAdmin().setStepId(this.getNextStep().getId());
- return IteratorUtils.of(traverser);
}
@Override
@@ -164,4 +163,37 @@ public final class XMatchStep<S> extends ComputerAwareStep<S, S> implements Trav
public Set<TraverserRequirement> getRequirements() {
return this.getSelfAndChildRequirements(TraverserRequirement.PATH, TraverserRequirement.SIDE_EFFECTS);
}
+
+ //////////////////////////////
+
+ public interface MatchAlgorithm extends Function<Traverser.Admin<Object>, Optional<Traversal.Admin<Object, Object>>> {
+ public void initialize(final List<Traversal.Admin<Object, Object>> traversals);
+ }
+
+ public static class GreedyMatchAlgorithm implements MatchAlgorithm {
+
+ private List<Traversal.Admin<Object, Object>> traversals;
+ private List<String> traversalLabels = new ArrayList<>();
+ private List<String> startLabels = new ArrayList<>();
+
+ @Override
+ public void initialize(final List<Traversal.Admin<Object, Object>> traversals) {
+ this.traversals = traversals;
+ for (final Traversal.Admin<Object, Object> traversal : traversals) {
+ this.traversalLabels.add(traversal.getStartStep().getLabels().iterator().next());
+ this.startLabels.add(((SelectOneStep<?, ?>) traversal.getStartStep()).getScopeKeys().iterator().next());
+ }
+ }
+
+ @Override
+ public Optional<Traversal.Admin<Object, Object>> apply(final Traverser.Admin<Object> traverser) {
+ final Path path = traverser.path();
+ for (int i = 0; i < this.traversals.size(); i++) {
+ if (path.hasLabel(this.startLabels.get(i)) && !path.hasLabel(this.traversalLabels.get(i))) {
+ return Optional.of(this.traversals.get(i));
+ }
+ }
+ return Optional.empty();
+ }
+ }
}