Repository: tinkerpop Updated Branches: refs/heads/master e533b7911 -> 2ea9a66ac
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/master Commit: 068bef855c0f6c44a2ed71c1c8f4b18ad1e1dbdb Parents: 3e6e08a Author: Stephen Mallette <[email protected]> Authored: Tue Jan 23 16:16:40 2018 -0500 Committer: Stephen Mallette <[email protected]> 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 +}
