You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sling.apache.org by kw...@apache.org on 2019/07/11 15:24:18 UTC
[sling-org-apache-sling-api] 01/01: SLING-8271 implement
AbstractStoppableDepthFirstVisitor
This is an automated email from the ASF dual-hosted git repository.
kwin pushed a commit to branch feature/SLING-8271_new-stoppable-visitor
in repository https://gitbox.apache.org/repos/asf/sling-org-apache-sling-api.git
commit 7acd1062af82526bdae2cdc32483292e53c64883
Author: Konrad Windszus <kw...@apache.org>
AuthorDate: Thu Jul 11 17:24:06 2019 +0200
SLING-8271 implement AbstractStoppableDepthFirstVisitor
---
.../api/resource/AbstractResourceVisitor.java | 4 +-
...AbstractStoppableDepthFirstResourceVisitor.java | 99 ++++++++++++++++
...ractStoppableDepthFirstResourceVisitorTest.java | 125 +++++++++++++++++++++
3 files changed, 226 insertions(+), 2 deletions(-)
diff --git a/src/main/java/org/apache/sling/api/resource/AbstractResourceVisitor.java b/src/main/java/org/apache/sling/api/resource/AbstractResourceVisitor.java
index e152a5f..3e4ae49 100644
--- a/src/main/java/org/apache/sling/api/resource/AbstractResourceVisitor.java
+++ b/src/main/java/org/apache/sling/api/resource/AbstractResourceVisitor.java
@@ -23,13 +23,13 @@ import java.util.Iterator;
import org.jetbrains.annotations.NotNull;
/**
- * This visitor will traverse the given resource and all its children in a breadth-first approach
+ * This visitor will traverse the given resource and all its children in a depth-first approach
* and call the {@link AbstractResourceVisitor#visit(Resource)} method for each visited resource.
* It decouples the actual traversal code from application code.
*
* Concrete subclasses must implement the {@link AbstractResourceVisitor#visit(Resource)} method.
*
- * @see <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Breadth-First-Search</a>
+ * @see <a href="https://en.wikipedia.org/wiki/Depth-first_search">Depth-First-Search</a>
* @since 2.2 (Sling API Bundle 2.2.0)
*/
public abstract class AbstractResourceVisitor {
diff --git a/src/main/java/org/apache/sling/api/resource/AbstractStoppableDepthFirstResourceVisitor.java b/src/main/java/org/apache/sling/api/resource/AbstractStoppableDepthFirstResourceVisitor.java
new file mode 100644
index 0000000..9feb81a
--- /dev/null
+++ b/src/main/java/org/apache/sling/api/resource/AbstractStoppableDepthFirstResourceVisitor.java
@@ -0,0 +1,99 @@
+/*
+ * 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.sling.api.resource;
+
+import java.util.Iterator;
+
+import org.jetbrains.annotations.NotNull;
+
+/**
+ * This visitor will traverse the given resource and all its children in a depth-first approach
+ * and call the {@link AbstractStoppableDepthFirstResourceVisitor#visit(Resource)} method for each visited resource.
+ * It decouples the actual traversal code from application code in its visit method.
+ *
+ * Concrete subclasses must implement only the {@link AbstractStoppableDepthFirstResourceVisitor#visit(Resource)} method.
+ *
+ * The difference between this class and {@link AbstractResourceVisitor} is that this class allows to stop
+ * the traversal early or skip some parts of the resource tree.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Depth-first_search">Depth-First-Search</a>
+ * @since 2.12.0 (Sling API Bundle 2.22.0)
+ */
+public abstract class AbstractStoppableDepthFirstResourceVisitor {
+
+ /**
+ * Defines how the traversal should be continued.
+ * <ul>
+ * <li>{@link #NORMAL} for regular continuation</li>
+ * <li>{@link #SKIP_SUBTREE} to skip the children of the current resource and continue with its siblings</li>
+ * <li>{@link #STOP} to stop the whole traversal (i.e. to no visit any other resource afterwards)</li>
+ */
+ enum TraversalContinuation {
+ NORMAL,
+ SKIP_SUBTREE,
+ STOP
+ }
+
+ /**
+ * Visit the given resource and all its descendants.
+ * @param resource The resource
+ * @return {@code false} in case traversal was stopped because one {@link #visit(Resource)} call returned
+ * {@link TraversalContinuation.STOP} otherwise {@code true}.
+ */
+ public boolean accept(final @NotNull Resource resource) {
+ boolean continueTraversal = true;
+ switch(this.visit(resource)) {
+ case STOP:
+ continueTraversal = false;
+ break;
+ case NORMAL:
+ continueTraversal = this.traverseChildren(resource.listChildren());
+ break;
+ default:
+ break;
+ }
+ return continueTraversal;
+ }
+
+ /**
+ * Visit the given resources.
+ * @param children The list of resources to traverse.
+ * @return {@code false} in case traversal should be stopped because one {@link #visit(Resource)} call returned
+ * {@link TraversalContinuation.STOP} otherwise {@code true}.
+ */
+ protected boolean traverseChildren(final @NotNull Iterator<Resource> children) {
+ while (children.hasNext()) {
+ final Resource child = children.next();
+ if (!accept(child)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Implement this method to do actual work on the resources.
+ * @param resource The resource
+ * @return one of the values of {@link TraversalContinuation} to optionally stop the traversal or
+ * not descend further (i.e. skip this subtree), usually {@link TraversalContinuation#NORMAL} to
+ * continue the depth-first traversal.
+ */
+ protected abstract @NotNull TraversalContinuation visit(final @NotNull Resource resource);
+
+}
diff --git a/src/test/java/org/apache/sling/api/resource/AbstractStoppableDepthFirstResourceVisitorTest.java b/src/test/java/org/apache/sling/api/resource/AbstractStoppableDepthFirstResourceVisitorTest.java
new file mode 100644
index 0000000..b6edcc2
--- /dev/null
+++ b/src/test/java/org/apache/sling/api/resource/AbstractStoppableDepthFirstResourceVisitorTest.java
@@ -0,0 +1,125 @@
+/*
+ * 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.sling.api.resource;
+
+import java.util.Arrays;
+import java.util.Iterator;
+
+import org.jetbrains.annotations.NotNull;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.InOrder;
+import org.mockito.Mock;
+import org.mockito.Mockito;
+import org.mockito.junit.MockitoJUnitRunner;
+
+@RunWith(MockitoJUnitRunner.class)
+public class AbstractStoppableDepthFirstResourceVisitorTest {
+
+ @Mock
+ private Resource a, aa, ab, aaa, aab, aba, abb;
+
+ private static Iterator<Resource> resourceIterator(Resource... args) {
+ return Arrays.stream(args).iterator();
+ }
+
+ @Before
+ public void setUp() {
+ Mockito.when(a.listChildren()).thenReturn(resourceIterator(aa, ab));
+ Mockito.when(aa.listChildren()).thenReturn(resourceIterator(aaa,aab));
+ Mockito.when(ab.listChildren()).thenReturn(resourceIterator(aba,abb));
+ Mockito.when(aaa.listChildren()).thenReturn(resourceIterator());
+ Mockito.when(aab.listChildren()).thenReturn(resourceIterator());
+ Mockito.when(aba.listChildren()).thenReturn(resourceIterator());
+ Mockito.when(abb.listChildren()).thenReturn(resourceIterator());
+ }
+
+ @Test
+ public void testFullTraversalWithCorrectOrder() {
+ AbstractStoppableDepthFirstResourceVisitor visitor = new AbstractStoppableDepthFirstResourceVisitor() {
+ @Override
+ protected @NotNull TraversalContinuation visit(@NotNull Resource resource) {
+ // call method for verification
+ resource.getName();
+ return TraversalContinuation.NORMAL;
+ }
+ };
+ Assert.assertTrue(visitor.accept(a));
+
+ InOrder orderVerifier = Mockito.inOrder(a, aa, aaa, aab, ab, aba, abb);
+ orderVerifier.verify(a).getName();
+ orderVerifier.verify(aa).getName();
+ orderVerifier.verify(aaa).getName();
+ orderVerifier.verify(aab).getName();
+ orderVerifier.verify(ab).getName();
+ orderVerifier.verify(aba).getName();
+ orderVerifier.verify(abb).getName();
+ }
+
+ @Test
+ public void testSkipSubtree() {
+ AbstractStoppableDepthFirstResourceVisitor visitor = new AbstractStoppableDepthFirstResourceVisitor() {
+ int elementNo = 0;
+
+ @Override
+ protected @NotNull TraversalContinuation visit(@NotNull Resource resource) {
+ // call method for verification
+ resource.getName();
+ if (elementNo++ == 1) { // element aa
+ return TraversalContinuation.SKIP_SUBTREE;
+ }
+ return TraversalContinuation.NORMAL;
+ }
+ };
+ Assert.assertTrue(visitor.accept(a));
+
+ InOrder orderVerifier = Mockito.inOrder(a, aa, ab, aba, abb);
+ orderVerifier.verify(a).getName();
+ orderVerifier.verify(aa).getName();
+ orderVerifier.verify(ab).getName();
+ orderVerifier.verify(aba).getName();
+ orderVerifier.verify(abb).getName();
+ Mockito.verifyZeroInteractions(aaa, aab);
+ }
+
+ @Test
+ public void testStop() {
+ AbstractStoppableDepthFirstResourceVisitor visitor = new AbstractStoppableDepthFirstResourceVisitor() {
+ int elementNo = 0;
+
+ @Override
+ protected @NotNull TraversalContinuation visit(@NotNull Resource resource) {
+ // call method for verification
+ resource.getName();
+ if (elementNo++ == 1) { // element aa
+ return TraversalContinuation.STOP;
+ }
+ return TraversalContinuation.NORMAL;
+ }
+ };
+ Assert.assertFalse(visitor.accept(a));
+
+ InOrder orderVerifier = Mockito.inOrder(a, aa);
+ orderVerifier.verify(a).getName();
+ orderVerifier.verify(aa).getName();
+ Mockito.verifyZeroInteractions(aaa, aab, ab, aba, abb);
+ }
+}