School of Engineering and Applied Science
Department of Computer Science
CSci 133 -- Algorithms and Data Structures I
http://www.seas.gwu.edu/~csci133/spring06
Prof. Michael B. Feldman
mfeldman@gwu.edu

Passive and Active Iteration in Collection Classes

Many reusable classes represent a collection of objects. Such classes often provide a method that moves through the collection, one element at a time, until each element in the class has been “visited” exactly once.

Formally, we call such a method a passive iterator method. An iterator is any operation that iterates through a data structure one element at a time; we call it passive because the client program simply calls it once and “stands back” passively while the iterator roams through the entire structure. Sometimes the term internal is used instead of passive. Java's toString method is a passive iterator: the client preogram  calls it and gets a string back that represents the whole collection.

Sometimes an application requires iterating through a structure, touching each element once, but allowing the client program the flexibility to decide just when to proceed to the next element. Moving through a structure in this fashion is called active iteration (sometimes called external) because the client program is actively involved in the process at every step.

Active Iterator Operations

To be actively involved in the iteration, the client program must execute a loop. We know that any loop must contain statements for loop initialization, termination, and incrementation; to support active iteration, the data structure package must provide these operations, and also one for retrieval of the current element in the traversal. We will call these operations initializeIteration, hasCurrentElement, advanceToNextElement, and getCurrentValue, respectively. The only one that needs explanation is hasCurrentElement; this is a boolean method that returns true if and only if we are not yet at the end of the iteration, that is, if there still is a current element.

Suppose the collection contains elements of type someObject, anObject is a variable of that type, and myCollection is a collection, then the basic client-program algorithm for active iteration is

myCollection.initializeIteration();       // loop initialization
while (myCollection.hasCurrentElement())  // loop termination condition
{
  anObject = myCollection.getCurrentValue();

  // process the current element here

  myCollection.advanceToNextElement();    // loop incrementation step
}

The implementation details of these operations depend upon the way the data structure is implemented. For example, if the collection is stored in an array, then we can declare a private variable currentElementIndex that gives the array subscript of the current element. The iteration methods might be implemented as follows:

(end of article)