tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From spmalle...@apache.org
Subject [28/50] [abbrv] tinkerpop git commit: TINKERPOP-1870 Made VertexTraverserSet more generic to IndexedTraverserSet
Date Thu, 01 Feb 2018 15:30:39 GMT
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 <spmva@genoprime.com>
Authored: Tue Jan 23 16:16:40 2018 -0500
Committer: Stephen Mallette <spmva@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
+}


Mime
View raw message