You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by sc...@apache.org on 2004/03/15 00:27:22 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/iterators TreeIterator.java
scolebourne 2004/03/14 15:27:22
Modified: collections/src/test/org/apache/commons/collections/iterators
TestAll.java
Added: collections/src/test/org/apache/commons/collections/iterators
TestTreeIterator.java
collections/src/java/org/apache/commons/collections/iterators
TreeIterator.java
Log:
Add TreeIterator for iterating over object graphs
Revision Changes Path
1.13 +2 -1 jakarta-commons/collections/src/test/org/apache/commons/collections/iterators/TestAll.java
Index: TestAll.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/iterators/TestAll.java,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -r1.12 -r1.13
--- TestAll.java 18 Feb 2004 01:20:33 -0000 1.12
+++ TestAll.java 14 Mar 2004 23:27:22 -0000 1.13
@@ -49,6 +49,7 @@
suite.addTest(TestLoopingIterator.suite());
suite.addTest(TestSingletonIterator.suite());
suite.addTest(TestSingletonListIterator.suite());
+ suite.addTest(TestTreeIterator.suite());
suite.addTest(TestUniqueFilterIterator.suite());
suite.addTest(TestUnmodifiableIterator.suite());
suite.addTest(TestUnmodifiableListIterator.suite());
1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/iterators/TestTreeIterator.java
Index: TestTreeIterator.java
===================================================================
/*
* Copyright 2004 The Apache Software Foundation
*
* 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.
*/
package org.apache.commons.collections.iterators;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import junit.framework.Test;
import junit.framework.TestSuite;
import junit.textui.TestRunner;
import org.apache.commons.collections.IteratorUtils;
import org.apache.commons.collections.Transformer;
/**
* Testcase.
*
* @version $Revision: 1.1 $ $Date: 2004/03/14 23:27:22 $
*
* @author Stephen Colebourne
*/
public class TestTreeIterator extends AbstractTestIterator {
protected String[] testArray = { "One", "Two", "Three", "Four", "Five", "Six" };
protected List list1 = null;
protected List list2 = null;
protected List list3 = null;
protected List iteratorList = null;
public TestTreeIterator(String testName) {
super(testName);
}
public static void main(String[] args) {
TestRunner.run(suite());
}
public static Test suite() {
return new TestSuite(TestTreeIterator.class);
}
public void setUp() {
list1 = new ArrayList();
list1.add("One");
list1.add("Two");
list1.add("Three");
list2 = new ArrayList();
list2.add("Four");
list3 = new ArrayList();
list3.add("Five");
list3.add("Six");
iteratorList = new ArrayList();
iteratorList.add(list1.iterator());
iteratorList.add(list2.iterator());
iteratorList.add(list3.iterator());
}
//-----------------------------------------------------------------------
public Iterator makeEmptyIterator() {
ArrayList list = new ArrayList();
return new TreeIterator(list.iterator(), null);
}
public Iterator makeFullIterator() {
return new TreeIterator(iteratorList.iterator(), null);
}
//-----------------------------------------------------------------------
public void testIteratorConstructor_null1() {
Iterator it = new TreeIterator(null);
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
try {
it.remove();
fail();
} catch (IllegalStateException ex) {
}
}
public void testIteratorConstructor_null_next() {
Iterator it = new TreeIterator(null);
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
}
public void testIteratorConstructor_null_remove() {
Iterator it = new TreeIterator(null);
try {
it.remove();
fail();
} catch (IllegalStateException ex) {
}
}
//-----------------------------------------------------------------------
public void testIteratorConstructorIteration_Empty() {
List iteratorList = new ArrayList();
Iterator it = new TreeIterator(iteratorList.iterator());
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
try {
it.remove();
fail();
} catch (IllegalStateException ex) {
}
}
public void testIteratorConstructorIteration_Simple() {
List iteratorList = new ArrayList();
iteratorList.add(list1.iterator());
iteratorList.add(list2.iterator());
iteratorList.add(list3.iterator());
Iterator it = new TreeIterator(iteratorList.iterator());
for (int i = 0; i < 6; i++) {
assertEquals(true, it.hasNext());
assertEquals(testArray[i], it.next());
}
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
}
public void testIteratorConstructorIteration_SimpleNoHasNext() {
List iteratorList = new ArrayList();
iteratorList.add(list1.iterator());
iteratorList.add(list2.iterator());
iteratorList.add(list3.iterator());
Iterator it = new TreeIterator(iteratorList.iterator());
for (int i = 0; i < 6; i++) {
assertEquals(testArray[i], it.next());
}
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
}
public void testIteratorConstructorIteration_WithEmptyIterators() {
List iteratorList = new ArrayList();
iteratorList.add(IteratorUtils.EMPTY_ITERATOR);
iteratorList.add(list1.iterator());
iteratorList.add(IteratorUtils.EMPTY_ITERATOR);
iteratorList.add(list2.iterator());
iteratorList.add(IteratorUtils.EMPTY_ITERATOR);
iteratorList.add(list3.iterator());
iteratorList.add(IteratorUtils.EMPTY_ITERATOR);
Iterator it = new TreeIterator(iteratorList.iterator());
for (int i = 0; i < 6; i++) {
assertEquals(true, it.hasNext());
assertEquals(testArray[i], it.next());
}
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
}
public void testIteratorConstructorRemove() {
List iteratorList = new ArrayList();
iteratorList.add(list1.iterator());
iteratorList.add(list2.iterator());
iteratorList.add(list3.iterator());
Iterator it = new TreeIterator(iteratorList.iterator());
for (int i = 0; i < 6; i++) {
assertEquals(testArray[i], it.next());
it.remove();
}
assertEquals(false, it.hasNext());
assertEquals(0, list1.size());
assertEquals(0, list2.size());
assertEquals(0, list3.size());
}
//-----------------------------------------------------------------------
public void testIteration_IteratorOfIterators() {
List iteratorList = new ArrayList();
iteratorList.add(list1.iterator());
iteratorList.add(list2.iterator());
iteratorList.add(list3.iterator());
Iterator it = new TreeIterator(iteratorList.iterator(), null);
for (int i = 0; i < 6; i++) {
assertEquals(true, it.hasNext());
assertEquals(testArray[i], it.next());
}
assertEquals(false, it.hasNext());
}
public void testIteration_IteratorOfIteratorsWithEmptyIterators() {
List iteratorList = new ArrayList();
iteratorList.add(IteratorUtils.EMPTY_ITERATOR);
iteratorList.add(list1.iterator());
iteratorList.add(IteratorUtils.EMPTY_ITERATOR);
iteratorList.add(list2.iterator());
iteratorList.add(IteratorUtils.EMPTY_ITERATOR);
iteratorList.add(list3.iterator());
iteratorList.add(IteratorUtils.EMPTY_ITERATOR);
Iterator it = new TreeIterator(iteratorList.iterator(), null);
for (int i = 0; i < 6; i++) {
assertEquals(true, it.hasNext());
assertEquals(testArray[i], it.next());
}
assertEquals(false, it.hasNext());
}
//-----------------------------------------------------------------------
public void testIteration_RootNull() {
Iterator it = new TreeIterator(null, null);
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
try {
it.remove();
fail();
} catch (IllegalStateException ex) {
}
}
public void testIteration_RootNoTransformer() {
Forest forest = new Forest();
Iterator it = new TreeIterator(forest, null);
assertEquals(true, it.hasNext());
assertSame(forest, it.next());
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
}
public void testIteration_Transformed1() {
Forest forest = new Forest();
Leaf l1 = forest.addTree().addBranch().addLeaf();
Iterator it = new TreeIterator(forest, new LeafFinder());
assertEquals(true, it.hasNext());
assertSame(l1, it.next());
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
}
public void testIteration_Transformed2() {
Forest forest = new Forest();
forest.addTree();
forest.addTree();
forest.addTree();
Branch b1 = forest.getTree(0).addBranch();
Branch b2 = forest.getTree(0).addBranch();
Branch b3 = forest.getTree(2).addBranch();
Branch b4 = forest.getTree(2).addBranch();
Branch b5 = forest.getTree(2).addBranch();
Leaf l1 = b1.addLeaf();
Leaf l2 = b1.addLeaf();
Leaf l3 = b2.addLeaf();
Leaf l4 = b3.addLeaf();
Leaf l5 = b5.addLeaf();
Iterator it = new TreeIterator(forest, new LeafFinder());
assertEquals(true, it.hasNext());
assertSame(l1, it.next());
assertEquals(true, it.hasNext());
assertSame(l2, it.next());
assertEquals(true, it.hasNext());
assertSame(l3, it.next());
assertEquals(true, it.hasNext());
assertSame(l4, it.next());
assertEquals(true, it.hasNext());
assertSame(l5, it.next());
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
}
public void testIteration_Transformed3() {
Forest forest = new Forest();
forest.addTree();
forest.addTree();
forest.addTree();
Branch b1 = forest.getTree(1).addBranch();
Branch b2 = forest.getTree(1).addBranch();
Branch b3 = forest.getTree(2).addBranch();
Branch b4 = forest.getTree(2).addBranch();
Branch b5 = forest.getTree(2).addBranch();
Leaf l1 = b1.addLeaf();
Leaf l2 = b1.addLeaf();
Leaf l3 = b2.addLeaf();
Leaf l4 = b3.addLeaf();
Leaf l5 = b4.addLeaf();
Iterator it = new TreeIterator(forest, new LeafFinder());
assertEquals(true, it.hasNext());
assertSame(l1, it.next());
assertEquals(true, it.hasNext());
assertSame(l2, it.next());
assertEquals(true, it.hasNext());
assertSame(l3, it.next());
assertEquals(true, it.hasNext());
assertSame(l4, it.next());
assertEquals(true, it.hasNext());
assertSame(l5, it.next());
assertEquals(false, it.hasNext());
try {
it.next();
fail();
} catch (NoSuchElementException ex) {
}
}
//-----------------------------------------------------------------------
static class LeafFinder implements Transformer {
public Object transform(Object input) {
if (input instanceof Forest) {
return ((Forest) input).treeIterator();
}
if (input instanceof Tree) {
return ((Tree) input).branchIterator();
}
if (input instanceof Branch) {
return ((Branch) input).leafIterator();
}
if (input instanceof Leaf) {
return input;
}
throw new ClassCastException();
}
}
//-----------------------------------------------------------------------
static class Forest {
List trees = new ArrayList();
Tree addTree() {
trees.add(new Tree());
return getTree(trees.size() - 1);
}
Tree getTree(int index) {
return (Tree) trees.get(index);
}
Iterator treeIterator() {
return trees.iterator();
}
}
static class Tree {
List branches = new ArrayList();
Branch addBranch() {
branches.add(new Branch());
return getBranch(branches.size() - 1);
}
Branch getBranch(int index) {
return (Branch) branches.get(index);
}
Iterator branchIterator() {
return branches.iterator();
}
}
static class Branch {
List leaves = new ArrayList();
Leaf addLeaf() {
leaves.add(new Leaf());
return getLeaf(leaves.size() - 1);
}
Leaf getLeaf(int index) {
return (Leaf) leaves.get(index);
}
Iterator leafIterator() {
return leaves.iterator();
}
}
static class Leaf {
String colour;
String getColour() {
return colour;
}
void setColour(String colour) {
this.colour = colour;
}
}
}
1.1 jakarta-commons/collections/src/java/org/apache/commons/collections/iterators/TreeIterator.java
Index: TreeIterator.java
===================================================================
/*
* Copyright 2004 The Apache Software Foundation
*
* 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.
*/
package org.apache.commons.collections.iterators;
import java.util.Iterator;
import java.util.NoSuchElementException;
import org.apache.commons.collections.ArrayStack;
import org.apache.commons.collections.Transformer;
import org.apache.commons.collections.TransformerUtils;
/**
* An Iterator that can traverse multiple iterators down an object graph.
* <p>
* This iterator can extract multiple objects from a complex tree-like object graph.
* The iteration starts from a single root object.
* It uses a <code>Transformer</code> to extract the iterators and elements.
* Its main benefit is that no intermediate <code>List</code> is created.
* <p>
* For example, consider an object graph:
* <pre>
* |- Branch -- Leaf
* | \- Leaf
* |- Tree | /- Leaf
* | |- Branch -- Leaf
* Forest | \- Leaf
* | |- Branch -- Leaf
* | | \- Leaf
* |- Tree | /- Leaf
* |- Branch -- Leaf
* |- Branch -- Leaf</pre>
* The following <code>Transformer</code>, used in this class, will extract all
* the Leaf objects without creating a combined intermediate list:
* <pre>
* public Object transform(Object input) {
* if (input instanceof Forest) {
* return ((Forest) input).treeIterator();
* }
* if (input instanceof Tree) {
* return ((Tree) input).branchIterator();
* }
* if (input instanceof Branch) {
* return ((Branch) input).leafIterator();
* }
* if (input instanceof Leaf) {
* return input;
* }
* throw new ClassCastException();
* }</pre>
* <p>
* Internally, iteration starts from the root object. When next is called,
* the transformer is called to examine the object. The transformer will return
* either an iterator or an object. If the object is an Iterator, the next element
* from that iterator is obtained and the process repeats. If the element is an object
* it is returned.
* <p>
* Under many circumstances, linking Iterators together in this manner is
* more efficient (and convenient) than using nested for loops to extract a list.
*
* @since Commons Collections 3.1
* @version $Revision: 1.1 $ $Date: 2004/03/14 23:27:22 $
*
* @author Stephen Colebourne
*/
public class TreeIterator implements Iterator {
/** The stack of iterators */
protected final ArrayStack stack = new ArrayStack(8);
/** The root object in the tree */
protected Object root;
/** The transformer to use */
protected Transformer transformer;
/** Whether there is another element in the iteration */
protected boolean hasNext = false;
/** The current iterator */
protected Iterator currentIterator;
/** The current value */
protected Object currentValue;
/** The last used iterator, needed for remove() */
protected Iterator lastUsedIterator;
//-----------------------------------------------------------------------
/**
* Constructs a TreeIterator using a root object and transformer.
* <p>
* The root object can be an iterator, in which case it will be immediately
* looped around.
*
* @param root the root object, null will result in an empty iterator
* @param transformer the transformer to use, null will use a no effect transformer
*/
public TreeIterator(Object root, Transformer transformer) {
super();
if (root instanceof Iterator) {
this.currentIterator = (Iterator) root;
} else {
this.root = root;
}
this.transformer = (transformer == null ? TransformerUtils.nopTransformer() : transformer);
}
/**
* Constructs a TreeIterator that will handle an iterator of iterators.
* <p>
* This constructor exists for convenience to emphasise that this class can
* be used to iterate over nested iterators. That is to say that the iterator
* passed in here contains other iterators, which may in turn contain further
* iterators.
*
* @param rootIterator the root iterator, null will result in an empty iterator
*/
public TreeIterator(Iterator rootIterator) {
super();
this.currentIterator = rootIterator;
this.transformer = TransformerUtils.nopTransformer();
}
//-----------------------------------------------------------------------
/**
* Loops around the iterators to find the next value to return.
*/
protected void updateCurrentIterator() {
if (hasNext) {
return;
}
if (currentIterator == null) {
if (root == null) {
// do nothing, hasNext will be false
} else {
Object value = transformer.transform(root);
findNext(value);
root = null;
}
} else {
findNext(currentIterator);
}
}
/**
* Finds the next object in the iteration.
*
* @param value the value to start from
*/
protected void findNext(Object value) {
if (value instanceof Iterator) {
if (value != currentIterator) {
// recurse a level
if (currentIterator != null) {
stack.push(currentIterator);
}
currentIterator = (Iterator) value;
}
while (currentIterator.hasNext() && hasNext == false) {
Object next = currentIterator.next();
next = transformer.transform(next);
findNext(next);
}
if (hasNext) {
// next value found
} else if (stack.isEmpty()) {
// all iterators exhausted
} else {
// current iterator exhausted, go up a level
currentIterator = (Iterator) stack.pop();
findNext(currentIterator);
}
} else {
// next value found
currentValue = value;
hasNext = true;
}
}
//-----------------------------------------------------------------------
/**
* Checks whether there are any more elements in the tree to obtain.
*
* @return true if elements remain in the iteration
*/
public boolean hasNext() {
updateCurrentIterator();
return hasNext;
}
/**
* Gets the next element of the iteration.
*
* @return the next element from the iteration
* @throws NoSuchElementException if all the Iterators are exhausted
*/
public Object next() {
updateCurrentIterator();
if (hasNext == false) {
throw new NoSuchElementException("No more elements in the iteration");
}
lastUsedIterator = currentIterator;
Object result = currentValue;
currentValue = null;
hasNext = false;
return result;
}
/**
* Removes from the underlying collection the last element returned.
* <p>
* This method calls remove() on the underlying Iterator and it may
* throw an UnsupportedOperationException if the underlying Iterator
* does not support this method.
*
* @throws UnsupportedOperationException
* if the remove operator is not supported by the underlying Iterator
* @throws IllegalStateException
* if the next method has not yet been called, or the remove method has
* already been called after the last call to the next method.
*/
public void remove() {
if (lastUsedIterator == null) {
throw new IllegalStateException("Iterator remove() cannot be called at this time");
}
lastUsedIterator.remove();
lastUsedIterator = null;
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org