3
\$\begingroup\$

I have implemented a simple iterator. Just want to check if I have missed anything.

interface iterator<E>
    {
        boolean hasNext();

        E next();
    }

    class Iterator<E> implements iterator
    {
        E[] arr;

        int curPos = 0;

        @Override
        public boolean hasNext()
        {
            if (curPos >= arr.length || arr[curPos] == null) 
            {
                return false;
            }
            else
            {
                return true;
            }
        }

        @Override
        public E next()
        {
            if(hasNext())
            {
                E res = arr[curPos];
                curPos++;
                return arr[curPos+1];
            }
            else
            {
                throw new runtimeException("No next element available !");
            }
        }

    }

Questions:

  1. Why should I not use Object instead of E/template everywhere ?
  2. How do I make an iterator for a binary tree.

I assume apart from the above, I would have to implement a traversal algorithm and try to find if the next "traversal" successor exist?

\$\endgroup\$
1
  • \$\begingroup\$ It is not very clear what is asked in the second question. Could you clarify it or (what probably would be better) move it to a separate question? \$\endgroup\$
    – CheatEx
    Jun 5, 2011 at 0:58

4 Answers 4

3
\$\begingroup\$

I would write an iterator for arrays that way:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArrayIterator<E> implements Iterator<E> {

    private final E[] arr;
    private int currentIndex = 0;

    public ArrayIterator(E... arr) {
        if(arr == null) {
            throw new IllegalArgumentException("Array is null");
        }
        this.arr = arr;
    }

    public boolean hasNext() {
        return currentIndex < arr.length;
    }

    public E next() {
        if (! hasNext()) {
            throw new NoSuchElementException();
        }
        return arr[currentIndex++];
    }

    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

}

To your second question: I assume you want to traverse the tree in-order, and that the nodes have no link to the parent, only to the children. Then you need a node list from the root node to the current node, which can store if a node was already visited or not, too.

Then you go left as deep as possible, storing the path in the node list. This is your first current node. When you need the next one, take its parent (from the node list). Next would be the right children of that node (if there are any) or its own parent. The best way to understand this is to take a sheet of paper, draw different trees, and look how the traversal must work.

\$\endgroup\$
2
  • \$\begingroup\$ Note, this will not be usable for arrays of primitives, e.g. int[], boolean[], ... \$\endgroup\$
    – Matt Ball
    Jun 8, 2011 at 5:26
  • \$\begingroup\$ @Matt: Yes, you would need specialized versions of that class, but this is a consequence from the insane way Java handles primitive arrays. You have that problem for all other collection stuff as well. On the other hand it's very easy to fix E to a wrapper like Integer and to adapt array and the constructor accordingly. \$\endgroup\$
    – Landei
    Jun 8, 2011 at 8:23
1
\$\begingroup\$

Because then the consumer of that code could write something like:

Iterator<Foo> iterator = new Iterator<Foo>();

//...

Foo theFoo = iterator.next();

instead of having to cast the object of type Object to type Foo like

Foo theFoo = (Foo)iterator.next();

It avoids potential confusion by being strict about what type of object to expect.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks, I also see that being strict would also enforce that people dont start equating arrays to trees !! \$\endgroup\$
    – p101
    Jun 4, 2011 at 22:05
1
\$\begingroup\$

The next method should throw an exception in case iterator reach the end. It is neither safe nor convenient to get an NPE after the iterator was used improperly.

\$\endgroup\$
1
\$\begingroup\$

If you don't define your own iterator, but use java.util.Iterator, you get this error from the compiler:

Iterator.java:9: Iterator is not abstract and does not override abstract method remove() in java.util.Iterator

To use it, where an Iterator is expected, you have to use the java.util.Iterator, which will not be too easy - removing from an array - but you could probably look up, how it is done in the Java source.

But then the compiler is your friend, and tells you, what is wrong.

For a tree, you could write implement multiple iterators - for depth-first traversal, or top-down.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.