A deduplicating iterator

Question

Implement an iterator (generic) which skips an element if it is equal to the previous element. e.g: AAABBCCCCD, produces ABCD.

Please suggest improvements.

import java.util.Iterator;

public class DeDupIterator implements Iterator {

E next = null;
Iterator<E> itr;

public DeDupIterator(Iterator<E> iter) {
    itr = iter;
    next = itr.next();
}

@Override
public boolean hasNext() {
    if(itr.hasNext())
    if (next != null) {
        return true;
    }
    return false;
}

@Override
public E next() {
    E item=null;
    while (itr.hasNext()) {
        item = (E) itr.next();
        if (!item.equals(next)) {
            E temp = next;
            next = item;
            return temp;
        }

    }
    next = item;
    return next;
}

@Override
public void remove() {
    itr.remove();
}
}

Answer 1

 public boolean hasNext() {
    if(itr.hasNext())
    if (next != null) {
        return true;
    }
    return false;
}

First, there's inconsistent usage of braces for your block if statements. Second, if you are already keeping track of what is the next element to be returned by your de-dup iterator, wouldn't it be enough to just check against that?

public boolean hasNext() {
    return next != null;
}

A suggestion regarding the remove() implementation: the Javadoc API suggests that it can be called only once per call to next(). Since your implementation of next() is already quite different, you may want to re-consider whether your implementation can be as simple as calling remove() on the underlying iterator. In your example, is it expected to be removing only one 'C' or all 'C's when remove() is called?

Answer 2

Generic Types

You appear to have copied this from inside another class, or something, because you are missing the Generic type for the iterator <E>. Also, assuming you get that right, there is no need to do the explicit cast inside the code.. the following line:

       item = (E) itr.next();

should be just:

    item = itr.next();

Nulls

Your code is not very defensive when it comes to null values. If the iterator contains a null, you will have NullPointer exceptions all over the place.

Bug

If the initial iterator is empty, you will throw a NoSuchElementException when you construct your DeDupIterator. This code:

public DeDupIterator(Iterator<E> iter) {
    itr = iter;
    next = itr.next();
}

Answer 3

Anyone trying to implement an Iterator (or an Iterable) with unusual semantics should review the implementations in the Guava library.

Iterators.java AbstractIterator.java

Notice, in particular, the use of the StatePattern in the abstract iterator. Because Iterator.next() should throw a NoSuchElementException when the iterator has been exhausted, you need to be able to remember what happened when you last tried to pre-fetch a value from the source iterator.

Also note that it's common to consider that some Iterators are Unmodifiable, throwing an UnsupportedOperationException if the consumer calls remove(). Since the problem statement is unclear what behavior is expected when remove is called, this is an approach that I would recommend in this case.

If you were using the Guava library, then it would make sense to use a Predicate to keep track of whether an element matches the previous element, and use Iterators.filter() to defer the iterator state work to the library.

EDIT

There actually is support for a look ahead iterator in Guava called PeekingIterator. You can wrap an iterator using Iterators.peekingIterator. You can check here for the implementation, and the example for PeekingIterator from the Guava documentation actually happens to be the problem you are trying to solve.

Answer 4

Iterator.remove(), if supported, is supposed to remove the most element most recently returned by .next(). However, since this iterator works by peeking ahead, calling .remove() on the underlying iterator is going to remove a future element instead of the most recently returned element.

I can't think of a good way to fix this bug. Perhaps .remove() will just have to be an unsupported operation.

Answer 5

For a de-duplicating iterator you can simply in the constructor of your DeDuplicator class iterate through all the elements and add to a set. then if the size of set is greater than 0 assign that set's iterator to your class iterator variable.

something like this:

class MyDeDup<E> implements Iterator<E>
{
    Iterator<E> itr;
    Set<E> s;

    MyDeDup(Iterator<E> itr)
    {
        this.itr=itr;

        while(this.itr.hasNext())
        {
            s.add(itr.next());
        }
        if(s.size()>0)
        this.itr=s.iterator();

    }

    @override
    public boolean hasNext()
    {
        return itr.hasNext();
    }
    //similarly override other functions
}