3

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:

  1. 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)
    
2
  • 1
    The second case; the first approach is essentially a convoluted/raundabout way to do a regular iterator (not a cursor). Cursor, as described here, is essentially a special case of the memento pattern; it has a special interface visible only to the aggregate (this is either done using an access modifier of some sort, or by contract/convention, depending on the language), and what the aggregate does is it transfers the responsibility of keeping track of the current position to the client (and only that), without exposing internal state (kind of like a stateless service). Nov 11, 2019 at 18:33
  • @FilipMilovanović You are right, I should have checked the footnote: "Cursors are a simple example of the Memento (316) pattern and share many of its implementation issues." So a cursor is the Memento class and an aggregate is the Originator class of the Memento pattern. Could you post this as an answer so that I can accept it?
    – Géry Ogam
    Nov 11, 2019 at 20:45

2 Answers 2

2

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.

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.