commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stephen Colebourne" <scolebou...@btopenworld.com>
Subject [collections] TreeIterator / Nested iterators
Date Sun, 14 Mar 2004 23:39:39 GMT
I have added TreeIterator to CVS to cover this sort of case. The class is
capable of navigating an object graph of arbitrary depth for iteration.

I recommend everyone reviews it, including the name before it is confirmed
for 3.1.

Stephen

----- Original Message -----
From: "pwomack" <pwomack@papermule.co.uk>
> I've attached my implementation of IteratorIterator,
> which is blatently derived from IteratorChain.
>
> If you want to include it (or its idea)
> in Collections feel free (or talk to me,
> and we'll formalise the handover in some way)
>
> I think it's a useful further abstraction
> of IteratorChain, extending the idea
> of "iterators over virtual lists" to
> the Implemetation of IteratorChain itself :-)
>
>       BugBear
>
>
>
>
> pwomack wrote:
> > I do have something in mind, but I'm so run off my feet
> > at the moment, I don't have time to implement it.
> > In my current project I've just done "the obvious".
> >
> > I will try to get back to you with what I'd like
> > at a later date.
> >
> > I think it will involve a class like IteratorChain
> > that (confusingly) takes an Iterator instead
> > of an Array (or a variation of Array).
> >
> > This paramater iterator would (of course)
> > iterate over iterators (which in turn Iterate
> > of the Elements)
> >
> >     BugBear
> >
> >
> > -------- Original Message --------
> > Subject: Re: [collections] how to *NEST* (not CHAIN) iterators
> > Date: Fri, 14 Nov 2003 23:53:08 -0000
> > From: Stephen Colebourne <scolebourne@btopenworld.com>
> > Reply-To: Jakarta Commons Users List <commons-user@jakarta.apache.org>
> > To: Jakarta Commons Users List <commons-user@jakarta.apache.org>
> > References: <3FB21B90.1060608@papermule.co.uk>
> > <006c01c3a97a$f7afbe60$83038051@oemcomputer>
> > <3FB3514B.3050801@papermule.co.uk>
> >
> > If you have a particular solution in mind, perhaps a patch or code
sample
> > would clarify it in my mind.
> >
> > You might also want to look at the new CompositeCollection class on the
> > CVS,
> > although I don't _think_ its what you need.
> >
> > Stephen
> >
> > From: "pwomack" <pwomack@papermule.co.uk>
> >
> >> Stephen Colebourne wrote:
> >> > We have nothing that I can think of that would help. What you need it
> >
> > would
> >
> >> > seem is a variation on the IteratorChain that takes in a collection
of
> >> > things that have iterators.
> >>
> >> I think I need something that takes an iterator...
> >> that returns things that have iterators.
> >>
> >> Essentially, the IteratorChain takes a collection (along
> >> with some very useful parameter overloads).
> >>
> >> But one of the claimed benefits of the design
> >> is *avoiding* having to construct collections,
> >> allowing the user to iterate over a "virtual" collection.
> >>
> >> What I want to do is add this benefit to IteratorChain
> >> itself.
> >>
> >>      BugBear
> >>
> >> >
> >> > Stephen
> >> >
> >> > ----- Original Message -----
> >> > From: "pwomack" <pwomack@papermule.co.uk>
> >> > To: <commons-user@jakarta.apache.org>
> >> > Sent: Wednesday, November 12, 2003 11:37 AM
> >> > Subject: [collections] how to *NEST* (not CHAIN) iterators
> >> >
> >> >
> >> >
> >> >>Consider the following:
> >> >>
> >> >>Class 'A' contains many 'B's
> >> >>It provides an Iterator() over these 'B's
> >> >>
> >> >>Class 'B' contains many 'C's
> >> >>It provides an Iterator() over these 'C's
> >> >>
> >> >>I would like to add a method to class 'A'
> >> >>that returns an iterator over the 'C's it
> >> >>(indirectly) contains.
> >> >>
> >> >>The obvious way is to use the 'A' level iterator
> >> >>to get all the 'B's, and to add the iterator from
> >> >>each 'B' to a ChainedIterator, whic gives the correct result.
> >> >>
> >> >>However, if A is large, the resulting ChainedIterator
> >> >>has is also large, and potentially time consuming to generate.
> >> >>
> >> >>Essentially we've been forced to build (something like)
> >> >>the list of 'B's which is what the various Iterators in
> >> >>Collections are designed to avoid.
> >> >>
> >> >>I would like (somehow) to iterate over the 'C's directly,
> >> >>by somehow "nesting" (as opposed to chaining) the 2 levels
> >> >>of iteration, but cannot see how.
> >> >>
> >> >>      BugBear (AKA P Womack)
> >> >>
> >> >>
> >> >>---------------------------------------------------------------------
> >> >>To unsubscribe, e-mail: commons-user-unsubscribe@jakarta.apache.org
> >>
>
>


----------------------------------------------------------------------------
----


> /*
>  * $Header: /safe/cvs/event/src/com/papermule/util/IteratorIterator.java,v
1.2 2004/02/25 17:28:28 bugbear Exp $
>  * $Revision: 1.2 $
>  * $Date: 2004/02/25 17:28:28 $
>  *
>  * ====================================================================
>  *
>  * The Apache Software License, Version 1.1
>  *
>  * Copyright (c) 1999-2001 The Apache Software Foundation.  All rights
>  * reserved.
>  *
>  * Redistribution and use in source and binary forms, with or without
>  * modification, are permitted provided that the following conditions
>  * are met:
>  *
>  * 1. Redistributions of source code must retain the above copyright
>  *    notice, this list of conditions and the following disclaimer.
>  *
>  * 2. Redistributions in binary form must reproduce the above copyright
>  *    notice, this list of conditions and the following disclaimer in
>  *    the documentation and/or other materials provided with the
>  *    distribution.
>  *
>  * 3. The end-user documentation included with the redistribution, if
>  *    any, must include the following acknowlegement:
>  *       "This product includes software developed by the
>  *        Apache Software Foundation (http://www.apache.org/)."
>  *    Alternately, this acknowlegement may appear in the software itself,
>  *    if and wherever such third-party acknowlegements normally appear.
>  *
>  * 4. The names "The Jakarta Project", "Commons", and "Apache Software
>  *    Foundation" must not be used to endorse or promote products derived
>  *    from this software without prior written permission. For written
>  *    permission, please contact apache@apache.org.
>  *
>  * 5. Products derived from this software may not be called "Apache"
>  *    nor may "Apache" appear in their names without prior written
>  *    permission of the Apache Group.
>  *
>  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
>  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
>  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
>  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
>  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
>  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
>  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
>  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
>  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
>  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
>  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
>  * SUCH DAMAGE.
>  * ====================================================================
>  *
>  * This software consists of voluntary contributions made by many
>  * individuals on behalf of the Apache Software Foundation.  For more
>  * information on the Apache Software Foundation, please see
>  * <http://www.apache.org/>.
>  *
>  */
> package com.papermule.util;
>
> import org.apache.commons.collections.iterators.*;
>
> import java.util.ArrayList;
> import java.util.Collection;
> import java.util.Collections;
> import java.util.Iterator;
> import java.util.List;
> import java.util.NoSuchElementException;
>
> /**
> IteratorIterator takes an {@link java.util.Iterator} which itself
> returns Iterators from it's next() method.
> Iterating over the IteratorIterator will
> iterate over the items returned by each
> successive Iterator in turn.<p>
>
> Note in the example below, that if
> outerContainer had a long list of "hasInt"s,
> the IteratorChain required to iterate over
> the integers could itself be expensive in terms
> of build time and storage.<p>
>
> Example:<br>
> <pre>
> class hasInt {
>     private List inner; // list of integers
>     List getInner() {
>         return inner;
>     }
> }
>
> class outerContainer {
>     List listOfHasInt;
>     // transforms an Instance of hasInt into an Iterator
>     // over the integers of the hasInt
>     static private Transformer trns = new Transformer() {
>         public Object transform(Object o) {
>             return ((hasInt)o).getInner().iterator();
>         }
>     };
>
>     // returns an Iterator over all the integers held (indirectly)
>     Iterator allInt() {
>         return new IteratorIterator(new
TransformIterator(listOfHasInt.iterator(), trns));
>     }
> }
> </pre>
> @see org.apache.commons.collections.iterators.IteratorChain
> */
>
> public class IteratorIterator implements Iterator {
>
>     protected final Iterator iteratorIterator;
>     protected Iterator currentIterator = null;
>     // the "last used" Iterator is the Iterator upon which
>     // next() or hasNext() was most recently called
>     // used for the remove() operation only
>     protected Iterator lastUsedIterator = null;
>
>     // ComparatorChain is "locked" after the first time
>     // compare(Object,Object) is called
>     protected boolean isLocked = false;
>
>     /**
>      * Construct an IteratorIterator with a single Iterator over Iterators
>      *
>      * @param iterator Iterator who's next() returns Iterators
>      */
>     public IteratorIterator(Iterator iterator) {
>         super();
>         iteratorIterator = iterator;
>     }
>
>     // throw an exception if the IteratorIterator is locked
>     private void checkLocked() {
>         if (isLocked == true) {
>             throw new UnsupportedOperationException("IteratorIterator
cannot be changed after the first use of a method from the Iterator
interface");
>         }
>     }
>
>     private void lockChain() {
>         isLocked = true;
>     }
>
>     // call this before any Iterator method to make sure that the current
Iterator
>     // is not exhausted
>     protected void updateCurrentIterator() {
>         if (currentIterator == null) {
>             if(iteratorIterator.hasNext()) {
>                 currentIterator = (Iterator)iteratorIterator.next();
>             } else {
>                 // use a real, but empty, place holder.
>                 currentIterator = EmptyIterator.iterator();
>             }
>             // set last used iterator here, in case the user calls remove
>             // before calling hasNext() or next() (although they
shouldn't)
>             lastUsedIterator = currentIterator;
>         }
>
>         while (currentIterator.hasNext() == false &&
iteratorIterator.hasNext()) {
>             currentIterator = (Iterator) iteratorIterator.next();
>         }
>     }
>
>     /**
>      * Return true if any Iterator in the IteratorIterator has a remaining
>      * element.
>      *
>      * @return true if elements remain
>      */
>     public boolean hasNext() throws UnsupportedOperationException {
>         lockChain();
>         updateCurrentIterator();
>         lastUsedIterator = currentIterator;
>
>         return currentIterator.hasNext();
>     }
>
>     /**
>      * Returns the next Object of the current Iterator
>      *
>      * @return Object from the current Iterator
>      * @exception NoSuchElementException
>      *                   if all the Iterators are exhausted
>      */
>     public Object next() throws NoSuchElementException,
UnsupportedOperationException {
>         lockChain();
>         updateCurrentIterator();
>         lastUsedIterator = currentIterator;
>
>         return currentIterator.next();
>     }
>
>     /**
>      * Removes from the underlying collection the last element
>      * returned by the Iterator.  As with next() and hasNext(),
>      * this method calls remove() on the underlying Iterator.
>      * Therefore, this method may throw an
>      * UnsupportedOperationException if the underlying
>      * Iterator does not support this method.
>      *
>      * @exception UnsupportedOperationException
>      *                   if the remove operator is not supported by the
underlying
>      *                   Iterator.
>      * @exception 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() throws UnsupportedOperationException,
IllegalStateException  {
>         lockChain();
>         updateCurrentIterator();
>
>         // implementation by delegation
>         lastUsedIterator.remove();
>     }
> }
>
>


---------------------------------------------------------------------
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