Iterator für eine geordnete Menge

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.

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 :D 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
 
K

kneitzel

Gast
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.
 
K

kneitzel

Gast
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.
 

ocsme

Top Contributor
Also so komme ich natürlich an die Datenelemente von Cell doch die sind dann ja null :D
Java:
@Override
        public boolean hasNext() {
            return new LinkedSet().new Cell().value != LinkedSet.this.anchor;
        }

Zumindest liess sich das bei mir übersetzen. Und wie man sieht: anchor ist direkt verfügbar.
Was ist bei dir Current? ich hab das in den Iterator eingefügt und alles ist rot :D

LG
 
K

kneitzel

Gast
Das ist das, was ich in meiner ersten Antwort erwähnt hatte:
a) der Iterator hat einen Zeiger auf ein Element. Dies speichert dann den Punkt, an dem man gerade ist.
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.
 

ocsme

Top Contributor
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 :D

LG
 

mrBrown

Super-Moderator
Mitarbeiter
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!
Du musst current im Konstruktor des Iterators noch initialisieren ;)

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 :D
Ersetz halt Object mit T ;)
 
K

kneitzel

Gast
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 :(

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?

Du musst current im Konstruktor des Iterators noch initialisieren ;)
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()....
 

mrBrown

Super-Moderator
Mitarbeiter
Nein, das muss nicht erfolgen, denn null als Initialisierung schien mir null prinzipiell gut genug zu sein.
Oh, stimmt, hätte noch mal den Code angucken sollen ':D

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()....
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
 
K

kneitzel

Gast
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

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?
 

mihe7

Top Contributor
Mal ein paar Dinge hervorheben:
Die Klasse LinkedSet repräsentiere geordnete Mengen als doppelt verkettete Ringlisten mit einer Anker-Zelle, die uach bei leeren Listen vorhanden ist.
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
 
K

kneitzel

Gast
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.
 

mrBrown

Super-Moderator
Mitarbeiter
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?
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


4. Es ist nicht gesagt, dass die Ankerzelle das kleinste Element darstellt
Es ist auch nicht gesagt, dass der Anker einen Wert hat, oder überseh ich das?
 

mihe7

Top Contributor
Es ist auch nicht gesagt, dass der Anker einen Wert hat, oder überseh ich das?
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...
 

mrBrown

Super-Moderator
Mitarbeiter
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...
Bei einer ein-Elementigen Liste könnte anchor.value == null oder aber anchor.value != null gelten

Die Aufgabestellung lässt viel Spielraum :D
 

mihe7

Top Contributor
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.
 

ocsme

Top Contributor
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 :D (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
 

mrBrown

Super-Moderator
Mitarbeiter

mihe7

Top Contributor
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
Pseudocode (Algorithmen) sind vollkommen ausreichend. Wenn ihr tatsächlich keine Ringbuffer besprochen habt, dann doch wohl wenigstens (doppelt) verkettete Listen.

Ich glaube die Aufgabe lass ich einfach sein.
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.
 

ocsme

Top Contributor
Pseudocode (Algorithmen) sind vollkommen ausreichend. Wenn ihr tatsächlich keine Ringbuffer besprochen habt, dann doch wohl wenigstens (doppelt) verkettete Listen.
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");
            }
        
    }
 

mrBrown

Super-Moderator
Mitarbeiter
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?
 

ocsme

Top Contributor
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.

Ich hab noch mehr solcher Fragen mal wieder :D
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 :D
 

ocsme

Top Contributor
Was gibt denn jetzt der erste, zweit, dritte, etc Aufruf von next zurück?

ach misst ich glaube immer das erste Element es wird nie weiter gerutscht stimmts :( MISST :D

Java:
 public T next() {
                if (hasNext()) {
                    T tmp = LinkedSet.this.first();
                    LinkedSet.this.remove(tmp);
                    return tmp;
                }
 
Zuletzt bearbeitet:

mrBrown

Super-Moderator
Mitarbeiter
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?
 

mrBrown

Super-Moderator
Mitarbeiter
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?
 

ocsme

Top Contributor
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:

mrBrown

Super-Moderator
Mitarbeiter
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.
 

ocsme

Top Contributor
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 :D

also muss man nur irgendwie mit dem anchor arbeiten stimmts?
 

mrBrown

Super-Moderator
Mitarbeiter
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 :D
Ja, der anchor ist niemals null, und anchor.value ist im einfachsten Fall immer null. pred und succ sind beide auch niemals null.


also muss man nur irgendwie mit dem anchor arbeiten stimmts?
Ja, für zwei Dinge musst du den anchor benutzen ;)
 

ocsme

Top Contributor
Ja, der anchor ist niemals null, und anchor.value ist im einfachsten Fall immer null. pred und succ sind beide auch niemals null.
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 :D

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

Xyz1

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

ocsme

Top Contributor
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 :D <- glaub ich zwar nicht dran aber naja! Danke :)
LG
 
Zuletzt bearbeitet:
K

kneitzel

Gast
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.
 

ocsme

Top Contributor
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 :D

Aber lieben Dank für deine Beiträge :)

Wenn es um das nächste Element geht, warum guckst du dir dann pred an?

Das ist eine gute Frage :D 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?
 

mrBrown

Super-Moderator
Mitarbeiter
Das ist eine gute Frage :D Benötige ich diesen Zeiger dann für remove?
Darüber kannst du dir Gedanken machen, wenn du remove schreibst ;)

Ist das den nun richtig?
Ja ;)




nein, noch nicht ganz, denn wenn es nur ein Elem gibt dann ist der Nachfolger des Ankers der Anker...
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.
 
X

Xyz1

Gast
Es kommt darauf an was mit "vorhanden" gemeint ist. Eigentlich heißt es dann nicht Ankerelem sondern dummy. :rolleyes: Die unzureichende Aufgabenstellung führt auch dazu, das null nicht erlaubt sein kann.

Aber es stimmt natürlich, meins ist zu kompliziert.
 

mrBrown

Super-Moderator
Mitarbeiter
Es kommt darauf an was mit "vorhanden" gemeint ist.
Nur, wenn man "vorhanden" als "ist null" interpretiert. Also nein.

Eigentlich heißt es dann nicht Ankerelem sondern dummy.
Nein. Niemand nennt es hier dummy. Anchor oder Head ist deutlich verbreiteter...

Die unzureichende Aufgabenstellung führt auch dazu, das null nicht erlaubt sein kann.
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"
 
X

Xyz1

Gast
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
 
X

Xyz1

Gast
Geht's hier nicht eigentlich um Sets oder habe ich etwas verpasst?
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?
 
K

kneitzel

Gast
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?

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 ....
 

ocsme

Top Contributor
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 :p
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 :D

Also vielen Lieben Dank an euch nochmals :) und jetzt wieder zurück zum Thema Iterator okay :p

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 :p :( Deswegen nochmals Danke für jeden kleinen Hinweis und der GLEICHEN :)

Nun den HAVE FUN :)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Eigener Iterator für LinkedList Java Basics - Anfänger-Themen 20
A Für was Iterator ? Java Basics - Anfänger-Themen 3
M Java Iterator Verständnisfrage Java Basics - Anfänger-Themen 6
N Kann man einen Iterator nur einmal verwenden Java Basics - Anfänger-Themen 5
N Warum Springt iterator nur in der Schleife weiter Java Basics - Anfänger-Themen 9
volcanos HashSet und Iterator -> Falsche Sortierreihenfolge ? Java Basics - Anfänger-Themen 18
J Methoden Die Reihenfolge der Iterator-Elemente umkehren Java Basics - Anfänger-Themen 3
J Methoden iterator for-schleife (hasNext() ) Java Basics - Anfänger-Themen 7
Stargirlxo Iterator + Methode Java Basics - Anfänger-Themen 10
G Java Listen und Iterator Java Basics - Anfänger-Themen 2
U Hashmap Iterator selbst implementieren Java Basics - Anfänger-Themen 10
F nur das erste Element mit iterator ausgeben Java Basics - Anfänger-Themen 5
O Iterator erneut! Java Basics - Anfänger-Themen 8
J Doppelte Ausgabe erzeugen Iterator Java Basics - Anfänger-Themen 6
K Iterator zurückliefern Java Basics - Anfänger-Themen 8
W Eigener Iterator soll mehrdimensionales Array durchlaufen Java Basics - Anfänger-Themen 4
S Iterator einer Liste Java Basics - Anfänger-Themen 4
B Sortieren mit Iterator Java Basics - Anfänger-Themen 4
I Erste Schritte Iterator Java Basics - Anfänger-Themen 3
M Iterator funktioniert nicht Java Basics - Anfänger-Themen 5
M Iterator cannot refer to a non final... Java Basics - Anfänger-Themen 20
O Interface Iterator Java Basics - Anfänger-Themen 2
M Collections Frage Beispielprogrammierung Iterator Java Basics - Anfänger-Themen 13
M Iterator Java Basics - Anfänger-Themen 25
J Iterator Funktioniert nicht richtig in StackImplementierung Java Basics - Anfänger-Themen 3
Z Hashmap Iterator löscht nicht Java Basics - Anfänger-Themen 8
L Iterator Java Basics - Anfänger-Themen 1
K Nutzung einer Klasse die das Iterator-Interface implementiert Java Basics - Anfänger-Themen 0
K Iterator-Interface implementieren mit Exception Handlung Java Basics - Anfänger-Themen 1
M Collections Iterator und generischer Baum Java Basics - Anfänger-Themen 0
O Kleine Frage zu Iterator und Iterable Java Basics - Anfänger-Themen 6
OnDemand Iterator Interfacve Java Basics - Anfänger-Themen 23
S Iterator next() Nullpointer Java Basics - Anfänger-Themen 2
T Methoden Iterator über ArrayList Java Basics - Anfänger-Themen 3
W Iterator Java Basics - Anfänger-Themen 2
D Aufgabe: Stack mit Iterator Java Basics - Anfänger-Themen 8
R Mit iterator auf Element zugreifen Java Basics - Anfänger-Themen 2
T Collections Zugriff auf Elemente aus Iterator() Schleife Java Basics - Anfänger-Themen 4
P Casting Warning bei Iterator Java Basics - Anfänger-Themen 32
F Wie Werte einer ArrayList an einen 'Custom'-Iterator übergeben? Java Basics - Anfänger-Themen 2
J Iterator Java Basics - Anfänger-Themen 5
P ArrayList mit Iterator / Iterable ausgeben Java Basics - Anfänger-Themen 8
B Funktionsweise Iterator unklar Java Basics - Anfänger-Themen 7
A Datentypen Iterator von hinten nach vorne durchlaufen Java Basics - Anfänger-Themen 4
D Wie Iterator Remove implementieren? Java Basics - Anfänger-Themen 11
B Datentypen Inhalt zum Iterator wieder aufrufen? Java Basics - Anfänger-Themen 10
D Iterator schaltet nicht weiter?! Java Basics - Anfänger-Themen 5
A Problem mit Iterator Java Basics - Anfänger-Themen 2
B Türme von Hanoi - Iterator Java Basics - Anfänger-Themen 50
V Hilfe beim implementieren von Iterator Java Basics - Anfänger-Themen 5
W Collections Iterator<E> Java Basics - Anfänger-Themen 7
L Lokale Variable und Instanzvariable innerhalb Iterator Java Basics - Anfänger-Themen 8
W OOP problem mit iterator! -.- Java Basics - Anfänger-Themen 9
B Iterator und Collection Java Basics - Anfänger-Themen 11
ruutaiokwu Iterator oder .size ??? Java Basics - Anfänger-Themen 6
vandread Iterator zählt nicht hoch?! Java Basics - Anfänger-Themen 3
L Problem mit Iterator bzw. Sortierte Liste Java Basics - Anfänger-Themen 14
N HashMap mit Iterator durchlaufen Java Basics - Anfänger-Themen 11
R Iterator Liste, Verständnisproblem Java Basics - Anfänger-Themen 4
J Verschachtelte for-Schleife mit Löschen von Iterationen. Wie über Iterator abbilden? Java Basics - Anfänger-Themen 6
M Iterator Java Basics - Anfänger-Themen 15
L Implementation gesucht - ArrayList.iterator() Java Basics - Anfänger-Themen 3
pun Iterator über ArrayList Java Basics - Anfänger-Themen 12
P Iterator.add() Java Basics - Anfänger-Themen 3
A For Schleife - Iterator wird null Java Basics - Anfänger-Themen 7
? Map und iterator Java Basics - Anfänger-Themen 11
0x7F800000 ungereimtheiten mit Iterator/ListIterator Java Basics - Anfänger-Themen 2
N "Dynamischer" Iterator Java Basics - Anfänger-Themen 21
J Iterator remove()? Java Basics - Anfänger-Themen 5
T Liste mit Iterator auslesen Java Basics - Anfänger-Themen 11
Kr0e Iterator Java Basics - Anfänger-Themen 2
D iterator instanziieren! Java Basics - Anfänger-Themen 11
M Der Umgang mit Iterator - Wie ein Objekt aus einer ArrayList Java Basics - Anfänger-Themen 2
J ArrayList mit Iterator Java Basics - Anfänger-Themen 3
W Iterator in Queue Java Basics - Anfänger-Themen 5
M warum interface iterator verwendbar? Java Basics - Anfänger-Themen 5
O Iterator - Durchlauf "einschränken" bzw. steuern&q Java Basics - Anfänger-Themen 2
K Collection und Iterator Java Basics - Anfänger-Themen 7
Q Iterator next erstellen Java Basics - Anfänger-Themen 4
S iterator problem Java Basics - Anfänger-Themen 3
S Iterator --__-- Zugriff auf nächstes Element Java Basics - Anfänger-Themen 5
N Set + Iterator oder doch nur zu blöd API zu lesen Java Basics - Anfänger-Themen 32
R Java 5.0 neue For schleife Iterator was ist der fehler? Java Basics - Anfänger-Themen 5
N generische HashMap und Iterator Java Basics - Anfänger-Themen 2
R Iterator und HashMap Java Basics - Anfänger-Themen 10
G Probleme mit Iterator Java Basics - Anfänger-Themen 2
E umgededrehte if anweisung funzt nicht , iterator. Java Basics - Anfänger-Themen 2
A Iterator, wie funkioniert das richtig? Java Basics - Anfänger-Themen 6
S Iterator Schreibweise Java Basics - Anfänger-Themen 7
P ArrayList, iterator: Fehler in while Schleife Java Basics - Anfänger-Themen 2
T Iterator Java Basics - Anfänger-Themen 8
G Frage zur Iterator ? Java Basics - Anfänger-Themen 12
A Iterator auf anfang setzen Java Basics - Anfänger-Themen 5
blackfeet Bildfadeffekt (Halptransparenz) & iterator Java Basics - Anfänger-Themen 8
C Problem mit verschachteltem Iterator Java Basics - Anfänger-Themen 2
R Problem mit Iterator Java Basics - Anfänger-Themen 6
M Problem mit Iterator.remove() Java Basics - Anfänger-Themen 5
R Enumeration oder Iterator? Java Basics - Anfänger-Themen 2
J Klasse Iterator Java Basics - Anfänger-Themen 5
D unregelmäßige NullPointerException bei LinkedList Iterator? Java Basics - Anfänger-Themen 9

Ähnliche Java Themen

Neue Themen


Oben