How to implement a cursor iterator?

Question

In the "Structure" section of the Iterator design pattern, the book Design Patterns: Elements of Reusable Object-Oriented Software defines the Iterator class with four basic operations: First, Next, IsDone and CurrentItem.

In the "Implementation" section, the book contains the following item:

2. Who defines the traversal algorithm? The iterator is not the only place where the traversal algorithm can be defined. The aggregate might define the traversal algorithm and use the iterator to store just the state of the iteration. We call this kind of iterator a cursor, since it merely points to the current position in the aggregate. A client will invoke the Next operation on the aggregate with the cursor as an argument, and the Next operation will change the state of the cursor.

   If the iterator is responsible for the traversal algorithm, then it’s easy to use different iteration algorithms on the same aggregate, and it can also be easier to reuse the same algorithm on different aggregates. On the other hand, the traversal algorithm might need to access the private variables of the aggregate. If so, putting the traversal algorithm in the iterator violates the encapsulation of the aggregate.

But no example implementation of a cursor iterator is provided.

Who should expose the interface for controlling the iteration, the cursor iterator or the aggregate?

Here after is how I would implement the two alternatives in Python.

• If the cursor iterator exposes the iteration interface, in addition to the GetState and SetState operations, it should define the First, Next, IsDone and CurrentItem basic operations and delegate to the corresponding aggregate operations:

  class Iterator:
  
      def __init__(self, aggregate):
          self.__aggregate = aggregate
  
      def first(self):
          self.__aggregate._first(self)
  
      def next(self):
          self.__aggregate._next(self)
  
      def is_done(self):
          return self.__aggregate._is_done(self)
  
      def current_item(self):
          return self.__aggregate._current_item(self)
  
      def _get_state(self):
          return self.__state
  
      def _set_state(self, state):
          self.__state = state
  

  And the aggregate should define the same basic operations which retrieve and update the cursor iterator state using its GetState and SetState operations:

  class Aggregate:
  
      def __init__(self, list):
          self.__list = list
  
      def _first(self, iterator):
          iterator._set_state(0)
  
      def _next(self, iterator):
          iterator._set_state(iterator._get_state() + 1)
  
      def _is_done(self, iterator):
          return iterator._get_state() >= len(self.__list)
  
      def _current_item(self, iterator):
          if self._is_done(iterator):
              raise ValueError
  
          return self.__list[iterator._get_state()]
  
      def create_iterator(self):
          return Iterator(self)
  

  The client would then use the cursor iterator to control the iteration:

  aggregate = Aggregate(["foo", "bar", "baz", "qux"])
  iterator = aggregate.create_iterator()
  iterator.first()
  
  while not iterator.is_done():
      print(iterator.current_item())
      iterator.next()
  

• If the aggregate exposes the iteration interface, the cursor iterator should define the GetState and SetState operations:

  class Iterator:
  
      def _get_state(self):
          return self.__state
  
      def _set_state(self, state):
          self.__state = state
  

  And the aggregate should define the First, Next, IsDone and CurrentItem basic operations which retrieve and update the cursor iterator state using its GetState and SetState operations:

  class Aggregate:
  
      def __init__(self, list):
          self.__list = list
  
      def first(self, iterator):
          iterator._set_state(0)
  
      def next(self, iterator):
          iterator._set_state(iterator._get_state() + 1)
  
      def is_done(self, iterator):
          return iterator._get_state() >= len(self.__list)
  
      def current_item(self, iterator):
          if self.is_done(iterator):
              raise ValueError
  
          return self.__list[iterator._get_state()]
  
      def create_iterator(self):
          return Iterator()
  

  The client would then use the aggregate to control the iteration:

  aggregate = Aggregate(["foo", "bar", "baz", "qux"])
  iterator = aggregate.create_iterator()
  aggregate.first(iterator)
  
  while not aggregate.is_done(iterator):
      print(aggregate.current_item(iterator))
      aggregate.next(iterator)
  

Answer 1

The correct approach for the cursor is option 2

The answer is already in your quote, which describes option 2:

(...) We call this kind of iterator a cursor, since it merely points to the current position in the aggregate. A client will invoke the Next operation on the aggregate with the cursor as an argument, and the Next operation will change the state of the cursor.

The wording strongly suggests that an aggregate can have several cursors, pointing to several positions. Since the aggregate defines the traversal algorithm, it means that the cursor must help to restore the state of this algorithm when it lead to the current position.

One of the easiest way to manage this, is to save the state into the cursor. This solution is suggested in the footnote (although it's not the only solution):

cursor are a simple example of the Memento pattern and share many of its implementation issues.

For reminder, one of the main issue with the memento implementation is to offer an interface to save and restore the state, without letting other classes interfere. Note however that the cursor does not need to restore the sate: it can be the state.

But option 1 is a near miss

Option 1 is not far from the cursor: it delegates to the aggregate the responsibility for the traversal algorithm, and it provides this algorithm with itself as argument. Furthermore the traversal algorithm seems to store its state in the iterator. So from the point of view of the aggregate, this would be a cursor.

But the interface of option 1 is that of a classical iterator and not of a cursor as described in the quote. The fact that it behaves like a cursor is a completely encapsulated implementation detail.

So from the client point of view, it's not a cursor, but an iterator that could be replaced with any other classical, self-standing iterator implementation.

Answer 2

tl;dr: use your language's recommended pattern.

The dilemma between iterator methods belonging to the aggregate or to the iterator looks like a classical pseudo-question of "object oriented design" to me. It is not different from "is writing text a method of pen, paper, hand, or the text". There is no definite answer to it in general, you should pick the way which would look more comprehensible for your case.

Luckily, for the specific topic of iterator, there is the answer in many specific cases. Most high-level languages provide interfaces for iterations which they should implement so that the language's iterating statements would recognize it. For python2 it was generators, now it may change to something which I cannot claim. For C++ you should use range expressions. For C# you should implement IEnumerable<T> interface. And so on.