Iterators

One operation that "collection" ADTs such as lists, sets, etc. have to support is iteration - walking through each element of the the collection. Lets extend the int_stack ADT with a mechanism for implementing iteration.

One way is to simply perform the iteration. Thus

	for( i = len_int_stack(stack)-1; i >= 0; i-- ) {
	   int el = val_int_stack(stack, i);
	   /* do stuff */
	}

This is unacceptable. It completely exposes the details of the implementation. If, for instance, we were to change the implementation of int_stack from a resized array to a linked list, we would have to modify code spread out across the entire program.

Another approach is to use a second iterator type. Iterator types support an API that includes init_, is_more_, next_ and get_ functions. Thus, assume we defined a type called int_stack_iter. Using that, we could write an iterator loop as:

	for( init_int_stack_iter(I);
		is_more_int_stack_iter(I);
		next_int_stack_iter(I) ) {
	  int el = get_int_stack_iter(I);
	  /* do stuff with el */
	}

In general, I find this approach too convoluted. Also, for more complicated data-structures, the performance overhead of using a separate iterator data structure can become large.

Instead, I prefer to use macros. I define FOR_INT_STACK() and END_INT_STACK() macros that I use as:

	FOR_INT_STACK(stack, el)
	  /* do stuff with el */
	END_INT_STACK

The definition of the macro, in the case of int_stack at least, is straight-forward.

	#define FOR_INT_STACK(_stack, _val) \
	  { \
	    struct cell_int_stack * _st = _stack; \
	    int	_i; \
	    for( _i = len_int_stack(_st)-1; _i >= 0; _i-- ) { \
	      int	_val = val_int_stack(_st, _i);

	#define END_INT_STACK \
	    } \
	  }

Now, if we were to change the implementation of int_stack so that it used a linked list, we would need only to change the definition of the macro.

	#define FOR_INT_STACK(_stack, _val) \
	  { \
	    struct cell_int_stack * _st = _stack; \
	    struct cell_int_stack * _p; \
	    struct cell_int_stack * _q; \
	    for( _p = list_int_stack(_st); _p; _p = _q) { \
	      _q = next_cell_int_stack(_st); \
	      { \
	        int _val = val_cell_int_stack(_st);

	#define END_INT_STACK \
	      } \
	    } \
	  }

Some rules I follow when writing iterators:

• The bound variable (e.g. el) is declared within the iterator.
• continue and break should do what the programmer expects. If that is not possible use a different prefix for the iterator (e.g. FOR2_).
• Reassignment of the input(s) to the iterator within the body of the iterator should not matter. This is why stack is copied to _st.
• If the current element of the collection is deleted, the iterator should continue to work. That is why we save next_cell_int_stack(_stack) in _q in the above implementation.

Actually this is not really the implementation that I would recommend. What I would do is in the public header add the declaration of FOR_INT_STACK as:

	/* int_stack.h */
	#define FOR_INT_STACK(_stack, _i)	X_FOR_INT_STACK(_stack, _i)
	#define END_INT_STACK			X_END_INT_STACK