16.1.4 The forward-iteration protocol

Dylan's forward-iteration protocol allows us to connect the usual collection iteration functions to our new collection class. Connecting to the forward-iteration protocol is as simple as defining an appropriate method for the forward-iteration-protocol generic function. This method must return two objects and six functions.

// This method enables many standard and user-defined collection operations
define method forward-iteration-protocol 
    (sorted-sequence :: <sorted-sequence>)
 => (initial-state :: <integer>, limit :: <integer>,
     next-state :: <function>, finished-state? :: <function>,
     current-key :: <function>, current-element :: <function>,
     current-element-setter :: <function>, copy-state :: <function>)
  values(
         // Initial state
         0,
         // Limit
         sorted-sequence.size,
          // Next state
         method (collection :: <sorted-sequence>, state :: <integer>)
           state + 1
         end,
         // Finished state?
         method (collection :: <sorted-sequence>, state :: <integer>,
                 limit :: <integer>)
           state = limit;
         end,
         // Current key
         method (collection :: <sorted-sequence>, state :: <integer>)
           state
         end,

         // Current element
         element,
         // Current element setter
         method (value :: <object>, collection :: <sorted-sequence>, 
                 state :: <integer>)
           error("Setting an element of a sorted sequence 
                 is not allowed.");
         end,
         // Copy state
         identity);
end method forward-iteration-protocol; 

If we are to iterate over any collection, we must maintain some state to help the iterator remember the current point of iteration. For the forward-iteration protocol, we maintain this state using any object suitable for a given collection. In this case, an integer is sufficient to maintain where we are in the iteration process. The first object returned by forward-iteration-protocol is a state object that is suitable for the start of an iteration. The second object returned is a state object that represents the ending state of the iteration. Since, in this case, the state object is just the current key of the sorted sequence, the integer 0 is the correct initial state, and the integer that represents the size of the collection is the correct ending state.

The third value returned is a function that takes the collection and the current iteration state, and returns a state that is the next step in the iteration. In this case, we can determine the next state simply by adding 1 to the current state.

The fourth value returned is a function that receives the collection, the current state, and the ending state, and that determines whether the iteration is complete. In this case, we need only to check whether the current state is equal to the ending state.

The fifth value returned is a function that generates the current key into the collection, given a collection and a state. In this case, the key is the state object.

The sixth value returned is a function that receives a collection and a state, and returns the current element of the collection. In this case, the element function is the obvious choice, since our state is just the key.

The seventh value returned is a function that receives a new value, a collection, and a state, and changes the current element to be the new value. In this case, such an operation is illegal, since the only rational way to add elements to sorted sequences is with add!. Because this operation is illegal, an error is signaled.

The eighth and final value returned is a function that receives a collection and a state, and returns a copy of the state. In this case, we just return the state, because it is an integer and thus has no slots that are modified during the iteration process. If we represented the state with an object that had one or more slots that did change during iteration, we would have to make a new state instance and to copy the significant information from the old state instance to the new state instance.

Once we have defined a forward-iteration-protocol method for sorted sequences, we can iterate over them using for loops, mapping functions, and other collections iterators described in Chapter 11, Collections and Control Flow. Also, if someone defines a new iterator that uses the forward-iteration protocol, then this new iterator will work with sorted sequences.

Dylan has several other related protocols for backward iteration and for tables. See the The Dylan Reference Manual for details.