How can I make a copy of an iterator in Java?

Question

We have a list of elements and have a very simplistic collision detection where we check every object against every other object.

The check is commutative, so to avoid repeating it twice, we would do this in C++:

for (list<Object>::iterator it0 = list.begin(); it0 != list.end(); ++it0)
{
    for (list<Object>::iterator it1 = it0; it1 != list.end(); ++it1)
    {
        Test(*it0, *it1);
    }
}

The key bit here is the copy

it1 = it0

How would you write this in Java?

Answer 1

You can do this with ListIterator:

for(ListIterator<O> outer = list.listIterator(); outer.hasNext() ; ) {
    O oVal = outer.next();
    for(ListIterator<O> inner = list.listIterator(outer.nextIndex()); inner.hasNext(); ) {
         Test(oVal, inner.next());
    }
}

For a linked list (which has slow index access) the list.listIterator(index) still needs to iterate to the right place, though. But this way it is only O(n²) (and you can't get better than this) instead of O(n³) like the index-access in the other answers then. (You might be even faster if you copy your list first to an array, but it is only a constant factor here.)

Of course, if you usually need index-based access (or this iterator-cloning), you would better use an array-based list (or a custom list whose iterator supports cloning).

Answer 2

You cannot copy Java iterators, so you'll have to do it without them:

for(int i=0; i<list.size(); i++){
    for(int j=i; j<list.size(); j++){
        Test(list.get(i), list.get(j));
    }
}

Answer 3

For a linked list (which has slow index access), I think there is a way to do it without incurring in the O(n²) slowdown that Paŭlo mentioned. As long as you don't care about the order the list is visited, you can start the outer loop from the last element and iterate back, and start the inner loop from the first element and iterate forward until the two iterators meet. See iterRevIterator in the code below. The call to list.listIterator(list.size()) is fast because list is a LinkedList, i.e. a doubly-linked list, and accessing the last element does not require iterating through the list. The difference is not enormous...

iterIndex: 384.59ms sum=29656666
iterIterator: 1.91ms sum=29656666
iterRevIterator: 1.55ms sum=29656666

but still significant.

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;


public class TestIter {

    public static int iterIndex(List<Integer> list) {
        int sum = 0;
        for(int i = 0; i < list.size(); ++i) {
            for(int j = i+1; j < list.size(); ++j) {
                sum += list.get(i) * list.get(j);
            }
        }
        return sum;
    }

    public static int iterIterator(List<Integer> list) {
        int sum = 0;
        for(ListIterator<Integer> outer = list.listIterator(); outer.hasNext() ; ) {
            Integer oVal = outer.next();
            for(ListIterator<Integer> inner = list.listIterator(outer.nextIndex()); inner.hasNext(); ) {
                sum += oVal * inner.next();
            }
        }
        return sum;
    }

    public static int iterRevIterator(List<Integer> list) {
        int sum = 0;
        for(ListIterator<Integer> outer = list.listIterator(list.size()); outer.hasPrevious() ; ) {
            Integer oVal = outer.previous();
            for(ListIterator<Integer> inner = list.listIterator(); inner.nextIndex() <= outer.previousIndex(); ) {
                sum += oVal * inner.next();
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int size = 1000;
        int rep = 100;
        int sum = 0;
        // List<Integer> list = new ArrayList<Integer>();
        List<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < size; ++i) {
            list.add(i);
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < rep; ++i) {
            sum = iterIndex(list);
        }
        System.out.println("iterIndex: " + (float)(System.currentTimeMillis() - startTime)/rep + "ms sum=" + sum);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < rep; ++i) {
            sum = iterIterator(list);
        }
        System.out.println("iterIterator: " + (float)(System.currentTimeMillis() - startTime)/rep + "ms sum=" + sum);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < rep; ++i) {
            sum = iterRevIterator(list);
        }
        System.out.println("iterRevIterator: " + (float)(System.currentTimeMillis() - startTime)/rep + "ms sum=" + sum);

    }

}