Iterator design pattern for beginners.

-

Background - 

Assume yourself as an expert in data structure. Someone asked you to create a container class. Which can hold any user-defined data type, and it has to be very efficient. As you are the expert of data structure. You will decide which data structure to be picked for implementing a given container efficiently. As you want to hold private information about implementation with yourself. You provide a container in the form of a library. Without mentioning how you have implemented it (fully encapsulated).

You did it because of many reasons. Like – you can change internal logic in the future without affecting much/no client code. Or you don’t want to put implementation in the public domain as you want to charge the client for it. Or you want to own code single-handed for future code manipulation.

Understand problem statement - 

  1. If you have chosen an array to implement your container, You can traverse data through the index. i.e array[index0], array[index1]... etc.
  2. If you have chosen a Linked list to implement your container. You can traverse data through pointer next. i.e data = data->next;
  3. If you have chosen a tree to implement your container. You can traverse data through DFS or BFS.
For all different types of DS traversing techniques are different (I have mentioned only 3, but there are many more). It means you have to tell the client what data structure you have chosen. For the client's sequential data traversal, because without knowing the DS no one can traverse stored data sequentially.

Okay, all set, the client has purchased your library. Without knowing the internal data structure. The core behavior of a container class is to hold data. The client has put his data into a container. But after putting data, he has to get those data back sequentially from container class as and when he needs.

Now without knowing the data structure. How you or any client can traverse the container and get the data back? Is it a linked list or array or hash table or tree? Traversing data is different in all different types of data structure, and you are not willing to tell what data structure you have used to implement your library. That makes sense as it is your library, and you want to keep internal implementation private.

Let me think about a straightforward solution. You would agree. Only one who knows the internal data structure is the container class itself. So why not, I introduce a function called next() as a public behavior/function in my container class? Then client just has to keep calling next() to traverse data.

Why the solution, as mentioned above, is not right, first we are violating the very first design principle, that says a class is not supposed to perform any operation which is not in its core behavior. Think about any container in real-life scenarios. It can contain the data, add or remove data. So – add(), remove() and insert(), but traversing container is not the core behavior of any container class.  Second, it will be encapsulation violation if we tell the internal data structure through next()'s function signature because without showing the internal data structure, it cannot traverse sequentially.
How to implement an algorithm (more specifically a container class) where we have to traverse my data sequentially, but without knowing the internal data structure? Answer is iterator design pattern.

Why we need iterator design pattern –

We can retrieve data sequentially without showing internal data structure, with following all OOAD design principles.


Iterator design pattern –

It uses implicit trusting. The container class will be the owner of the iterator object, and it will destroy the iterator object as soon as work gets completed. Below mentioned UML will give you high-level understanding -

UML Structure -


iterator DP
UML structure of iterator design pattern.

C++ Example -





#include<iostream>
using namespace std;
 
const int MAXSIZE = 10;

class Stack 
{
  public:
    Stack()
    {
      m_tos = -1;
    }
    void Push(int input)
    {
      if(m_tos > MAXSIZE) 
      {
        cout<<"List is full, first delete some item then insert "<<endl;
        return;
      }
      m_array[++m_tos] = input;
    }
    int Pop() 
    {
      if(m_tos == -1) 
      {
        cout<<"List is empty, first insert some item then delete "<<endl;
        return 0;
      }
      return m_array[m_tos++];
    }
    bool IsEmpty()
    {
      if(m_tos == -1)
        return true;
      return false;
    }
    Stack* Begin()
    {
      return this;
    }
    int End()
    {
      return MAXSIZE;
    }

    friend class StackIterator;
    class StackIterator* CreateIterator() const;

  private:
    int m_array[MAXSIZE];
    int m_tos;
};
 
class StackIterator 
{
  public:
    StackIterator(): m_stackIterator(NULL),m_index(0) {}
    StackIterator(const Stack* stack):m_stackIterator(stack),m_index(0){}
    void Next()
    {
      m_index++;
    }
    int CurrentItem()
    {
      return m_stackIterator->m_array[m_index];
    }
    void operator = (const Stack* stack)
    {
      m_stackIterator = stack;
    }
    bool operator !=(int input)
    {
      if (m_index < input)
          return true;
      return false;
    }
    int CurrentIndex()
    {
      return m_index;
    }

  private:
    int m_index;
    const Stack* m_stackIterator;
};
 
StackIterator* Stack::CreateIterator() const 
{
  return new StackIterator(this);
}
/*
#######################################################################################
#########  __  __       _        ######################################################
######### |  \/  | __ _(_)_ __   ######################################################
######### | |\/| |/ _` | | '_ \  ######################################################
######### | |  | | (_| | | | | | ######################################################
######### |_|  |_|\__,_|_|_| |_| ######################################################
#######################################################################################
*/
int main(int argc, char** argv) 
{
  Stack objStack;
     
  for(int index = 0; index < MAXSIZE; ++index) 
  {
      objStack.Push(index);
  }
  StackIterator *objStackIterator = objStack.CreateIterator();
  for(; (objStackIterator->CurrentIndex()) != (objStack.End()); objStackIterator->Next())
  {
    cout<<" "<< (objStackIterator->CurrentItem());
  }
  cout << endl;
  return 0;
}
 
///////////////////////////////////////////////////////////////////-------------OutPut
/*
$ ./a.exe
 0 1 2 3 4 5 6 7 8 9

*/

Thanks for reading it. To learn more about design patterns and basic design principles, please see my web page.

Comments

Post a Comment

Popular posts from this blog

Non-virtual interface idiom (NVI)

-
In almost every cases, it’s recommended to follow OOAD principles, but sometimes we should try to look some other alternatives, provided by programming languages, which could be a better options for certain situations. In C++, we can implement virtual function in private and we can redefine its behavior in derived class's private  and it will work in same way(did you try that?). When we define virtual function as private and expose a non-virtual public function to outer world, we call it “ non-virtual interface idiom ”. Non-virtual public function will internally call virtual function, in other words you are not exposing your virtual function to client. You will achieve high encapsulation, plus we can add pre and post execution/condition in the body of non-virtual public function. Call some set of functions, as prerequisite of calling virtual function, and after call returns from virtual function, again call some set of function as part of post cleanups/conditions,
Read more

Architectural patterns => Mud to structure => layers.

-
Image
Background - We apply mud to structure when a large system requires decomposition. If you notice, your application/requirement has verity of logical units which can be decomposed into a group of sub-tasks, first,  group them into different levels of abstraction. One abstract unit perform a totally different task(s) from other units, but any unit alone is not enough to give meaningful service to customer. Actually, different issues/solutions are splinted into different abstract units. Second,  after you divide them into different units, if you see a mix of low and high-level dependencies, where high-level operations depend on low-level operations, then assume those logical units as layers, third draw a dependency diagram between layers.  If control flows from high to low layer (or dependency diagram forms a stack, one layer on top of other), you can think of implementing it through layer pattern. Layer architecture - We can have many components in one layer. Layer
Read more

Architectural style -> Adoptable system -> Reflection.

-
Image
Background - We have discussed very less about reflection, especially if you are C, C++, mainframe, LSI developer and working on server side implementation or in low level hardware-interaction development team.  But it is very popular among high level languages like JAVA, Scala, C#, Python etc, many languages have implemented reflection in it.  It gives you flexibility to do things dynamically (at run-time). After working closely with different clients, you will get a clear understanding that no one is as confusing as a software client, not even your girlfriend! So we should have a flexible architecture in place who can absorb shocks of client’s last moment changes. Not only that, sometimes we have N number of different behaviors and structure in place, and we want our application to behave differently depending upon run-time situations. Let’s build understanding step by step through an example. Think you have got an assignment where you have to build an application
Read more