CODEWITHSUNDEEP
javaiterator
Thomas Padron-McCarthy
Thomas Padron-McCarthy

Reputation: 27632

Clone an Iterator in Java?

In a game I have a list of players, let's say like this:

LinkedList<String> players = new LinkedList<String>();

I want to let each player interact with each of the other players, so I write two nested loops:

Iterator<String> i1 = players.iterator();
while (i1.hasNext()) {
    String p1 = i1.next();
    Iterator<String> i2 = players.iterator();
    // But I want to do this: Iterator<String> i2 = i1.clone();
    while (i2.hasNext()) {
        String p2 = i2.next();
        System.out.println("Interact: " + p1 + ", " + p2);
    }
}

Since I only want each pair of players to interact once, I want to start the inner loop with the player after the outer loop's current player. So I want to clone the iterator, but that doesn't compile.

So, what should I do instead?

Upvotes: 20

Views: 20038

Answers (3)

Luca Citi
Luca Citi

Reputation: 1430

For a solution that avoids the linear cost associated to listIterator(int) (NPE's answer), see my answer to a similar question. In brief, 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. 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. See example below:

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;
}

Upvotes: 1

aioobe
aioobe

Reputation: 420990

In addition to aix answer, I'd like to point out that however you create an iterator starting at a specific index, it's bound to be a linear operation. If it wasn't, you would be able to do arbitrary access to the list in constant time using

elementN = createIterator(linkedList, N).next();

which would be contradictory.

In your situation I therefore believe that the most efficient solution would actually be to do

List<String> tmp = new ArrayList<String>(players);
for (int p1 = 0; p1 < tmp.size(); p1++)
    for (int p2 = p1+1; p2 < tmp.size(); p2++)
        System.out.println("Interact: " + tmp.get(p1) + ", " + tmp.get(p2));

Note however, that it is still the same complexity as the solution by aix; O(n2) but probably with a smaller constant factor.

Upvotes: 3

NPE
NPE

Reputation: 500357

The following will do it:

ListIterator<String> i1 = players.listIterator(0);
while (i1.hasNext()) {
    String p1 = i1.next();
    ListIterator<String> i2 = players.listIterator(i1.nextIndex());
    while (i2.hasNext()) {
        String p2 = i2.next();
        System.out.println("Interact: " + p1 + ", " + p2);
    }
}

It relies on the ListIterator's ability to start from the given position and to also know its current position.

Upvotes: 27

Related Questions