[Java] iterazione "doppia"

[71104]

tramite una LinkedList vorrei realizzare un algoritmo banalissimo, una doppia iterazione su tutta la lista (come due for annidati in poche parole), ma non ci riesco perché le iterazioni prevedono la cancellazione occasionale di coppie di elementi

praticamente dovrei realizzare un algoritmo come quello che scrivo di seguito in pseudocodice:

# L è una lista doppiamente linkata
for each A in L
	for each B in L
		if (A != B) AND <some other conditions>
			L <- L \ {A U B}  # rimuovi sia A che B

secondo voi è fattibili in Java tramite LinkedList e iteratori?
ho persino provato a reimplementare una mia AbstractSequentialList ma ho desistito presto: è troppo difficile da implementare perché è inutilmente complessa a causa di quell'idiotissimo sistema di indici che fa parte dell'interfaccia Collection

[^TiGeRShArK^]

ma se scorri la lista al contrario non risolvi?

[71104]

Originariamente inviato da ^TiGeRShArK^

ma se scorri la lista al contrario non risolvi?

non vedo perché dovrei...
mi fai un esempio?

[DanieleC88]

Originariamente inviato da ^TiGeRShArK^

ma se scorri la lista al contrario non risolvi?

Uhm, se non ho capito male, scorrendo gli elementi A dall'inizio alla fine, e scorrendo gli elementi B dalla fine all'inizio? Potrebbe funzionare...

[^TiGeRShArK^]

Originariamente inviato da DanieleC88

Uhm, se non ho capito male, scorrendo gli elementi A dall'inizio alla fine, e scorrendo gli elementi B dalla fine all'inizio? Potrebbe funzionare...

in java che io sappia è l'unico modo per cancellare degli elementi in una lista durante un'iterazione, e per me ha sempre funzionato..

EDIT: o meglio è il modo + semplice.
Un altro modo potrebbe essere quello di memorizzarsi gli indici degli elementi da eliminare ed eliminarli subito dopo la fine dell'iterazione.

[71104]

ma se io modifico la lista tramite un altro iterator (quello che uso per cancellare gli elementi B) non dovrebbe venir lanciata una ConcurrentModificationException?

e poi non ho capito perché, usando due iteratori, col secondo dovrei andare dalla fine verso l'inizio

[feboss]

in pratica devi scorrere la lista e cancellare tutti gli element che si ripetono?

[wingman87]

# L è una lista doppiamente linkata
for each A in L
	for each B in L
		if (A != B) AND <some other conditions>
			L <- L \ {A U B}  # rimuovi sia A che B

Non ho ben capito il problema, l'unica cosa che mi viene in mente è che in questo pseudocodice che hai scritto probabilmente manca un break dopo la cancellazione della coppia di elementi.
Per il resto, perché non dovrebbe funzionare? Dov'è il problema anche se cancelli qualche elemento?

[k0nt3]

non puoi banalmente fare:

for (Object a : list) {
	for (Object b : list) {
		if(whatever) {
			Object[] toRemove = {a, b};
			list.remove(toRemove);
		}
	}
}

[feboss]

Originariamente inviato da k0nt3

non puoi banalmente fare:

for (Object a : list) {
	for (Object b : list) {
		if(whatever) {
			Object[] toRemove = {a, b};
			list.remove(toRemove);
		}
	}
}

Mi piace questo codice.Potresti per favore spiegarmi ogni istruzione?
perchè mi interessa particolarmente.se è possibile anche trasformando quel for, in un for normale
Tranne l'ultimo pezzo

Object[] toRemove = {a, b};
			list.remove(toRemove);

grazie

[k0nt3]

Originariamente inviato da feboss

Mi piace questo codice.Potresti per favore spiegarmi ogni istruzione?
perchè mi interessa particolarmente.se è possibile anche trasformando quel for, in un for normale
Tranne l'ultimo pezzo

Object[] toRemove = {a, b};
			list.remove(toRemove);

grazie

niente si traduce con: per ogni oggetto a in list fai ecc... in questo modo la creazione dell'iteratore è implicita (funziona da java5 in poi)
potresti scriverlo così:

for (Iterator i1 = list.iterator(); i1.hasNext();) {
	Object a = (Object) i1.next();
	for (Iterator i2 = list.iterator(); i2.hasNext();) {
		Object b = (Object) i2.next();
		if(...) {
			Object[] toRemove = {a, b};
			list.remove(toRemove);
		}
	}
}

[^TiGeRShArK^]

no, attenzione.
Con il metodo della cancellazione immediata senza memorizzazione degli indici degli oggetti da rimuovere non si può utilizzare un iteratore, ma bisogna scorrere la lista al contrario, e mi sembrava ovvio e scontato che l'unico modo per fare questo è utilizzando un ciclo for che parta dalla fine e decrementi l'indice di uno fino ad arrivare a zero.
Per la memorizzazione degli indici invece si può utilizzare la struttura che si preferisce per iterare sulla lista perchè tanto la cancellazione avviene solo in un momento successivo iterando sulla lista degli elementi da cancellare e eliminandoli dall'altra lista.

[^TiGeRShArK^]

tradotto in codice:

for (int i = lista.size() - 1; i >= 0; i--) {
    for (int j = lista.size() - 1; j >= 0; j--) {
        if (condition) {
            lista.remove(i);
            lista.remove(j);
        }
    }
}

[^TiGeRShArK^]

mmmm..
ora che ci penso con l'iterazione doppia non l'ho mai provata..
vabbè..
in caso non dovesse andare puoi sempre memorizzarti in una lista gli indici (o gli oggetti) da rimuovere e dopo aver finito l'iterazione iteri questa lista e li elimini dalla lista originaria.

[DanieleC88]

Originariamente inviato da ^TiGeRShArK^

[...]
        if (condition) {
            lista.remove(i);
            lista.remove(j);
        }
[...]

Uhm, però così dovresti fare uno step su i ad ogni rimozione (altrimenti, dopo la prima, lista.remove(i) cosa va a rimuovere?), almeno ad occhio mi pare così.

[DanieleC88]

for (int i = lista.size() - 1; i >= 0; i--) {
    bool found = false;

    for (int j = lista.size() - 1; j >= 0; j--) {
        if (condition) {
            lista.remove(j);
            found = true;
        }
    }

    if (found) {
        lista.remove(i);
    }
}

Una cosa del genere?

[banryu79]

Originariamente inviato da DanieleC88

for (int i = lista.size() - 1; i >= 0; i--) {
    bool found = false;

    for (int j = lista.size() - 1; j >= 0; j--) {
        if (condition) {
            lista.remove(j);
            found = true;
        }
    }

    if (found) {
        lista.remove(i);
    }
}

Una cosa del genere?

Va bene solo se l'elemento j-esimo è sempre successivo all'elemento i-esimo; in caso contrario l'ultima istruzione (lista.remove(i)) opera su un indice *non più valido* [perchè prima verrebbe eseguito lista.remove[j] e se j precede i non va bene]
Ciò dipende dalla logica espressa in "if(condition)"...


La soluzione per me è iterare la lista linkata con tutti gli Iterator che si ritiene necessario per raccogliere in un'altra Collection gli indici degli elementi da rimuovere e rimuovere tutto alla fine, a parte.

Certo per valutare se la cosa è possibile e non porta via troppo tempo sarebbe utile sapere prima a cosa serve la lista linkata nel programma e che dimensioni può avere.

[71104]

Originariamente inviato da feboss

in pratica devi scorrere la lista e cancellare tutti gli element che si ripetono?

non proprio in verità, comunque si, per semplificare potremmo dire che devo cancellare una coppia di elementi (A, B), con A che precede B, se (A != B) && (A.equals(B))

Originariamente inviato da wingman87

# L è una lista doppiamente linkata
for each A in L
	for each B in L
		if (A != B) AND <some other conditions>
			L <- L \ {A U B}  # rimuovi sia A che B

Non ho ben capito il problema, l'unica cosa che mi viene in mente è che in questo pseudocodice che hai scritto probabilmente manca un break dopo la cancellazione della coppia di elementi.

uh? no, dopo averli cancellati devo andare avanti e vedere se ci sono altre coppie da cancellare.

Per il resto, perché non dovrebbe funzionare? Dov'è il problema anche se cancelli qualche elemento?

ConcurrentModificationException

Originariamente inviato da k0nt3

non puoi banalmente fare:

for (Object a : list) {
	for (Object b : list) {
		if(whatever) {
			Object[] toRemove = {a, b};
			list.remove(toRemove);
		}
	}
}

ConcurrentModificationException

[71104]

Originariamente inviato da ^TiGeRShArK^

no, attenzione.
Con il metodo della cancellazione immediata senza memorizzazione degli indici degli oggetti da rimuovere non si può utilizzare un iteratore, ma bisogna scorrere la lista al contrario, e mi sembrava ovvio e scontato che l'unico modo per fare questo è utilizzando un ciclo for che parta dalla fine e decrementi l'indice di uno fino ad arrivare a zero.
Per la memorizzazione degli indici invece si può utilizzare la struttura che si preferisce per iterare sulla lista perchè tanto la cancellazione avviene solo in un momento successivo iterando sulla lista degli elementi da cancellare e eliminandoli dall'altra lista.

usare il sistema degli indici è una cosa che vorrei evitare: è un sistema totalmente idiota che trasforma l'operazione di cancellazione da una lista da O(1) a O(N)
non mi capacito di come sia possibile che gli autori del Collection Framework abbiano avuto un'idea così cretina

al limite piuttosto che cancellare per indice preferirei flaggare gli elementi da cancellare e fare quindi una cosa del genere:

LinkedList<MyItem> originalList;

.
.
.

class ItemContainer
{
	public MyItem item;
	public boolean delete = false;

	public ItemContainer(MyItem item)
	{
		this.item = item;
	}

}

.
.
.

LinkedList<ItemContainer> copiedList = new LinkedList<ItemContainer>();
for (MyItem item : originalList)
{
	copiedList.add(new ItemContainer(item));
}

for (ItemContainer A : copiedList)
{
	for (ItemContainer B : copiedList)
	{
		if ((A != B) && (<some other conditions>))
		{
			A.delete = true;
			B.delete = true;
		}
	}
}

Iterator<ItemContainer> i = copiedList.iterator();
while (i.hasNext())
{
	if (i.next().delete)
	{
		i.remove();
	}
}

originalList.clear();
for (ItemContainer container : copiedList)
{
	originalList.add(container.item);
}

ma sinceramente mi sembra scandaloso, speravo in qualcosa di molto più semplice

[71104]

una condizione che forse può aiutare a risolvere il problema (anche se credo che non ci sia soluzione ) è che se esiste una coppia (A, B) di elementi da cancellare allora A nella lista precede B, e quindi l'iterazione interna non ha bisogno di esaminare anche tutti gli elementi che precedono A, ma può partire dal successore.