commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From scolebou...@apache.org
Subject cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/iterators TreeIterator.java
Date Sun, 14 Mar 2004 23:27:22 GMT
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


Mime
View raw message