[EGIT PATCH 09/10] Implement a Tree iterator

[Robin Rosenberg <robin.rosenberg@dewire.com>]

This is an implementation of the Iterator interace. It can
be used for iterating over all entries in a tree in Git
order. Since it is an iterator it can be used to walk more
than one tree in parallel.

Although only post order is needed, preorder and leaves-only
mode is also implemented here.

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../spearce/jgit/lib/TreeIteratorLeafOnlyTest.java |   85 +++++++++
 .../jgit/lib/TreeIteratorPostOrderTest.java        |  103 +++++++++++
 .../spearce/jgit/lib/TreeIteratorPreOrderTest.java |  103 +++++++++++
 .../src/org/spearce/jgit/lib/TreeIterator.java     |  182 ++++++++++++++++++++
 4 files changed, 473 insertions(+), 0 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorLeafOnlyTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPostOrderTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPreOrderTest.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorLeafOnlyTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorLeafOnlyTest.java
new file mode 100644
index 0000000..7d65982
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorLeafOnlyTest.java
@@ -0,0 +1,85 @@
+package org.spearce.jgit.lib;
+
+import java.io.IOException;
+
+public class TreeIteratorLeafOnlyTest extends RepositoryTestCase {
+
+	/** Empty tree */
+	public void testEmpty() {
+		Tree tree = new Tree(db);
+		TreeIterator i = makeIterator(tree);
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * one file
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF1() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("x", i.next().getName());
+	}
+
+	/**
+	 * two files
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF2() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a");
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getName());
+		assertEquals("x", i.next().getName());
+	}
+
+	/**
+	 * Empty tree
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleT() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addTree("a");
+		TreeIterator i = makeIterator(tree);
+		assertFalse(i.hasNext());
+	}
+	
+	public void testTricky() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a.b");
+		tree.addFile("a.c");
+		tree.addFile("a/b.b/b");
+		tree.addFile("a/b");
+		tree.addFile("a/c");
+		tree.addFile("a=c");
+		tree.addFile("a=d");
+
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a.c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=d", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	private TreeIterator makeIterator(Tree tree) {
+		return new TreeIterator(tree);
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPostOrderTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPostOrderTest.java
new file mode 100644
index 0000000..a6def1d
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPostOrderTest.java
@@ -0,0 +1,103 @@
+package org.spearce.jgit.lib;
+
+import java.io.IOException;
+
+public class TreeIteratorPostOrderTest extends RepositoryTestCase {
+
+	/** Empty tree */
+	public void testEmpty() {
+		Tree tree = new Tree(db);
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * one file
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF1() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("x", i.next().getName());
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * two files
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF2() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a");
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getName());
+		assertEquals("x", i.next().getName());
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * Empty tree
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleT() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addTree("a");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+	
+	public void testTricky() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a.b");
+		tree.addFile("a.c");
+		tree.addFile("a/b.b/b");
+		tree.addFile("a/b");
+		tree.addFile("a/c");
+		tree.addFile("a=c");
+		tree.addFile("a=d");
+
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a.c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=d", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	private TreeIterator makeIterator(Tree tree) {
+		return new TreeIterator(tree, TreeIterator.Order.POSTORDER);
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPreOrderTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPreOrderTest.java
new file mode 100644
index 0000000..e7e9bf4
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPreOrderTest.java
@@ -0,0 +1,103 @@
+package org.spearce.jgit.lib;
+
+import java.io.IOException;
+
+public class TreeIteratorPreOrderTest extends RepositoryTestCase {
+
+	/** Empty tree */
+	public void testEmpty() {
+		Tree tree = new Tree(db);
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * one file
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF1() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("x", i.next().getName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * two files
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF2() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a");
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getName());
+		assertEquals("x", i.next().getName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * Empty tree
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleT() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addTree("a");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+	
+	public void testTricky() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a.b");
+		tree.addFile("a.c");
+		tree.addFile("a/b.b/b");
+		tree.addFile("a/b");
+		tree.addFile("a/c");
+		tree.addFile("a=c");
+		tree.addFile("a=d");
+
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a.c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=d", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	private TreeIterator makeIterator(Tree tree) {
+		return new TreeIterator(tree, TreeIterator.Order.PREORDER);
+	}
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java
new file mode 100644
index 0000000..e45d1fc
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java
@@ -0,0 +1,182 @@
+/*
+ *  Copyright (C) 2008 Robin Rosenberg
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Lesser General Public
+ *  License, version 2.1, as published by the Free Software Foundation.
+ *
+ *  This library is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  Lesser General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public
+ *  License along with this library; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
+ */
+
+package org.spearce.jgit.lib;
+
+import java.io.IOException;
+import java.util.Iterator;
+
+/**
+ * A tree iterator iterates over a tree and all its members recursing into
+ * subtrees according to order.
+ *
+ * Default is to only visit leafs. An {@link Order} value can be supplied to
+ * make the iteration include Tree nodes as well either before or after the
+ * child nodes have been visited.
+ */
+public class TreeIterator implements Iterator<TreeEntry> {
+
+	private Tree tree;
+
+	private int index;
+
+	private TreeIterator sub;
+
+	private Order order;
+
+	private boolean visitTreeNodes;
+
+	private boolean hasVisitedTree;
+
+	/**
+	 * Traversal order
+	 */
+	public enum Order {
+		/**
+		 * Visit node first, then leaves
+		 */
+		PREORDER,
+
+		/**
+		 * Visit leaves first, then node
+		 */
+		POSTORDER
+	};
+
+	/**
+	 * Construct a {@link TreeIterator} for visiting all non-tree nodes.
+	 *
+	 * @param start
+	 */
+	public TreeIterator(Tree start) {
+		this(start, Order.PREORDER, false);
+	}
+
+	/**
+	 * Construct a {@link TreeIterator} visiting all nodes in a tree in a given
+	 * order.
+	 *
+	 * @param start Root node
+	 * @param order {@link Order}
+	 */
+	public TreeIterator(Tree start, Order order) {
+		this(start, order, true);
+	}
+
+	/**
+	 * Construct a {@link TreeIterator}
+	 *
+	 * @param start First node to visit
+	 * @param order Visitation {@link Order}
+	 * @param visitTreeNode True to include tree node
+	 */
+	private TreeIterator(Tree start, Order order, boolean visitTreeNode) {
+		this.tree = start;
+		this.visitTreeNodes = visitTreeNode;
+		this.index = -1;
+		this.order = order;
+		if (!visitTreeNodes)
+			this.hasVisitedTree = true;
+		try {
+			step();
+		} catch (IOException e) {
+			throw new Error(e);
+		}
+	}
+
+	public TreeEntry next() {
+		try {
+			TreeEntry ret = nextTreeEntry();
+			step();
+			return ret;
+		} catch (IOException e) {
+			throw new Error(e);
+		}
+	}
+
+	private TreeEntry nextTreeEntry() throws IOException {
+		TreeEntry ret;
+		if (sub != null)
+			ret = sub.nextTreeEntry();
+		else {
+			if (index < 0 && order == Order.PREORDER) {
+				return tree;
+			}
+			if (order == Order.POSTORDER && index == tree.memberCount()) {
+				return tree;
+			}
+			ret = tree.members()[index];
+		}
+		return ret;
+	}
+
+	public boolean hasNext() {
+		try {
+			return hasNextTreeEntry();
+		} catch (IOException e) {
+			throw new Error(e);
+		}
+	}
+
+	private boolean hasNextTreeEntry() throws IOException {
+		if (tree == null)
+			return false;
+		return sub != null
+			|| index < tree.memberCount()
+			|| order == Order.POSTORDER && index == tree.memberCount();
+	}
+
+	private boolean step() throws IOException {
+		if (tree == null)
+			return false;
+
+		if (sub != null) {
+			if (sub.step())
+				return true;
+			sub = null;
+		}
+
+		if (index < 0 && !hasVisitedTree && order == Order.PREORDER) {
+			hasVisitedTree = true;
+			return true;
+		}
+
+		while (++index < tree.memberCount()) {
+			TreeEntry e = tree.members()[index];
+			if (e instanceof Tree) {
+				sub = new TreeIterator((Tree) e, order, visitTreeNodes);
+				if (sub.hasNextTreeEntry())
+					return true;
+				sub = null;
+				continue;
+			}
+			return true;
+		}
+
+		if (index == tree.memberCount() && !hasVisitedTree
+				&& order == Order.POSTORDER) {
+			hasVisitedTree = true;
+			return true;
+		}
+		return false;
+	}
+
+	public void remove() {
+		throw new IllegalStateException(
+				"TreeIterator does not suppport remove()");
+	}
+}
-- 
1.5.4.2