¿Clonar un iterador en Java?

Question

En un juego que tengo una lista de jugadores, digamos así:

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

Quiero que cada jugador interactuar con cada uno de los otros jugadores, por lo que escribo dos bucles anidados:

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

Como solo quiero que cada par de jugadores interactúen una vez, quiero comenzar el bucle interno con el jugador después del jugador actual del bucle externo. Así que quiero clonar el iterador, pero eso no se compila.

Entonces, ¿qué debo hacer?

Answer 1

El siguiente lo hará:

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

Se basa en la capacidad de la ListIterator 's que empezar desde la posición dada y conocer también su posición actual.

Answer 2

Además de aix answer, me gustaría señalar que, sin importar cómo cree un iterador que comience en un índice específico, seguramente será una operación lineal. Si no fue así, que sería capaz de hacer el acceso arbitrario a la lista en tiempo constante usando

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

lo que sería contradictorio.

En su situación, por lo tanto creo que la solución más eficiente sería en realidad hacer

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

Obsérvese, sin embargo, que es todavía la misma complejidad que la solución de Aix; O (n) pero probablemente con un factor constante menor.

Answer 3

Para una solución que evita el costo lineal asociado a listIterator(int) (respuesta de NPE), consulte mi answer to a similar question. En resumen, siempre que no le importe el orden en que se visita la lista, puede iniciar el ciclo externo desde el último elemento e iterar, e iniciar el ciclo interno desde el primer elemento e iterar hacia adelante hasta que los dos iteradores reunirse. La llamada a list.listIterator (list.size()) es rápida porque la lista es una LinkedList, es decir, una lista doblemente vinculada, y acceder al último elemento no requiere iterar a través de la lista. Vea el siguiente ejemplo:

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