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 <[email protected]> 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);
