Abstract

The Super Iterator pattern, like the standard Iterator pattern, traverses an unknown data structure without exposing that structure. With the standard Iterator pattern, clients must create a different iterator for each new structure, and the object returned must be of the specific type stored in the structure, even when they share a common super class. With the Super Iterator pattern, the object returned is of the common super class, and the iterator itself need not be altered when adding a new subtype with custom data structures. The client, however, must change two lines of code to load and instantiate the new subclass.

Introduction

The Super Iterator design pattern emerged because we needed a more extendable version of the Gang of Four Iterator pattern [1]. We have designed an optimisation library to allocate resources for wilderness Search and Rescue. There are many algorithms in the Operations Research literature, depending on whether the target is moving or fixed, the number of resource types, etc. The algorithms often have their own highly optimised and idiosyncratic data structures [2, 3], but in the end, they all allocate resources to areas. So clients should be able to treat all allocations the same, regardless of how they were created and without knowledge of – or interference with – their management.

New algorithms should not alter the rest of the library; neither should we transform the data into some generic structure likely to be suboptimal. With the Super Iterator pattern, developers wishing to switch to a newly available resource allocation algorithm need change only two lines of their code: first, they include the new algorithm’s header file, second, they change one line of code to create an allocation object of the new type instead of the old type. Once the type is created under this pattern all the rest of their code will work as it did before with no other changes. This pattern lowers the burden for application developers who wish to integrate the latest research. It also lowers the burden for researchers who can reuse testharnesses to evaluate new algorithms.

II. Intent

• Avoid coupling the sender of a request to its receiver.
• Allow the sender to iterate over an arbitrary data structure of receiver’s subtype as if it were a sequence of super-type, without customized external helper classes.

III. Motivation

While developing our library, we found a new algorithm for multiple resource types [2]. It was highly optimized with a peculiar but very efficient data structure. Still, it did what all these algorithms do – allocated resources to areas. Clients needed to see it as a generic allocation. The traditional Iterator pattern didn’t work – the client would have to know what kind of iterator to make, and unpack whatever peculiar object it pointed to. It was clear we could expect similar problems for most new algorithms.

The “obvious” answer was to make each algorithm convert or copy its objects to a generic allocation table. But the idea was repugnant – the data was already there, efficiently packed. Why copy it? Furthermore, modifiable allocations presented a synchronization problem, and overhead. The approach also complicated things for the developer.

We needed abstraction. The Super Iterator pattern uses a single set of iterators for all subclasses and protects the data from alteration. Therefore clients can switch algorithms just
by changing the initial call type. The iterators they previously coded will work as before, even though the new algorithm may consider many more factors and create a much more complicated structure.

To make it work, each algorithm makes available a set of helper methods that befriend the generic iterators. In effect this moves the mechanics of the GoF helper classes inside
the algorithms, hiding them from the client.

Read the full paper.

Full citation: Andre Oboler, Charles Twardy and David Albrecht, Super Iterator: A design pattern for Algorithm and Data structure collections, in proceedings of Fourth International Conference on Information Technology : New Generations (ITNG 2007), Las Vegas, Nevada, USA, April 2-4, 2007