Iterator für eine geordnete Menge

O

ocsme

Top Contributor
Hallo,

hänge bei einer Aufgabe und habe keinen wirklichen Plan wie man das machen muss 🙁

Aufgabenstellung:
Die Klasse LinkedSet repräsentiere geordnete Mengen als doppelt verkettete Ringlisten mit einer Anker-Zelle, die uach bei leeren Listen vorhanden ist.
Von der Implementierung ist folgendes bekannt:
Code: 
public class LinkedSet<T extends Comparable<T>> implements SortedSet<T>{

    private class Cell {
        Object value;
        Cell pred, succ;
    }
    private Cell anchor;
        
    public Iterator<T> iterator() {...    }
}

Implementiern Sie die Methode iterator(...). Diese soll einen Iterator<T> zurückgeben, mit dem man die Menge in aufsteigender Reihenfolge durchlaufen kann. Sie brauchen nur die Methoden T next() un dboolen hasNext() zu implementieren.
Zum Vergrößern anklicken....

Meine Idee zu dieser Aufgabe war folgende:
Java: 
public class LinkedSet<T extends Comparable<T>> implements SortedSet<T>{

    private class Cell {
        Object value;
        Cell pred, succ;
    }
    private Cell anchor;
        
    class LinkedSetIterator implements Iterator<T> {

public boolean hasNext() {
            return Cell.first() != Cell.last();
        }

        @Override
        public T next() {
            // TODO Auto-generated method stub
            return Cell.first();
        }
        
    }
    
    @Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }
}

Natürlich funktioniert das ganze so nicht 😀 bekomme es nicht mal übersetzt!
Doch denke man sieht die Idee dahinter.

Kann mir jemand weiter helfen wie ich nun ein Datenelement in die Klasse LinkedSetIterator bekomme? und stimmt es den annähernd was ich dort gemacht habe mit den 2 Methoden?

LG
 
Aus meiner Sicht müsste das in etwa wie folgt aussehen:
a) der Iterator hat einen Zeiger auf ein Element. Dies speichert dann den Punkt, an dem man gerade ist.
b) Prüfung, ob es noch ein Element gibt: Wenn die Liste leer ist oder der Zeiger auf dem Vorgänger des ersten Elements steht, dann gibt es kein nächstes Element.
c) next: Wenn es noch ein Element gibt: Der Zeiger wird auf das erste Element gesetzt so er null ist oder er wird auf das nachfolgende Element gesetzt. Dann wird value des Zeigers zurück gegeben.

Was mir an Deinem Code noch auffällt: value ist Object, aber das sollte T sein. Dafür hast Du ja den Generic. Den sollte man dann auch nutzen wenn möglich.
 
Die innere Klasse hat doch Zugriff auf die Element der äußeren Klasse. Also etwas wie das Folgende sollte schon funktionieren:

Java: 
        @Override
        public T next() {
            if (hasNext()) {
                current = current != null ? current=current.succ : anchor;
                return current.value;
            }
            
            throw new IllegalStateException("No more elements");
        }

Zumindest liess sich das bei mir übersetzen. Und wie man sieht: anchor ist direkt verfügbar.
 
Also so komme ich natürlich an die Datenelemente von Cell doch die sind dann ja null 😀
Java: 
@Override
        public boolean hasNext() {
            return new LinkedSet().new Cell().value != LinkedSet.this.anchor;
        }

kneitzel hat gesagt.:
Zumindest liess sich das bei mir übersetzen. Und wie man sieht: anchor ist direkt verfügbar.
Zum Vergrößern anklicken....
Was ist bei dir Current? ich hab das in den Iterator eingefügt und alles ist rot 😀

LG
 
Das ist das, was ich in meiner ersten Antwort erwähnt hatte:
kneitzel hat gesagt.:
a) der Iterator hat einen Zeiger auf ein Element. Dies speichert dann den Punkt, an dem man gerade ist.
Zum Vergrößern anklicken....
Somit habe ich ein Feld current vom Typ Cell.
Und die Methode schaut halt: Gibt es noch ein nächstes Element? Wenn current null ist, ist das nächste Element das erste Element. Ansonsten ist das nächste Element das folgende Element. Und dann wird der Wert ausgegeben.
 
Ja nur wenn du Cell current in die Iterator-Klasse als Datenelement schreibst hat es den Wert null.
Das bringt doch nichts.
Denn du fragst im bedingten Operator ob current != null ist das wird nie true werden!

Also die Aufgabe ist ja mal mega Schrott 🙁

Kann das sein das die Aufgabe gar kein Sinn macht? Denn es soll ja auch bei next() ein T zurück gegeben werden. Da ich nun aber ein Object habe mekert der Compiler auch da Object nicht T ist! Wobei nach Type-rawe eh wieder alles object ist 😀

LG
 
ocsme hat gesagt.:
Ja nur wenn du Cell current in die Iterator-Klasse als Datenelement schreibst hat es den Wert null.
Das bringt doch nichts.
Denn du fragst im bedingten Operator ob current != null ist das wird nie true werden!
Zum Vergrößern anklicken....
Du musst current im Konstruktor des Iterators noch initialisieren 😉

ocsme hat gesagt.:
Kann das sein das die Aufgabe gar kein Sinn macht? Denn es soll ja auch bei next() ein T zurück gegeben werden. Da ich nun aber ein Object habe mekert der Compiler auch da Object nicht T ist! Wobei nach Type-rawe eh wieder alles object ist 😀
Zum Vergrößern anklicken....
Ersetz halt Object mit T 😉
 
ocsme hat gesagt.:
Ja nur wenn du Cell current in die Iterator-Klasse als Datenelement schreibst hat es den Wert null.
Das bringt doch nichts.
Denn du fragst im bedingten Operator ob current != null ist das wird nie true werden!

Also die Aufgabe ist ja mal mega Schrott 🙁
Zum Vergrößern anklicken....

Also ich glaube, dass Du den Code nicht richtig angeschaut hast...
Java: 
current = current != null ? current=current.succ : anchor;
Das war doch der Code. Spiel ihn doch einfach einmal durch ... Was passiert in der Zeile?

mrBrown hat gesagt.:
Du musst current im Konstruktor des Iterators noch initialisieren 😉
Zum Vergrößern anklicken....
Nein, das muss nicht erfolgen, denn null als Initialisierung schien mir null prinzipiell gut genug zu sein.

Daher kommt ja in meinem Code der Check mit dem null Wert. Man kann natürlich auch eine Initialisierung machen auf den letzten Wert, aber da hatte ich dann Probleme mit der hasNext Methode, denn bei einem Element wäre current ja nach dem next() genau auf dem gleichen Wert wie vor dem next()....
 
kneitzel hat gesagt.:
Nein, das muss nicht erfolgen, denn null als Initialisierung schien mir null prinzipiell gut genug zu sein.
Zum Vergrößern anklicken....
Oh, stimmt, hätte noch mal den Code angucken sollen '😀

kneitzel hat gesagt.:
Daher kommt ja in meinem Code der Check mit dem null Wert. Man kann natürlich auch eine Initialisierung machen auf den letzten Wert, aber da hatte ich dann Probleme mit der hasNext Methode, denn bei einem Element wäre current ja nach dem next() genau auf dem gleichen Wert wie vor dem next()....
Zum Vergrößern anklicken....
Wo siehst du da ein Problem? hasNext dürft doch immer gleich aussehen, egal wie man next umsetzt.

Initialisierung vermeiden halt den Check auf null
 
mrBrown hat gesagt.:
Wo siehst du da ein Problem? hasNext dürft doch immer gleich aussehen, egal wie man next umsetzt.

Initialisierung vermeiden halt den Check auf null
Zum Vergrößern anklicken....

Die Frage ist aber doch, auf was Du current setzt und wie Du hasNext setzt...

Mein hasNext prüft, ob es Elemente gibt und ob current auf das letzte Element zeigt.

Wenn ich current nun aber initialisiere auf das letzte Element, dann muss ich mir irgendwie noch zusätzlich merken, ob ich da durch die Initialisierung hin gekommen bin oder ob ich eben das letzte Element ausgegeben habe. In beiden Fällen wäre current auf dem letzten Element. Oder übersehe ich da jetzt etwas?
 
Mal ein paar Dinge hervorheben:
ocsme hat gesagt.:
Die Klasse LinkedSet repräsentiere geordnete Mengen als doppelt verkettete Ringlisten mit einer Anker-Zelle, die uach bei leeren Listen vorhanden ist.
Zum Vergrößern anklicken....
1. Die Ordnung wird über Comparable definiert.
2. Es existiert eine Zelle, die nicht null ist, die Ankerzelle
3. Die Liste ist ein Ring.
4. Es ist nicht gesagt, dass die Ankerzelle das kleinste Element darstellt
 
Ahh, ok. Das hatte ich übersehen. Ich bin irgendwie davon ausgegangen, dass der Anker bei leerer Liste null wäre. Damit ist meine Implementation was das angeht natürlich erst einmal obsolet.
 
kneitzel hat gesagt.:
Die Frage ist aber doch, auf was Du current setzt und wie Du hasNext setzt...

Mein hasNext prüft, ob es Elemente gibt und ob current auf das letzte Element zeigt.

Wenn ich current nun aber initialisiere auf das letzte Element, dann muss ich mir irgendwie noch zusätzlich merken, ob ich da durch die Initialisierung hin gekommen bin oder ob ich eben das letzte Element ausgegeben habe. In beiden Fällen wäre current auf dem letzten Element. Oder übersehe ich da jetzt etwas?
Zum Vergrößern anklicken....
Initial ist current der Anker.
hasNext prüft, ob current.succ != anchor
next prüft hasNext, setzt current = current.succ, und gibt dann current zurück


mihe7 hat gesagt.:
4. Es ist nicht gesagt, dass die Ankerzelle das kleinste Element darstellt
Zum Vergrößern anklicken....
Es ist auch nicht gesagt, dass der Anker einen Wert hat, oder überseh ich das?
 
mihe7 hat gesagt.:
Ich verstehe "auch bei leeren Listen vorhanden" so, dass bei einer leeren Liste anchor != null gilt und dem entsprechend anchor.value == null gelten muss.

EDIT: wobei ja auch pred/succ bei einer leeren Liste null sein könnten...
Zum Vergrößern anklicken....
Bei einer ein-Elementigen Liste könnte anchor.value == null oder aber anchor.value != null gelten

Die Aufgabestellung lässt viel Spielraum 😀
 
Ja, daher auch die Überlegung am Ende, dass die leere Liste auch per pred/succ == null dargestellt werden könnte. Ich denke mal, dass es per "Vorlesungskonvention" geklärt wurde, wie die Liste auszusehen hat.
 
Erst einmal vielen Lieben Dank für eure Beteiligung an dieser Aufgabenstellung 🙂

In der Vorlesung hatten wir so etwas nie besprochen 🙁 Das ist bei uns getrennt wir haben ALDA als Fach wo wir alles in Pseudocode besprechen und Prog mit Java und C/C++ wo das dann Umgesetzt werden soll. Doch auch in Alda wurden Ringe nicht besprochen 😀 (selbst Studium)

Denke wir sind uns über diese Methode einig das sollte Korrekt sein:
Java: 
    @Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }

Meine LinkedSetIterator Klasse sieht nun so aus:
Java: 
class LinkedSetIterator implements Iterator<T> {
        Cell current;
        LinkedSetIterator() {
            Cell current = anchor;
        }
        
        @Override
        public boolean hasNext() {
            return current.succ != LinkedSet.this.anchor;
        }

         public T next() {
                if (hasNext()) {
                    current = current != null ? current=current.succ : anchor;
                    return (T) current.value;
                }
                throw new IllegalStateException("No more elements");
            }
        
    }

Nun Frage ich mich ob T next() überhaupt Korrekt ist? Denn current = anchor das bedeutet ist der anchor != null setzt er current auf succ und andernfalls auf den anchor. Das bedeutet ich verliere meinen anchor oder etwa nicht und ich laufe im Kreis.

bei hasNext() gibt es auch keinen Sinn mehr.

Ich glaube die Aufgabe lass ich einfach sein.
Danke für eure Hilfe 🙂

LG
 
ocsme hat gesagt.:
Das ist bei uns getrennt wir haben ALDA als Fach wo wir alles in Pseudocode besprechen und Prog mit Java und C/C++ wo das dann Umgesetzt werden soll. Doch auch in Alda wurden Ringe nicht besprochen
Zum Vergrößern anklicken....
Pseudocode (Algorithmen) sind vollkommen ausreichend. Wenn ihr tatsächlich keine Ringbuffer besprochen habt, dann doch wohl wenigstens (doppelt) verkettete Listen.

ocsme hat gesagt.:
Ich glaube die Aufgabe lass ich einfach sein.
Zum Vergrößern anklicken....
Das solltest Du nicht tun. Die Aufgabe ist an sich sehr schön und äußerst sinnvoll. Das einzige Problem ist, dass man ohne weitere Informationen/halbwegs gesicherte Annahmen nicht weiß, ob die Lösung das ist, was der Aufgabensteller sich vorstellt. Darfst Du davon ausgehen, dass die Methoden des Sets verwendbar sind? Dann könntest Du isEmpty() und first() verwenden. Falls nicht, musst Du beide im Iterator "simulieren". Dazu muss man aber wissen, wie die Liste aufgebaut sein soll, insbesondere, wie die leere Liste dargestellt wird, ob die Liste null-Werte enthalten darf, wenn ja, wo die null eingeordnet werden muss (ist null das kleinste oder größte Element) usw.

Meine Vermutung wäre, dass einfach keine null-Werte zugelassen sind und die leere Liste durch einen Anker mit null-Wert dargestellt wird.

Deine Lösung berücksichtigt btw. nicht, dass das Ankerelement nicht das kleinste Element sein muss.
 
mihe7 hat gesagt.:
Pseudocode (Algorithmen) sind vollkommen ausreichend. Wenn ihr tatsächlich keine Ringbuffer besprochen habt, dann doch wohl wenigstens (doppelt) verkettete Listen.
Zum Vergrößern anklicken....
Doppeltverkettete Listen hatten wir ja 🙂

------
Die Methoden des Sets die Implementiert werden müssen dürfen benutzt werden 🙂
Wenn ich das richtig sehe bräuchte ich doch dann Cell gar nicht oder?
Ich hab jetzt den Iterator so geschrieben:

Java: 
    class LinkedSetIterator implements Iterator<T> {
        LinkedSetIterator() {
            
        }
        
        @Override
        public boolean hasNext() {
            return LinkedSet.this.isEmpty();
        }

         public T next() {
                if (hasNext()) {
                    return LinkedSet.this.first();
                }
                throw new IllegalStateException("No more elements");
            }
        
    }
 
Was gibt denn jetzt der erste, zweit, dritte, etc Aufruf von next zurück?

Und wenn das Set nicht leer ist, gibt es dann immer ein nächstes Element?
 
mihe7 hat gesagt.:
Das solltest Du nicht tun. Die Aufgabe ist an sich sehr schön und äußerst sinnvoll. Das einzige Problem ist, dass man ohne weitere Informationen/halbwegs gesicherte Annahmen nicht weiß, ob die Lösung das ist, was der Aufgabensteller sich vorstellt. Darfst Du davon ausgehen, dass die Methoden des Sets verwendbar sind? Dann könntest Du isEmpty() und first() verwenden. Falls nicht, musst Du beide im Iterator "simulieren". Dazu muss man aber wissen, wie die Liste aufgebaut sein soll, insbesondere, wie die leere Liste dargestellt wird, ob die Liste null-Werte enthalten darf, wenn ja, wo die null eingeordnet werden muss (ist null das kleinste oder größte Element) usw.
Zum Vergrößern anklicken....

Ich hab noch mehr solcher Fragen mal wieder 😀
Mein Problem ist auch oft das ich so das Gefühl habe rein gar nicht gelernt zu haben 🙁
Es sind auch super viele Themen in so kurzer Zeit. Packages, Exceptions, I/O, JavaCollectionFramework, Generics, Swing, AWT, JavaFX, Lambdas in1 Semester 😀
 
mrBrown hat gesagt.:
Was gibt denn jetzt der erste, zweit, dritte, etc Aufruf von next zurück?
Zum Vergrößern anklicken....

ach misst ich glaube immer das erste Element es wird nie weiter gerutscht stimmts 🙁 MISST 😀

Java: 
 public T next() {
                if (hasNext()) {
                    T tmp = LinkedSet.this.first();
                    LinkedSet.this.remove(tmp);
                    return tmp;
                }
 
Zuletzt bearbeitet:
Jetzt löscht du Elemente aus dem Set, während du drüber iterierst 😉



Geh noch mal einen Schritt zurück und vom Code weg.

Wie kommst du von einer Cell zu deren Nachfolger?
 
Du hast ein aktuelles Element, an dem der Iterator grad steht - nennen wir es mal current - von da an kämst du doch an das nächste Element, oder?
 
meinst du sowas:
Code: 
T current = LinkedSet.this.first();

wenn current Cell sein soll wie soll ich später T zurück geben 🙁 NEIN sry ich komme nicht dahinter!


Wenn Cell current = anchor wäre, ist disere Ausdruck doch immer false denn anchor ist immer null
current = current != null ? current=current.succ : anchor;
also kommt dort immer anchor zurück.

So jetzt versteh ich gar nichts mehr und lass es!!!

Danke nochmals

LG
 
Zuletzt bearbeitet:
Nein. Die Frage war, wie du von einer Cell zu der nächsten kommst, nicht wie du das erste Element des Sets bekommst.


Der Iterator muss sich irgendwie merken, an welcher Stelle er grad ist. Sonst kannst du ja nicht prüfen, ob es ein nächstes Element gibt oder zu diesem wechseln. Und für beides musst du von einem Element zum nächsten wechseln, irgendwelche Methoden des Sets brauchst du dafür nicht, vor allem nicht first oder remove.
 
Ja ich bin eh gerade wieder mega verwirrt.
Der anchor ist sicherlich nicht null! also ich meine anchor = null. sondern anchor.vlaue = null denn der anchor hat ja auch den pred und succ zeigt für das nächste element vorwärts wie rückwärts 😀

also muss man nur irgendwie mit dem anchor arbeiten stimmts?
 
ocsme hat gesagt.:
Der anchor ist sicherlich nicht null! also ich meine anchor = null. sondern anchor.vlaue = null denn der anchor hat ja auch den pred und succ zeigt für das nächste element vorwärts wie rückwärts 😀
Zum Vergrößern anklicken....
Ja, der anchor ist niemals null, und anchor.value ist im einfachsten Fall immer null. pred und succ sind beide auch niemals null.


ocsme hat gesagt.:
also muss man nur irgendwie mit dem anchor arbeiten stimmts?
Zum Vergrößern anklicken....
Ja, für zwei Dinge musst du den anchor benutzen 😉
 
mrBrown hat gesagt.:
Ja, der anchor ist niemals null, und anchor.value ist im einfachsten Fall immer null. pred und succ sind beide auch niemals null.
Zum Vergrößern anklicken....
achso pred und succ des anchors sind auch niemals null. stimmt sie zeigen ja auch anchor selbst!

also ist das hier jetzt auch wieder misst 😀

Java: 
class LinkedSetIterator implements Iterator<T> {
        Cell current;
        
        LinkedSetIterator() {
            current = anchor;
        }
        
        @Override
        public boolean hasNext() {
            return (current.succ != null || current.pred != null);
        }

         public T next() {
                if (hasNext()) {
                    
                }
                throw new IllegalStateException("No more elements");
            }
        
    }
 
Ich sage gleich dazu es ginge auch etwas kürzer:

Java: 
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.StringJoiner;

public class LinkedSet<T extends Comparable<T>> implements SortedSet<T> {
	public static void main(String[] args) {
		LinkedSet<Integer> s = new LinkedSet<>();
		System.out.println(iterToString(s.iterator()));
		for (int i = 0; i < 10; i++) {
			s.add((int) (Math.random() * 5.0));
			System.out.println(iterToString(s.iterator()));
		}

		s.clear();
		System.out.println(iterToString(s.iterator()));
		for (int i = 0; i < 10; i++) {
			s.add((int) (Math.random() * 5.0));
			System.out.println(iterToString(s.iterator()));
		}
	}

	public static String iterToString(Iterator<?> i) {
		StringJoiner j = new StringJoiner("; ");
		while (i.hasNext())
			j.add(i.next().toString());
		return j.toString();
	}

	private class Cell {
		Object value;
		Cell pred, succ;
	}

	private Cell anchor;

	public Iterator<T> iterator() {
		return new Iterator<T>() {

			Cell a = anchor;
			boolean b = true;

			@Override
			public boolean hasNext() {
				if (a == null)
					return false;
				if (b && a.succ == anchor) {
					b = false;
					return true;
				}
				return b;
			}

			@Override
			public T next() {
				T t = (T) a.value;
				a = a.succ;
				return t;
			}
		};
	}

	@Override
	public boolean add(T t) {
		if (anchor == null) {
			anchor = new Cell();
			anchor.pred = anchor;
			anchor.succ = anchor;
			anchor.value = t;
		} else {
			if (anchor.succ == anchor) {
				if (((Comparable<T>) anchor.value).compareTo(t) < 0) {
					Cell n = new Cell();
					n.pred = anchor;
					n.succ = anchor;
					n.value = t;
					anchor.pred = n;
					anchor.succ = n;

				} else {
					Cell n = new Cell();
					n.pred = anchor;
					n.succ = anchor;
					n.value = t;
					anchor.pred = n;
					anchor.succ = n;
					anchor = n;
				}
			} else {
				Cell a = anchor;
				while (a.succ != anchor) {
					if (((Comparable<T>) a.value).compareTo(t) > 0) {
						Cell n = new Cell();
						n.pred = a.pred;
						n.succ = a;
						n.value = t;
						a.pred.succ = n;
						a.pred = n;

						if (a == anchor)
							anchor = n;
						break;
					}
					a = a.succ;
				}
				if (a.succ == anchor) {
					if (((Comparable<T>) a.value).compareTo(t) > 0) {
						Cell n = new Cell();
						n.pred = a.pred;
						n.succ = a;
						n.value = t;
						a.pred.succ = n;
						a.pred = n;
					} else {
						Cell n = new Cell();
						n.pred = a;
						n.succ = a.succ;
						n.value = t;
						a.succ.pred = n;
						a.succ = n;
					}
				}
			}
		}
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public void clear() {
		anchor = null;
	}

	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean isEmpty() {
		return anchor == null;
	}

	@Override
	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int size() {
		int s = 1;
		if (isEmpty())
			return 0;
		Cell a = anchor;
		while (a.succ != null)
			s++;
		return s;
	}

	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Comparator<? super T> comparator() {
		return (T a, T b) -> a.compareTo(b);
	}

	@Override
	public T first() {
		return (T) anchor.value;
	}

	@Override
	public SortedSet<T> headSet(T arg0) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public T last() {
		return (T) anchor.pred;
	}

	@Override
	public SortedSet<T> subSet(T fromElement, T toElement) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public SortedSet<T> tailSet(T fromElement) {
		// TODO Auto-generated method stub
		return null;
	}
}
 
Danke Tobias-nrw 🙂

so und nun bin ich noch deprimierter!
Es sind ja Theoretisch nur ein paar Zeilen auf die ich NIE gekommen wäre 🙁

Vielleicht bekomme ich ja die remove(Object o) Methode hin beim Iterator 😀 <- glaub ich zwar nicht dran aber naja! Danke 🙂
LG
 
Zuletzt bearbeitet:
Also ich mische auch noch einmal kurz mit, da ich das Gefühl habe, dass ich sehr gut beigetragen habe, Verwirrung zu stiften.

Also erst einmal ganz wichtig: Bei meinem Code bin ich ursprünglich von einer falschen Annahme ausgegangen. Ich hatte angenommen, dass Anchor bei einer leeren Liste auch leer ist und so. Das führt dazu, dass mein Code nicht die gestellte Aufgabe erfüllt!

Und da meine Codezeile immer wieder weiter auftaucht: Ich habe eine sehr kompakte Zeile geschrieben, die evtl. zu schwer zu verstehen ist. Ich habe den "Conditional Operator" verwendet und das scheint zu Verwirrungen zu führen. Die Zeile
Java: 
current = current != null ? current=current.succ : anchor;
Ist in erster Linie eine Zuweisung. current bekommt einen neuen Wert zugewiesen. Und dann kommt ein Abfrage., ob current derzeit nicht null ist. So dies der Fall ist, wird current der Wert current.succ zugewiesen. Ansonsten wird im anchor zugewiesen.

Aber da es Probleme mit dem Verständnis dieser Zeile gibt, würde ich dazu raten bei zukünftigen Gedankengängen diesen wenn überhaupt durch ein Konstrukt wie
Java: 
if (current != null) {
    current = current.succ;
} else {
    current = anchor;
}
zu ersetzen.
Aber auf Grund der ersten Punktes ist dieser Ansatz so nicht korrekt.

Und nun hoffe ich, dass ich nicht weiter verwirrt habe. Sorry @mrBrown, Du führst Ihn gerade sehr schön und da wollte ich eigentlich nicht reingrätschen, aber diese Richtigstellung fand ich doch notwendig.
 
kneitzel dein Code hat mich so nicht Verwirrt sondern ich dachte die ganze Zeit das anchor = null wäre.
Also nicht anchor.vlaue sondern, die Variable anchor insgesamt. Deswegen konnte ich mit deinem Code nichts anfangen.
Wenn wir current = anchor = null setzen was kommt dann bei deinem Code raus? Ja genau current = anchor = null 😀

Aber lieben Dank für deine Beiträge 🙂

mrBrown hat gesagt.:
Wenn es um das nächste Element geht, warum guckst du dir dann pred an?
Zum Vergrößern anklicken....

Das ist eine gute Frage 😀 Benötige ich diesen Zeiger dann für remove?

also mein hasNext() wäre nun diese hier:
Code: 
@Override
        public boolean hasNext() {
            return (current.succ != anchor);
        }

Ist das den nun richtig?
 
ocsme hat gesagt.:
Das ist eine gute Frage 😀 Benötige ich diesen Zeiger dann für remove?
Zum Vergrößern anklicken....
Darüber kannst du dir Gedanken machen, wenn du remove schreibst 😉

ocsme hat gesagt.:
Ist das den nun richtig?
Zum Vergrößern anklicken....
Ja 😉




Tobias-nrw hat gesagt.:
nein, noch nicht ganz, denn wenn es nur ein Elem gibt dann ist der Nachfolger des Ankers der Anker...
Zum Vergrößern anklicken....
Nein, wenn es ein Element gibt, ist der Nachfolger des Ankers dieses eine Element.

Der Nachfolger des Ankers ist nur dann der Anker selbst, wenn das Set leer ist.
 
Es kommt darauf an was mit "vorhanden" gemeint ist. Eigentlich heißt es dann nicht Ankerelem sondern dummy. 🙄 Die unzureichende Aufgabenstellung führt auch dazu, das null nicht erlaubt sein kann.

Aber es stimmt natürlich, meins ist zu kompliziert.
 
Tobias-nrw hat gesagt.:
Es kommt darauf an was mit "vorhanden" gemeint ist.
Zum Vergrößern anklicken....
Nur, wenn man "vorhanden" als "ist null" interpretiert. Also nein.

Tobias-nrw hat gesagt.:
Eigentlich heißt es dann nicht Ankerelem sondern dummy.
Zum Vergrößern anklicken....
Nein. Niemand nennt es hier dummy. Anchor oder Head ist deutlich verbreiteter...

Tobias-nrw hat gesagt.:
Die unzureichende Aufgabenstellung führt auch dazu, das null nicht erlaubt sein kann.
Zum Vergrößern anklicken....
Keine Ahnung worauf du dich beziehst.
anchor darf niemals null sein, anchor.value sollte immer null sein. Keine Ahnung, wo null da "nicht erlaubt sein kann"
 
Schau mal @ocsme das müsste hinkommen:
Java: 
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.StringJoiner;

public class LinkedSet<T extends Comparable<T>> implements SortedSet<T> {
	public static void main(String[] args) {
		LinkedSet<Integer> s = new LinkedSet<>();
		System.out.println(iterToString(s.iterator()));
		for (int i = 0; i < 10; i++) {
			s.add((int) (Math.random() * 5.0));
			System.out.println(iterToString(s.iterator()));
		}

		s.clear();
		System.out.println(iterToString(s.iterator()));
		for (int i = 0; i < 10; i++) {
			s.add((int) (Math.random() * 5.0));
			System.out.println(iterToString(s.iterator()));
		}
	}

	public static String iterToString(Iterator<?> i) {
		StringJoiner j = new StringJoiner("; ");
		while (i.hasNext())
			j.add(i.next().toString());
		return j.toString();
	}

	private class Cell {
		Object value;
		Cell pred, succ;
	}

	private Cell anchor;

	public LinkedSet() {
		anchor = new Cell();
		anchor.pred = anchor;
		anchor.succ = anchor;
	}

	public Iterator<T> iterator() {
		return new Iterator<T>() {

			Cell a = anchor;
			boolean b = true;

			@Override
			public boolean hasNext() {
				if (b && a.succ == anchor) {
					b = false;
					return a.value != null;
				}
				return b && a.value != null;
			}

			@Override
			public T next() {
				T t = (T) a.value;
				a = a.succ;
				return t;
			}
		};
	}

	@Override
	public boolean add(T t) {
		if (anchor.value == null) {
			anchor.value = t;
		} else {
			if (anchor.succ == anchor) {
				if (((Comparable<T>) anchor.value).compareTo(t) < 0) {
					Cell n = new Cell();
					n.pred = anchor;
					n.succ = anchor;
					n.value = t;
					anchor.pred = n;
					anchor.succ = n;

				} else {
					Cell n = new Cell();
					n.pred = anchor;
					n.succ = anchor;
					n.value = t;
					anchor.pred = n;
					anchor.succ = n;
					anchor = n;
				}
			} else {
				Cell a = anchor;
				while (a.succ != anchor) {
					if (((Comparable<T>) a.value).compareTo(t) > 0) {
						Cell n = new Cell();
						n.pred = a.pred;
						n.succ = a;
						n.value = t;
						a.pred.succ = n;
						a.pred = n;

						if (a == anchor)
							anchor = n;
						break;
					}
					a = a.succ;
				}
				if (a.succ == anchor) {
					if (((Comparable<T>) a.value).compareTo(t) > 0) {
						Cell n = new Cell();
						n.pred = a.pred;
						n.succ = a;
						n.value = t;
						a.pred.succ = n;
						a.pred = n;
					} else {
						Cell n = new Cell();
						n.pred = a;
						n.succ = a.succ;
						n.value = t;
						a.succ.pred = n;
						a.succ = n;
					}
				}
			}
		}
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public void clear() {
		anchor.pred = anchor;
		anchor.succ = anchor;
		anchor.value = null;
	}

	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean isEmpty() {
		return anchor.value == null;
	}

	@Override
	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int size() {
		int s = 1;
		if (isEmpty())
			return 0;
		Cell a = anchor;
		while (a.succ != anchor)
			s++;
		return s;
	}

	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Comparator<? super T> comparator() {
		return (T a, T b) -> a.compareTo(b);
	}

	@Override
	public T first() {
		return (T) anchor.value;
	}

	@Override
	public SortedSet<T> headSet(T arg0) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public T last() {
		return (T) anchor.pred.value;
	}

	@Override
	public SortedSet<T> subSet(T fromElement, T toElement) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public SortedSet<T> tailSet(T fromElement) {
		// TODO Auto-generated method stub
		return null;
	}
}


Insbesondere interessant ist:
Java: 
			@Override
			public boolean hasNext() {
				if (b && a.succ == anchor) {
					b = false;
					return a.value != null;
				}
				return b && a.value != null;
			}


@mrBrown : Ich finde die Aufgabenstellung etwas unnötig kompliziert oder nicht ausreichend gestellt formuliert...

@ocsme Eine Ausgabe kann dann zum Bleistift so schauen:
Java: 
 leer
1
1; 4
1; 1; 4
1; 1; 4; 4
1; 1; 4; 4; 4
1; 1; 4; 4; 4; 4
0; 1; 1; 4; 4; 4; 4
0; 0; 1; 1; 4; 4; 4; 4
0; 0; 1; 1; 2; 4; 4; 4; 4
0; 0; 1; 1; 2; 4; 4; 4; 4; 4

3
2; 3
1; 2; 3
1; 2; 2; 3
1; 2; 2; 3; 4
0; 1; 2; 2; 3; 4
0; 1; 2; 2; 3; 3; 4
0; 1; 2; 2; 2; 3; 3; 4
0; 1; 2; 2; 2; 3; 3; 3; 4
0; 0; 1; 2; 2; 2; 3; 3; 3; 4
 
Meniskusschaden hat gesagt.:
Geht's hier nicht eigentlich um Sets oder habe ich etwas verpasst?
Zum Vergrößern anklicken....
Nein nix verpasst....
Ehrlich, ich habe das nicht genau gelesen & darüber nachgedacht...

Es gibt auch noch viele Fragezeichen. Welchen Zustand nimmt das "Startelement" wann ein, wann soll wie verknüpft sein, sind null-Elemente erlaubt, wieso gab es keinen Konstruktor?
 
Tobias-nrw hat gesagt.:
Es gibt auch noch viele Fragezeichen. Welchen Zustand nimmt das "Startelement" wann ein, wann soll wie verknüpft sein, sind null-Elemente erlaubt, wieso gab es keinen Konstruktor?
Zum Vergrößern anklicken....

Aber gut, dass wir eine fertige Implementation haben, die als Lösung vorgestellt wurde. Das wird dem TE bestimmt sehr geholfen haben. Das sind so Dinge, die so Realitätsverweigerer wie @mrBrown und ich halt nicht verstehen ....
 
WoW jetzt mal ganz langsam hier 🙂

1. Bin ich echt über jede Hilfe von euch Froh 🙂 denn wie Ihr sicherlich einigen Kommentaren vorher wieder sehr schön entnehmen könnt das ich wieder alles hin werfen wollte 😛
2. Habe ich nun auch verstanden was @mihe7 mit seinem Kommentar gemeint hat die Aufgabe ist wichtig 🙂
3. Ist diese Aufgabe zu Lückenhaft. Leider ist es die Komplette Aufgabe mehr steht da nicht 🙁
4. Würde ich mich sehr freuen wenn Ihr euch alle VERTRAGT 🙂 Es geht doch darum etwas zu Lernen und Lernen kann schließlich sehr viel Spaß machen auch wenn mich die Programmierung schon viele Graue Haare beschert hat! <- Bildlich gesprochen 😀

Also vielen Lieben Dank an euch nochmals 🙂 und jetzt wieder zurück zum Thema Iterator okay 😛

Denn mir fehlt so gesehen auch noch die next() Methode wobei ich sie von @Tobias-nrw übernehmen könnte das macht Sinn für mich nur einfach Ärgerlich das ich zu "doof" bin und nicht von alleine drauf gekommen bin 🙁
Hab mir vorhin also ich im Wald laufen war auch überlegt wie man eine remove(object x) Methode schreiben könnte und soll ich euch mal sagen JA ich bin zu "doof" auch dafür jetzt immer noch 😛 🙁 Deswegen nochmals Danke für jeden kleinen Hinweis und der GLEICHEN 🙂

Nun den HAVE FUN 🙂
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Schnelle, dynamische, geordnete Datenstruktur?
Antworten: 11
geordnete Zahlen
Antworten: 14
Geordnete Arrays ausgeben
Antworten: 31
Liste in pseudo geordnete Reihenfolge bringen
Antworten: 9
Geordnete, begrenzte Collection
Antworten: 3

Zurück
Oben