You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by da...@apache.org on 2025/08/13 08:27:48 UTC
(jackrabbit-oak) 01/01: OAK-11833 : replaced Guava's Traverser with OAK commons
This is an automated email from the ASF dual-hosted git repository.
daim pushed a commit to branch OAK-11833
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git
commit 8586cd68a0632624227019dc3bd9ce9cd9c1df02
Author: rishabhdaim <ri...@gmail.com>
AuthorDate: Wed Aug 13 13:57:30 2025 +0530
OAK-11833 : replaced Guava's Traverser with OAK commons
---
.../apache/jackrabbit/oak/commons/Traverser.java | 104 ++++++++++++-
.../oak/commons/io/FileTreeTraverser.java | 16 +-
.../jackrabbit/oak/commons/TraverserTest.java | 171 +++++++++++++++++++++
3 files changed, 281 insertions(+), 10 deletions(-)
diff --git a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/Traverser.java b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/Traverser.java
index 7ee6fc5cc2..d3f1583d74 100644
--- a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/Traverser.java
+++ b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/Traverser.java
@@ -23,11 +23,9 @@ import org.apache.commons.collections4.iterators.UnmodifiableIterator;
import org.jetbrains.annotations.NotNull;
import java.util.ArrayDeque;
-import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
-import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.Function;
@@ -169,5 +167,107 @@ public class Traverser {
return current;
}
}
+
+ /**
+ * Returns an iterator that traverses a tree structure in post-order. Null nodes are strictly forbidden.
+ * <p>
+ * In post-order traversal, all children of a node are visited from left to right, followed by
+ * the node itself. This creates a bottom-up traversal pattern where leaf nodes are visited first,
+ * then their parents, and finally the root.
+ *
+ * @param <T> the type of value in the tree nodes
+ * @param root the root node of the tree, may be null
+ * @param childExtractor function to extract children from a node, must not be null
+ * @return an iterator that traverses the tree in post-order
+ * @throws NullPointerException if childExtractor or any child is null
+ */
+ public static <T> FluentIterable<T> postOrderTraversal(final T root, final @NotNull Function<T, Iterable<? extends T>> childExtractor) {
+ Objects.requireNonNull(childExtractor, "Children extractor function must not be null");
+ if (root == null) {
+ return FluentIterable.empty();
+ }
+ return FluentIterable.of(new Iterable<>() {
+ @Override
+ public @NotNull Iterator<T> iterator() {
+ return UnmodifiableIterator.unmodifiableIterator(new PostOrderIterator<>(root, childExtractor));
+ }
+ });
+ }
+
+ private static final class PostOrderIterator<T> implements Iterator<T> {
+
+ private final Deque<PostOrderNode<T>> stack;
+ private final Function<T, Iterable<? extends T>> childExtractor;
+
+ PostOrderIterator(final T root, final Function<T, Iterable<? extends T>> childExtractor) {
+ this.childExtractor = childExtractor;
+ this.stack = new ArrayDeque<>();
+ // Start by pushing the leftmost path to initialize
+ pushChildren(root, childExtractor);
+ }
+
+ @Override
+ public boolean hasNext() {
+ return !stack.isEmpty();
+ }
+
+ @Override
+ public T next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException("No more nodes in the tree");
+ }
+
+ while (!stack.isEmpty()) {
+ final PostOrderNode<T> frame = stack.getLast();
+
+ // If there are more children, process the next one first
+ if (frame.childIterator.hasNext()) {
+ // throw NPE if any child is null
+ T nextChild = frame.childIterator.next();
+ Objects.requireNonNull(nextChild, "Child nodes must not be null");
+
+ pushChildren(nextChild, childExtractor);
+ continue; // Continue the loop to get the next leaf
+ }
+
+ // No more children, remove this node (post-order behavior)
+ stack.removeLast();
+ return frame.node;
+ }
+
+ throw new AssertionError("Should not reach here");
+ }
+
+ private void pushChildren(final T node, final Function<T, Iterable<? extends T>> childExtractor) {
+
+ // Iteratively go down the leftmost path
+ T current = node;
+ Objects.requireNonNull(node, "node must not be null");
+ while (current != null) {
+ Iterator<? extends T> childItr = childExtractor.apply(current).iterator();
+ stack.addLast(new PostOrderNode<>(current, childItr));
+
+ // Move to the leftmost child if available
+ // Check for null child IMMEDIATELY when retrieving it
+ if (childItr.hasNext()) {
+ T child = childItr.next();
+ // This validation needs to happen here, before any other processing
+ current = Objects.requireNonNull(child, "Child nodes must not be null");
+ } else {
+ current = null;
+ }
+ }
+ }
+ }
+
+ private static class PostOrderNode<T> {
+ final T node;
+ final Iterator<? extends T> childIterator;
+
+ PostOrderNode(final T node, final Iterator<? extends T> childItr) {
+ this.node = node;
+ this.childIterator = childItr;
+ }
+ }
}
diff --git a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/io/FileTreeTraverser.java b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/io/FileTreeTraverser.java
index 8f2468bc70..ffa98f3e67 100644
--- a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/io/FileTreeTraverser.java
+++ b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/io/FileTreeTraverser.java
@@ -18,37 +18,37 @@
*/
package org.apache.jackrabbit.oak.commons.io;
-import org.apache.jackrabbit.guava.common.graph.SuccessorsFunction;
-import org.apache.jackrabbit.guava.common.graph.Traverser;
+import org.apache.jackrabbit.oak.commons.Traverser;
import org.jetbrains.annotations.NotNull;
import java.io.File;
import java.util.Arrays;
import java.util.Set;
+import java.util.function.Function;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public class FileTreeTraverser {
- private static final FileSystemTree FILE_SYSTEM_TREE = new FileSystemTree();
+ private static final @NotNull Function<File, Iterable<? extends File>> FILE_SYSTEM_TREE = new FileSystemTree();
public static Stream<File> depthFirstPostOrder(File startNode) {
- Iterable<File> iterable = Traverser.forTree(FILE_SYSTEM_TREE).depthFirstPostOrder(startNode);
+ Iterable<File> iterable = Traverser.postOrderTraversal(startNode, FILE_SYSTEM_TREE);
return StreamSupport.stream(iterable.spliterator(), false);
}
public static Stream<File> breadthFirst(File startNode) {
- Iterable<File> iterable = Traverser.forTree(FILE_SYSTEM_TREE).breadthFirst(startNode);
+ Iterable<File> iterable = Traverser.breadthFirstTraversal(startNode, FILE_SYSTEM_TREE);
return StreamSupport.stream(iterable.spliterator(), false);
}
public static Stream<File> depthFirstPreOrder(File startNode) {
- Iterable<File> iterable = Traverser.forTree(FILE_SYSTEM_TREE).depthFirstPreOrder(startNode);
+ Iterable<File> iterable = Traverser.preOrderTraversal(startNode, FILE_SYSTEM_TREE);
return StreamSupport.stream(iterable.spliterator(), false);
}
- private static class FileSystemTree implements SuccessorsFunction<File> {
+ private static class FileSystemTree implements Function<File, Iterable<? extends File>> {
@Override
- public @NotNull Iterable<? extends File> successors(File file) {
+ public @NotNull Iterable<? extends File> apply(File file) {
if (!file.isDirectory()) {
return Set.of();
}
diff --git a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/TraverserTest.java b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/TraverserTest.java
index 056e1902be..1e768a03bc 100644
--- a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/TraverserTest.java
+++ b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/TraverserTest.java
@@ -348,10 +348,180 @@ public class TraverserTest {
Assert.assertEquals(result, traverser.breadthFirstTraversal(root).transform(Node::getValue).toList());
}
+ @Test
+ public void testPostOrderTraversalWithNormalTree() {
+ // Create a simple tree structure:
+ // 1
+ // / \
+ // 2 3
+ // / \ / \
+ // 4 5 6 7
+ Node root = new Node(1,
+ new Node(2,
+ new Node(4),
+ new Node(5)),
+ new Node(3,
+ new Node(6),
+ new Node(7)));
+
+ List<Integer> result = Traverser.postOrderTraversal(root, Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: visit left subtree, right subtree, then root
+ Assert.assertEquals(Arrays.asList(4, 5, 2, 6, 7, 3, 1), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithNullRoot() {
+ FluentIterable<Node> result = Traverser.postOrderTraversal(null, Node::getChildren);
+ Assert.assertTrue(result.isEmpty());
+ }
+
+ @Test
+ public void testPostOrderTraversalWithSingleNode() {
+ Node root = new Node(1);
+ List<Integer> result = Traverser.postOrderTraversal(root, Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ Assert.assertEquals(Collections.singletonList(1), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithAsymmetricTree() {
+ // Create an asymmetric tree:
+ // 1
+ // / \
+ // 2 3
+ // / \
+ // 4 7
+ // \
+ // 5
+ Node root = new Node(1,
+ new Node(2,
+ new Node(4,
+ new Node(5))),
+ new Node(3,
+ new Node(7)));
+
+ List<Integer> result = Traverser.postOrderTraversal(root, Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: visit children before parent
+ Assert.assertEquals(Arrays.asList(5, 4, 2, 7, 3, 1), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithNullChildExtractor() {
+ Node root = new Node(1);
+ Assert.assertThrows(NullPointerException.class, () -> Traverser.postOrderTraversal(root, null));
+ }
+
+ @Test(expected = NullPointerException.class)
+ public void testPostOrderTraversalWithNullChildren() {
+ // A tree with some null children
+ Node root = new Node(1,
+ null,
+ new Node(3));
+
+ Traverser.postOrderTraversal(root, Node::getChildren).transform(Node::getValue).forEach(System.out::println);
+
+ Assert.fail("Shouldn't reach here");
+ }
+
+ @Test
+ public void testPostOrderTraversalWithDeepTree() {
+ // Create a deep tree with many levels (linked-list-like)
+ Node n1 = new Node(1);
+ Node n2 = new Node(2);
+ Node n3 = new Node(3);
+ Node n4 = new Node(4);
+ Node n5 = new Node(5);
+
+ n1.addChild(n2);
+ n2.addChild(n3);
+ n3.addChild(n4);
+ n4.addChild(n5);
+
+ List<Integer> result = Traverser.postOrderTraversal(n1, Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: deepest nodes first
+ Assert.assertEquals(Arrays.asList(5, 4, 3, 2, 1), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithBinarySearchTree() {
+ // Create a binary search tree structure
+ // 4
+ // / \
+ // 2 6
+ // / \ / \
+ // 1 3 5 7
+ Node root = new Node(4,
+ new Node(2,
+ new Node(1),
+ new Node(3)),
+ new Node(6,
+ new Node(5),
+ new Node(7)));
+
+ List<Integer> result = Traverser.postOrderTraversal(root, Node::getChildren).transform(Node::getValue).toList();
+ Assert.assertEquals(Arrays.asList(1, 3, 2, 5, 7, 6, 4), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithTree() {
+ // Create a tree structure
+ // 4
+ // / \
+ // 0,2 6
+ // / \
+ // 1,3,5 7,8,9
+ Node root = new Node(4,
+ new Node(0),
+ new Node(2,
+ new Node(1),
+ new Node(3),
+ new Node(5)),
+ new Node(6,
+ new Node(7),
+ new Node(8),
+ new Node(9)));
+
+ List<Integer> result = Traverser.postOrderTraversal(root, Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: left subtree, right subtree, root
+ Assert.assertEquals(Arrays.asList(0, 1, 3, 5, 2, 7, 8, 9, 6, 4), result);
+ }
+
+ // TODO remove this test when we remove guava dependency
+ @Test
+ public void testPostOrderTraversalWithRandomTree() {
+
+ final Node root = getRoot(10000);
+
+ List<Integer> result = Traverser.postOrderTraversal(root, Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: left subtree, right subtree, root
+ final List<Integer> guavaTraversal = new ArrayList<>(10000);
+ org.apache.jackrabbit.guava.common.graph.Traverser.forTree(Node::getChildren).depthFirstPostOrder(root).forEach(n -> guavaTraversal.add(n.value));
+ Assert.assertEquals(result, guavaTraversal);
+ }
+
// Helper class for testing tree traversal
+
private static class Node {
private final int value;
private final List<Node> children = new ArrayList<>();
+
public Node(int value, Node... children) {
this.value = value;
this.children.addAll(Arrays.asList(children));
@@ -375,6 +545,7 @@ public class TraverserTest {
}
}
+
private @NotNull Node getRoot(final int count) {
final Node root = new Node(4);