ObjectSpace Homepage

JGL - The Generic Collection Library for Java
Contents Function Objects Voyager

Iterators

Iterators and Algorithms
Iterators and Containers
Reverse Iterators
Insertion Iterators
Iterating over Java Streams

Most Java programmers are familiar with the concept of an iterator, which is an object that may be used to traverse a sequence of elements, whether they are in a JGL container, a JDK container, a native Java array, a Java stream, or another kind of sequence. The JDK Enumeration is a kind of iterator that is created by invoking elements() on a JDK container. When an Enumeration is first created, it is positioned at the first element of the container. As long as hasMoreElements() returns true, it is safe to use nextElement() to get the element that the Enumeration is currently positioned at and then advance the Enumeration to the next element.

An Enumeration is a limited form of iterator because it is read-only and can only be advanced by one position at a time. JGL includes a more powerful hierarchy of interfaces that embrace and extend Enumeration, as shown by the following diagram.

Here is a brief overview of each iterator interface.

Iterator Interface Description
InputIterator can read one item at a time, in a forward direction only
OutputIterator can write one item at a time, in a forward direction only
ForwardIterator combines characteristics of input and output iterators
BidirectionalIterator like forward, plus the ability to move backwards
RandomAccessIterator like bidirectional, plus the ability to jump by an arbitrary distance

Each JGL container has an associated class of iterator. Here is a table that lists every JGL container class in alphabetical order together with its associated iterator and the interface that its iterator implements.

Container Associated Iterator Iterator Interface
Array ArrayIterator RandomAccessIterator
BooleanArray
BooleanBuffer 		BooleanIterator RandomAccessIterator
ByteArray
ByteBuffer 		ByteIterator RandomAccessIterator
CharArray
CharBuffer 		CharIterator RandomAccessIterator
Deque DequeIterator RandomAccessIterator
DoubleArray
DoubleBuffer 		DoubleIterator RandomAccessIterator
FloatArray
FloatBuffer 		FloatIterator RandomAccessIterator
IntArray
IntBuffer 		IntIterator RandomAccessIterator
DList DListIterator BidirectionalIterator
HashMap HashMapIterator ForwardIterator
ObjectArray ObjectIterator RandomAccessIterator
OrderedMap OrderedMapIterator BidirectionalIterator
OrderedSet OrderedSetIterator BidirectionalIterator
PriorityQueue ArrayIterator RandomAccessIterator
Queue Same as underlying sequenceSame as underlying sequence
HashSet HashSetIterator ForwardIterator
ShortArray
ShortBuffer 		ShortIterator RandomAccessIterator
SList SListIterator ForwardIterator
Stack Same as underlying sequenceSame as underlying sequence
VectorArray VectorIterator RandomAccessIterator

For compatibility with JDK, all JGL containers respond to elements() by returning an instance of their associated iterator class cast to an Enumeration and positioned at their first element. The following example uses an Enumeration to iterate through every element of an Array.


Example Iterators1.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import java.util.Enumeration;

public class Iterators1
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "magical" );
    array.add( "mystery" );
    array.add( "tour" );
    Enumeration iterator = array.elements();
    while ( iterator.hasMoreElements() )
      System.out.println( iterator.nextElement() );
    }
  }

Output
magical
mystery
tour

All JGL containers respond to start() by returning an instance of their associated iterator class cast to a ForwardIterator and positioned at the first element. finish() works in a similar fashion except that the iterator is positioned immediately after the last element.

All JGL iterators may be compared using equals(), cloned using the standard clone() message, and advanced by one or more positions using advance(). You can read the object that an iterator is currently positioned at by using get(), and replace the object that an iterator is currently positioned at by using put(). The following example uses these operations to convert every String in an Array and a DList to uppercase.


Example Iterators2.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;

public class Iterators2
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "magical" );
    array.add( "mystery" );
    array.add( "tour" );
    System.out.println( "before array = " + array );
    toUppercase( array );
    System.out.println( "after array = " + array );

    DList list = new DList();
    list.add( "magical" );
    list.add( "mystery" );
    list.add( "tour" );
    System.out.println( "before list = " + list );
    toUppercase( list );
    System.out.println( "after list = " + list );
    }

  static void toUppercase( Container container )
    {
    // Obtain iterator positioned at first element.
    ForwardIterator iterator = container.start();

    // Obtain iterator positioned immediately after last element.
    ForwardIterator end = container.finish();

    // Loop through every element.
    while ( !iterator.equals( end ) )
      {
      String current = (String) iterator.get();
      // Replace current element with uppercase equivalent.
      iterator.put( current.toUpperCase() );
      iterator.advance(); // Move forward by one element.
      }
    }
  }

Output
before array = Array( magical, mystery, tour )
after array = Array( MAGICAL, MYSTERY, TOUR )
before list = DList( magical, mystery, tour )
after list = DList( MAGICAL, MYSTERY, TOUR )

In most cases, the functionality of an Enumeration or a ForwardIterator will suffice. However, there are occasions that require you to use the full power of the container's native iterator type. For example, a BidirectionalIterator can also move backwards by one or more positions using retreat(), and can get and put elements that are a specified distance (ahead or behind) from their current position using a more powerful version of get() and put(). All JGL containers respond to begin() by returning an uncast instance of their associated iterator class positioned at their first element. Similarly, end() returns an uncast instance of a container's associated iterator class that is positioned immediately after its last element.

The following example uses some of these more advanced features to iterator backwards through an Array. Note that the same thing can be accomplished more easily by using a reverse iterator, described later in this chapter.


Example Iterators3.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;

public class Iterators3
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "ape" );
    array.add( "giraffe" );
    array.add( "lizard" );
    System.out.println( "array = " + array );

    // Obtain iterator positioned "just-past-the-end".
    ArrayIterator iterator = array.end();

    // Obtain iterator positioned at first element.
    ArrayIterator begin = array.begin();

    while ( !iterator.equals( begin ) )
      {
      iterator.retreat();
      System.out.println( iterator.get() );
      }
    }
  }

Output
array = Array( ape, giraffe, lizard )
lizard
giraffe
ape

Iterators and Algorithms

All JGL algorithms can be easily applied to an entire container. However, there are occasions where you might want to apply an algorithm to a sub-range of a container. Most algorithms therefore have a variation that allows you to specify a sub-range by supplying an iterator positioned at the first element of the range and another iterator positioned immediately after the last element of the range. The following two lines of code are therefore equivalent:

  Sorting.sort( array );
  Sorting.sort( array.begin(), array.end() );

The following example uses iterator-based versions of the sort and replace algorithms to sort the first half of an Array and to replace every 7 in the last three elements with a 0.


Example Iterators4.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import com.objectspace.jgl.algorithms.*;

public class Iterators4
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( new Integer( 4 ) );
    array.add( new Integer( 7 ) );
    array.add( new Integer( 2 ) );
    array.add( new Integer( 7 ) );
    array.add( new Integer( 1 ) );
    array.add( new Integer( 7 ) );
    System.out.println( "array = " + array );

    // Obtain iterator positioned at first element.
    ArrayIterator first = array.begin();

    // Obtain iterator positioned immediately after third element.
    ArrayIterator last = array.begin();
    last.advance( 3 );

    // Sort first three elements.
    Sorting.sort( first, last );
    System.out.println( "array = " + array );

    // Replace 7 with 0 in last three elements.
    Replacing.replace( last, array.end(), new Integer( 7 ), new Integer( 0 ) );
    System.out.println( "array = " + array );
    }
  }

Output
array = Array( 4, 7, 2, 7, 1, 7 )
array = Array( 2, 4, 7, 7, 1, 7 )
array = Array( 2, 4, 7, 0, 1, 0 )

Iterators and Containers

All operations can be performed on JGL containers without any knowledge of iterators. However, there are a few methods that can operate more efficiently with iterators. For example, let's say you wish to remove the first occurrence of a particular object from a DList. One way to do this is to use indexOf() to find the index of the first occurrence and then use index-based version of remove() to delete the node with that index. However, since a DList is not random access, the index-based versions of the methods can only reach a node with a particular index by starting at the head node and moving link by link until the specified node is reached. For long DLists, this would be very slow. A more efficient way to achieve the same result is to use find() to obtain an iterator positioned at the first occurrence and then use the iterator-based version of remove() to delete the node that the iterator is positioned at. Because the iterator refers directly to the node, it is very fast to unlink the node and no list traversal is necessary. The following example illustrates this technique.


Example Iterators5.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;

public class Iterators5
  {
  public static void main( String[] args )
    {
    DList list = new DList();
    list.add( "ape" );
    list.add( "bat" );
    list.add( "cat" );
    list.add( "dog" );
    System.out.println( "list = " + list );
    DListIterator iterator = list.find( "cat" );
    System.out.println( "iterator positioned @ " + iterator.get() );
    list.remove( iterator );
    System.out.println( "list = " + list );
    }
  }

Output
list = DList( ape, bat, cat, dog )
iterator positioned @ cat
list = DList( ape, bat, dog )

Another example of an iterator-oriented method is equalRange() in HashMap. This method returns a pair of iterators, with the first iterator positioned at the first occurrence of a particular key and the second iterator positioned immediately after the last occurrence of the key.

Note that HashMapIterator and OrderedMapIterator both contain the methods key() and value() which allow you to read the key and value associated with the iterators current position, respectively. They also both contain a version of value() that allows you to modify the value that the iterator is currently positioned at.

The following example illustrates most of these features.


Example Iterators6.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;

public class Iterators6
  {
  public static void main( String[] args )
    {
    HashMap map = new HashMap( true ); // allow duplicates
    map.add( "cat", "beauty" );
    map.add( "dog", "marble" );
    map.add( "cat", "agatha" );
    map.add( "fox", "paula" );
    System.out.println( "map = " + map );

    Range range = map.equalRange( "cat" );
    HashMapIterator iterator = (HashMapIterator) range.begin;
    HashMapIterator last = (HashMapIterator) range.end;
    while ( !iterator.equals( last ) )
      {
      System.out.print( "pair = " + iterator.get() );
      System.out.print( ", key = " + iterator.key() );
      System.out.println( ", value = " + iterator.value() );
      iterator.advance();
      }
    }
  }

Output
map = HashMap( Pair( dog, marble ), Pair( fox, paula ), Pair( cat, beauty ), Pair( cat, agatha ) )
pair = Pair( cat, beauty ), key = cat, value = beauty
pair = Pair( cat, agatha ), key = cat, value = agatha

Reverse Iterators

Reverse iterators are just like regular iterators except that they traverse a sequence backwards instead of forwards. To iterator backwards through a container, construct a ReverseIterator onto a BidirectionalIterator that is positioned immediately after the end of the container. nextElement() moves a reverse iterator's underlying iterator one place backwards and then returns its current item. hasMoreElements() returns true until the reverse iterator has read the first element of the container.

The following example uses a reverse iterator for iterating backwards through an Array of Strings.


Example Iterators7.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import com.objectspace.jgl.util.*;

public class Iterators7
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "ape" );
    array.add( "bat" );
    array.add( "cat" );
    array.add( "dog" );
    System.out.println( "array = " + array );

    ReverseIterator iterator = new ReverseIterator( array.end() );
    while ( iterator.hasMoreElements() )
      System.out.println( iterator.nextElement() );
    }
  }

Output
array = Array( ape, bat, cat, dog )
dog
cat
bat
ape

Insertion Iterators

JGL includes an output iterator called an InsertIterator that adds an object to a specified container using add() whenever the iterator is written to. The following example uses an InsertIterator to append the results of a transform() algorithm to a Deque.


Example Iterators8.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import com.objectspace.jgl.algorithms.*;
import com.objectspace.jgl.functions.*;
import com.objectspace.jgl.util.*;

public class Iterators8
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "ape" );
    array.add( "giraffe" );
    array.add( "elephant" );
    System.out.println( "array = " + array );

    Deque deque = new Deque();
    InsertIterator iterator = new InsertIterator( deque );
    UnaryFunction function = new LengthString();
    Transforming.transform( array, iterator, function );
    System.out.println( "deque = " + deque );
    }
  }

Output
array = Array( ape, giraffe, elephant )
deque = Deque( 3, 7, 8 )

Iterating over Java Streams

JGL allows you to construct an iterator onto a java.io.OutputStream by using the OutputStreamIterator class. When an object is written using put(), it is converted into a string using toString() and then written to the output stream. The default constructor connects the iterator to System.out. The following example uses an OutputStreamIterator to send the contents of a Array to the standard output stream.


Example Iterators9.java
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import com.objectspace.jgl.algorithms.*;
import com.objectspace.jgl.util.*;
import java.util.Enumeration;

public class Iterators9
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "ape" );
    array.add( "bat" );
    array.add( "cat" );

    OutputStreamIterator output = new OutputStreamIterator( System.out );
    Enumeration input = array.elements();

    while ( input.hasMoreElements() )
      output.put( input.nextElement() );
    System.out.println(); // Flush output.

    // You can use an algorithm to do the same thing.
    Copying.copy( array, output );
    System.out.println(); // Flush output.
    }
  }

Output
ape bat cat
ape bat cat

Contents Function Objects Voyager