This is an automated email from the ASF dual-hosted git repository.
Cole-Greer pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
The following commit(s) were added to refs/heads/master by this push:
new 065a6ae71e Make Tree no longer extend HashMap (#3448)
065a6ae71e is described below
commit 065a6ae71e829fc68ada44f61b7d0a19f20e5bc9
Author: Guian Gumpac <[email protected]>
AuthorDate: Mon Jun 15 11:25:52 2026 -0700
Make Tree no longer extend HashMap (#3448)
Changes Tree from extends HashMap<T, Tree<T>> to a final class that
holds a Map internally and exposes a tree-shaped public API. Tree is no
longer a Map, which removes inherited Map methods whose behavior did not
align with tree semantics (e.g. size() returned root-entry count, not total
nodes; containsKey only checked immediate children).
Per the dev-list discussion:
https://lists.apache.org/thread/o0nqh6kmrkdht531655p351ldjll045d
This is a breaking change targeted at TinkerPop 4.0.0.
Changes:
Tree now exposes:
- Navigation: rootNodes(), childAt(key) (throws if absent), hasChild(key),
contains(value) (recursive), findSubtree(key) (recursive, Optional),
getOrCreateChild(key) (construction primitive).
- Structure: isLeaf(), nodeCount(), getNodesAtDepth(int),
getTreesAtDepth(int), getLeafNodes(), getLeafTrees().
- Composition/output: addTree(), splitParents(), prettyPrint(),
structural equals/hashCode/toString.
Behavior fixes that fall out of the rewrite:
- isLeaf() returns true on an empty tree instead of throwing.
- getNodesAtDepth(0) returns the root nodes (now 0-based).
Internal callers migrated off the removed Map surface:
- TreeStep / TreeSideEffectStep use getOrCreateChild during construction.
- GraphBinary TreeSerializer and GraphSON TreeJacksonSerializer/
Deserializer (V1–V4) iterate via rootNodes()/childAt() and rebuild via
getOrCreateChild() + addTree().
- DetachedFactory / ReferenceFactory gained an explicit Tree branch
(previously handled via the instanceof Map path).
Breaking changes
- Code treating a Tree as a Map (assignment to Map, instanceof Map,
get/put/keySet/entrySet/size) no longer compiles.
- Gremlin patterns that worked only because Tree was a Map (select(keys),
count(local), unfold() on a tree) no longer compose; process the result
client-side after next() or reshape the upstream traversal.
Speed and Memory
Analytical estimates (not benchmarked); the backing HashMap table and
entries
are identical before and after.
- Memory: ~16 B more per node — Tree now holds a HashMap instead of
being one, adding one wrapper object per node. The map itself is
unchanged.
- Speed: comparable. Construction is slightly faster (getOrCreateChild is
1–2 map ops vs. the old 3); childAt is one op slower (collapsible to
one).
Wire-format encoding is unchanged.
Testing
- TreeTest rewritten against the new API (navigation, recursive
containment/search, depth queries, leaf detection, null keys, structural
equality, toString, pretty-print); TreeSupplierTest updated.
Assisted-by: Kiro: Claude Opus 4.8
---
CHANGELOG.asciidoc | 3 +
docs/src/reference/the-traversal.asciidoc | 17 +-
docs/src/upgrade/release-4.x.x.asciidoc | 54 ++++
.../process/traversal/step/map/CountLocalStep.java | 4 +-
.../process/traversal/step/map/TreeStep.java | 4 +-
.../step/sideEffect/TreeSideEffectStep.java | 4 +-
.../gremlin/process/traversal/step/util/Tree.java | 285 ++++++++++++++++-----
.../structure/io/binary/types/TreeSerializer.java | 11 +-
.../io/graphson/GraphSONSerializersV1.java | 14 +-
.../io/graphson/GraphSONSerializersV2.java | 15 +-
.../io/graphson/GraphSONSerializersV3.java | 14 +-
.../io/graphson/GraphSONSerializersV4.java | 14 +-
.../structure/io/gryo/GryoSerializersV1.java | 25 ++
.../structure/io/gryo/GryoSerializersV3.java | 25 ++
.../gremlin/structure/io/gryo/GryoVersion.java | 4 +-
.../structure/util/detached/DetachedFactory.java | 16 +-
.../structure/util/reference/ReferenceFactory.java | 16 +-
.../traversal/step/map/CountLocalStepTest.java | 34 +++
.../process/traversal/step/util/TreeTest.java | 251 ++++++++++++++----
.../gremlin/util/function/TreeSupplierTest.java | 4 +-
.../gremlin/groovy/loaders/SugarLoader.groovy | 13 +
.../gremlin/groovy/TreeSubscriptTest.groovy | 68 +++++
.../tinkerpop/gremlin/features/StepDefinition.java | 14 +-
.../gremlin/test/features/sideEffect/Tree.feature | 20 +-
.../gremlin/util/ser/AbstractRoundTripTest.java | 8 +-
.../ser/binary/TypeSerializerFailureTests.java | 2 +-
26 files changed, 749 insertions(+), 190 deletions(-)
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 097aacb7c5..594070c05c 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -27,6 +27,9 @@
image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
* Added configurable CORS `allowedOrigins` setting to Gremlin Server; warns
when wildcard origin is used alongside authentication.
* Fixed `ByteBuf` leak in `GraphBinaryMessageSerializerV4` when serialization
throws an `IOException`.
+* Changed `Tree` to no longer extend `HashMap`; it is now a final class with a
tree-shaped API (`childAt`, `hasChild`, `contains`, `findSubtree`,
`getOrCreateChild`, `getNodesAtDepth`, `getLeafNodes`, `nodeCount`) and is no
longer a `Map`.
+* Changed `count(local)` on a `Tree` to return the total node count
(`Tree.nodeCount()`) instead of the root-entry count.
+* Changed Tree class in Java to not extend from HashMap and offered a new
tree-shaped API for navigation.
* Added typed numeric wrappers and `preciseNumbers` connection option to
`gremlin-javascript` for explicit control over numeric type serialization and
deserialization.
* Added `NextN(n)` to `Traversal` in `gremlin-go` for batched result
iteration, providing API parity with `next(n)` in the Java, Python, and .NET
GLVs, and updated the Go translators in `gremlin-core` and `gremlin-javascript`
to emit `NextN(n)` for the batched form.
* Added Provider Defined Types (PDT) support — graph providers can define
custom types via `@ProviderDefined` annotation that serialize/deserialize
seamlessly across all GLVs without driver-side configuration. Replaces TP3
custom type mechanism.
diff --git a/docs/src/reference/the-traversal.asciidoc
b/docs/src/reference/the-traversal.asciidoc
index 75b7aba7b3..a2bc194fb6 100644
--- a/docs/src/reference/the-traversal.asciidoc
+++ b/docs/src/reference/the-traversal.asciidoc
@@ -1481,8 +1481,9 @@ g.V().hasLabel('person').outE('created').count().map
{it.get() * 10}.path() <2>
<1> `count()`-step is a <<a-note-on-barrier-steps,reducing barrier step>>
meaning that all of the previous traversers are folded into a new traverser.
<2> The path of the traverser emanating from `count()` starts at `count()`.
-IMPORTANT: `count(local)` counts the current, local object (not the objects in
the traversal stream). This works for
-`Collection`- and `Map`-type objects. For any other object, a count of 1 is
returned.
+IMPORTANT: `count(local)` counts the current, local object (not the objects in
the traversal stream). For a
+`Collection` it returns the number of elements, for a `Map` the number of
entries, for a `Path` the number of
+objects in the path, and for a `Tree` the total number of nodes in the tree.
For any other object, a count of 1 is returned.
*Additional References*
@@ -5156,14 +5157,17 @@ It is important to see how the paths of all the
emanating traversers are united
image::tree-step2.png[width=500]
-The resultant tree data structure can then be manipulated (see `Tree` JavaDoc).
+The resultant tree data structure can then be navigated with its tree-shaped
API such as `childAt()`, `findSubtree()`, `getNodesAtDepth()`, and
`getLeafNodes()` (see `Tree` JavaDoc).
[gremlin-groovy,modern]
----
tree = g.V().out().out().tree().by('name').next()
+tree.childAt('marko')
+tree.childAt('marko').childAt('josh')
+tree.getNodesAtDepth(2)
+// The sugar plugin offer convenience accessors
tree['marko']
tree['marko']['josh']
-tree.getObjectsAtDepth(3)
----
Note that when using `by()`-modulation, tree nodes are combined based on
projection uniqueness, not on the
@@ -5179,6 +5183,11 @@ g.V().has('name','josh').out('created').values('name').
<1> When the `tree()` is created, vertex 3 and 5 are unique and thus, form
unique branches in the tree structure.
<2> When the `tree()` is `by()`-modulated by `label`, then vertex 3 and 5 are
both "software" and thus are merged to a single node in the tree.
+NOTE: A `Tree` keys its children by node value, so sibling branches that
resolve to the same value (whether the
+original objects or a `by()`-projection) collapse into a single node. This
means structure can be lost when distinct
+paths share a value at the same depth. If every path must be preserved, use
`path()`; if a queryable result that
+retains element identity, cycles, and parallel edges is required, use
`subgraph()`.
+
The `tree()` step can also take a side-effect key as an argument. When using
this form, the `Tree` is is built up in a
side-effect as each traverser passes through. The `Tree` can later be accessed
by either `select()` or `cap()`.
diff --git a/docs/src/upgrade/release-4.x.x.asciidoc
b/docs/src/upgrade/release-4.x.x.asciidoc
index c5c45a284e..b2a3bdf09e 100644
--- a/docs/src/upgrade/release-4.x.x.asciidoc
+++ b/docs/src/upgrade/release-4.x.x.asciidoc
@@ -635,6 +635,41 @@ effort to the old custom serializer approach but is
entirely optional for basic
* <<gremlin-go-pdt,Gremlin-Go>>
+==== Tree No Longer Extends HashMap
+
+`Tree` no longer extends `HashMap`. It is now a `final` class that holds a
`Map` internally and exposes a
+tree-shaped API instead of `Map` methods. This is a breaking change for code
that treated a `tree()` result as a
+`Map`.
+
+Replacements for the common `Map`-based access patterns:
+
+[options="header"]
+|=======================
+|3.x (`Tree` as `Map`) |4.x (`Tree` API)
+|`tree.get(key)` |`tree.childAt(key)` (throws if absent) or
`tree.findSubtree(key)` (recursive, returns `Optional`)
+|`tree.containsKey(key)` |`tree.hasChild(key)`
+|`tree.keySet()` |`tree.rootNodes()`
+|`tree.size()` |`tree.rootNodes().size()` for root entries, or
`tree.nodeCount()` for total nodes
+|`getObjectsAtDepth(d)` |`getNodesAtDepth(d)` (now 0-based: depth 0 returns
the roots)
+|`getLeafObjects()` |`getLeafNodes()`
+|=======================
+
+A few Gremlin patterns that worked only because `Tree` was a `Map` (for
example `select(keys)` and `unfold()`
+applied to a `Tree`) no longer compose. Process the `Tree` result client-side
after `next()`, or reshape the
+upstream traversal.
+
+`count(local)` on a `Tree` has changed semantics. Previously, because `Tree`
was a `Map`, it returned the
+number of root entries; it now returns the total number of nodes in the tree
(`Tree.nodeCount()`), consistent
+with how `count(local)` counts the contents of other local objects (for
example the objects in a `Path`). Use
+`rootNodes().size()` on the materialized `Tree` if the root-entry count is
required.
+
+`isLeaf()` no longer throws on an empty tree (it returns `true`), and a `Tree`
keeps the long-standing limitation
+that sibling branches resolving to the same value collapse into one node; use
`path()` or `subgraph()` when full
+path structure must be preserved.
+
+See:
link:https://lists.apache.org/thread/o0nqh6kmrkdht531655p351ldjll045d[[DISCUSS]
Make Tree no longer extend HashMap]
+
+
=== Upgrading for Providers
==== Graph System Providers
@@ -654,6 +689,25 @@ benefiting all driver users transparently.
See <<provider-defined-types>> for full details on annotation usage, field
filtering, nested types, and ServiceLoader
registration.
+`Tree` no longer extends `HashMap`. Provider code that inspected or rebuilt a
`Tree` via `Map` methods
+(`get`, `put`, `keySet`, `entrySet`, `size`) must use the tree-shaped API
instead: read with `rootNodes()` +
+`childAt(key)` and build with `getOrCreateChild(key)` + `addTree(subtree)`.
The GraphSON (`g:Tree`) and
+GraphBinary (`0x2b`) wire formats are unchanged, so no GraphSON- or
GraphBinary-serialized data or cross-version
+===== Tree Serialization and API Changes
+
+`Tree` no longer extends `HashMap`.
+
+Providers that use the reference (de)serializers receive a `Tree` instance
from TinkerPop. Code that inspected or
+rebuilt that `Tree` via `Map` methods (`get`, `put`, `keySet`, `entrySet`,
`size`) must use the tree-shaped API
+instead: read with `rootNodes()` + `childAt(key)` and build with
`getOrCreateChild(key)` + `addTree(subtree)`.
+
+The GraphSON (`g:Tree`) and GraphBinary (`0x2b`) wire formats are unchanged,
so no GraphSON- or GraphBinary-serialized data or cross-version
+compatibility is affected. The Gryo `Tree` wire format, however, did change:
in 3.x a `Tree` was serialized via
+Kryo's default `Map` serializer because it extended `HashMap`, whereas in 4.x
it has an explicit `Tree`
+serializer. As a result, Gryo-serialized `Tree` data written by 3.x cannot be
read by 4.x and vice versa. The
+Gryo type registration id (`61`) is unchanged and 4.x-to-4.x Gryo round-trips
correctly; this Gryo break is
+expected for the 4.0.0 major release.
+
==== Graph Driver Providers
===== Request Interceptors
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/CountLocalStep.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/CountLocalStep.java
index 8fb2b5c0f8..912150ffbb 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/CountLocalStep.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/CountLocalStep.java
@@ -21,6 +21,7 @@ package
org.apache.tinkerpop.gremlin.process.traversal.step.map;
import org.apache.tinkerpop.gremlin.process.traversal.Path;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Tree;
import
org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
@@ -42,7 +43,8 @@ public final class CountLocalStep<S> extends ScalarMapStep<S,
Long> {
@Override
protected Long map(final Traverser.Admin<S> traverser) {
final S item = traverser.get();
- return (item instanceof Collection) ? ((Collection) item).size()
+ return (item instanceof Tree) ? ((Tree) item).nodeCount()
+ : (item instanceof Collection) ? ((Collection) item).size()
: (item instanceof Map) ? ((Map) item).size()
: (item instanceof Path) ? ((Path) item).size()
: IteratorUtils.count(IteratorUtils.asIterator(item));
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java
index 930d2d8a55..ecc26e9695 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java
@@ -85,9 +85,7 @@ public final class TreeStep<S> extends ReducingBarrierStep<S,
Tree> implements T
final TraversalProduct product =
TraversalUtil.produce(path.<Object>get(i), this.traversalRing.next());
if (product.isProductive()) {
final Object object = product.get();
- if (!depth.containsKey(object))
- depth.put(object, new Tree<>());
- depth = (Tree) depth.get(object);
+ depth = depth.getOrCreateChild(object);
}
}
this.traversalRing.reset();
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java
index 60f4f0b1ef..dd2f171cb4 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java
@@ -61,9 +61,7 @@ public final class TreeSideEffectStep<S> extends
SideEffectBarrierStep<S> implem
final Path path = traverser.path();
for (int i = 0; i < path.size(); i++) {
final Object object =
TraversalUtil.applyNullable(path.<Object>get(i), this.traversalRing.next());
- if (!depth.containsKey(object))
- depth.put(object, new Tree<>());
- depth = (Tree) depth.get(object);
+ depth = depth.getOrCreateChild(object);
}
this.traversalRing.reset();
this.getTraversal().getSideEffects().add(this.sideEffectKey, root);
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Tree.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Tree.java
index 71ece42241..aa64f0df7f 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Tree.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Tree.java
@@ -20,125 +20,250 @@ package
org.apache.tinkerpop.gremlin.process.traversal.step.util;
import java.io.Serializable;
import java.util.ArrayList;
-import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
/**
+ * A tree data structure with a tree-shaped public API.
+ * <p>
+ * Iteration order over the nodes at a given level is not promised. Because
children are keyed by node value,
+ * sibling branches that resolve to the same value are represented as a single
node; callers that require every
+ * path to be preserved should use {@link
org.apache.tinkerpop.gremlin.process.traversal.Path} instead.
+ *
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
-public class Tree<T> extends HashMap<T, Tree<T>> implements Serializable {
+public final class Tree<T> implements Serializable {
+
+ private final Map<T, Tree<T>> children = new HashMap<>();
public Tree() {
- super();
}
+ /**
+ * Creates a tree with the given values as root keys, each mapping to an
empty {@link Tree}.
+ */
@SafeVarargs
- public Tree(final T... children) {
- this();
- for (final T t : children) {
- this.put(t, new Tree<>());
+ public Tree(final T... rootValues) {
+ for (final T t : rootValues) {
+ this.children.put(t, new Tree<>());
}
}
- @SafeVarargs
- public Tree(final Map.Entry<T, Tree<T>>... children) {
- this();
- for (final Map.Entry<T, Tree<T>> entry : children) {
- this.put(entry.getKey(), entry.getValue());
+ // ------------------------------------------------------------------
+ // navigation
+ // ------------------------------------------------------------------
+
+ /**
+ * Returns the set of keys at the root of this tree. The returned set is
unmodifiable.
+ */
+ public Set<T> rootNodes() {
+ return Collections.unmodifiableSet(this.children.keySet());
+ }
+
+ /**
+ * Returns the child subtree for the given key.
+ *
+ * @throws IllegalArgumentException if no child exists for the given key
+ */
+ public Tree<T> childAt(final T key) {
+ if (!this.children.containsKey(key)) {
+ throw new IllegalArgumentException("Tree has no child for key: " +
key);
}
+ return this.children.get(key);
}
+ /**
+ * Returns {@code true} if the given key is an immediate child of this
tree.
+ */
+ public boolean hasChild(final T key) {
+ return this.children.containsKey(key);
+ }
- public List<Tree<T>> getTreesAtDepth(final int depth) {
- List<Tree<T>> currentDepth = Collections.singletonList(this);
- for (int i = 0; i < depth; i++) {
- if (i == depth - 1) {
- return currentDepth;
- } else {
- final List<Tree<T>> temp = new ArrayList<Tree<T>>();
- for (final Tree<T> t : currentDepth) {
- temp.addAll(t.values());
- }
- currentDepth = temp;
+ /**
+ * Returns {@code true} if the given value appears as a key anywhere in
this tree (recursive).
+ */
+ public boolean contains(final T value) {
+ if (this.children.containsKey(value)) {
+ return true;
+ }
+ for (final Tree<T> sub : this.children.values()) {
+ if (sub.contains(value)) {
+ return true;
}
}
- return Collections.emptyList();
+ return false;
+ }
+
+ /**
+ * Recursively searches the tree for the first subtree rooted at {@code
key} and returns it. The search visits
+ * direct children first and then recurses, but iteration order across
siblings is unspecified.
+ */
+ public Optional<Tree<T>> findSubtree(final T key) {
+ if (this.children.containsKey(key)) {
+ return Optional.of(this.children.get(key));
+ }
+ for (final Tree<T> sub : this.children.values()) {
+ final Optional<Tree<T>> found = sub.findSubtree(key);
+ if (found.isPresent()) {
+ return found;
+ }
+ }
+ return Optional.empty();
+ }
+
+ /**
+ * Returns the existing child for {@code key}, or inserts and returns a
new empty {@link Tree} if absent.
+ */
+ public Tree<T> getOrCreateChild(final T key) {
+ Tree<T> child = this.children.get(key);
+ if (null == child) {
+ child = new Tree<>();
+ this.children.put(key, child);
+ }
+ return child;
+ }
+
+ // ------------------------------------------------------------------
+ // structural
+ // ------------------------------------------------------------------
+
+ /**
+ * Returns {@code true} if this tree has no children. An empty tree is
considered a leaf.
+ */
+ public boolean isLeaf() {
+ return this.children.isEmpty();
+ }
+
+ /**
+ * Returns the total number of nodes (keys) in the tree, counted
recursively.
+ */
+ public int nodeCount() {
+ int count = this.children.size();
+ for (final Tree<T> sub : this.children.values()) {
+ count += sub.nodeCount();
+ }
+ return count;
}
- public List<T> getObjectsAtDepth(final int depth) {
- final List<T> list = new ArrayList<T>();
+ /**
+ * Returns the keys at the given depth. Depth {@code 0} returns the root
keys.
+ */
+ public List<T> getNodesAtDepth(final int depth) {
+ final List<T> list = new ArrayList<>();
for (final Tree<T> t : this.getTreesAtDepth(depth)) {
- list.addAll(t.keySet());
+ list.addAll(t.children.keySet());
}
return list;
}
- public List<Tree<T>> getLeafTrees() {
- final List<Tree<T>> leaves = new ArrayList<>();
+ /**
+ * Returns the trees at the given depth. Depth {@code 0} returns a
singleton list containing this tree.
+ * Depths beyond the tree's height return an empty list.
+ */
+ public List<Tree<T>> getTreesAtDepth(final int depth) {
+ if (depth < 0) {
+ return Collections.emptyList();
+ }
List<Tree<T>> currentDepth = Collections.singletonList(this);
- boolean allLeaves = false;
- while (!allLeaves) {
- allLeaves = true;
- final List<Tree<T>> temp = new ArrayList<>();
+ for (int i = 0; i < depth; i++) {
+ final List<Tree<T>> next = new ArrayList<>();
for (final Tree<T> t : currentDepth) {
- if (t.isLeaf()) {
- for (Map.Entry<T, Tree<T>> t2 : t.entrySet()) {
- leaves.add(new Tree<T>(t2));
- }
- } else {
- allLeaves = false;
- temp.addAll(t.values());
- }
+ next.addAll(t.children.values());
}
- currentDepth = temp;
-
+ if (next.isEmpty()) {
+ return Collections.emptyList();
+ }
+ currentDepth = next;
}
+ return currentDepth;
+ }
+
+ /**
+ * Returns all keys whose subtrees are leaves.
+ */
+ public List<T> getLeafNodes() {
+ final List<T> leaves = new ArrayList<>();
+ collectLeafKeys(leaves);
return leaves;
}
- public List<T> getLeafObjects() {
- final List<T> leaves = new ArrayList<T>();
- for (final Tree<T> t : this.getLeafTrees()) {
- leaves.addAll(t.keySet());
+ private void collectLeafKeys(final List<T> out) {
+ for (final Map.Entry<T, Tree<T>> entry : this.children.entrySet()) {
+ if (entry.getValue().isLeaf()) {
+ out.add(entry.getKey());
+ } else {
+ entry.getValue().collectLeafKeys(out);
+ }
}
- return leaves;
}
- public boolean isLeaf() {
- final Collection<Tree<T>> values = this.values();
- return values.iterator().next().isEmpty();
+ /**
+ * Returns single-key trees representing each leaf key in this tree,
preserving the original
+ * key-to-empty-subtree mapping.
+ */
+ public List<Tree<T>> getLeafTrees() {
+ final List<Tree<T>> leaves = new ArrayList<>();
+ collectLeafTrees(leaves);
+ return leaves;
+ }
+ private void collectLeafTrees(final List<Tree<T>> out) {
+ for (final Map.Entry<T, Tree<T>> entry : this.children.entrySet()) {
+ if (entry.getValue().isLeaf()) {
+ final Tree<T> leaf = new Tree<>();
+ leaf.children.put(entry.getKey(), entry.getValue());
+ out.add(leaf);
+ } else {
+ entry.getValue().collectLeafTrees(out);
+ }
+ }
}
- public void addTree(final Tree<T> tree) {
- tree.forEach((k, t) -> {
- if (this.containsKey(k)) {
- this.get(k).addTree(t);
+ // ------------------------------------------------------------------
+ // composition
+ // ------------------------------------------------------------------
+
+ /**
+ * Recursively merges {@code other} into this tree. For overlapping keys,
child subtrees are merged in turn.
+ * For keys present only in {@code other}, the corresponding subtree
reference is adopted directly.
+ */
+ public void addTree(final Tree<T> other) {
+ other.children.forEach((k, t) -> {
+ if (this.children.containsKey(k)) {
+ this.children.get(k).addTree(t);
} else {
- this.put(k, t);
+ this.children.put(k, t);
}
});
}
+ /**
+ * Splits this tree into one tree per root key. If the tree has a single
root, returns a singleton list
+ * containing this tree.
+ */
public List<Tree<T>> splitParents() {
- if (this.keySet().size() == 1) {
+ if (this.children.size() == 1) {
return Collections.singletonList(this);
- } else {
- final List<Tree<T>> parents = new ArrayList<>();
- this.forEach((k, t) -> {
- final Tree<T> parentTree = new Tree<>();
- parentTree.put(k, t);
- parents.add(parentTree);
- });
- return parents;
}
+ final List<Tree<T>> parents = new ArrayList<>();
+ this.children.forEach((k, t) -> {
+ final Tree<T> parentTree = new Tree<>();
+ parentTree.children.put(k, t);
+ parents.add(parentTree);
+ });
+ return parents;
}
+ // ------------------------------------------------------------------
+ // output
+ // ------------------------------------------------------------------
+
/**
- * Produce a formatted string representation of the tree structure.
+ * Produces a formatted string representation of the tree structure using
a {@code |--} ASCII style.
*/
public String prettyPrint() {
final StringBuilder builder = new StringBuilder();
@@ -148,10 +273,36 @@ public class Tree<T> extends HashMap<T, Tree<T>>
implements Serializable {
}
private void prettyPrint(final StringBuilder builder, final String prefix)
{
- for (Map.Entry<T, Tree<T>> entry : this.entrySet()) {
+ for (final Map.Entry<T, Tree<T>> entry : this.children.entrySet()) {
builder.append(prefix).append("|--").append(entry.getKey());
builder.append(System.lineSeparator());
entry.getValue().prettyPrint(builder, prefix + " ");
}
}
+
+ // ------------------------------------------------------------------
+ // identity
+ // ------------------------------------------------------------------
+
+ /**
+ * Structural recursive equality. Order across siblings is irrelevant; two
trees are equal if they have the
+ * same set of keys and each key's subtree is recursively equal.
+ */
+ @Override
+ public boolean equals(final Object other) {
+ if (this == other) return true;
+ if (!(other instanceof Tree)) return false;
+ final Tree<?> that = (Tree<?>) other;
+ return this.children.equals(that.children);
+ }
+
+ @Override
+ public int hashCode() {
+ return this.children.hashCode();
+ }
+
+ @Override
+ public String toString() {
+ return this.children.toString();
+ }
}
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/binary/types/TreeSerializer.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/binary/types/TreeSerializer.java
index 5aab638812..dcce24a7ea 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/binary/types/TreeSerializer.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/binary/types/TreeSerializer.java
@@ -37,7 +37,9 @@ public class TreeSerializer extends
SimpleTypeSerializer<Tree> {
final Tree result = new Tree();
for (int i = 0; i < length; i++) {
- result.put(context.read(buffer), context.readValue(buffer,
Tree.class, false));
+ final Object key = context.read(buffer);
+ final Tree value = context.readValue(buffer, Tree.class, false);
+ result.getOrCreateChild(key).addTree(value);
}
return result;
@@ -45,11 +47,12 @@ public class TreeSerializer extends
SimpleTypeSerializer<Tree> {
@Override
protected void writeValue(final Tree value, final Buffer buffer, final
GraphBinaryWriter context) throws IOException {
- buffer.writeInt(value.size());
+ final java.util.Set<Object> rootNodes = value.rootNodes();
+ buffer.writeInt(rootNodes.size());
- for (Object key : value.keySet()) {
+ for (final Object key : rootNodes) {
context.write(key, buffer);
- context.writeValue(value.get(key), buffer, false);
+ context.writeValue(value.childAt(key), buffer, false);
}
}
}
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV1.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV1.java
index 4841b482b4..db4d4a8d60 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV1.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV1.java
@@ -50,7 +50,6 @@ import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
-import java.util.Set;
import java.util.concurrent.TimeUnit;
/**
@@ -284,14 +283,13 @@ final class GraphSONSerializersV1 {
throws IOException {
jsonGenerator.writeStartObject();
if (typeSerializer != null)
jsonGenerator.writeStringField(GraphSONTokens.CLASS, HashMap.class.getName());
-
- Set<Map.Entry<Element, Tree>> set = tree.entrySet();
- for(Map.Entry<Element, Tree> entry : set)
- {
-
jsonGenerator.writeObjectFieldStart(entry.getKey().id().toString());
+
+ for (final Object key : tree.rootNodes()) {
+ final Element elementKey = (Element) key;
+
jsonGenerator.writeObjectFieldStart(elementKey.id().toString());
if (typeSerializer != null)
jsonGenerator.writeStringField(GraphSONTokens.CLASS, HashMap.class.getName());
- jsonGenerator.writeObjectField(GraphSONTokens.KEY,
entry.getKey());
- jsonGenerator.writeObjectField(GraphSONTokens.VALUE,
entry.getValue());
+ jsonGenerator.writeObjectField(GraphSONTokens.KEY, elementKey);
+ jsonGenerator.writeObjectField(GraphSONTokens.VALUE,
tree.childAt(key));
jsonGenerator.writeEndObject();
}
jsonGenerator.writeEndObject();
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV2.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV2.java
index 8b52323c94..c3113ebfe4 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV2.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV2.java
@@ -68,7 +68,6 @@ import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
-import java.util.Set;
import java.util.concurrent.TimeUnit;
import static
org.apache.tinkerpop.gremlin.structure.io.graphson.GraphSONUtil.safeWriteObjectField;
@@ -282,11 +281,10 @@ class GraphSONSerializersV2 {
@Override
public void serialize(final Tree tree, final JsonGenerator
jsonGenerator, final SerializerProvider serializerProvider) throws IOException,
JsonGenerationException {
jsonGenerator.writeStartArray();
- final Set<Map.Entry<Element, Tree>> set = tree.entrySet();
- for (Map.Entry<Element, Tree> entry : set) {
+ for (final Object key : tree.rootNodes()) {
jsonGenerator.writeStartObject();
- jsonGenerator.writeObjectField(GraphSONTokens.KEY,
entry.getKey());
- jsonGenerator.writeObjectField(GraphSONTokens.VALUE,
entry.getValue());
+ jsonGenerator.writeObjectField(GraphSONTokens.KEY, key);
+ jsonGenerator.writeObjectField(GraphSONTokens.VALUE,
tree.childAt(key));
jsonGenerator.writeEndObject();
}
jsonGenerator.writeEndArray();
@@ -692,7 +690,12 @@ class GraphSONSerializersV2 {
final List<Map> data =
deserializationContext.readValue(jsonParser, List.class);
final Tree t = new Tree();
for (Map<String, Object> entry : data) {
- t.put(entry.get(GraphSONTokens.KEY),
entry.get(GraphSONTokens.VALUE));
+ final Object key = entry.get(GraphSONTokens.KEY);
+ final Object value = entry.get(GraphSONTokens.VALUE);
+ final Tree child = t.getOrCreateChild(key);
+ if (value instanceof Tree) {
+ child.addTree((Tree) value);
+ }
}
return t;
}
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV3.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV3.java
index 6df9141f5b..b6761dc529 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV3.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV3.java
@@ -303,11 +303,10 @@ class GraphSONSerializersV3 {
@Override
public void serialize(final Tree tree, final JsonGenerator
jsonGenerator, final SerializerProvider serializerProvider) throws IOException,
JsonGenerationException {
jsonGenerator.writeStartArray();
- final Set<Map.Entry<Element, Tree>> set = tree.entrySet();
- for (Map.Entry<Element, Tree> entry : set) {
+ for (final Object key : tree.rootNodes()) {
jsonGenerator.writeStartObject();
- jsonGenerator.writeObjectField(GraphSONTokens.KEY,
entry.getKey());
- jsonGenerator.writeObjectField(GraphSONTokens.VALUE,
entry.getValue());
+ jsonGenerator.writeObjectField(GraphSONTokens.KEY, key);
+ jsonGenerator.writeObjectField(GraphSONTokens.VALUE,
tree.childAt(key));
jsonGenerator.writeEndObject();
}
jsonGenerator.writeEndArray();
@@ -730,7 +729,12 @@ class GraphSONSerializersV3 {
final List<Map> data =
deserializationContext.readValue(jsonParser, List.class);
final Tree t = new Tree();
for (Map<String, Object> entry : data) {
- t.put(entry.get(GraphSONTokens.KEY),
entry.get(GraphSONTokens.VALUE));
+ final Object key = entry.get(GraphSONTokens.KEY);
+ final Object value = entry.get(GraphSONTokens.VALUE);
+ final Tree child = t.getOrCreateChild(key);
+ if (value instanceof Tree) {
+ child.addTree((Tree) value);
+ }
}
return t;
}
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV4.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV4.java
index 66361a0f05..d68458b671 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV4.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV4.java
@@ -306,11 +306,10 @@ class GraphSONSerializersV4 {
@Override
public void serialize(final Tree tree, final JsonGenerator
jsonGenerator, final SerializerProvider serializerProvider) throws IOException,
JsonGenerationException {
jsonGenerator.writeStartArray();
- final Set<Map.Entry<Element, Tree>> set = tree.entrySet();
- for (Map.Entry<Element, Tree> entry : set) {
+ for (final Object key : tree.rootNodes()) {
jsonGenerator.writeStartObject();
- jsonGenerator.writeObjectField(GraphSONTokens.KEY,
entry.getKey());
- jsonGenerator.writeObjectField(GraphSONTokens.VALUE,
entry.getValue());
+ jsonGenerator.writeObjectField(GraphSONTokens.KEY, key);
+ jsonGenerator.writeObjectField(GraphSONTokens.VALUE,
tree.childAt(key));
jsonGenerator.writeEndObject();
}
jsonGenerator.writeEndArray();
@@ -581,7 +580,12 @@ class GraphSONSerializersV4 {
final List<Map> data =
deserializationContext.readValue(jsonParser, List.class);
final Tree t = new Tree();
for (Map<String, Object> entry : data) {
- t.put(entry.get(GraphSONTokens.KEY),
entry.get(GraphSONTokens.VALUE));
+ final Object key = entry.get(GraphSONTokens.KEY);
+ final Object value = entry.get(GraphSONTokens.VALUE);
+ final Tree child = t.getOrCreateChild(key);
+ if (value instanceof Tree) {
+ child.addTree((Tree) value);
+ }
}
return t;
}
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoSerializersV1.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoSerializersV1.java
index 6e73125054..27cd177efd 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoSerializersV1.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoSerializersV1.java
@@ -23,6 +23,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.P;
import org.apache.tinkerpop.gremlin.process.traversal.Path;
import org.apache.tinkerpop.gremlin.process.traversal.Text;
import org.apache.tinkerpop.gremlin.process.traversal.TextP;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Tree;
import org.apache.tinkerpop.gremlin.process.traversal.util.AndP;
import org.apache.tinkerpop.gremlin.process.traversal.util.ConnectiveP;
import org.apache.tinkerpop.gremlin.process.traversal.util.OrP;
@@ -264,4 +265,28 @@ public final class GryoSerializersV1 {
return new DefaultRemoteTraverser<>(o, input.readLong());
}
}
+
+ public final static class TreeSerializer implements SerializerShim<Tree> {
+ @Override
+ public <O extends OutputShim> void write(final KryoShim<?, O> kryo,
final O output, final Tree tree) {
+ final java.util.Set keys = tree.rootNodes();
+ output.writeInt(keys.size());
+ for (final Object key : keys) {
+ kryo.writeClassAndObject(output, key);
+ this.write(kryo, output, (Tree) tree.childAt(key));
+ }
+ }
+
+ @Override
+ public <I extends InputShim> Tree read(final KryoShim<I, ?> kryo,
final I input, final Class<Tree> clazz) {
+ final Tree tree = new Tree();
+ final int size = input.readInt();
+ for (int i = 0; i < size; i++) {
+ final Object key = kryo.readClassAndObject(input);
+ final Tree child = this.read(kryo, input, clazz);
+ tree.getOrCreateChild(key).addTree(child);
+ }
+ return tree;
+ }
+ }
}
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoSerializersV3.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoSerializersV3.java
index 5a0beec2ae..0b748813f5 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoSerializersV3.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoSerializersV3.java
@@ -23,6 +23,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.P;
import org.apache.tinkerpop.gremlin.process.traversal.Path;
import org.apache.tinkerpop.gremlin.process.traversal.Text;
import org.apache.tinkerpop.gremlin.process.traversal.TextP;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Tree;
import org.apache.tinkerpop.gremlin.process.traversal.util.AndP;
import org.apache.tinkerpop.gremlin.process.traversal.util.ConnectiveP;
import
org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalMetrics;
@@ -447,6 +448,30 @@ public final class GryoSerializersV3 {
}
}
+ public final static class TreeSerializer implements SerializerShim<Tree> {
+ @Override
+ public <O extends OutputShim> void write(final KryoShim<?, O> kryo,
final O output, final Tree tree) {
+ final java.util.Set keys = tree.rootNodes();
+ output.writeInt(keys.size());
+ for (final Object key : keys) {
+ kryo.writeClassAndObject(output, key);
+ this.write(kryo, output, (Tree) tree.childAt(key));
+ }
+ }
+
+ @Override
+ public <I extends InputShim> Tree read(final KryoShim<I, ?> kryo,
final I input, final Class<Tree> clazz) {
+ final Tree tree = new Tree();
+ final int size = input.readInt();
+ for (int i = 0; i < size; i++) {
+ final Object key = kryo.readClassAndObject(input);
+ final Tree child = this.read(kryo, input, clazz);
+ tree.getOrCreateChild(key).addTree(child);
+ }
+ return tree;
+ }
+ }
+
private static void writeElementProperties(final KryoShim kryo, final
OutputShim output, final Element element) {
final Iterator<? extends Property> properties = element.properties();
output.writeBoolean(properties.hasNext());
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 86f4edd1f0..dd05a5da70 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
@@ -381,7 +381,7 @@ public enum GryoVersion {
add(GryoTypeReg.of(ReservedKeysVerificationStrategy.class, 190));
add(GryoTypeReg.of(TraverserSet.class, 58));
- add(GryoTypeReg.of(Tree.class, 61));
+ add(GryoTypeReg.of(Tree.class, 61, new
GryoSerializersV3.TreeSerializer()));
add(GryoTypeReg.of(HashSet.class, 62));
add(GryoTypeReg.of(BulkSet.class, 64));
add(GryoTypeReg.of(Metrics.class, 69, new
GryoSerializersV3.MetricsSerializer()));
@@ -560,7 +560,7 @@ public enum GryoVersion {
add(GryoTypeReg.of(TraverserSet.class, 58));
- add(GryoTypeReg.of(Tree.class, 61));
+ add(GryoTypeReg.of(Tree.class, 61, new
GryoSerializersV1.TreeSerializer()));
add(GryoTypeReg.of(HashSet.class, 62));
add(GryoTypeReg.of(BulkSet.class, 64));
add(GryoTypeReg.of(MutableMetrics.class, 69));
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/detached/DetachedFactory.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/detached/DetachedFactory.java
index 0c9b17db98..8fbddf4550 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/detached/DetachedFactory.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/detached/DetachedFactory.java
@@ -106,11 +106,19 @@ public class DetachedFactory {
set.add(DetachedFactory.detach(item, withProperties));
}
return (D) set;
+ } else if (object instanceof Tree) {
+ final Tree newTree = new Tree();
+ final Tree<Object> sourceTree = (Tree<Object>) object;
+ for (final Object key : sourceTree.rootNodes()) {
+ final Object detachedKey = DetachedFactory.detach(key,
withProperties);
+ final Tree<Object> detachedSubtree = (Tree<Object>)
DetachedFactory.detach(sourceTree.childAt(key), withProperties);
+ newTree.getOrCreateChild(detachedKey).addTree(detachedSubtree);
+ }
+ return (D) newTree;
} else if (object instanceof Map) {
- final Map map = object instanceof Tree ? new Tree() :
- object instanceof LinkedHashMap ?
- new LinkedHashMap(((Map) object).size()) :
- new HashMap(((Map) object).size());
+ final Map map = object instanceof LinkedHashMap ?
+ new LinkedHashMap(((Map) object).size()) :
+ new HashMap(((Map) object).size());
for (final Map.Entry<Object, Object> entry : ((Map<Object,
Object>) object).entrySet()) {
map.put(DetachedFactory.detach(entry.getKey(),
withProperties), DetachedFactory.detach(entry.getValue(), withProperties));
}
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferenceFactory.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferenceFactory.java
index fa595311a0..63e746f8fe 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferenceFactory.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferenceFactory.java
@@ -102,11 +102,19 @@ public class ReferenceFactory {
set.add(ReferenceFactory.detach(item));
}
return (D) set;
+ } else if (object instanceof Tree) {
+ final Tree newTree = new Tree();
+ final Tree<Object> sourceTree = (Tree<Object>) object;
+ for (final Object key : sourceTree.rootNodes()) {
+ final Object detachedKey = ReferenceFactory.detach(key);
+ final Tree<Object> detachedSubtree = (Tree<Object>)
ReferenceFactory.detach(sourceTree.childAt(key));
+ newTree.getOrCreateChild(detachedKey).addTree(detachedSubtree);
+ }
+ return (D) newTree;
} else if (object instanceof Map) {
- final Map map = object instanceof Tree ? new Tree() :
- object instanceof LinkedHashMap ?
- new LinkedHashMap(((Map) object).size()) :
- new HashMap(((Map) object).size());
+ final Map map = object instanceof LinkedHashMap ?
+ new LinkedHashMap(((Map) object).size()) :
+ new HashMap(((Map) object).size());
for (final Map.Entry<Object, Object> entry : ((Map<Object,
Object>) object).entrySet()) {
map.put(ReferenceFactory.detach(entry.getKey()),
ReferenceFactory.detach(entry.getValue()));
}
diff --git
a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/CountLocalStepTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/CountLocalStepTest.java
index ce9a99fcd5..0126a366a7 100644
---
a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/CountLocalStepTest.java
+++
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/CountLocalStepTest.java
@@ -20,12 +20,18 @@ package
org.apache.tinkerpop.gremlin.process.traversal.step.map;
import org.apache.tinkerpop.gremlin.process.traversal.Scope;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
import org.apache.tinkerpop.gremlin.process.traversal.step.StepTest;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Tree;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_O_Traverser;
+import org.junit.Test;
import java.util.Collections;
import java.util.List;
+import static org.junit.Assert.assertEquals;
+
/**
* @author Daniel Kuppitz (http://gremlin.guru)
*/
@@ -35,4 +41,32 @@ public class CountLocalStepTest extends StepTest {
protected List<Traversal> getTraversals() {
return Collections.singletonList(__.count(Scope.local));
}
+
+ @Test
+ public void shouldCountTotalNodesOnTree() {
+ final Traversal.Admin<Object, Long> traversal =
__.<Object>count(Scope.local).asAdmin();
+ final CountLocalStep<Object> step = (CountLocalStep<Object>)
traversal.getSteps().get(0);
+
+ // tree: a -> b (two total nodes)
+ final Tree<String> tree = new Tree<>();
+ tree.getOrCreateChild("a").getOrCreateChild("b");
+ final Traverser.Admin<Object> traverser = new
B_O_Traverser<>(tree, 1L);
+
+ // count(local) on a Tree returns the total node count
(Tree.nodeCount()), not the root-entry count
+ assertEquals(Long.valueOf(2L), step.map(traverser));
+ }
+
+ @Test
+ public void shouldCountTotalNodesOnMultiRootTree() {
+ final Traversal.Admin<Object, Long> traversal =
__.<Object>count(Scope.local).asAdmin();
+ final CountLocalStep<Object> step = (CountLocalStep<Object>)
traversal.getSteps().get(0);
+
+ // tree with two roots and nested children: x -> x1, y (three
total nodes)
+ final Tree<String> tree = new Tree<>();
+ tree.getOrCreateChild("x").getOrCreateChild("x1");
+ tree.getOrCreateChild("y");
+ final Traverser.Admin<Object> traverser = new
B_O_Traverser<>(tree, 1L);
+
+ assertEquals(Long.valueOf(3L), step.map(traverser));
+ }
}
diff --git
a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/TreeTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/TreeTest.java
index 5bf6e43533..4e2710ecbb 100644
---
a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/TreeTest.java
+++
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/TreeTest.java
@@ -24,15 +24,17 @@ import
org.apache.tinkerpop.gremlin.process.traversal.step.StepTest;
import org.hamcrest.Matchers;
import org.junit.Test;
-import java.util.AbstractMap;
import java.util.Arrays;
import java.util.List;
-import java.util.Map;
+import java.util.Optional;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.fail;
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
@@ -40,69 +42,215 @@ import static org.junit.Assert.assertTrue;
*/
public class TreeTest extends StepTest {
+ /**
+ * Helper that builds a subtree shaped like {@code key -> subtree}.
+ */
+ private static <T> Tree<T> branch(final T key, final Tree<T> subtree) {
+ final Tree<T> wrapper = new Tree<>();
+ wrapper.getOrCreateChild(key).addTree(subtree);
+ return wrapper;
+ }
+
@Test
public void shouldProvideValidDepths() {
- Tree<String> tree = new Tree<String>();
- tree.put("marko", new Tree<String>(TreeTest.createTree("a", new
Tree<String>("a1", "a2")), TreeTest.createTree("b", new Tree<String>("b1",
"b2", "b3"))));
- tree.put("josh", new Tree<String>("1", "2"));
+ final Tree<String> tree = new Tree<>();
+ final Tree<String> markoSubtree = new Tree<>();
+ markoSubtree.addTree(branch("a", new Tree<>("a1", "a2")));
+ markoSubtree.addTree(branch("b", new Tree<>("b1", "b2", "b3")));
+ tree.getOrCreateChild("marko").addTree(markoSubtree);
+ tree.getOrCreateChild("josh").addTree(new Tree<>("1", "2"));
+
+ assertEquals(2, tree.getNodesAtDepth(0).size());
+ assertTrue(tree.getNodesAtDepth(0).containsAll(Arrays.asList("marko",
"josh")));
+ assertEquals(4, tree.getNodesAtDepth(1).size());
+ assertEquals(5, tree.getNodesAtDepth(2).size());
+ assertEquals(0, tree.getNodesAtDepth(3).size());
+ assertEquals(0, tree.getNodesAtDepth(4).size());
+ assertEquals(0, tree.getNodesAtDepth(5).size());
- assertEquals(0, tree.getObjectsAtDepth(0).size());
- assertEquals(2, tree.getObjectsAtDepth(1).size());
- assertEquals(4, tree.getObjectsAtDepth(2).size());
- assertEquals(5, tree.getObjectsAtDepth(3).size());
- assertEquals(0, tree.getObjectsAtDepth(4).size());
- assertEquals(0, tree.getObjectsAtDepth(5).size());
+ assertEquals(1, tree.getTreesAtDepth(0).size());
+ assertEquals(tree, tree.getTreesAtDepth(0).get(0));
- assertEquals(2, tree.get("josh").size());
- assertEquals(0, tree.get("marko").get("b").get("b1").size());
- assertEquals(3, tree.get("marko").get("b").size());
- assertNull(tree.get("marko").get("c"));
+ assertEquals(2, tree.childAt("josh").rootNodes().size());
+ assertTrue(tree.childAt("marko").childAt("b").childAt("b1").isLeaf());
+ assertEquals(3, tree.childAt("marko").childAt("b").rootNodes().size());
+ assertFalse(tree.childAt("marko").hasChild("c"));
}
@Test
public void shouldProvideValidLeaves() {
- Tree<String> tree = new Tree<String>();
- tree.put("marko", new Tree<String>(TreeTest.createTree("a", new
Tree<String>("a1", "a2")), TreeTest.createTree("b", new Tree<String>("b1",
"b2", "b3"))));
- tree.put("josh", new Tree<String>("1", "2"));
+ final Tree<String> tree = new Tree<>();
+ final Tree<String> markoSubtree = new Tree<>();
+ markoSubtree.addTree(branch("a", new Tree<>("a1", "a2")));
+ markoSubtree.addTree(branch("b", new Tree<>("b1", "b2", "b3")));
+ tree.getOrCreateChild("marko").addTree(markoSubtree);
+ tree.getOrCreateChild("josh").addTree(new Tree<>("1", "2"));
assertEquals(7, tree.getLeafTrees().size());
- for (Tree<String> t : tree.getLeafTrees()) {
- assertEquals(1, t.keySet().size());
- final String key = t.keySet().iterator().next();
+ for (final Tree<String> t : tree.getLeafTrees()) {
+ assertEquals(1, t.rootNodes().size());
+ final String key = t.rootNodes().iterator().next();
assertTrue(Arrays.asList("a1", "a2", "b1", "b2", "b3", "1",
"2").contains(key));
}
- assertEquals(7, tree.getLeafObjects().size());
- for (String s : tree.getLeafObjects()) {
+ assertEquals(7, tree.getLeafNodes().size());
+ for (final String s : tree.getLeafNodes()) {
assertTrue(Arrays.asList("a1", "a2", "b1", "b2", "b3", "1",
"2").contains(s));
}
}
@Test
public void shouldMergeTreesCorrectly() {
- Tree<String> tree1 = new Tree<>();
- tree1.put("1", new Tree<String>(TreeTest.createTree("1_1", new
Tree<String>("1_1_1")), TreeTest.createTree("1_2", new Tree<String>("1_2_1"))));
- Tree<String> tree2 = new Tree<>();
- tree2.put("1", new Tree<String>(TreeTest.createTree("1_1", new
Tree<String>("1_1_1")), TreeTest.createTree("1_2", new Tree<String>("1_2_2"))));
+ final Tree<String> tree1 = new Tree<>();
+ final Tree<String> tree1OneSubtree = new Tree<>();
+ tree1OneSubtree.addTree(branch("1_1", new Tree<>("1_1_1")));
+ tree1OneSubtree.addTree(branch("1_2", new Tree<>("1_2_1")));
+ tree1.getOrCreateChild("1").addTree(tree1OneSubtree);
+
+ final Tree<String> tree2 = new Tree<>();
+ final Tree<String> tree2OneSubtree = new Tree<>();
+ tree2OneSubtree.addTree(branch("1_1", new Tree<>("1_1_1")));
+ tree2OneSubtree.addTree(branch("1_2", new Tree<>("1_2_2")));
+ tree2.getOrCreateChild("1").addTree(tree2OneSubtree);
- Tree<String> mergeTree = new Tree<>();
+ final Tree<String> mergeTree = new Tree<>();
mergeTree.addTree(tree1);
mergeTree.addTree(tree2);
- assertEquals(1, mergeTree.size());
- assertEquals(0, mergeTree.getObjectsAtDepth(0).size());
- assertEquals(1, mergeTree.getObjectsAtDepth(1).size());
- assertEquals(2, mergeTree.getObjectsAtDepth(2).size());
- assertEquals(3, mergeTree.getObjectsAtDepth(3).size());
- assertTrue(mergeTree.getObjectsAtDepth(3).contains("1_1_1"));
- assertTrue(mergeTree.getObjectsAtDepth(3).contains("1_2_1"));
- assertTrue(mergeTree.getObjectsAtDepth(3).contains("1_2_2"));
+ assertEquals(1, mergeTree.rootNodes().size());
+ assertEquals(1, mergeTree.getNodesAtDepth(0).size());
+ assertEquals(2, mergeTree.getNodesAtDepth(1).size());
+ assertEquals(3, mergeTree.getNodesAtDepth(2).size());
+ assertEquals(0, mergeTree.getNodesAtDepth(3).size());
+ assertTrue(mergeTree.getNodesAtDepth(2).contains("1_1_1"));
+ assertTrue(mergeTree.getNodesAtDepth(2).contains("1_2_1"));
+ assertTrue(mergeTree.getNodesAtDepth(2).contains("1_2_2"));
+ }
+
+ @Test
+ public void shouldGetOrCreateChild() {
+ final Tree<String> tree = new Tree<>();
+ final Tree<String> child = tree.getOrCreateChild("a");
+ assertNotNull(child);
+ assertTrue(child.isLeaf());
+ // calling again returns the same instance
+ assertSame(child, tree.getOrCreateChild("a"));
+
+ // mutating the returned subtree is observable through the parent
+ child.getOrCreateChild("a1");
+ assertTrue(tree.childAt("a").hasChild("a1"));
+ }
+
+ @Test
+ public void shouldAllowNullKeys() {
+ // HashMap allows null keys; the new Tree must preserve this
(TreeSideEffectStep relies on it).
+ final Tree<Object> tree = new Tree<>();
+ final Tree<Object> nullChild = tree.getOrCreateChild(null);
+ assertNotNull(nullChild);
+ assertTrue(tree.hasChild(null));
+ assertEquals(1, tree.rootNodes().size());
+ }
+
+ @Test
+ public void shouldThrowOnMissingChildAt() {
+ final Tree<String> tree = new Tree<>();
+ tree.getOrCreateChild("a");
+ try {
+ tree.childAt("missing");
+ fail("expected IllegalArgumentException for missing key");
+ } catch (final IllegalArgumentException iae) {
+ assertThat(iae.getMessage(), Matchers.containsString("missing"));
+ }
+ }
+
+ @Test
+ public void shouldDetectImmediateAndRecursiveContainment() {
+ final Tree<String> tree = new Tree<>();
+
tree.getOrCreateChild("root").getOrCreateChild("child").getOrCreateChild("grandchild");
+
+ assertTrue(tree.hasChild("root"));
+ assertFalse(tree.hasChild("child"));
+ assertFalse(tree.hasChild("grandchild"));
+
+ assertTrue(tree.contains("root"));
+ assertTrue(tree.contains("child"));
+ assertTrue(tree.contains("grandchild"));
+ assertFalse(tree.contains("nope"));
+ }
+
+ @Test
+ public void shouldFindSubtreeRecursively() {
+ final Tree<String> tree = new Tree<>();
+
tree.getOrCreateChild("root").getOrCreateChild("child").getOrCreateChild("grandchild");
+
+ final Optional<Tree<String>> found = tree.findSubtree("grandchild");
+ assertTrue(found.isPresent());
+ assertTrue(found.get().isLeaf());
+
+ assertFalse(tree.findSubtree("missing").isPresent());
+ }
+
+ @Test
+ public void shouldReportNodeCount() {
+ final Tree<String> tree = new Tree<>();
+ assertEquals(0, tree.nodeCount());
+ tree.getOrCreateChild("a");
+ assertEquals(1, tree.nodeCount());
+ tree.getOrCreateChild("b").getOrCreateChild("b1");
+ assertEquals(3, tree.nodeCount());
+ }
+
+ @Test
+ public void shouldReportLeafForEmptyTree() {
+ assertTrue(new Tree<String>().isLeaf());
+
+ // a node with children is not a leaf
+ final Tree<String> tree = new Tree<>();
+ tree.getOrCreateChild("a");
+ assertFalse(tree.isLeaf());
+ }
+
+ @Test
+ public void shouldBeStructurallyEqualOrderInsensitive() {
+ final Tree<String> a = new Tree<>();
+ a.getOrCreateChild("x").getOrCreateChild("x1");
+ a.getOrCreateChild("y");
+
+ final Tree<String> b = new Tree<>();
+ b.getOrCreateChild("y");
+ b.getOrCreateChild("x").getOrCreateChild("x1");
+
+ assertEquals(a, b);
+ assertEquals(a.hashCode(), b.hashCode());
+
+ final Tree<String> c = new Tree<>();
+ c.getOrCreateChild("x");
+ c.getOrCreateChild("y");
+ assertFalse(a.equals(c));
+ }
+
+ @Test
+ public void shouldSplitParents() {
+ final Tree<String> single = new Tree<>();
+ single.getOrCreateChild("only").getOrCreateChild("child");
+ final List<Tree<String>> singleSplit = single.splitParents();
+ assertEquals(1, singleSplit.size());
+ assertEquals(single, singleSplit.get(0));
+
+ final Tree<String> multi = new Tree<>();
+ multi.getOrCreateChild("a").getOrCreateChild("a1");
+ multi.getOrCreateChild("b").getOrCreateChild("b1");
+ final List<Tree<String>> multiSplit = multi.splitParents();
+ assertEquals(2, multiSplit.size());
+ for (final Tree<String> parent : multiSplit) {
+ assertEquals(1, parent.rootNodes().size());
+ }
}
@Test
public void testPrettyPrintSingleNode() {
final Tree<String> tree = new Tree<>();
- tree.put("root", new Tree<>());
+ tree.getOrCreateChild("root");
final String expected = "|--root";
assertEquals(expected, tree.prettyPrint());
@@ -111,11 +259,9 @@ public class TreeTest extends StepTest {
@Test
public void testPrettyPrintMultipleNodes() {
final Tree<String> tree = new Tree<>();
- final Tree<String> child1 = new Tree<>();
- final Tree<String> child2 = new Tree<>();
- tree.put("root", new Tree<>());
- tree.get("root").put("child1", child1);
- tree.get("root").put("child2", child2);
+ final Tree<String> root = tree.getOrCreateChild("root");
+ root.getOrCreateChild("child1");
+ root.getOrCreateChild("child2");
// either can be expected since Tree doesn't maintain node order
final String expected1 = "|--root" + System.lineSeparator() +
@@ -130,11 +276,7 @@ public class TreeTest extends StepTest {
@Test
public void testPrettyPrintNestedTree() {
final Tree<String> tree = new Tree<>();
- final Tree<String> child1 = new Tree<>();
- final Tree<String> grandchild = new Tree<>();
- tree.put("root", new Tree<>());
- tree.get("root").put("child1", child1);
- tree.get("root").get("child1").put("grandchild", grandchild);
+
tree.getOrCreateChild("root").getOrCreateChild("child1").getOrCreateChild("grandchild");
final String expected = "|--root" + System.lineSeparator() +
" |--child1" + System.lineSeparator() +
@@ -149,8 +291,17 @@ public class TreeTest extends StepTest {
assertEquals(expected, tree.prettyPrint());
}
- private static <T> Map.Entry<T, Tree<T>> createTree(T key, Tree<T> tree) {
- return new AbstractMap.SimpleEntry<>(key, tree);
+ @Test
+ public void shouldRenderToStringAsUnderlyingMap() {
+ assertEquals("{}", new Tree<String>().toString());
+
+ final Tree<String> single = new Tree<>();
+ single.getOrCreateChild("root");
+ assertEquals("{root={}}", single.toString());
+
+ final Tree<String> nested = new Tree<>();
+ nested.getOrCreateChild("root").getOrCreateChild("child");
+ assertEquals("{root={child={}}}", nested.toString());
}
@Override
diff --git
a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/util/function/TreeSupplierTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/util/function/TreeSupplierTest.java
index 880b5b7d73..a13c0bf97b 100644
---
a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/util/function/TreeSupplierTest.java
+++
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/util/function/TreeSupplierTest.java
@@ -34,12 +34,12 @@ import static org.junit.Assert.assertNotSame;
public class TreeSupplierTest {
@Test
public void shouldSupplyTree() {
- assertEquals(0, TreeSupplier.instance().get().size());
+ assertEquals(0, TreeSupplier.instance().get().nodeCount());
}
@Test
public void shouldSupplyTreeInstance() {
- assertEquals(0, TreeSupplier.instance().get().size());
+ assertEquals(0, TreeSupplier.instance().get().nodeCount());
assertThat(TreeSupplier.instance().get(), instanceOf(Tree.class));
}
diff --git
a/gremlin-groovy/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoader.groovy
b/gremlin-groovy/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoader.groovy
index f80b651c77..5f33f27723 100644
---
a/gremlin-groovy/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoader.groovy
+++
b/gremlin-groovy/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoader.groovy
@@ -20,6 +20,7 @@ package org.apache.tinkerpop.gremlin.groovy.loaders
import org.apache.tinkerpop.gremlin.process.traversal.Traversal
import org.apache.tinkerpop.gremlin.process.traversal.Traverser
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Tree
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal
import
org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__
@@ -76,6 +77,7 @@ class SugarLoader {
Vertex.metaClass.mixin(VertexCategory.class);
Edge.metaClass.mixin(ElementCategory.class);
VertexProperty.metaClass.mixin(ElementCategory.class);
+ Tree.metaClass.mixin(TreeCategory.class);
}
public static class TraverserCategory {
@@ -88,6 +90,17 @@ class SugarLoader {
}
}
+ public static class TreeCategory {
+ // Groovy subscript on a Tree: tree['marko'] -> tree.childAt('marko').
+ public static final Object getAt(final Tree tree, final String key) {
+ return tree.childAt(key);
+ }
+
+ public static final Object getAt(final Tree tree, final Object key) {
+ return tree.childAt(key);
+ }
+ }
+
public static class ElementCategory {
public static final Object get(final Element element, final String
key) {
final Property property = element.property(key);
diff --git
a/gremlin-groovy/src/test/groovy/org/apache/tinkerpop/gremlin/groovy/TreeSubscriptTest.groovy
b/gremlin-groovy/src/test/groovy/org/apache/tinkerpop/gremlin/groovy/TreeSubscriptTest.groovy
new file mode 100644
index 0000000000..b2d068e2c4
--- /dev/null
+++
b/gremlin-groovy/src/test/groovy/org/apache/tinkerpop/gremlin/groovy/TreeSubscriptTest.groovy
@@ -0,0 +1,68 @@
+/*
+ * 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.groovy
+
+import org.apache.tinkerpop.gremlin.groovy.loaders.SugarLoader
+import org.apache.tinkerpop.gremlin.groovy.util.SugarTestHelper
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.Tree
+import org.apache.tinkerpop.gremlin.tinkergraph.structure.TinkerFactory
+import org.junit.Before
+import org.junit.Test
+
+import static org.junit.Assert.assertEquals
+import static org.junit.Assert.assertTrue
+import static org.junit.Assert.fail
+
+/**
+ * Verifies that, with the Gremlin Groovy sugar loaded, the subscript operator
(tree[key]) on a
+ * {@link Tree} resolves to {@code childAt(key)}, restoring the
tree['marko']['josh'] syntax after
+ * {@code Tree} stopped extending {@code HashMap}.
+ */
+class TreeSubscriptTest {
+
+ @Before
+ public void setup() throws Exception {
+ SugarTestHelper.clearRegistry()
+ SugarLoader.load()
+ }
+
+ @Test
+ public void shouldSupportSubscriptViaSugar() {
+ def g = TinkerFactory.createModern().traversal()
+ Tree tree = g.V(1).out().out().tree().by('name').next()
+
+ assertEquals(tree.childAt('marko'), tree['marko'])
+ assertEquals(tree.childAt('marko').childAt('josh'),
tree['marko']['josh'])
+ assertTrue(tree['marko']['josh'].rootNodes().contains('ripple'))
+ assertTrue(tree['marko']['josh'].rootNodes().contains('lop'))
+ }
+
+ @Test
+ public void shouldThrowOnMissingSubscriptKey() {
+ def g = TinkerFactory.createModern().traversal()
+ Tree tree = g.V(1).out().out().tree().by('name').next()
+
+ try {
+ tree['nonexistent']
+ fail("expected IllegalArgumentException for missing subscript key")
+ } catch (IllegalArgumentException iae) {
+ assertTrue(iae.message.contains('nonexistent'))
+ }
+ }
+}
diff --git
a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/features/StepDefinition.java
b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/features/StepDefinition.java
index 45f29c17b6..59bc869f63 100644
---
a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/features/StepDefinition.java
+++
b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/features/StepDefinition.java
@@ -545,20 +545,20 @@ public final class StepDefinition {
final List<TreeNode> roots = parseTree(asciiTree);
// Validate that the tree matches the data in roots
- assertEquals(roots.size(), tree.keySet().size());
+ assertEquals(roots.size(), tree.rootNodes().size());
for (TreeNode root : roots) {
assertThat(String.format("Tree not matching at %s",
root.getValue()),
- tree.containsKey(root.getValue()), CoreMatchers.is(true));
- validateTreeStructure((Tree) tree.get(root.getValue()), root);
+ tree.hasChild(root.getValue()), CoreMatchers.is(true));
+ validateTreeStructure(tree.childAt(root.getValue()), root);
}
}
- private void validateTreeStructure(final Tree<?> actualTree, final
TreeNode expectedNode) {
- assertEquals(expectedNode.getChildren().size(),
actualTree.keySet().size());
+ private void validateTreeStructure(final Tree actualTree, final TreeNode
expectedNode) {
+ assertEquals(expectedNode.getChildren().size(),
actualTree.rootNodes().size());
for (TreeNode child : expectedNode.getChildren()) {
assertThat(String.format("Tree not matching at %s",
child.getValue()),
- actualTree.containsKey(child.getValue()),
CoreMatchers.is(true));
- validateTreeStructure(actualTree.get(child.getValue()), child);
+ actualTree.hasChild(child.getValue()),
CoreMatchers.is(true));
+ validateTreeStructure(actualTree.childAt(child.getValue()), child);
}
}
diff --git
a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/Tree.feature
b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/Tree.feature
index efc44e02c0..c239ad053b 100644
---
a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/Tree.feature
+++
b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/Tree.feature
@@ -216,12 +216,12 @@ Feature: Step - tree()
When iterated to list
Then the result should be unordered
| result |
- | d[3].l |
- | d[3].l |
- | d[3].l |
- | d[3].l |
- | d[3].l |
- | d[3].l |
+ | d[9].l |
+ | d[9].l |
+ | d[9].l |
+ | d[9].l |
+ | d[9].l |
+ | d[9].l |
@InsertionOrderingRequired
Scenario: g_V_out_order_byXnameX_localXtreeXaX_selectXaX_countXlocalXX
@@ -233,9 +233,9 @@ Feature: Step - tree()
When iterated to list
Then the result should be unordered
| result |
- | d[1].l |
- | d[1].l |
- | d[1].l |
- | d[2].l |
| d[2].l |
| d[3].l |
+ | d[4].l |
+ | d[6].l |
+ | d[7].l |
+ | d[9].l |
diff --git
a/gremlin-util/src/test/java/org/apache/tinkerpop/gremlin/util/ser/AbstractRoundTripTest.java
b/gremlin-util/src/test/java/org/apache/tinkerpop/gremlin/util/ser/AbstractRoundTripTest.java
index 36b40b88b4..cfc23e99eb 100644
---
a/gremlin-util/src/test/java/org/apache/tinkerpop/gremlin/util/ser/AbstractRoundTripTest.java
+++
b/gremlin-util/src/test/java/org/apache/tinkerpop/gremlin/util/ser/AbstractRoundTripTest.java
@@ -98,10 +98,10 @@ public abstract class AbstractRoundTripTest {
final Tree<Vertex> tree = new Tree<>();
final Tree<Vertex> subTree = new Tree<>();
final Tree<Vertex> subSubTree = new Tree<>();
- subSubTree.put(new ReferenceVertex(1, "animal"), new Tree<>());
- subSubTree.put(new ReferenceVertex(2, "animal"), new Tree<>());
- subTree.put(new ReferenceVertex(100, "animal"), subSubTree);
- tree.put(new ReferenceVertex(1000, "animal"), subTree);
+ subSubTree.getOrCreateChild(new ReferenceVertex(1, "animal"));
+ subSubTree.getOrCreateChild(new ReferenceVertex(2, "animal"));
+ subTree.getOrCreateChild(new ReferenceVertex(100,
"animal")).addTree(subSubTree);
+ tree.getOrCreateChild(new ReferenceVertex(1000,
"animal")).addTree(subTree);
final MutableMetrics metrics = new MutableMetrics("id1", "name1");
metrics.setDuration(123, TimeUnit.MICROSECONDS);
diff --git
a/gremlin-util/src/test/java/org/apache/tinkerpop/gremlin/util/ser/binary/TypeSerializerFailureTests.java
b/gremlin-util/src/test/java/org/apache/tinkerpop/gremlin/util/ser/binary/TypeSerializerFailureTests.java
index e8573a1763..0ff8db09cf 100644
---
a/gremlin-util/src/test/java/org/apache/tinkerpop/gremlin/util/ser/binary/TypeSerializerFailureTests.java
+++
b/gremlin-util/src/test/java/org/apache/tinkerpop/gremlin/util/ser/binary/TypeSerializerFailureTests.java
@@ -65,7 +65,7 @@ public class TypeSerializerFailureTests {
final MutableMetrics metrics = new MutableMetrics("a metric", null);
final Tree<Vertex> tree = new Tree<>();
- tree.put(vertex, null);
+ tree.getOrCreateChild(vertex);
// Provide instances that are malformed for serialization to fail
return Arrays.asList(
