9 - Iterator
Tags: flutter, dart, oop, programming
Published: 2021-03-14 22:21:36

In the last article, I have analyzed one of the behavioural design patterns — Interpreter. This time I would like to represent the pattern which specific implementation(s) you have probably already used in your day-to-day programming without even noticing or considering it — the Iterator design pattern.

## Table of Contents

* What is the Iterator design pattern?
* Analysis
* Implementation
* Your Contribution

## What is the Iterator design pattern?

![Iterating Over The Graph](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qpcii7l1qbwi1a0rtvhw.gif)

**Iterator** is a **behavioural** design pattern, also known as **Cursor**. The intention of this design pattern is described in the [GoF book](https://en.wikipedia.org/wiki/Design_Patterns):

> Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

The key idea in this pattern is to take the responsibility for access and traversal out of the list object (or any other collection) and put it into an **iterator** object. This class defines an interface to iterate over the specific collection, access its elements and is responsible to track the current position of the iterator in the collection. Also, the collection interface is defined to store the underlying data structure which will be iterated over and provides a method to create the specific iterator for that particular collection. These abstractions over the collection and its iteration logic allow the client to use different data structures and iterate over them just like they would be the same by using both — iterator and collection — interfaces.

As I have already mentioned, you have probably already used this design pattern (at least its implementation) without even noticing it, especially if you are familiar with the development using Java or C#/.NET. For instance, all Java collections provide some internal implementations of the Iterator interface which is used to iterate over collection elements. In C# context, there are some special container types capable of holding a collection of values e.g. *List*, and *ArrayList*, which come with the possibility to iterate over them.

Let’s move to the analysis and implementation parts to understand the details about this pattern and to learn how to implement our custom iterator!

## Analysis

The general structure of the Iterator design pattern looks like this:

![Iterator Class Diagram](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j3aeoebgi3z8tq9wnq6s.png)

* *IterableCollection* — defines an interface for creating an *Iterator* object;
* *ConcreteCollection* — implements the *Iterator* creation interface to return a new instance of a particular specific iterator class each time the client requests one. This class could also contain additional code/logic e.g. to store the data structure which should be iterated;
* *Iterator* — defines an interface for accessing and traversing elements of the collection;
* *ConcreteIterator* — implements the *Iterator* interface. Also, this class should track the traversal progress e.g. the current position in the traversal of the collection;
* *Client* — references and uses both collections and iterators via their interfaces.

### Applicability

The Iterator design pattern should be used when you want to abstract the iteration logic of the collection, access its elements without exposing the internal structure of the collection itself. This promotes the idea of the [Single Responsibility Principle](https://en.wikipedia.org/wiki/Single_responsibility_principle) as well as the [DRY](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself) (Don’t Repeat Yourself) principle.

Furthermore, this pattern is useful when you want to traverse the same collection in several different ways, depending on what you want to accomplish. For instance, you want to have one iterator to iterate over the whole collection and another to iterate only over the specific collection items which match the filter criteria, or, let’s say, iterate over every second element in the collection. For this case, you do not need to bloat a single interface to implement different iteration algorithms, you just create different iterator classes implementing the same interface with their specific iteration logic.

Finally, the Iterator design pattern could help when you are not sure about the specific implementation of your data structures beforehand, but you want to implement the logic to traverse them and use it in your client. The pattern provides a couple of generic interfaces for both collections and iterators. Given that your code now uses these interfaces, it will still work if you pass it various kinds of collections and iterators that implement these interfaces.

## Implementation

![It's Time For Us To Implement Our Plan](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uyhbql3p9y7pj6vlto6e.gif)

First of all, to understand the implementation part better, you should be familiar with the tree data structure. If you are not following the series, I have explained it when analysing the Composite design pattern, but if you have already read this article — *10 points for Gryffindor*!

This time we will investigate one of the fundamental parts in graph theory — the [graph traversal](https://en.wikipedia.org/wiki/Graph_theory). The graph traversal is defined as:

> In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal.

This time, we will focus only on the tree traversal case. There are several graph/tree traversal algorithms available out there:

* **Depth-first search (DFS)** — visits the child vertices before visiting the sibling vertices; that is, it traverses the depth of any particular path before exploring its breadth;
* **Breadth-first search (BFS)** — visits the sibling vertices before visiting the child vertices.

![BFS vs DFS](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/57vwxztukiog2ki24kqd.png)

Let’s say you want to experiment with the tree traversal using different algorithms. Furthermore, the visualization of these algorithms should be provided to the UI where you can switch between different algorithms easily, but use the same tree data structure for both of them. Also, you want to hide the implementation details of how the tree data structure should be iterated for each algorithm. To implement this, the Iterator design pattern is an obvious choice.

### Class diagram

The class diagram below shows the implementation of the Iterator design pattern:

![Iterator Implementation Class Diagram](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fble4afhuxkj3fwsrjpn.png)

*ITreeCollection* defines a common interface for all the specific tree collections:

* *createIterator()* — creates an iterator for the specific tree collection;
* *getTitle()* — returns the title of the tree collection which is used in the UI.

*DepthFirstTreeCollection* and *BreadthFirstTreeCollection* are concrete implementations of the *ITreeCollection* interface. *DepthFirstTreeCollection* creates the *DepthFirstIterator* while *BreadthFirstTreeCollection* creates the *BreadthFirstIterator*. Also, both of these collections stores the *Graph* object to save the tree data structure itself.

*ITreeIterator* defines a common interface for all specific iterators of the tree collection:

* *hasNext()* — returns true if the iterator did not reach the end of the collection yet, otherwise false;
* *getNext()* — returns the next value of the collection;
* *reset()* — resets the iterator and sets the current position of it to the beginning.

*DepthFirstIterator* and *BreadthFirstIterator* are concrete implementations of the *ITreeIterator* interface. *DepthFirstIterator* implements the **depth-first** algorithm to traverse the tree collection. Correspondingly, *BreadthFirstIterator* implements the **breadth-first** algorithm. The main difference between these two algorithms is the order in which all of the nodes are visited. Hence, the depth-first algorithm is implemented using the **stack** data structure while the breadth-first algorithm uses the **queue** data structure to store nodes (vertices) that should be visited next.

*IteratorExample* references both interfaces — *ITreeCollection* and *ITreeIterator* — to specify the required tree collection and create an appropriate iterator for it.

### Graph

A class that stores the [adjacency list](https://en.wikipedia.org/wiki/Adjacency_list) of the graph. It is stored as a map data structure where the key represents the node’s (vertex) id and the value is a list of vertices (ids of other nodes) adjacent to the vertex of that id (key). Also, this class defines the *addEdge()* method to add an edge to the adjacency list.

![graph.dart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/k27svvbcltjm20gkg0bk.png)

### ITreeCollection

An interface that defines methods to be implemented by all specific tree collection classes. Dart language does not support the interface as a class type, so we define an interface by creating an abstract class and providing a method header (name, return type, parameters) without the default implementation.

![itree_collection.dart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yhcnjo4621479leh9efa.png)

### Tree collections

*DepthFirstTreeCollection* — a tree collection class that stores the graph object and implements the *createIterator()* method to create an iterator that uses the depth-first algorithm to traverse the graph.

![depth_first_tree_collection.dart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6dp1ck12indjq2kd4l7t.png)

*BreadthFirstTreeCollection* — a tree collection class that stores the graph object and implements the *createIterator()* method to create an iterator that uses the breadth-first algorithm to traverse the graph.

![breadth_first_tree_collection.dart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jm10ryvbqo5vzkm73wvl.png)

### ITreeIterator

An interface that defines methods to be implemented by all specific iterators of the tree collection.

![itree_iterator.dart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gye12iprsy4p2ts0qezh.png)

### Tree iterators

*DepthFirstIterator* — a specific implementation of the tree iterator which traverses the tree collection by using the depth-first algorithm. This algorithm uses the **stack** data structure to store vertices (nodes) that should be visited next using the *getNext()* method.

![depth_first_iterator.dart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/js4zxl7o3wzfmhnm36bg.png)

*BreadthFirstIterator* — a specific implementation of the tree iterator which traverses the tree collection by using the breadth-first algorithm. This algorithm uses the **queue** data structure to store vertices (nodes) that should be visited next using the *getNext()* method.

![breadth_first_iterator.dart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9wcw64v8x2v8qmlmll4a.png)

### Example

First of all, a markdown file is prepared and provided as a pattern’s description:

![Iterator Markdown](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xhl0y9kakvsloyfq06x9.gif)

*IteratorExample* widget is responsible for building the tree (graph) using the *Graph* class and contains a list of tree collection objects. After selecting the specific tree collection from the list and triggering the *traverseTree()* method, an appropriate iterator of that particular tree collection is created and used to traverse the tree data structure.

![iterator_example.dart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sc02pwh4mbw6xm0k9ktu.png)

As you can see in the *traverseTree()* method, all the implementation details of the tree collection’s traversal are hidden from the client, it only uses the *hasNext()* and *getNext()* methods defined by the *ITreeIterator* interface to iterate through all of the vertices (nodes) of the built *Graph* object (tree).

The final result of the Iterator design pattern’s implementation looks like this:

![Iterator Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ccy6mch1wcsj58dfx1kb.gif)

As you can see in the example, by selecting the specific tree collection and creating its iterator, the algorithm to traverse the tree also changes and it is visually noticeable in the demonstration.

All of the code changes for the Iterator design pattern and its example implementation could be found [here](https://github.com/mkobuolys/flutter-design-patterns/pull/10).

## Your Contribution

💖 or 🦄 this article to show your support and motivate me to write better!
💬 Leave a response to this article by providing your insights, comments or wishes for the next topic.
📢 Share this article with your friends, colleagues in social media.
➕ Follow me on dev.to or any other social media platform.
⭐ Star the [Github](https://github.com/mkobuolys/flutter-design-patterns) repository.