Chapter 8: Reusability - TOC - 8.3 ADAPTABILITY

8.3.6 Iterators

guideline

Provide iterators for traversing complex data structures within reusable parts.

Consider providing both active and passive iterators.

Protect the iterators from errors due to modification of the data structure during iteration.

Document the behavior of the iterators when the data structure is modified during traversal.

example

Ada provides several mechanisms for building reusable iterators. The following examples discuss the alternatives of "simple" generics, access discriminants, and type extension. The terms active and passive are used to differentiate whether the iteration mechanism (i.e., the way in which the complex data structure is traversed) is exposed or hidden. A passive iterator hides the traversal (e.g., looping mechanism) and consists of a single operation, iterate, that is parameterized by the processing you do on each element of the data structure. By contrast, an active iterator exposes the primitive operations by which you traverse the data structure (Booch 1987).

The first example shows a generic package that defines an abstract list data type, with both active and passive iterators for traversing a list:

------------------------------------------------------------------------
generic
   type Element is limited private;
   ...
package Unbounded_List is
   type List is limited private;
   procedure Insert (New_Element : in     Element;
                     Into        : in out List);
   -- Passive (generic) iterator.
   generic
      with procedure Process (Each : in out Element);
   procedure Iterate (Over : in     List);
   -- Active iterator
   type Iterator is limited private;

   procedure Initialize (Index         : in out Iterator;
                         Existing_List : in     List);

   function  More       (Index         : in     Iterator)
     return Boolean;

   -- The procedure Get_Next combines an "Advance" and "Current" function
   procedure Get_Next   (Index           : in out Iterator;
                         Current_Element :    out Element);
   ...
private
   ...
end Unbounded_List;
------------------------------------------------------------------------

After instantiating the generic package and declaring a list as:

------------------------------------------------------------------------
with Unbounded_List;
procedure List_User is
   type Employee is ...;
   package Roster is
      new Unbounded_List (Element => Employee, ...);
   Employee_List : Roster.List;

the passive iterator is instantiated, specifying the name of the routine that should be called for each list element when the iterator is called.

   ---------------------------------------------------------------------
   procedure Process_Employee (Each : in out Employee) is
   begin
      ...
      -- Perform the required action for EMPLOYEE here.
   end Process_Employee;
   ---------------------------------------------------------------------
   procedure Process_All is
      new Roster.Iterate (Process => Process_Employee);

The passive iterator can then be called as:

begin  -- List_User
   Process_All (Employee_List);
end List_User;
------------------------------------------------------------------------

Alternatively, the active iterator can be used without the second instantiation required by the passive iterator:

   Iterator         : Roster.Iterator;
   Current_Employee : Employee;
   procedure Process_Employee (Each : in     Employee) is separate;
begin  -- List_User
   Roster.Initialize (Index         => Iterator,
                      Existing_List => Employee_List);

   while Roster.More (Iterator) loop

      Roster.Get_Next (Index           => Iterator,
                       Current_Element => Current_Employee);

      Process_Employee (Current_Employee);

   end loop;
end List_User;
------------------------------------------------------------------------

The second example shows a code excerpt from Rationale (1995, §3.7.1) on how to construct iterators using access discriminants:

generic
   type Element is private;
package Sets is
   type Set is limited private;
   ... -- various set operations
   type Iterator (S : access Set) is limited private;
   procedure Start (I : Iterator);
   function Done (I : Iterator) return Boolean;
   procedure Next (I : in out Iterator);
   ...  -- other iterator operations
private
   type Node;
   type Ptr is access Node;
   type Node is
      record
         E    : Element;
         Next : Ptr;
      end record;
   type Set is new Ptr;
   type Iterator (S : access Set) is
      record
         This : Ptr;
      end record;
end Sets;
package body Sets is
   ...  -- bodies of the various set operations
   procedure Start (I : in out Iterator) is
   begin
      I.This := Ptr(I.S.all);
   end Start;
   function Done (I : Iterator) return Boolean is
   begin
      return I.This = null;
   end Done;
   procedure Next (I : in out Iterator) is
   begin
      I.This := I.This.Next;
   end Next;
   ...
end Sets;

The iterator operations allow you to iterate over the elements of the set with the component This of the iterator object accessing the current element. The access discriminant always points to the enclosing set to which the current element belongs.

The third example uses code fragments from Rationale (1995, §4.4.4) to show an iterator using type extension and dispatching:

type Element is ...
package Sets is
   type Set is limited private;
   -- various set operations
   type Iterator is abstract tagged null record;
   procedure Iterate (S : in Set; IC : in out Iterator'Class);
   procedure Action (E : in out Element;
                     I : in out Iterator) is abstract;
private
   -- definition of Node, Ptr (to Node), and Set
end Sets;
package body Sets is
   ...
   procedure Iterate (S : in Set; IC : in out Iterator'Class) is
      This : Ptr := Ptr (S);
   begin
      while This /= null loop
         Action (This.E, IC);  -- dispatch
         This := This.Next;
      end loop;
   end Iterate;
end Sets;

The general purpose iterator looks like this:

package Sets.Something is
   procedure Do_Something (S : Set; P : Parameters);
end Sets.Something;
package body Sets.Something is
   type My_Iterator is new Iterator with
      record
         -- components for parameters and workspace
      end record;
   procedure Action (E : in out Element;
                     I : in out My_Iterator) is
   begin
      -- do something to element E using data from iterator I
   end Action;
   procedure Do_Something (S : Set; P : Parameters) is
      I : My_Iterator;
   begin  -- Do_Something
      ...  -- copy parameters into iterator
      Iterate (S, I);
      ... copy any results from iterator back to parameters
   end Do_Something;

end Sets.Something;

rationale

Iteration over complex data structures is often required and, if not provided by the part itself, can be difficult to implement without violating information hiding principles.

Active and passive iterators each have their advantages, but neither is appropriate in all situations. Therefore, it is recommended that both be provided to give the user a choice of which to use in each situation.

Passive iterators are simpler and less error-prone than active iterators, in the same way that the for loop is simpler and less error-prone than the while loop. There are fewer mistakes that the user can make in using a passive iterator. Simply instantiate it with the routine to be executed for each list element, and call the instantiation for the desired list. Active iterators require more care by the user. Care must be taken to invoke the iterator operations in the proper sequence and to associate the proper iterator variable with the proper list variable. It is possible for a change made to the software during maintenance to introduce an error, perhaps an infinite loop.

On the other hand, active iterators are more flexible than passive iterators. With a passive iterator, it is difficult to perform multiple, concurrent, synchronized iterations. For example, it is much easier to use active iterators to iterate over two sorted lists, merging them into a third sorted list. Also, for multidimensional data structures, a small number of active iterator routines may be able to replace a large number of passive iterators, each of which implements one combination of the active iterators. Finally, active iterators can be passed as generic formal parameters while passive iterators cannot because passive iterators are themselves generic, and generic units cannot be passed as parameters to other generic units.

For either type of iterator, semantic questions can arise about what happens when the data structure is modified as it is being iterated. When writing an iterator, be sure to consider this possibility, and indicate with comments the behavior that occurs in such a case. It is not always obvious to the user what to expect. For example, to determine the "closure" of a mathematical "set" with respect to some operation, a common algorithm is to iterate over the members of the set, generating new elements and adding them to the set. In such a case, it is important that elements added to the set during the iteration be encountered subsequently during the iteration. On the other hand, for other algorithms, it may be important that the iterated set is the same set that existed at the beginning of the iteration. In the case of a prioritized list data structure, if the list is iterated in priority order, it may be important that elements inserted at lower priority than the current element during iteration not be encountered subsequently during the iteration but that elements inserted at a higher priority should be encountered. In any case, make a conscious decision about how the iterator should operate, and document that behavior in the package specification.

Deletions from the data structure also pose a problem for iterators. It is a common mistake for a user to iterate over a data structure, deleting it piece by piece during the iteration. If the iterator is not prepared for such a situation, it is possible to end up dereferencing a null pointer or committing a similar error. Such situations can be prevented by storing extra information with each data structure, which indicates whether it is currently being iterated, and using this information to disallow any modifications to the data structure during iteration. When the data structure is declared as a limited private type, as should usually be the case when iterators are involved, the only operations defined on the type are declared explicitly in the package that declares the type, making it possible to add such tests to all modification operations.

The Rationale (1995, §4.4.4) notes that the access discriminant and type extension techniques are inversions of each other. In the access discriminant approach, you have to write out the looping mechanism for each action. In the type extension approach, you write one loop and dispatch to the desired action. Thus, an iterator that uses the access discriminant technique would be considered active, while an iterator that uses the type extension technique would be considered passive.

notes

You can use an access to subprogram type as an alternative to generic instantiation, using a nongeneric parameter as a pointer to subprogram. You would then apply the referenced subprogram to every element in a collection ( Rationale 1995, §3.7.2). There are drawbacks to this approach, however, because you cannot use it to create a general purpose iterator. Anonymous access to subprogram parameters is not allowed in Ada; thus, the following fragment is illegal:

procedure Iterate (C      : Collection;
                   Action : access procedure (E : in out Element));

The formal parameter Action must be of a named access subtype, as in:

type Action_Type is access procedure (E : in out Element);
procedure Iterate (C      : Collection;
                   Action : Action_Type);

In order for this to work, you must make sure that the action subprogram is in scope and not defined internal to another subprogram. If it is defined as a nested procedure, it would be illegal to access it. See the Rationale (1995, §4.4.4) for a more complete example.

For further discussion of passive and active iterators, see the Rationale (1995, §3.7.1 and §4.4.4), Ross (1989), and Booch (1987).