Iterator kopieren

[Quurks]

Ich habe eine LinkedList mit max 200 Objekten.
Nun will ich oft alle Elemente mit den anderen Elementen vergleichen.
Das wäre ja relativ einfach möglich, wenn man zwei Iteratoren machen würde und die dann ineinander verschachteln würde:

Iterator it1=list.iterator();
Iterator it2=list.iterator();
while(it1.hasNext()){
    while(it2.hasnext()){
         //Mach wa smit
        it1.next();
        it2.next();
        }
    }

Aber dort würde ich unnötige Vergleiche anstellen, da ich dann zuerst Element 1 mit 2 vergleichen würde, und dann Element 2 mit 1

Ich hab es bis jetzt mit arrays gelöst, in der Form:

for (int i =0; j < arr.length; j++) {
    for (int j = i + 1; j < arr.length; j++) {
        //mach was
        }
    }

Aber aus Arrays kann man keine Elemente löschen.
Bei Vectoren gibt es das Problem, dass meine häufigen Löschvorgänge den Vector langsam machen, außerdem hat der Vector bei mir irgendwelche Probleme mit mehr als 150 Elementen, er wird einfach langsam.

DEshalb hab ich mich für die LinkedList entschieden, als Lösung vür mein Problem, dachte ich dass ich evtl den Iterator kopieren könnte:

Iterator it1=list.iterator();

while(it1.hasNext()){
    Iterator it2=clone(it1);//in der Richtung
    while(it2.hasnext()){
         //Mach wa smit
        it1.next();
        it2.next();
        }
    }

damit ich die ersten Elemente nicht nochmal durchgehen muss.
Aber eclipse meint:

Die Methode clone() im Typ Object ist für die Argumente nicht anwendbar (Iterator)

Ich hoffe auf eure Vorshläge
Ich steig auch gern auf einen anderen Typ um, wenn dort die Probleme nicht auftreten[/code]

 

[Schandro]

genau dasselbe Problem: http://java-forum.org/de/viewtopic.php?t=82025&highlight=

Außerdem geht die Syntax von clone so:

Iterator it2=(Iterator)it1.clone();

clone() returnt nur ein Object, deswegen muss es noch zu einem Iterator gecastet werden.
Ob dieser Lösungsansatz aber so sinnvol ist weiß ich jetzt nicht.

 

[Quurks]

Gut, Danke, aber clonen lassen sich Iteratoren nicht (laut eclipse):

Die Methode clone() ist für den Typ Iterator nicht definiert (undefined)

Den anderen Thread habe ich nicht gefunden, wol die falschen Suchberffe benutzt

 

[0x7F800000]

Hmm, bin erst vor kurzem auf fast dasselbe Problem gestoßen, allerdings galt in meiner Situation die einschränkung, dass aus der doppelt verketteten Liste nichts gelöscht wird, sondern nur weitere elemente dazukommen.

http://java-forum.org/de/viewtopic.php?t=82138&postdays=0&postorder=asc&start=15 (bringt nicht wirklich viel das durchzulesen)

Mir ist damals irgendeine andere passable Lösung eingefallen, aber irgendwie war ich mit der auch nicht wirklich zufrieden.

Prinzipiell ist es ein Kinderspiel, dir eine eigene Iterator-Klasse zu basteln, die solche Scherze wie das Löschen von Elementen in verschachtelten Iterator-Schleifen ohne ConcurrentModificationException ermöglicht: du nimmst dir den code aus java.util.LinkedList , aus der privaten Inneren Klasse ListIterator, kopierst den code fast 1:1 in eine neue eigene Iterator-Klasse, und löschst einfach diese Methode:

	final void checkForComodification() {
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	}

aus dem ursprünglichen code raus. Dadurch wird das fail-fast verhalten unterbunden. Damit geht natrlich auch eine gewisse sicherheit verloren, da musst du nochmal drei mal genauer nachdenken, wie du es denn so anstellst, dass sich die Iteratoren nicht beißen :roll:

Dann kannst du auch noch einen copy-konstruktor für Iterator hinzufügen (oder Cloneable implementieren, was bei normalen Iteratoren nicht gemacht ist), und fertig ist ein "kopierbarer fail-slow" Iterator, der für deine Anwendung sinnvoller erscheint.

Ich würde aber an deiner Stelle dreimal überlegen, ob du das Problem nicht evtl ganz Umgehen kannst, indem du etwa statt einer Liste ein Set verwendest o.ä.

 

[Quurks]

Ob dafür Sets das optimale sind?

Die scheinen mir ja auch mit Iteratoren zu Arbeiten?

 

[0x7F800000]

ja, aber das ist dann egal. Du wolltest mit einer 2D-Schleife über die Liste iterieren, objekte vergleichen, und irgendwas löschen. Darauß habe ich geschlossen, dass du womöglich einfach nur die Kopien aus der Liste rauslöschen willst. Aber dann wäre das ganze Unternehmen Sinnfrei, weil du ja dann auch gleich einen TreeSet o.ä. nehmen könntest.

 

[bananenkasper]

Hi, bin gerade über das gleiche Problem gestoßen und habe mal etwas gebastelt:

Die Methoden sind aus ArrayList kopiert, allerdings ohne den modification check.

Zusätzlich wird das Cloneable - interface implementiert; für die angesprochenen Anwendungszwecke.

/**
 * 
 * 
 * TODO description
 * 
 * TODO example
 * 
 * @version 2010-09-17
 * 
 * @param <T>
 */
public class ExtendedIteratorImpl<T> implements ListIterator<T>, Cloneable {

	// Fileds //

	/**
	 * 
	 */
	protected final List<T> list;

	protected volatile int numLeft;

	protected volatile int lastPosition = -1;

	/**
	 * 
	 * 
	 * Constructs a new {@code ExtendedIteratorImpl} for given Collection.
	 * 
	 * @param col
	 *            collection over which will be iterated
	 */
	public ExtendedIteratorImpl(Collection<? extends T> collection) {
		if (collection == null)
			throw new NullPointerException();
		synchronized (ExtendedIteratorImpl.class) {
			list = new ArrayList<T>();
			list.addAll(collection);
			numLeft = list.size();
		}
	}

	protected ExtendedIteratorImpl(int numLeft, int lastPosition, List<T> list) {
		this.list = list;
		this.numLeft = numLeft;
		this.lastPosition = lastPosition;
	}

	// Private //

	//

	// Protected //

	//

	// Public //

	//

	// Override //

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof ExtendedIteratorImpl))
			return false;
		ExtendedIteratorImpl<?> other = (ExtendedIteratorImpl<?>) obj;
		if (nextIndex() != other.nextIndex())
			return false;
		if (list == null) {
			if (other.list != null)
				return false;
		} else if (!list.equals(other.list))
			return false;
		return true;
	}
	
	@Override
	protected Object clone() {
		return new ExtendedIteratorImpl<T>(numLeft, lastPosition, list);
	}

	@Override
	public String toString() {
		return nextIndex() + ": " + list;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + nextIndex();
		result = prime * result + ((list == null) ? 0 : list.hashCode());
		return result;
	}

	// Implement //

	/**
	 * 
	 */
	public boolean hasNext() {
		return numLeft > 0;
	}

	/**
	 * 
	 */
	public boolean hasPrevious() {
		return numLeft < list.size();
	}

	/**
	 * 
	 */
	public T next() {
		try {
			int index = list.size() - numLeft;
			T result = (T) list.get(index);
			lastPosition = index;
			numLeft--;
			return result;
		} catch (IndexOutOfBoundsException e) {
			throw new NoSuchElementException();
		}
	}

	/**
	 * 
	 */
	public T previous() {
		int index = list.size() - numLeft - 1;
		T result = list.get(index);
		numLeft++;
		lastPosition = index;
		return result;
	}

	/**
	 * 
	 */
	public synchronized ExtendedIteratorImpl<T> iteratorOverSubList(int startIndex,
			int stopIndex) {
		try{
		return iteratorOverSubList(new ZeroPositiveRange(startIndex, stopIndex));
		}catch(RangeException e){
			throw new IllegalArgumentException(e);
		}
	}

	/**
	 * 
	 */
	public ExtendedIteratorImpl<T> iteratorOverSubList(Range range) {
		return new ExtendedIteratorImpl<T>(list.subList(range.getStart(),
				range.getStop()));
	}

	/**
	 * 
	 */
	public int nextIndex() {
		return list.size() - numLeft;
	}

	/**
	 * 
	 */
	public int previousIndex() {
		return list.size() - numLeft - 1;
	}

	/**
	 * 
	 */
	public void remove() {
		if (lastPosition == -1) {
			throw new IllegalStateException();
		}
		if (lastPosition == list.size() - numLeft) {
			numLeft--; // we're removing after a call to previous()
		}
		list.remove(lastPosition);
		lastPosition = -1;
	}

	/**
	 * 
	 */
	public void set(T object) {

		list.set(lastPosition, object);

	}

	/**
	 * 
	 */
	public void add(T object) {
		list.add(list.size() - numLeft, object);
		lastPosition = -1;
	}

}