Friday, 17 June 2016

Iterator Design Pattern

Background

In one of the previous posts we saw Introduction to Design Patterns. In that we learned how different design patterns solve some pre identified design concerns and provide a good solution. Above post also states types of design patterns and links to design patterns we have already covered. In this post we will see another design patter - Iterator pattern. Is it same as the iterator I use to iterate over collections? Yes it is! And that a design pattern? What problem does that solve? Hold on to that we will come there in some time :)



Problem

Lets say there are two companies - Company A and company B. They both maintain employee records for their respective employees and their implementation is something like below - 

Company A Employee records - 

/**
 * 
 * @author athakur
 *
 */
public class CompanyAEmpRecords {

    private Employee[] companyEmployees = new Employee[10];
    private int index = -1;

    public void addEmployee(Employee newEmployee) {
        if (index == 10) {
            throw new RuntimeException("Maximum employee limit reached");
        }
        companyEmployees[index++] = newEmployee;
    }

    public void removeEmployee(String name) {
        // implementation to remove employee
    }

    public int getNoOfEmployees() {
        return index + 1;
    }
    
    public Employee[] getEmployees() {
        return companyEmployees;
    }

}

Company B Employee records - 

/**
 * 
 * @author athakur
 *
 */
public class CompanyBEmpRecords {
    private List<Employee> companyEmployees = new ArrayList<>();

    public void addEmployee(Employee newEmployee) {
        companyEmployees.add(newEmployee);
    }

    public void removeEmployee(String name) {
        // implementation to remove an employee based on name
    }

    public int getNoOfEmployees() {
        return companyEmployees.size();
    }
    
    public List<Employee> getEmployees() {
        return companyEmployees;
    }

}

Life was all good when they were working independently. Company A was small and sufficient with less than 10 employees where as Company B did not really care how many employees joined. But then one day they decided to merge and expand their business. Employees of both the companies will now be under one entity and the task to create code that lists down both company's employees now rests on you. You know both Employee record implementation of companies. So you start writing code using it.


/**
 * 
 * @author athakur
 *
 */
public class CompanyRecordsPrinter {
    
    public void pringCompanyEMployeeRecords(CompanyAEmpRecords companyAEmpRecords, CompanyBEmpRecords companyBEmpRecords) {
        
        Employee[] companyAEmployees = companyAEmpRecords.getEmployees();
        for(int i=0; i< companyAEmpRecords.getNoOfEmployees();i++) {
            System.out.println(companyAEmployees[i]);
        }
        
        List<Employee> companyBEmployees= companyBEmpRecords.getEmployees();
        for(Employee emp : companyBEmployees) {
            System.out.println(emp);
        }
        
    }

}

Well that serves the purpose. We are printing employees in both companies using their records. But is it a good design. Two loops for two different types of data structures. What if Company C is merged with this later. Add a new loop to handle it? Naah. Something does not feel right. This is where iterator pattern comes into picture.

Iterator Pattern defined

The Iterator pattern provides a way to access the elements of an aggregate object sequentially without exposing it's underlying representation.

Solution

You will basically have a common interface called Iterator which will have methods like -
  • boolean hasNext()
  • Object next()
Each Employee Record class will have a method called getIterator() that will basically return corresponding new instance of Iterator. Lets call it -
  • CompanyAEmpRecordsIterator
  • CompanyBEmpRecordsIterator
Then you can have a common method that take an Object of type Iterator and iterate over it using hasNext() method and get the actual data using next() method.

Sample code -

public class CompanyAEmpRecords implements CompanyEmpRecords {

    private Employee[] companyEmployees = new Employee[10];
    private int index = -1;

    @Override
    public void addEmployee(Employee newEmployee) {
        if (index == 9) {
            throw new RuntimeException("Employees limit reached");
        }
        companyEmployees[++index] = newEmployee;
    }

    @Override
    public void removeEmployee(Employee oldEmployee) {
        int i = 0;
        for (; i <= index; i++) {
            if (companyEmployees[i].equals(oldEmployee)) {
                break;
            }
        }
        for (int j = i; j <= index - 1; j++) {
            companyEmployees[j] = companyEmployees[j + 1];
        }
        companyEmployees[index] = null;
        index--;

    }

    @Override
    public int getNoOfEmployees() {
        return index + 1;
    }

    @Override
    public Iterator getIterator() {
        return new CompanyAEmpRecordsIterator();
    }

    private class CompanyAEmpRecordsIterator implements Iterator {

        int currIndex = -1;

        @Override
        public boolean hasNext() {
            if (currIndex + 1 <= index)
                return true;
            else
                return false;
        }

        @Override
        public Object next() {
            if (currIndex + 1 <= index)
                return companyEmployees[++currIndex];
            else
                return null;
        }

    }

}


You get the point.  And your printing logic will be as simple as  -

    public void pringCompanyEMployeeRecords(CompanyAEmpRecords companyAEmpRecords, CompanyBEmpRecords companyBEmpRecords) {
        
        printRecord(companyAEmpRecords.getIterator());
        printRecord(companyBEmpRecords.getIterator());
    }
    
    private void printRecord(Iterator recordIterator) {
        while(recordIterator.hasNext()) {
            System.out.println(recordIterator.next());
        }
    }


This is just the snippet I have provided. You can download the complete code from my git repository -
NOTE : Instead of defining your own iterator interface you can use java.util.Iterator interface instead.

NOTE :  we have not added remove() method in the Iterator interface. Neither are we handling multi threading scenarios like what happens when the collection gets modified when you are iterating using that iterator. The way this is handled is that when iterator is created we copy the modcount (modification count) and at any point during the iteration this is different than the original count we throw java.util.ConcurrentModificationException.

For sample code you can refer to Iterator provided by ArrayList class in Java -

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }


Modification count and ConcurrentModificationException


Lets try to understand modcount we just discussed above in a better way. Now a collection when initialized has a variable called

protected transient int modCount = 0;

This keeps track of modifications made to the collection. Now when you create an iterator for your collection this modcount gets copied over to your iterator as expectedModCount -

int expectedModCount = modCount;

Now during each iterator of iterator checkForComodification() method is called which does following -

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

So if modCount of the collection is not same as what was copied over to it's iterator during it's creation (stored as expectedModCount) then it throws ConcurrentModificationException.

Exception for this is when you use iterators remove method in which case iterator updates it's expectedModCount accordingly.

Class Diagram



Related Links

No comments:

Post a comment

t> UA-39527780-1 back to top