You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by sp...@apache.org on 2018/02/01 15:30:39 UTC
[28/50] [abbrv] tinkerpop git commit: TINKERPOP-1870 Made
VertexTraverserSet more generic to IndexedTraverserSet
TINKERPOP-1870 Made VertexTraverserSet more generic to IndexedTraverserSet
IndexedTraverserSet does what VertexTraverserSet was doing, but in a more complete way. It respects all the semantics of a TraverserSet and fixes a problem that VertexTraverserSet had where it didn't properly account for Traverser merges. Added a full grip of unit tests for both TraverserSet and IndexedTraverserSet.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/068bef85
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/068bef85
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/068bef85
Branch: refs/heads/TINKERPOP-1857
Commit: 068bef855c0f6c44a2ed71c1c8f4b18ad1e1dbdb
Parents: 3e6e08a
Author: Stephen Mallette <sp...@genoprime.com>
Authored: Tue Jan 23 16:16:40 2018 -0500
Committer: Stephen Mallette <sp...@genoprime.com>
Committed: Tue Jan 23 18:45:20 2018 -0500
----------------------------------------------------------------------
CHANGELOG.asciidoc | 3 +-
.../traversal/TraversalVertexProgram.java | 10 +-
.../computer/traversal/WorkerExecutor.java | 26 +--
.../traverser/util/IndexedTraverserSet.java | 112 ++++++++++
.../traversal/traverser/util/TraverserSet.java | 3 +-
.../traverser/util/VertexTraverserSet.java | 71 -------
.../gremlin/structure/io/gryo/GryoVersion.java | 4 +-
.../tinkerpop/gremlin/structure/util/Host.java | 23 +++
.../traverser/util/IndexedTraverserSetTest.java | 189 +++++++++++++++++
.../util/TraverserSetImplementationTest.java | 207 +++++++++++++++++++
.../process/traversal/step/map/ProgramTest.java | 8 +-
11 files changed, 551 insertions(+), 105 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 1fd0311..7377d24 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -25,7 +25,8 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
* Delayed setting of the request identifier until `RequestMessage` construction by the builder.
* Removed hardcoded expectation in metrics serialization test suite as different providers may have different outputs.
-* Added `VertexTraverserSet` which indexes on a `Vertex` thus improving performance in `VertexProgram` implementations.
+* Added `IndexedTraverserSet` which indexes on the value of a `Traverser` thus improving performance when used.
+* Utilized `IndexedTraverserSet` in `TraversalVertexProgram` to avoid extra iteration when doing `Vertex` lookups.
* Fixed a bug in `ComputerAwareStep` that didn't handle `reset()` properly and thus occasionally produced some extra traversers.
[[release-3-2-7]]
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
index d4c605b..3cb4d00 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
@@ -53,7 +53,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.HaltedTraverserStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.ComputerVerificationStrategy;
-import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.VertexTraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.IndexedTraverserSet;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.util.MutableMetrics;
@@ -230,13 +230,13 @@ public final class TraversalVertexProgram implements VertexProgram<TraverserSet<
toProcessTraversers.add(traverser);
});
assert this.haltedTraversers.isEmpty();
- final VertexTraverserSet<Object> remoteActiveTraversers = new VertexTraverserSet<>();
+ final IndexedTraverserSet<Object,Vertex> remoteActiveTraversers = new IndexedTraverserSet.VertexIndexedTraverserSet();
MasterExecutor.processTraversers(this.traversal, this.traversalMatrix, toProcessTraversers, remoteActiveTraversers, this.haltedTraversers, this.haltedTraverserStrategy);
memory.set(HALTED_TRAVERSERS, this.haltedTraversers);
memory.set(ACTIVE_TRAVERSERS, remoteActiveTraversers);
} else {
memory.set(HALTED_TRAVERSERS, new TraverserSet<>());
- memory.set(ACTIVE_TRAVERSERS, new VertexTraverserSet<>());
+ memory.set(ACTIVE_TRAVERSERS, new IndexedTraverserSet.VertexIndexedTraverserSet());
}
// local variable will no longer be used so null it for GC
this.haltedTraversers = null;
@@ -316,12 +316,12 @@ public final class TraversalVertexProgram implements VertexProgram<TraverserSet<
MemoryTraversalSideEffects.setMemorySideEffects(this.traversal.get(), memory, ProgramPhase.TERMINATE);
final boolean voteToHalt = memory.<Boolean>get(VOTE_TO_HALT);
memory.set(VOTE_TO_HALT, true);
- memory.set(ACTIVE_TRAVERSERS, new VertexTraverserSet<>());
+ memory.set(ACTIVE_TRAVERSERS, new IndexedTraverserSet.VertexIndexedTraverserSet());
if (voteToHalt) {
// local traverser sets to process
final TraverserSet<Object> toProcessTraversers = new TraverserSet<>();
// traversers that need to be sent back to the workers (no longer can be processed locally by the master traversal)
- final VertexTraverserSet<Object> remoteActiveTraversers = new VertexTraverserSet<>();
+ final IndexedTraverserSet<Object,Vertex> remoteActiveTraversers = new IndexedTraverserSet.VertexIndexedTraverserSet();
// halted traversers that have completed their journey
final TraverserSet<Object> haltedTraversers = memory.get(HALTED_TRAVERSERS);
// get all barrier traversers
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/WorkerExecutor.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/WorkerExecutor.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/WorkerExecutor.java
index a875afe..b437a9d 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/WorkerExecutor.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/WorkerExecutor.java
@@ -31,13 +31,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.LocalBarrier;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.HaltedTraverserStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
-import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.VertexTraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.IndexedTraverserSet;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalMatrix;
-import org.apache.tinkerpop.gremlin.structure.Edge;
import org.apache.tinkerpop.gremlin.structure.Element;
import org.apache.tinkerpop.gremlin.structure.Property;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import org.apache.tinkerpop.gremlin.structure.util.Attachable;
+import org.apache.tinkerpop.gremlin.structure.util.Host;
import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceFactory;
import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
@@ -75,7 +75,7 @@ final class WorkerExecutor {
// MASTER ACTIVE
// these are traversers that are going from OLTP (master) to OLAP (workers)
// these traversers were broadcasted from the master traversal to the workers for attachment
- final VertexTraverserSet<Object> maybeActiveTraversers = memory.get(TraversalVertexProgram.ACTIVE_TRAVERSERS);
+ final IndexedTraverserSet<Object,Vertex> maybeActiveTraversers = memory.get(TraversalVertexProgram.ACTIVE_TRAVERSERS);
// some memory systems are interacted with by multiple threads and thus, concurrent modification can happen at iterator.remove().
// its better to reduce the memory footprint and shorten the active traverser list so synchronization is worth it.
// most distributed OLAP systems have the memory partitioned and thus, this synchronization does nothing.
@@ -160,7 +160,7 @@ final class WorkerExecutor {
// decide whether to message the traverser or to process it locally
if (traverser.get() instanceof Element || traverser.get() instanceof Property) { // GRAPH OBJECT
// if the element is remote, then message, else store it locally for re-processing
- final Vertex hostingVertex = WorkerExecutor.getHostingVertex(traverser.get());
+ final Vertex hostingVertex = Host.getHostingVertex(traverser.get());
if (!vertex.equals(hostingVertex)) { // if its host is not the current vertex, then send the traverser to the hosting vertex
voteToHalt.set(false); // if message is passed, then don't vote to halt
messenger.sendMessage(MessageScope.Global.of(hostingVertex), new TraverserSet<>(traverser.detach()));
@@ -200,7 +200,7 @@ final class WorkerExecutor {
if (traverser.isHalted() &&
(returnHaltedTraversers ||
(!(traverser.get() instanceof Element) && !(traverser.get() instanceof Property)) ||
- getHostingVertex(traverser.get()).equals(vertex))) {
+ Host.getHostingVertex(traverser.get()).equals(vertex))) {
if (returnHaltedTraversers)
memory.add(TraversalVertexProgram.HALTED_TRAVERSERS, new TraverserSet<>(haltedTraverserStrategy.halt(traverser)));
else
@@ -223,7 +223,7 @@ final class WorkerExecutor {
// if its a ReferenceFactory (one less iteration required)
((returnHaltedTraversers || ReferenceFactory.class == haltedTraverserStrategy.getHaltedTraverserFactory()) &&
(!(traverser.get() instanceof Element) && !(traverser.get() instanceof Property)) ||
- getHostingVertex(traverser.get()).equals(vertex))) {
+ Host.getHostingVertex(traverser.get()).equals(vertex))) {
if (returnHaltedTraversers)
memory.add(TraversalVertexProgram.HALTED_TRAVERSERS, new TraverserSet<>(haltedTraverserStrategy.halt(traverser)));
else
@@ -234,18 +234,4 @@ final class WorkerExecutor {
});
}
}
-
- private static Vertex getHostingVertex(final Object object) {
- Object obj = object;
- while (true) {
- if (obj instanceof Vertex)
- return (Vertex) obj;
- else if (obj instanceof Edge)
- return ((Edge) obj).outVertex();
- else if (obj instanceof Property)
- obj = ((Property) obj).element();
- else
- throw new IllegalStateException("The host of the object is unknown: " + obj.toString() + ':' + obj.getClass().getCanonicalName());
- }
- }
}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/IndexedTraverserSet.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/IndexedTraverserSet.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/IndexedTraverserSet.java
new file mode 100644
index 0000000..3df335b
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/IndexedTraverserSet.java
@@ -0,0 +1,112 @@
+/*
+ * 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.traverser.util;
+
+import org.apache.commons.collections.map.MultiValueMap;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.structure.util.Host;
+
+import java.util.Collection;
+import java.util.function.Function;
+
+/**
+ * A {@link TraverserSet} that has an index back to the object in the {@link Traverser}. Using this extension of
+ * {@link TraverserSet} can make it easier to find traversers within the set if the internal value is known. Without
+ * the index the entire {@link TraverserSet} needs to be iterated to find a particular value.
+ */
+public class IndexedTraverserSet<S,I> extends TraverserSet<S> {
+
+ private final MultiValueMap index = new MultiValueMap();
+ private final Function<S,I> indexingFunction;
+
+ public IndexedTraverserSet(final Function<S, I> indexingFunction) {
+ this(indexingFunction, null);
+ }
+
+ public IndexedTraverserSet(final Function<S, I> indexingFunction, final Traverser.Admin<S> traverser) {
+ super(traverser);
+ this.indexingFunction = indexingFunction;
+ }
+
+ @Override
+ public void clear() {
+ index.clear();
+ super.clear();
+ }
+
+ @Override
+ public boolean add(final Traverser.Admin<S> traverser) {
+ final boolean newOne = super.add(traverser);
+
+ // if newly added then the traverser will be the same as the one passed in here to add().
+ // if it is not, then it was merged to an existing traverser and the bulk would have
+ // updated on that reference, thus only new stuff really needs to be added to the index
+ if (newOne) index.put(indexingFunction.apply(traverser.get()), traverser);
+
+ return newOne;
+ }
+
+ /**
+ * Gets a collection of {@link Traverser} objects that contain the specified value.
+ *
+ * @param k the key produced by the indexing function
+ * @return
+ */
+ public Collection<Traverser.Admin<S>> get(final I k) {
+ final Collection<Traverser.Admin<S>> c = index.getCollection(k);
+
+ // if remove() is called on this class, then the MultiValueMap *may* (javadoc wasn't clear
+ // what the expectation was - used the word "typically") return an empty list if the last
+ // item removed leaves the list empty. i think we want to enforce null for TraverserSet
+ // semantics
+ return c != null && c.isEmpty() ? null : c;
+ }
+
+ @Override
+ public boolean offer(final Traverser.Admin<S> traverser) {
+ return this.add(traverser);
+ }
+
+ @Override
+ public Traverser.Admin<S> remove() {
+ final Traverser.Admin<S> removed = super.remove();
+ index.remove(indexingFunction.apply(removed.get()), removed);
+ return removed;
+ }
+
+ @Override
+ public boolean remove(final Object traverser) {
+ if (!(traverser instanceof Traverser.Admin))
+ throw new IllegalArgumentException("The object to remove must be traverser");
+
+ final boolean removed = super.remove(traverser);
+ if (removed) index.remove(indexingFunction.apply(((Traverser.Admin<S>) traverser).get()), traverser);
+ return removed;
+ }
+
+ /**
+ * An {@link IndexedTraverserSet} that indexes based on a {@link Vertex} traverser.
+ */
+ public static class VertexIndexedTraverserSet extends IndexedTraverserSet<Object, Vertex> {
+ public VertexIndexedTraverserSet() {
+ super(Host::getHostingVertex);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/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 3e3d5ea..29f5f70 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
@@ -47,7 +47,8 @@ public class TraverserSet<S> extends AbstractSet<Traverser.Admin<S>> implements
}
public TraverserSet(final Traverser.Admin<S> traverser) {
- this.map.put(traverser, traverser);
+ if (traverser != null)
+ this.map.put(traverser, traverser);
}
@Override
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/VertexTraverserSet.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/VertexTraverserSet.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/VertexTraverserSet.java
deleted file mode 100644
index 05ba3a0..0000000
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/VertexTraverserSet.java
+++ /dev/null
@@ -1,71 +0,0 @@
-/*
- * 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.traverser.util;
-
-import org.apache.commons.collections.map.MultiValueMap;
-import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
-import org.apache.tinkerpop.gremlin.structure.Edge;
-import org.apache.tinkerpop.gremlin.structure.Property;
-import org.apache.tinkerpop.gremlin.structure.Vertex;
-
-import java.util.Collection;
-
-public class VertexTraverserSet<S> extends TraverserSet<S> {
- // that should be MultiValueMap<Vertex, Traverser.Admin<S>> but 3.2.2 apache collection do not use generics
- private final MultiValueMap vertexIndex = new MultiValueMap();
-
- @Override
- public void clear() {
- vertexIndex.clear();
- super.clear();
- }
-
- @Override
- public boolean add(final Traverser.Admin<S> traverser) {
- if (super.add(traverser)) {
- vertexIndex.put(getHostingVertex(traverser.get()), traverser);
- return true;
- } else {
- return false;
- }
- }
-
- public Collection<Traverser.Admin<S>> get(Vertex v) {
- return vertexIndex.getCollection(v);
- }
-
- @Override
- public boolean offer(final Traverser.Admin<S> traverser) {
- return this.add(traverser);
- }
-
- private static Vertex getHostingVertex(final Object object) {
- Object obj = object;
- while (true) {
- if (obj instanceof Vertex)
- return (Vertex) obj;
- else if (obj instanceof Edge)
- return ((Edge) obj).outVertex();
- else if (obj instanceof Property)
- obj = ((Property) obj).element();
- else
- throw new IllegalStateException("The host of the object is unknown: " + obj.toString() + ':' + obj.getClass().getCanonicalName());
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
index 6d76ce8..6d5e99a 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
@@ -52,7 +52,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.traverser.LP_O_OB_S_SE_SL_
import org.apache.tinkerpop.gremlin.process.traversal.traverser.O_OB_S_SE_SL_Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.O_Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.ProjectedTraverser;
-import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.VertexTraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.IndexedTraverserSet;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalMetrics;
import org.apache.tinkerpop.gremlin.process.traversal.util.ImmutableMetrics;
@@ -308,7 +308,7 @@ public enum GryoVersion {
add(GryoTypeReg.of(OrderGlobalStep.OrderBiOperator.class, 118, new JavaSerializer()));
add(GryoTypeReg.of(ProfileStep.ProfileBiOperator.class, 119));
// skip 171, 172 to sync with tp33
- add(GryoTypeReg.of(VertexTraverserSet.class, 173)); // ***LAST ID***
+ add(GryoTypeReg.of(IndexedTraverserSet.VertexIndexedTraverserSet.class, 173)); // ***LAST ID***
}};
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Host.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Host.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Host.java
index 92962b0..6945434 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Host.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/Host.java
@@ -18,10 +18,33 @@
*/
package org.apache.tinkerpop.gremlin.structure.util;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Property;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+
/**
* A marker interface that identifies an object as something that an {@link Attachable} can connect to.
*
* @author Stephen Mallette (http://stephen.genoprime.com)
*/
public interface Host {
+
+ /**
+ * Extracts the {@link Vertex} that is holding the specified object.
+ *
+ * @throws IllegalStateException if the object is not a graph element type
+ */
+ public static Vertex getHostingVertex(final Object object) {
+ Object obj = object;
+ while (true) {
+ if (obj instanceof Vertex)
+ return (Vertex) obj;
+ else if (obj instanceof Edge)
+ return ((Edge) obj).outVertex();
+ else if (obj instanceof Property)
+ obj = ((Property) obj).element();
+ else
+ throw new IllegalStateException("The host of the object is unknown: " + obj.toString() + ':' + obj.getClass().getCanonicalName());
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/IndexedTraverserSetTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/IndexedTraverserSetTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/IndexedTraverserSetTest.java
new file mode 100644
index 0000000..0d765f4
--- /dev/null
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/IndexedTraverserSetTest.java
@@ -0,0 +1,189 @@
+/*
+ * 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.traverser.util;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_O_Traverser;
+import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.core.IsNull.nullValue;
+import static org.hamcrest.core.Is.is;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+
+/**
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+public class IndexedTraverserSetTest {
+ @Test
+ public void shouldIndexTraversers() {
+ final IndexedTraverserSet<String, String> ts = makeTraverserSet();
+
+ final List<Traverser.Admin<String>> testTraversers = new ArrayList<>(ts.get("test"));
+ assertEquals(1, testTraversers.size());
+ assertEquals(10, testTraversers.get(0).bulk());
+
+ final List<Traverser.Admin<String>> nopeTraversers = new ArrayList<>(ts.get("nope"));
+ assertEquals(1, nopeTraversers.size());
+ assertEquals(1, nopeTraversers.get(0).bulk());
+ }
+
+ @Test
+ public void shouldClear() {
+ final IndexedTraverserSet<String,String> ts = new IndexedTraverserSet<>(x -> x);
+ ts.add(makeTraverser("test", 1));
+
+ final List<Traverser.Admin<String>> testTraversers = new ArrayList<>(ts.get("test"));
+ assertEquals(1, testTraversers.size());
+ assertEquals(1, testTraversers.get(0).bulk());
+
+ ts.clear();
+
+ assertThat(ts.get("test"), nullValue());
+ assertThat(ts.isEmpty(), is(true));
+ }
+
+ @Test
+ public void shouldRemove() {
+ final IndexedTraverserSet<String, String> ts = makeTraverserSet();
+
+ final List<Traverser.Admin<String>> testTraversers = new ArrayList<>(ts.get("test"));
+ assertEquals(1, testTraversers.size());
+ assertEquals(10, testTraversers.get(0).bulk());
+
+ ts.remove();
+
+ assertThat(ts.get("test"), nullValue());
+
+ final List<Traverser.Admin<String>> nopeTraversers = new ArrayList<>(ts.get("nope"));
+ assertEquals(1, nopeTraversers.size());
+ assertEquals(1, nopeTraversers.get(0).bulk());
+ }
+
+ @Test
+ public void shouldRemoveSpecific() {
+ final IndexedTraverserSet<String, String> ts = makeTraverserSet();
+
+ final List<Traverser.Admin<String>> testTraversers = new ArrayList<>(ts.get("test"));
+ assertEquals(1, testTraversers.size());
+ assertEquals(10, testTraversers.get(0).bulk());
+
+ ts.remove(makeTraverser("test", 1));
+
+ assertThat(ts.get("test"), nullValue());
+
+ final List<Traverser.Admin<String>> nopeTraversers = new ArrayList<>(ts.get("nope"));
+ assertEquals(1, nopeTraversers.size());
+ assertEquals(1, nopeTraversers.get(0).bulk());
+ }
+
+ @Test
+ public void shouldMaintainIndexOfTraversersAfterShuffle() {
+ final IndexedTraverserSet<String, String> ts = makeOtherTraverserSet();
+
+ final List<Traverser.Admin<String>> testTraversers = new ArrayList<>(ts.get("test"));
+ assertEquals(1, testTraversers.size());
+ assertEquals(4, testTraversers.get(0).bulk());
+
+ final List<Traverser.Admin<String>> nopeTraversers = new ArrayList<>(ts.get("nope"));
+ assertEquals(1, nopeTraversers.size());
+ assertEquals(1, nopeTraversers.get(0).bulk());
+
+ ts.shuffle();
+
+ final List<Traverser.Admin<String>> testTraversersAfterShuffle = new ArrayList<>(ts.get("test"));
+ assertEquals(1, testTraversersAfterShuffle.size());
+ assertEquals(4, testTraversersAfterShuffle.get(0).bulk());
+
+ final List<Traverser.Admin<String>> nopeTraversersAfterShuffle = new ArrayList<>(ts.get("nope"));
+ assertEquals(1, nopeTraversersAfterShuffle.size());
+ assertEquals(1, nopeTraversersAfterShuffle.get(0).bulk());
+ }
+
+ @Test
+ public void shouldMaintainIndexOfTraversersAfterSort() {
+ final IndexedTraverserSet<String, String> ts = makeOtherTraverserSet();
+
+ final List<Traverser.Admin<String>> testTraversers = new ArrayList<>(ts.get("test"));
+ assertEquals(1, testTraversers.size());
+ assertEquals(4, testTraversers.get(0).bulk());
+
+ final List<Traverser.Admin<String>> nopeTraversers = new ArrayList<>(ts.get("nope"));
+ assertEquals(1, nopeTraversers.size());
+ assertEquals(1, nopeTraversers.get(0).bulk());
+
+ final List<Traverser<String>> traversersBefore = IteratorUtils.asList(ts.iterator());
+
+ ts.sort(Comparator.comparing(Traverser::get));
+
+ final List<Traverser<String>> traversersAfter = IteratorUtils.asList(ts.iterator());
+
+ final List<Traverser.Admin<String>> testTraversersAfterSort = new ArrayList<>(ts.get("test"));
+ assertEquals(1, testTraversersAfterSort.size());
+ assertEquals(4, testTraversersAfterSort.get(0).bulk());
+
+ final List<Traverser.Admin<String>> nopeTraversersAfterSort = new ArrayList<>(ts.get("nope"));
+ assertEquals(1, nopeTraversersAfterSort.size());
+ assertEquals(1, nopeTraversersAfterSort.get(0).bulk());
+
+ assertNotEquals(traversersBefore, traversersAfter);
+ }
+
+ private IndexedTraverserSet<String, String> makeTraverserSet() {
+ final IndexedTraverserSet<String,String> ts = new IndexedTraverserSet<>(x -> x);
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("nope", 1));
+ return ts;
+ }
+
+ private IndexedTraverserSet<String, String> makeOtherTraverserSet() {
+ final IndexedTraverserSet<String,String> ts = new IndexedTraverserSet<>(x -> x);
+ ts.add(makeTraverser("testf", 1));
+ ts.add(makeTraverser("teste", 1));
+ ts.add(makeTraverser("testd", 1));
+ ts.add(makeTraverser("testc", 1));
+ ts.add(makeTraverser("testa", 1));
+ ts.add(makeTraverser("testb", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("test", 1));
+ ts.add(makeTraverser("nope", 1));
+ return ts;
+ }
+
+ private <T> Traverser.Admin<T> makeTraverser(final T val, final long bulk) {
+ return new B_O_Traverser<>(val, bulk).asAdmin();
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSetImplementationTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSetImplementationTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSetImplementationTest.java
new file mode 100644
index 0000000..f46d380
--- /dev/null
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSetImplementationTest.java
@@ -0,0 +1,207 @@
+/*
+ * 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.traverser.util;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_O_Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.util.FastNoSuchElementException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.function.Supplier;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.core.Is.is;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+
+/**
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+@RunWith(Parameterized.class)
+public class TraverserSetImplementationTest {
+ @Parameterized.Parameters(name = "expect({0})")
+ public static Iterable<Object[]> data() {
+ return Arrays.asList(new Object[][]{
+ {TraverserSet.class.getSimpleName(), (Supplier) TraverserSet::new},
+ {IndexedTraverserSet.class.getSimpleName(), (Supplier) () -> new IndexedTraverserSet<String,String>(x -> x.substring(0,1))}});
+ }
+
+ @Parameterized.Parameter(value = 0)
+ public String name;
+
+ @Parameterized.Parameter(value = 1)
+ public Supplier<TraverserSet> traverserSetMaker;
+
+ @Test
+ public void shouldBeEmpty() {
+ assertThat(traverserSetMaker.get().isEmpty(), is(true));
+ }
+
+ @Test
+ public void shouldNotBeEmpty() {
+ final TraverserSet<String> ts = traverserSetMaker.get();
+ ts.add(makeTraverser("test", 1));
+ assertThat(ts.isEmpty(), is(false));
+ }
+
+ @Test
+ public void shouldGetSize() {
+ final TraverserSet<String> ts = traverserSetMaker.get();
+ ts.add(makeTraverser("a", 1));
+ ts.add(makeTraverser("a", 1));
+ ts.add(makeTraverser("b1", 1));
+ ts.add(makeTraverser("b2", 2));
+ ts.add(makeTraverser("c", 1));
+
+ assertEquals(4, ts.size());
+ }
+
+ @Test
+ public void shouldGetBulkSize() {
+ final TraverserSet<String> ts = makeStringTraversers();
+
+ assertEquals(5, ts.bulkSize());
+ }
+
+ @Test
+ public void shouldIterateAll() {
+ final TraverserSet<String> ts = makeStringTraversers();
+
+ final Iterator<Traverser.Admin<String>> itty = ts.iterator();
+ final Traverser.Admin<String> a = itty.next();
+ assertEquals("a", a.get());
+ assertEquals(2, a.bulk());
+
+ final Traverser.Admin<String> b1 = itty.next();
+ assertEquals("b1", b1.get());
+ assertEquals(1, b1.bulk());
+
+ final Traverser.Admin<String> b2 = itty.next();
+ assertEquals("b2", b2.get());
+ assertEquals(1, b2.bulk());
+
+ final Traverser.Admin<String> c = itty.next();
+ assertEquals("c", c.get());
+ assertEquals(1, c.bulk());
+
+ assertThat(itty.hasNext(), is(false));
+ }
+
+ @Test
+ public void shouldGetTraverser() {
+ final TraverserSet<String> ts = makeStringTraversers();
+
+ final Traverser.Admin<String> a = ts.get(makeTraverser("a", 1));
+ assertEquals("a", a.get());
+ assertEquals(2, a.bulk());
+
+ final Traverser.Admin<String> b2 = ts.get(makeTraverser("b2", 1));
+ assertEquals("b2", b2.get());
+ assertEquals(1, b2.bulk());
+
+ final Traverser.Admin<String> notHere = ts.get(makeTraverser("notHere", 1));
+ assertNull(notHere);
+ }
+
+ @Test
+ public void shouldDetermineIfTraverserIsPresent() {
+ final TraverserSet<String> ts = makeStringTraversers();
+
+ assertThat(ts.contains(makeTraverser("a", 1)), is(true));
+ assertThat(ts.contains(makeTraverser("b1", 1)), is(true));
+ assertThat(ts.contains(makeTraverser("b2", 1)), is(true));
+ assertThat(ts.contains(makeTraverser("c", 1)), is(true));
+ assertThat(ts.contains(makeTraverser("notHere", 1)), is(false));
+ }
+
+ @Test
+ public void shouldAddAndMerge() {
+ final TraverserSet<String> ts = traverserSetMaker.get();
+ assertThat(ts.add(makeTraverser("a", 1)), is(true));
+ assertThat(ts.add(makeTraverser("a", 1)), is(false));
+ assertThat(ts.add(makeTraverser("a", 1)), is(false));
+ assertThat(ts.add(makeTraverser("a", 1)), is(false));
+ assertThat(ts.add(makeTraverser("a", 1)), is(false));
+ assertThat(ts.add(makeTraverser("a", 1)), is(false));
+ assertThat(ts.add(makeTraverser("a", 1)), is(false));
+ assertThat(ts.add(makeTraverser("b", 1)), is(true));
+
+ final Iterator<Traverser.Admin<String>> itty = ts.iterator();
+ final Traverser.Admin<String> a = itty.next();
+ assertEquals(7, a.bulk());
+ final Traverser.Admin<String> b = itty.next();
+ assertEquals(1, b.bulk());
+
+ assertThat(itty.hasNext(), is(false));
+ }
+
+ @Test
+ public void shouldOfferTraverser() {
+ final TraverserSet<String> ts = traverserSetMaker.get();
+ assertThat(ts.offer(makeTraverser("a", 1)), is(true));
+ assertThat(ts.offer(makeTraverser("a", 1)), is(false));
+ assertThat(ts.offer(makeTraverser("a", 1)), is(false));
+ assertThat(ts.offer(makeTraverser("a", 1)), is(false));
+ assertThat(ts.offer(makeTraverser("a", 1)), is(false));
+ assertThat(ts.offer(makeTraverser("a", 1)), is(false));
+ assertThat(ts.offer(makeTraverser("a", 1)), is(false));
+ assertThat(ts.offer(makeTraverser("b", 1)), is(true));
+
+ final Iterator<Traverser.Admin<String>> itty = ts.iterator();
+ final Traverser.Admin<String> a = itty.next();
+ assertEquals(7, a.bulk());
+ final Traverser.Admin<String> b = itty.next();
+ assertEquals(1, b.bulk());
+
+ assertThat(itty.hasNext(), is(false));
+ }
+
+ @Test(expected = FastNoSuchElementException.class)
+ public void shouldRemoveTraverserAndThrowBecauseEmpty() {
+ traverserSetMaker.get().remove();
+ }
+
+ @Test
+ public void shouldRemoveTraverser() {
+ final TraverserSet<String> ts = makeStringTraversers();
+ assertEquals(4, ts.size());
+ assertEquals(5, ts.bulkSize());
+ ts.remove();
+ assertEquals(3, ts.size());
+ assertEquals(3, ts.bulkSize());
+ }
+
+ private TraverserSet<String> makeStringTraversers() {
+ final TraverserSet<String> ts = traverserSetMaker.get();
+ ts.add(makeTraverser("a", 1));
+ ts.add(makeTraverser("a", 1));
+ ts.add(makeTraverser("b1", 1));
+ ts.add(makeTraverser("b2", 1));
+ ts.add(makeTraverser("c", 1));
+ return ts;
+ }
+
+ private <T> Traverser.Admin<T> makeTraverser(final T val, final long bulk) {
+ return new B_O_Traverser<>(val, bulk).asAdmin();
+ }
+}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/068bef85/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProgramTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProgramTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProgramTest.java
index c50109e..db76bbc 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProgramTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProgramTest.java
@@ -43,7 +43,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.TraversalSideEffects;
import org.apache.tinkerpop.gremlin.process.traversal.TraverserGenerator;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.BulkSet;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
-import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.VertexTraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.IndexedTraverserSet;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
import org.apache.tinkerpop.gremlin.process.traversal.util.EmptyTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.util.PureTraversal;
@@ -194,13 +194,11 @@ public abstract class ProgramTest extends AbstractGremlinProcessTest {
assertEquals(2, map.size());
assertTrue(map.values().contains(3l));
assertTrue(map.values().contains(1l));
- final VertexTraverserSet<Object> activeTraversers = new VertexTraverserSet<>();
+ final IndexedTraverserSet<Object,Vertex> activeTraversers = new IndexedTraverserSet.VertexIndexedTraverserSet();
map.keySet().forEach(vertex -> activeTraversers.add(this.haltedTraversers.peek().split(vertex, EmptyStep.instance())));
this.haltedTraversers.clear();
this.checkSideEffects();
memory.set(TraversalVertexProgram.ACTIVE_TRAVERSERS, activeTraversers);
-
-
}
@Override
@@ -319,4 +317,4 @@ public abstract class ProgramTest extends AbstractGremlinProcessTest {
assertEquals(4, bulkSet.get("java"));
}
}
-}
\ No newline at end of file
+}