[FOray-commit] SF.net SVN: foray:[12146] trunk/foray/foray-common/src

[<vic...@us...>]

Revision: 12146
          http://sourceforge.net/p/foray/code/12146
Author:   victormote
Date:     2021-11-28 15:35:38 +0000 (Sun, 28 Nov 2021)
Log Message:
-----------
Add iterator over the leaf nodes of a ParaBranch.

Modified Paths:
--------------
    trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4a.java
    trunk/foray/foray-common/src/main/java/org/foray/common/sequence/IntArrayBuilder.java
    trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aTests.java

Added Paths:
-----------
    trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4aIterator.java
    trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aIteratorTests.java

Modified: trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4a.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4a.java	2021-11-28 01:37:07 UTC (rev 12145)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4a.java	2021-11-28 15:35:38 UTC (rev 12146)
@@ -190,8 +190,7 @@
 
     @Override
     public ListIterator<ParaLeaf> iterator() {
-        // TODO Auto-generated method stub
-        return null;
+        return new ParaBranch4aIterator(this);
     }
 
     @Override

Added: trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4aIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4aIterator.java	                        (rev 0)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4aIterator.java	2021-11-28 15:35:38 UTC (rev 12146)
@@ -0,0 +1,192 @@
+/*
+ * Copyright 2021 The FOray Project.
+ *      http://www.foray.org
+ *
+ * Licensed 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.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ *      Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.para;
+
+import org.foray.common.sequence.IntArrayBuilder;
+
+import org.axsl.common.para.ParaBranch;
+import org.axsl.common.para.ParaLeaf;
+import org.axsl.common.para.ParaNode;
+
+import java.util.ListIterator;
+import java.util.NoSuchElementException;
+import java.util.Stack;
+
+/**
+ * Depth-first bidirectional iterator over the Leaf nodes of a {@link ParaBranch} instance.
+ * Note that because this iterator is bidirectional, there is no concept of a "current" node, but rather "previous" and
+ * "next" which can be found at {@link #nextIndex()} and {@link #previousIndex()} respectively.
+ * This means that node "n" returned by next(), will also be returned again if the next call is to previous(), and vice
+ * versa.
+ */
+public class ParaBranch4aIterator implements ListIterator<ParaLeaf> {
+
+    /** The iterator conceptually sits immediately after (index - 1) and immediately before (index). */
+    private int leafIndex = 0;
+
+    /** The number of leaves in the branch. */
+    private int paraLeafSize;
+
+    /** The stack of branches being iterated. The root branch being iterated (i.e. the one passed in the constructor)
+     * is at the bottom of the stack, and the one currently being iterated is at the top. Each item on the stack must
+     * be a child of the item immediately below it in the stack. Together with {@link #branchIndexes}, which should
+     * always be of the same size, this defines the current location of the iterator as it traverses the content of
+     * the root. */
+    private Stack<ParaBranch> branchStack = new Stack<ParaBranch>();
+
+    /** The stack of descendant branch indexes. Together with {@link #branchStack}, which should always be of the same
+     * size, this defines the current location of the iterator as it traverses the content of the root. The index
+     * stored is conceptually the "next" index to be iterated. */
+    private IntArrayBuilder branchIndexes = new IntArrayBuilder();
+
+    public ParaBranch4aIterator(final ParaBranch branch) {
+        this.branchStack.push(branch);
+        this.paraLeafSize = branch.paraLeafSize();
+        branchIndexes.push(0);
+    }
+
+    @Override
+    public boolean hasNext() {
+        return this.leafIndex < this.paraLeafSize;
+    }
+
+    @Override
+    public ParaLeaf next() {
+        final ParaLeaf next = internalNext();
+        this.leafIndex ++;
+        return next;
+    }
+
+    private ParaLeaf internalNext() {
+        if (this.branchStack.isEmpty()) {
+            throw new NoSuchElementException("There is no \"next\" element.");
+        }
+        final ParaBranch currentBranch = this.branchStack.peek();
+        final int nextIndex = this.branchIndexes.peek();
+        if (nextIndex >= currentBranch.paraNodeSize()) {
+            this.branchStack.pop();
+            this.branchIndexes.pop();
+            incrementBranchIndex();
+            return internalNext();
+        }
+        final ParaNode node = currentBranch.paraNodeAt(nextIndex);
+        if (node.asParaLeaf() != null) {
+            incrementBranchIndex();
+            return node.asParaLeaf();
+        }
+        this.branchStack.push(node.asParaBranch());
+        this.branchIndexes.push(0);
+        return internalNext();
+    }
+
+    @Override
+    public boolean hasPrevious() {
+        return this.leafIndex > 0;
+    }
+
+    @Override
+    public ParaLeaf previous() {
+        final ParaLeaf previous = internalPrevious();
+        this.leafIndex --;
+        return previous;
+    }
+
+    private ParaLeaf internalPrevious() {
+        if (this.branchStack.isEmpty()) {
+            throw new NoSuchElementException("There is no \"previous\" element.");
+        }
+        final ParaBranch currentBranch = this.branchStack.peek();
+        final int previousIndex = this.branchIndexes.peek() - 1;
+        if (previousIndex < 0) {
+            this.branchStack.pop();
+            this.branchIndexes.pop();
+            decrementBranchIndex();
+            return internalPrevious();
+        }
+        final ParaNode node = currentBranch.paraNodeAt(previousIndex);
+        if (node.asParaLeaf() != null) {
+            decrementBranchIndex();
+            return node.asParaLeaf();
+        }
+        final ParaBranch branch = node.asParaBranch();
+        this.branchStack.push(branch);
+        this.branchIndexes.push(branch.paraNodeSize());
+        return internalPrevious();
+    }
+
+    @Override
+    public int nextIndex() {
+        return this.leafIndex;
+    }
+
+    @Override
+    public int previousIndex() {
+        return this.leafIndex - 1;
+    }
+
+    @Override
+    public void remove() {
+        throw new UnsupportedOperationException("This iterator is read-only.");
+    }
+
+    @Override
+    public void set(final ParaLeaf e) {
+        throw new UnsupportedOperationException("This iterator is read-only.");
+    }
+
+    @Override
+    public void add(final ParaLeaf e) {
+        throw new UnsupportedOperationException("This iterator is read-only.");
+    }
+
+    /**
+     * Increments the top item on the branch index stack.
+     */
+    private void incrementBranchIndex() {
+        if (this.branchIndexes.isEmpty()) {
+            return;
+        }
+        int currentIndex = this.branchIndexes.pop();
+        currentIndex ++;
+        this.branchIndexes.push(currentIndex);
+    }
+
+    /**
+     * Decrements the top item on the branch index stack.
+     */
+    private void decrementBranchIndex() {
+        if (this.branchIndexes.isEmpty()) {
+            return;
+        }
+        int currentIndex = this.branchIndexes.pop();
+        currentIndex --;
+        this.branchIndexes.push(currentIndex);
+    }
+
+}


Property changes on: trunk/foray/foray-common/src/main/java/org/foray/common/para/ParaBranch4aIterator.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/sequence/IntArrayBuilder.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/sequence/IntArrayBuilder.java	2021-11-28 01:37:07 UTC (rev 12145)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/sequence/IntArrayBuilder.java	2021-11-28 15:35:38 UTC (rev 12146)
@@ -39,7 +39,8 @@
  * but with ints instead of chars.</p>
  *
  * <p>This class can also operate as a stack of primitive ints.
- * The {@link #push(int)}, {@link #pop()}, and {@link #peek()} methods exist to support that use case.</p>
+ * The {@link #push(int)}, {@link #pop()}, {@link #peek()}, and {@link #isEmpty()} methods exist to support that use
+ * case.</p>
  */
 public class IntArrayBuilder extends AbstractIntSequence implements IntSequenceMutable {
 
@@ -329,6 +330,10 @@
         return intAt(index);
     }
 
+    public boolean isEmpty() {
+        return this.length < 1;
+    }
+
     @Override
     public IntSequenceMutable asMutable() {
         return this;

Added: trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aIteratorTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aIteratorTests.java	                        (rev 0)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aIteratorTests.java	2021-11-28 15:35:38 UTC (rev 12146)
@@ -0,0 +1,142 @@
+/*
+ * Copyright 2021 The FOray Project.
+ *      http://www.foray.org
+ *
+ * Licensed 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.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ *      Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.para;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.NoSuchElementException;
+
+/**
+ * Tests of {@link ParaBranch4aIterator}.
+ */
+public class ParaBranch4aIteratorTests {
+
+    /**
+     * Makes assertions about the state of the iterator.
+     * @param iterator The iterator about which the assertions are made.
+     * @param expectedHasNext The expected value for hasNext().
+     * @param expectedHasPrevious The expected value for hasPrevious().
+     * @param expectedNextIndex The expected value for nextIndex().
+     * @param expectedPreviousIndex The expected value for previousIndex().
+     */
+    private void iteratorAssertions(final ParaBranch4aIterator iterator, final boolean expectedHasNext,
+            final boolean expectedHasPrevious, final int expectedNextIndex, final int expectedPreviousIndex) {
+        Assert.assertEquals(expectedHasNext, iterator.hasNext());
+        Assert.assertEquals(expectedHasPrevious, iterator.hasPrevious());
+        Assert.assertEquals(expectedNextIndex, iterator.nextIndex());
+        Assert.assertEquals(expectedPreviousIndex, iterator.previousIndex());
+    }
+
+    @Test
+    public void test_001() {
+        final ParaBranch4a para = ParaBranch4aTests.createTestPara();
+        final ParaBranch4aIterator out = new ParaBranch4aIterator(para);
+        iteratorAssertions(out, true, false, 0, -1);
+
+        /* Iterate forward. */
+        Assert.assertEquals("B", out.next().getText());
+        iteratorAssertions(out, true, true, 1, 0);
+        Assert.assertEquals("e", out.next().getText());
+        iteratorAssertions(out, true, true, 2, 1);
+        Assert.assertEquals(" ", out.next().getText());
+        iteratorAssertions(out, true, true, 3, 2);
+        Assert.assertEquals("not", out.next().getText());
+        iteratorAssertions(out, true, true, 4, 3);
+        Assert.assertEquals(" ", out.next().getText());
+        iteratorAssertions(out, true, true, 5, 4);
+        Assert.assertEquals("afraid", out.next().getText());
+        iteratorAssertions(out, true, true, 6, 5);
+        Assert.assertEquals(" ", out.next().getText());
+        iteratorAssertions(out, true, true, 7, 6);
+        Assert.assertEquals("of", out.next().getText());
+        iteratorAssertions(out, true, true, 8, 7);
+        Assert.assertEquals(" ", out.next().getText());
+        iteratorAssertions(out, true, true, 9, 8);
+        Assert.assertEquals("great", out.next().getText());
+        iteratorAssertions(out, true, true, 10, 9);
+        Assert.assertEquals("-", out.next().getText());
+        iteratorAssertions(out, true, true, 11, 10);
+        Assert.assertEquals("ness", out.next().getText());
+        iteratorAssertions(out, true, true, 12, 11);
+        Assert.assertEquals(".", out.next().getText());
+        iteratorAssertions(out, true, true, 13, 12);
+
+        /* Now iterate backward for awhile. */
+        Assert.assertEquals(".", out.previous().getText());
+        iteratorAssertions(out, true, true, 12, 11);
+        Assert.assertEquals("ness", out.previous().getText());
+        iteratorAssertions(out, true, true, 11, 10);
+        Assert.assertEquals("-", out.previous().getText());
+        iteratorAssertions(out, true, true, 10, 9);
+        Assert.assertEquals("great", out.previous().getText());
+        iteratorAssertions(out, true, true, 9, 8);
+
+        /* Reverse direction to forward again. */
+        Assert.assertEquals("great", out.next().getText());
+        iteratorAssertions(out, true, true, 10, 9);
+        Assert.assertEquals("-", out.next().getText());
+        iteratorAssertions(out, true, true, 11, 10);
+
+        /* Reverse direction to backward again. Read back to the beginning. */
+        Assert.assertEquals("-", out.previous().getText());
+        iteratorAssertions(out, true, true, 10, 9);
+        Assert.assertEquals("great", out.previous().getText());
+        iteratorAssertions(out, true, true, 9, 8);
+        Assert.assertEquals(" ", out.previous().getText());
+        iteratorAssertions(out, true, true, 8, 7);
+        Assert.assertEquals("of", out.previous().getText());
+        iteratorAssertions(out, true, true, 7, 6);
+        Assert.assertEquals(" ", out.previous().getText());
+        iteratorAssertions(out, true, true, 6, 5);
+        Assert.assertEquals("afraid", out.previous().getText());
+        iteratorAssertions(out, true, true, 5, 4);
+        Assert.assertEquals(" ", out.previous().getText());
+        iteratorAssertions(out, true, true, 4, 3);
+        Assert.assertEquals("not", out.previous().getText());
+        iteratorAssertions(out, true, true, 3, 2);
+        Assert.assertEquals(" ", out.previous().getText());
+        iteratorAssertions(out, true, true, 2, 1);
+        Assert.assertEquals("e", out.previous().getText());
+        iteratorAssertions(out, true, true, 1, 0);
+        Assert.assertEquals("B", out.previous().getText());
+        iteratorAssertions(out, true, false, 0, -1);
+
+        /* We just retrieved the first node using previous(). The cursor is sitting before index 0. Another previous()
+         * should throw an exception. */
+        try {
+            out.previous();
+            Assert.fail("Exception expected here.");
+        } catch (final NoSuchElementException e) {
+            /* This is the expected case. */
+            Assert.assertEquals("There is no \"previous\" element.", e.getMessage());
+        }
+    }
+
+}


Property changes on: trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aIteratorTests.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aTests.java	2021-11-28 01:37:07 UTC (rev 12145)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/para/ParaBranch4aTests.java	2021-11-28 15:35:38 UTC (rev 12146)
@@ -40,10 +40,10 @@
 public class ParaBranch4aTests {
 
     /**
-     * Test of {@link ParaBranch4a#paraLeafAt(int)}.
+     * Creates a paragraph suitable for testing.
+     * @return A test paragraph.
      */
-    @Test
-    public void paraLeafAtTest_001() {
+    public static ParaBranch4a createTestPara() {
         /*
          * Be not afraid of greatness. Some are born great, some achieve greatness, and some have greatness thrust upon
          * them.
@@ -108,7 +108,16 @@
         nodeThem.add(new ParaBoxChars("m"));
         nodeThem.add(new ParaBoxChars("."));
         out.add(nodeThem);                      // Node 38, Leaf 45 - 49
+        return out;
+    }
 
+    /**
+     * Test of {@link ParaBranch4a#paraLeafAt(int)}.
+     */
+    @Test
+    public void paraLeafAtTest_001() {
+        final ParaBranch4a out = createTestPara();
+
         /* Test the /node/ count. */
         Assert.assertEquals(39, out.paraNodeSize());
 

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.