Evitare ConcurrentModificationException

[lelmarir]

Salve a tutti, sto sviluppando una sorta di gioco con delle palline che si muovono sullo schermo e per tenerne traccia sono inserite in una LinkedList che scorro con un ciclo for each (for(object o: listaPalline){ <codicegestione> })

All'interno del ciclo gestisco i movimenti e il disegno stesso di tutti gli oggetti, ma capita che se certe condizioni sono verificate debba eliminare o aggiungere oggetti alla lista.

for(object o: listaPalline){ 
  if(<condizione>)
  {
     listaPalline.remove(o);
     //ma anche
     listaPalline.remove(o.oggettoCollegato); //non l'oggetto corrente ma ad esempio uno successivo o precedente sempre enlla lista
    //oppure ancora, il caso piu fastidioso
    funzioneCheEliminaOggetti(listaPalline);
  }
  //oppure
  if(<condizione2>)
  {
    listaPalline.add(new pallina());
  }
 } 

In entrambi i casi l'iteratore di listaPalline solleva l'eccezione ConcurrentModificationException.
(e ha anche ragione lui oltretutto....)

Non so bene quale potrebbe essere la soluzione migliore per risolvere questo problema. Fino ad ora avevo pensato a:

-Costruire un nuovo iteratore e una nuova lista che mi permetta di rimuovere/aggiungere oggetti a piacimento, facendo questo andrie pero a violare un meccanismo che non e' errato e la cosa sarebbe poco elegante ( e oltretutto ho idea che realizzare un nuovo iteratore e una nuova lista (seppure ereditati da quelli che uso attualmente) non sia una cosa proprio comoda...)

-Inserire gli oggetti da eliminare in una lista per poi rimuoverli una volta completato il ciclo (idem per gli oggetti da aggiungere). Il problema e' pero che la modifica prende piede solo al ciclo successivo, mentre a me interesserebbe che l'oggetto eliminato (nel caso sia successivo a quello corrente) non venga esaminato nel ciclo corrente (idem per gli oggetti aggiunti, sarebbe bello venissero esaminati nello stesso ciclo in cui sono stati aggiunti.
-Potrei quindi inserire un campo nel mio oggetto che mi indica se e' stato eliminato e quindi controllare all'entrata del ciclo per saltare gli oggetti eliminati ( ma questo mi costringerebbe a fare un controllo agiuntivo, e nel caso non sia io a creare il ciclo la cosa sarebbe inpossibile)

Per ora sono arrivato qui a pensare. qualche suggerimento o idea?

[andbin]

Originariamente inviato da lelmarir
In entrambi i casi l'iteratore di listaPalline solleva l'eccezione ConcurrentModificationException.
(e ha anche ragione lui oltretutto....)

Le collezioni "base" in java.util hanno un iteratore che viene definito "fail-fast". Ogni volta che si usa next(), l'iteratore verifica se la collezione associata è stata modificata "strutturalmente". Se è stata modificata viene lanciata ConcurrentModificationException. E tecnicamente questo comunque non è garantito al 100% per questioni che adesso non sto a precisare.

Quando ho detto "modificata" intendo dire modificata direttamente con i metodi della collezione. Se invece usi il remove() del iteratore puoi rimuovere tranquillamente l'elemento.

Questo però implica una cosa: non puoi usare il for-each in quanto "nasconde" l'iteratore. Semplicemente prendi l'iteratore in modo esplicito e usalo nel solito ciclo while(iter.hasNext()) { ... }

[lelmarir]

Originariamente inviato da andbin
Quando ho detto "modificata" intendo dire modificata direttamente con i metodi della collezione. Se invece usi il remove() del iteratore puoi rimuovere tranquillamente l'elemento.

Questo però implica una cosa: non puoi usare il for-each in quanto "nasconde" l'iteratore. Semplicemente prendi l'iteratore in modo esplicito e usalo nel solito ciclo while(iter.hasNext()) { ... }

Usare direttamente l'iteratore per rimuovere un elemento e' una cosa scomoda e poco naturale, e oltretutto mi permetterebbe di rimuovere solo l'elemento corrente (iterator.next()) e non un elemento qualsiasi della lista.

La mia necessità è di rimuovere un elemento qualunque della lista e poter aggiungere nuovi elementi (in coda, o meno) possibilmente ottenendo che questi vengano processati (o ignorati se sono stati rimossi) all'interno dello stesso ciclo che li ha generati (se sono sati generati in coda o in posizioni successive alla attuale).

Ad ogni modo, ti ringrazio della tua risposta.

[andbin]

Originariamente inviato da lelmarir
Usare direttamente l'iteratore per rimuovere un elemento e' una cosa scomoda e poco naturale

Che per te possa essere scomodo ... potrei capirlo. Che sia poco "naturale" no ... nel senso che quello è quanto viene offerto da java.util.Iterator e molte volte è utile, specialmente in logiche di "filtro".

Originariamente inviato da lelmarir
La mia necessità è di rimuovere un elemento qualunque della lista e poter aggiungere nuovi elementi (in coda, o meno) possibilmente ottenendo che questi vengano processati (o ignorati se sono stati rimossi) all'interno dello stesso ciclo che li ha generati (se sono sati generati in coda o in posizioni successive alla attuale).

Soluzioni:

1) Cercare un'altra collezione che non abbia un iteratore "fail-fast".
2) Implementare una "tua" lista (se non ci sono motivi seri/particolari te lo sconsiglio).

Oppure la soluzione ancora più banale .... e che probabilmente non ti è nemmeno passata per la testa:

3) Non usare un Iterator (né implicito in un for-each né esplicito) ma fare il solito/classico/banale ciclo for da i=0 per i<lista.size(). Ovviamente è una buona soluzione se è una lista ad "accesso casuale" veloce, es. ArrayList/Vector.
Quindi puoi rimuovere/aggiungere in ogni momento quello che ti pare .....

[lelmarir]

Originariamente inviato da andbin

1) Cercare un'altra collezione che non abbia un iteratore "fail-fast".
2) Implementare una "tua" lista (se non ci sono motivi seri/particolari te lo sconsiglio).

Oppure la soluzione ancora più banale .... e che probabilmente non ti è nemmeno passata per la testa:

3) Non usare un Iterator (né implicito in un for-each né esplicito) ma fare il solito/classico/banale ciclo for da i=0 per i<lista.size(). Ovviamente è una buona soluzione se è una lista ad "accesso casuale" veloce, es. ArrayList/Vector.
Quindi puoi rimuovere/aggiungere in ogni momento quello che ti pare .....

for(int i = 0; i < list.size();i++){ <codice di modifica lista> }

L'idea e' talmente banale, che e' errata e per questo non l'ho nemmeno nominata.
La mia lista e' una linked list, e quindi non ad accesso casuale.
Oltre tutto, con un approccio simile, se si elimina un elemento precedente a quello attuale (o l'attuale stesso) si ottiene come risultato che il ciclo salta l'elemento successivo, infatti gli indici della lista slittano all'indietro e l'elemento i+1 ottiene l'indice i ( che non viene quindi gestito).

Sapresti suggerirmi una lista con iteratore non-fail-fast ? (della documentazione ufficiale non sono riuscito a trovarne una)

[Alex'87]

Originariamente inviato da lelmarir
La mia lista e' una linked list, e quindi non ad accesso casuale.

Intendi java.util.LinkedList? I metodi per ottenere/modificare l'i-esimo elemento ci sono: http://java.sun.com/j2se/1.5.0/docs/...inkedList.html

[lelmarir]

Originariamente inviato da Alex'87
Intendi java.util.LinkedList? I metodi per ottenere/modificare l'i-esimo elemento ci sono: http://java.sun.com/j2se/1.5.0/docs/...inkedList.html

La lista espone si i metodi per ottenere un elemento dato l'indice, ma come suggerisce il nome si tratta dell'implementazione di una lista vera e propria ( la cara vecchia lista a puntatori del c) e il metodo di lettura "naturale" e' quello sequenziale, sfruttando gli iteratori, al contrario della ArrayList che e' implementata tramite Vettori, ed e' di fatto una lista ad accesso casuale e veloce (in quanto il costo di accesso alla cella i-esima e' identico per qualunque i)

vedi: http://forum.html.it/forum/showthread/t-1252526.html

Per i miei scopi e' piu adatta una LinkedList, in quanto ad ogni ciclo leggo sempre tutti gli elementi partendo dal primo.
(un accesso tramite indice sarebbe anche piu lento in questo caso)

[andbin]

Originariamente inviato da lelmarir
La mia lista e' una linked list, e quindi non ad accesso casuale.

Ok ... non potevo saperlo. Anzi ... speravo non fosse proprio questa!

Originariamente inviato da lelmarir
Oltre tutto, con un approccio simile, se si elimina un elemento precedente a quello attuale (o l'attuale stesso) si ottiene come risultato che il ciclo salta l'elemento successivo, infatti gli indici della lista slittano all'indietro e l'elemento i+1 ottiene l'indice i ( che non viene quindi gestito).

Ma questo, se ci pensi, sarebbe facilmente aggirabile .... basta fare un test e decrementare i se necessario!! Insomma ... come si dice, non fasciarti la testa prima di romperla.

Originariamente inviato da lelmarir
Sapresti suggerirmi una lista con iteratore non-fail-fast ? (della documentazione ufficiale non sono riuscito a trovarne una)

L'unica collezione List che non ha l'iteratore fail-fast è la CopyOnWriteArrayList che ha l'iteratore "snapshot" ma è una lista molto particolare, appropriata solo quando le modifiche sono poche e le iterazioni sorpassano di molto le modifiche. Quindi non ti serve.

Tra l'altro una cosa: se ho ben capito, durante la iterazione, in base ad una certa condizione vuoi rimuovere un certo oggetto x ... dovunque sia (prima o dopo). Ma il remove(oggetto) sulla collezione ha comunque una complessità O(N) quindi .... beh già lì avrebbe il suo bel da fare ....

Comunque ricapitoliamo:
- Hai un LinkedList.
- Durante la iterazione devi rimuovere un elemento qualunque in base ad una condizione o aggiungere un elemento in base ad un'altra condizione.
- Non puoi usare un iteratore (né implicito né esplicito) se fai un remove(oggetto) sulla collezione durante la iterazione.

Se ho ben capito, se aggiungi, lo fai sempre aggiungendo al fondo. Se hai già una idea che le rimozioni non sono tantissime potresti fare nel seguente modo.
Usi un ListIterator (non un semplice Iterator) che ha anche il add() (safe anche durante la iterazione) e poi quando devi aggiungere usi il add() del ListIterator.
Quando devi rimuovere un elemento arbitrario, non lo rimuovi subito ma ad esempio lo metti dentro un set (HashSet).
Finita la prima iterazione, ne fai una seconda dove invece, per ogni elemento verifichi se è nel set e se presente, lo rimuovi dalla lista con remove() del ListIterator. E il remove() del iteratore ha complessità O(1), quindi molto meglio!

Che ne pensi?

[lelmarir]

Si, era un po l'idea che mi era venuta all'inizio, ma speravo di poter evitare un approccio del genere perche in questo modo ho da gestire 2 liste aggiuntive (listaRimozioni e ListaAggiunte) da elaborare alla fine di ogni ciclo.
Inoltre il problema era che un oggetto, una volta rimosso dalla lista durante il ciclo (nel caso sia successivo alla posizione attuale) non deve essere considerato :
- metto un attributo all'oggetto stesso che indica se e' stato cancellato o meno, ma in questo modo si rischiano problemi di incoerenza perchè potrebbe succedere che un oggetto ottenga lo stato di cancellato restando nella lista oppure venga eliminato senza ottenere lo stato di cancellato e quindi processato durante il ciclo.
- controllo ad ogni iterazione del ciclo se l'oggetto corrente appartiene alla lista dei cancellati, ma questo rischia di essere abbastanza lento...

(le modifiche sulla lista in termini di cancellazione sono abbastanza frequenti e massicce, può capitare che vengano cancellati anche tutti gli oggetti, o quasi)

il problema si ripete uguale anche per le aggiunte...sarebbe bello che venissero esaminate durante lo stesso ciclo che le ha generate, l'idea sarebbe quella di iterare anche sulla lista degli oggetti da aggiungere, ma se per un malaugurato caso uno di questi vuole rimuovere uno dei vettori appena aggiunti il problema si ripresenta.

Sperando di trovare idee su come risolvere intanto cerco di creare un iteratore non-fail-fast.

[andbin]

Originariamente inviato da lelmarir
in questo modo ho da gestire 2 liste aggiuntive (listaRimozioni e ListaAggiunte) da elaborare alla fine di ogni ciclo.

No ... io parlavo solo di 1 "set" (HashSet) in più, non di 2 liste in più.
Se devi aggiungere, aggiungi subito immediatamente alla lista, se devi rimuovere lo fai con un secondo ciclo.

Originariamente inviato da lelmarir
Inoltre il problema era che un oggetto, una volta rimosso dalla lista durante il ciclo (nel caso sia successivo alla posizione attuale) non deve essere considerato :

Pensando di usare il set, vai a cercare se l'elemento è nel set, se esiste allora è poi da rimuovere ... e non lo prendi in considerazione.

Originariamente inviato da lelmarir
- controllo ad ogni iterazione del ciclo se l'oggetto corrente appartiene alla lista dei cancellati, ma questo rischia di essere abbastanza lento...

Ripeto che io parlavo di HashSet, la ricerca ha complessità O(1) ... tempo costante.

Originariamente inviato da lelmarir
le modifiche sulla lista in termini di cancellazione sono abbastanza frequenti e massicce, può capitare che vengano cancellati anche tutti gli oggetti, o quasi.

Questo è un problemino ... ma se usi il HashSet avresti solo lo spazio in più per la sua struttura (gli oggetti sono gli stessi della lista) e facendo il remove in un secondo step usi il remove() del ListIterator che ha complessità O(1).

Originariamente inviato da lelmarir
il problema si ripete uguale anche per le aggiunte...sarebbe bello che venissero esaminate durante lo stesso ciclo che le ha generate

Ma sarebbe proprio come ho detto!