March 08, 2016

Composite Iterator. Java

Imagine you have two collections of different types of data. Both of them are sorted by any rule. You need to iterate over both of collections, saving the order they are sorted. Like this:
I want to share simple, but effective technique of using interfaces Iterator and Iterable.


Let's suppose that we have such hierarchy of classes:


Method compareTo() implements comparison by field id in natural order. Method toString() returns exact name of object's class and id.

Once upon time I faced with similar hierarchy in production code. In addition there were two types of lists: List<Bar> and List<Qux>. I want to remind, that both lists are sorted!


So, the task is - iterate over these two lists effectively: linear time complexity O(n), no copies of collections, no additional sorting, no unnecessary loops.

"The simplest" solution is to write two loops, then get two element (one from each list), compare them, decide which to use, iterate again. If one list become empty too fast we need to check this situation in separated loop. This code will be too complex and not reusable. (I don't want to provide any example here, you may do this by yourself like a training task.)

From other side we can avoid lot of complications by using Iterator interface. Let's declare class CompositeIterator in such way:


Fields it1 and it2 will refer to iterators from both collections. Comparator is used for solving a task of ordering. Field lastUsed will save iterator which was used last time returning value. Fields obj1 and obj2 refer to objects retrieved from it1 and it2 correspondingly. Well, how will it works?


Method hasNext() will check at least one object (obj1 or obj2) already retrieved. If both of them are null, we will check at least one of iterators by calling hasNext().

If one of these four conditions is true, we will pass into the next() method. Now we need to be sure that we use both iterators, so if obj1 and obj2 are null, then we need to get them from iterators. Now if they're both not equals null, we need to compare them and choose which to return. Otherwise we just return one of them which is not null. In case if both of them are null at the end of this method, this means method next() was used wrong - need to throw NoSuchElementException.

Pay attention to two methods obj1() and obj2(). They are used in order to save reference to last used iterator and clear reference on object which was returned.

Method remove() will use field lastUsed in order to remove last returned element from a proper iterator.

In order to easy use this iterator, we will create simple implementation of Iterable interface, which will create CompositeIterator every time when method iterator() is called:


That's all! Don't believe? Try it!


Wow! I even didn't expect so pretty code. Here is the output:


In addition I want to mention that you can use this approach for any number of collections wrapped. Two, three, four - it doesn't depend! You can wrap them in pairs many times.

I hope this solution will help you to process collections better. You may download all files from this example on Github. Thanks for reading!

No comments:

Post a Comment