# Iterator für eine geordnete Menge



## ocsme (2. Jun 2019)

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



Meine Idee zu dieser Aufgabe war folgende:

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


----------



## kneitzel (2. Jun 2019)

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.


----------



## ocsme (2. Jun 2019)

Wie komme ich in der Inneren Klasse class terator an die Daten von class Cell?


----------



## mrBrown (2. Jun 2019)

ocsme hat gesagt.:


> Wie komme ich in der Inneren Klasse class terator an die Daten von class Cell?


An den Anker kommst du über `LinkedSet.this.anchor`


----------



## kneitzel (2. Jun 2019)

Die innere Klasse hat doch Zugriff auf die Element der äußeren Klasse. Also etwas wie das Folgende sollte schon funktionieren:


```
@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 (2. Jun 2019)

Also so komme ich natürlich an die Datenelemente von Cell doch die sind dann ja null 

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


Was ist bei dir Current? ich hab das in den Iterator eingefügt und alles ist rot 

LG


----------



## kneitzel (2. Jun 2019)

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.


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 (2. Jun 2019)

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


----------



## mrBrown (2. Jun 2019)

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!


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


Ersetz halt Object mit T


----------



## kneitzel (2. Jun 2019)

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



Also ich glaube, dass Du den Code nicht richtig angeschaut hast...

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


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 (2. Jun 2019)

kneitzel hat gesagt.:


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



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


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


----------



## kneitzel (2. Jun 2019)

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



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 (2. Jun 2019)

Mal ein paar Dinge hervorheben:


ocsme hat gesagt.:


> Die Klasse LinkedSet repräsentiere *geordnete Mengen* als doppelt verkettete *Ring*listen 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


----------



## kneitzel (2. Jun 2019)

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 (2. Jun 2019)

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?


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


Es ist auch nicht gesagt, dass der Anker einen Wert hat, oder überseh ich das?


----------



## mihe7 (2. Jun 2019)

mrBrown hat gesagt.:


> 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 (2. Jun 2019)

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


Bei einer ein-Elementigen Liste könnte anchor.value == null oder aber anchor.value != null gelten

Die Aufgabestellung lässt viel Spielraum


----------



## mihe7 (2. Jun 2019)

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 (3. Jun 2019)

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:

```
@Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }
```

Meine LinkedSetIterator Klasse sieht nun so aus:

```
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 (3. Jun 2019)

ocsme hat gesagt.:


> Denn current = anchor das bedeutet ist der anchor != null setzt er current auf succ und andernfalls auf den anchor.


`anchor != null` gilt immer 



ocsme hat gesagt.:


> Das bedeutet ich verliere meinen anchor oder etwa nicht und ich laufe im Kreis.


Nein, den anchor der Liste veränderst du nie (kannst du noch sicherstellen, indem du die den anchor final machst.


----------



## mihe7 (3. Jun 2019)

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


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.


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 (3. Jun 2019)

mihe7 hat gesagt.:


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


```
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 (3. Jun 2019)

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 (3. Jun 2019)

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.



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


----------



## ocsme (3. Jun 2019)

mrBrown hat gesagt.:


> 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 


```
public T next() {
                if (hasNext()) {
                    T tmp = LinkedSet.this.first();
                    LinkedSet.this.remove(tmp);
                    return tmp;
                }
```


----------



## mrBrown (3. Jun 2019)

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?


----------



## ocsme (3. Jun 2019)

mrBrown hat gesagt.:


> Wie kommst du von einer Cell zu deren Nachfolger?


Über die in der Cell definierten "Pointer" succ und pred. Doch dann habe ich ja wieder die selbe Frage wie um Himmelswillen kommen ich an diese Pointer ran?


----------



## mrBrown (3. Jun 2019)

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 (3. Jun 2019)

meinst du sowas:

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


----------



## mrBrown (3. Jun 2019)

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 (3. Jun 2019)

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?


----------



## mrBrown (3. Jun 2019)

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


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?


Ja, für zwei Dinge musst du den anchor benutzen


----------



## ocsme (3. Jun 2019)

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.


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 


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


----------



## Xyz1 (3. Jun 2019)

Ich sage gleich dazu es ginge auch etwas kürzer:


```
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 (3. Jun 2019)

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


----------



## mrBrown (3. Jun 2019)

ocsme hat gesagt.:


> Wäre das richtig?


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


BWT, den grad geposteten Code solltest du ignorieren.


----------



## kneitzel (3. Jun 2019)

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

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

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


----------



## Xyz1 (3. Jun 2019)

mrBrown hat gesagt.:


> den grad geposteten Code solltest du ignorieren


Ich weiß, richtige Sachen ignorieren ist deiner Ansicht nach richtig. Realitätsverweigerung, ähnlich wie bei @kneitzel .



ocsme hat gesagt.:


> Danke Tobias-nrw


Bitte.



ocsme hat gesagt.:


> so und nun bin ich noch deprimierter


Schade.


----------



## ocsme (3. Jun 2019)

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?



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

also mein hasNext() wäre nun diese hier:

```
@Override
        public boolean hasNext() {
            return (current.succ != anchor);
        }
```

Ist das den nun richtig?


----------



## Xyz1 (3. Jun 2019)

ocsme hat gesagt.:


> Ist das den nun richtig


nein, noch nicht ganz, denn wenn es nur ein Elem gibt dann ist der Nachfolger des Ankers der Anker...


----------



## mrBrown (3. Jun 2019)

ocsme hat gesagt.:


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


Darüber kannst du dir Gedanken machen, wenn du remove schreibst 



ocsme hat gesagt.:


> Ist das den nun richtig?


Ja 






Tobias-nrw hat gesagt.:


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


----------



## Xyz1 (3. Jun 2019)

mrBrown hat gesagt.:


> Der Nachfolger des Ankers ist nur dann der Anker selbst, wenn das Set leer ist


leider nein, leider gar nicht; siehe auch die Aufgabenstellung


----------



## mrBrown (3. Jun 2019)

Tobias-nrw hat gesagt.:


> leider nein, leider gar nicht; siehe auch die Aufgabenstellung


Hab ich. Es gibt *immer *ein Ankerelement.
Wenn man es nicht überflüssig umständlich kompliziert macht - wie du das getan hast - hat dieses Anker-Element immer einen value von null. So wie das auf den letzten zwei Seiten angenommen wird.


----------



## Xyz1 (3. Jun 2019)

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.


----------



## mrBrown (3. Jun 2019)

Tobias-nrw hat gesagt.:


> Es kommt darauf an was mit "vorhanden" gemeint ist.


Nur, wenn man "vorhanden" als "ist null" interpretiert. Also nein.



Tobias-nrw hat gesagt.:


> Eigentlich heißt es dann nicht Ankerelem sondern dummy.


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.


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"


----------



## Xyz1 (3. Jun 2019)

Schau mal @ocsme das müsste hinkommen:

```
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:

```
@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:

```
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 (3. Jun 2019)

Tobias-nrw hat gesagt.:


> Eine Ausgabe kann dann zum Bleistift so schauen:


Geht's hier nicht eigentlich um Sets oder habe ich etwas verpasst?


----------



## Xyz1 (3. Jun 2019)

Meniskusschaden hat gesagt.:


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


----------



## kneitzel (3. Jun 2019)

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?



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 (3. Jun 2019)

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


----------



## ocsme (3. Jun 2019)

Tobias-nrw hat gesagt.:


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



und genau dafür entschuldige ich mich nochmals  und deswegen kein STREIT hier  

LG


----------



## ocsme (3. Jun 2019)

remove() soll x aus der Menge entfernen und dann true liefern (andernfalls false). Gesucht ist die Implementierung von remove(Object x).

Verstehe ich das richtig? -> Die Klasse LinkedSet implementiert SortedSet dieses Interface hat Collection als Interface und dort steht eine remove Methode. Soll man also in dieser remove Methode einfach die Methode von LinkedList aufrufen? bzw. wäre das erlaubt? 
Danach wollte ich noch die normale remove Methode schreiben also ohne ein Object zu übergeben. Diese Methode kann man ja erst Aufrufen wenn man mindestens 1x next() gemacht hat. 

So hätte ich jetzt die remove(object x) geschrieben:

```
public boolean remove(Object x) {
             return LinkedSet.this.remove(x);
         }
```


----------



## Xyz1 (3. Jun 2019)

ocsme hat gesagt.:


> remove() soll x aus der Menge entfernen und dann true liefern (andernfalls false).


Das ist mit ein Grund, warum doppelte Elemente eigentlich falsch ist.



ocsme hat gesagt.:


> Soll man also in dieser remove Methode einfach die Methode von LinkedList aufrufen?


Nein, Du musst jede Methode, die überschrieben werden soll, auch selber überschreiben. Das sind fast alle Methoden... (leider..)


----------



## mrBrown (3. Jun 2019)

Bitte beim Thema bleiben, persönlich werdendes OT wird entfernt...


----------



## ocsme (3. Jun 2019)

mrBrown hat gesagt.:


> OT


Was heißt OT?

Nochmal kurz eine Frage: wie bekomme ich ein Datenelement aus einer Out() Klasse in eine Lokale Klasse? Muss man dazu eine Instanz erstellen hier ein Bsp:


```
public class Out {
    String a = "a";
   
    public void test() {
        System.out.println("Test");
        class In {
            public void test() {
                System.out.println(new Out().a);
            }
        }
        new In.test();
    }
}
```


----------



## mrBrown (3. Jun 2019)

ocsme hat gesagt.:


> Was heißt OT?


Off-Topic




ocsme hat gesagt.:


> Nochmal kurz eine Frage: wie bekomme ich ein Datenelement aus einer Out() Klasse in eine Lokale Klasse? Muss man dazu eine Instanz erstellen hier ein Bsp:


Kommt drauf an was du eigentlich machen willst...in dem Beispiel ginge das mit `Out.this`


----------



## ocsme (3. Jun 2019)

Danke genau das habe ich gesucht.
Verstehen tu ich den Aufruf zwar nicht wirklich.
Wenn ich z. B. String.this. aufrufe was heißt das?
Ich hab zugriff auf String sowie auch auf Object!

LG


----------



## mrBrown (3. Jun 2019)

Klassenname.this ist *nur* sinnvoll, wenn du aus einer inneren Klasse heraus eine Instanz der äußeren brauchst. Jede innere Klasse hat eine Referenz auf die äußere, und die spricht man eben mit Klassenname.this an.


Im Zusammenhang mit String und Object brauchst du das nie, das ist nur bei deinen eigenen Klassen sinnvoll.


----------



## Xyz1 (3. Jun 2019)

mrBrown hat gesagt.:


> Out.this


Also der Grund, weswegen man Out.this nicht benötigt ist hierbei, weil die "äußere Klasse" nicht auf Deine eigene Implementierung zugreifen kann und weil ein Teil der "Kern"-Implementierung in einer eigenen Klasse vorgegeben ist, welche Du erweitern solltest...

Es wäre anders, wenn die "Kern"-Implementierung der "äußeren Klasse" vorgegeben gewesen wäre... (also wenn ihr auf diese zurückgreifen hättet sollen...)


----------



## mrBrown (3. Jun 2019)

Tobias-nrw hat gesagt.:


> Also der Grund, weswegen man Out.this nicht benötigt ist hierbei, weil die "äußere Klasse" nicht auf Deine eigene Implementierung zugreifen kann und weil ein Teil der "Kern"-Implementierung in einer eigenen Klasse vorgegeben ist, welche Du erweitern solltest...
> 
> Es wäre anders, wenn die "Kern"-Implementierung der "äußeren Klasse" vorgegeben gewesen wäre... (also wenn ihr auf diese zurückgreifen hättet sollen...)


Häh?


----------



## mihe7 (3. Jun 2019)

ocsme hat gesagt.:


> Ist diese Aufgabe zu Lückenhaft. Leider ist es die Komplette Aufgabe mehr steht da nicht


Mit der Info, dass die Methoden des Set verwendet werden dürfen, ist die Aufgabe lösbar: man kann das kleinste Element mit first() erhalten und die Frage, ob die Menge leer ist, lässt sich mit isEmpty() beantworten.

Da hier schon Lösungen genannt wurden, schreibe ich hier mal meine mit der Entwicklung einer solchen Lösung verbundenen Gedanken zusammen. Vielleicht hilft es für das Verständnis.

Der Iterator hat einen Zeiger (current), der auf die "aktuelle" Zelle zeigt. Wurde die aktuelle Zelle noch nicht bestimmt, ist sie null. 

Wann gibt es ein nächstes Element? Wenn die aktuelle Zelle noch nicht bestimmt wurde, wäre das kleinste Element das nächste Element. Es gibt genau dann ein kleinstes Element, wenn die Liste nicht leer ist. D. h.

```
boolean hasNext() {
    if (current == null) {
        return !isEmpty();
    }
}
```

Damit wäre der Fall für die leere Liste abgehakt. 

Jetzt ist es ja so, dass man einen Ring hat, den man sich wie eine analoge Uhr vorstellen kann. Das kleinste Element wäre dort die 1. Es gibt nun so lange nächste Elemente, bis man wieder beim kleinsten Element angelangt ist, richtig? Also muss hasNext() so lange true liefern, so lange current nicht auf die Zelle mit dem kleinsten Wert zeigt.


```
boolean hasNext() {
    if (current == null) {
        return !isEmpty();
    } else {
        return current != smallest; 
    }
}
```
oder kurz:

```
boolean hasNext() {
    return current == null ? !isEmpty() : current != smallest;
}
```

Gut, was passiert nun in next()? Zuerst einmal wird geprüft, ob es ein nächstes Element gibt. Falls nein, wird eine NoSuchElementException geworfen (Contract von Iterator). Falls ja, muss der Wert der aktuellen Zelle zurückgegeben werden, gleichzeitig muss der Zeiger auf die nächste Zelle vorrücken. 


```
T next() {
    if (hasNext()) {
        // current == null kommt gleich 
        T value  = current.value;
        current = current.succ;
        return value;
    } else {
        throw new NoSuchElementException();
    }
}
```

Jetzt muss noch der Fall current == null behandelt werden. Das ist der Fall, wenn next() erstmals aufgerufen wurde. Hier muss im Wesentlichen die Zelle mit dem kleinsten Element bestimmt werden, denn das muss nicht die Ankerzelle sein (z. B. könnte auf der Uhr die Zelle mit der 3 die Ankerzelle sein - wir haben ja einen Ring). 

Das kleinste Element erhält man über das Set via first(). Man fängt bei der Ankerzelle an (smallest = anchor). So lange nun smallest.value und first() ungleich sind, rückt man den Zeiger um eine Zelle zurück. Am Ende setzt man current = smallest.

Also

```
T next() {
    if (hasNext()) {
        if (current == null) {
            smallest = anchor;
            T smallestValue = first(); 
            while (!Objects.equals(smallest.value, smallestValue)) {
                smallest = smallest.pred;
            }
            current = smallest;
        }
        T value  = current.value;
        current = current.succ;
        return value;
    } else {
        throw new NoSuchElementException();
    }
}
```

Dabei wird Objects.equals verwendet, weil nicht klar ist, ob null-Werte zulässig sind. Sollte passen.


----------



## mrBrown (3. Jun 2019)

Mal meine Lösung:

Ausgehend von der Annahme, `anchor != null && anchor.value == null` und `isEmpty() == (anchor.succ==anchor.pred==anchor)` und, dass direkt geordnet eingefügt wird.

`current` ist das Element, bei welchem der Iterator aktuell steht. Bevor next das erste Mal aufgerufen wurde, steht das ganze vor ersten wirklichen Element, was der Anker ist:

```
Cell current = anchor;
```

Es gibt immer so lange ein nächstes Element, bis das nächste wieder der Anker ist, man also wieder am Anfang angekommen wäre:


```
public boolean hasNext() {
    return current.succ != anchor;
}
```

In next wird dann jeweils auf das nächste Element "weiter geschaltet", und dessen Wert dann zurück gegeben.
Erst wird natürlich geprüft, ob es überhaupt ein nächstes Element gibt, und notfalls die Exception geworfen.


```
public T next() {
    if (!hasNext()) throw new NoSuchElementException();
    current = current.succ;
    return current.value;
}
```

Im gesamten:

```
class LinkedSetIterator implements Iterator<T> {

    Cell current = anchor;

    public boolean hasNext() {
        return current.succ != anchor;
    }

    @Override
    public T next() {
        if (!hasNext()) throw new NoSuchElementException();
        current = current.succ;
        return current.value;
    }

}
```


----------



## Xyz1 (3. Jun 2019)

Habe mal weiter gemacht und tests dafür geschrieben, `remove()`.... habe ich "delegiert" an den iterator. Sicherlich nicht die bestmögliche Lösung und es sollte eigentlich mit so 10.000 Elem getestet werden, aber es sind nur noch 4 tests rot. 


```
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 void remove() {
				a.pred.pred.succ = a;
				a.pred = a.pred.pred;
			}

		};
	}

	@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) {
		for (T t : c) {
			add(t);
		}
		return true;
	}

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

	@Override
	public boolean contains(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o))
				return true;
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object o : c) {
			if (!contains(o))
				return false;
		}
		return true;
	}

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

	@Override
	public boolean remove(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o)) {
				i.remove();
				return true;
			}
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		for (Object o : c) {
			if (!remove(o)) {
				return false;
			}
		}
		return true;
	}

	@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++;
			a = a.succ;
		}
		return s;
	}

	@Override
	public Object[] toArray() {
		Object[] a = new Object[size()];
		int j = 0;
		Iterator<T> i = iterator();
		while (i.hasNext())
			a[j++] = i.next();
		return a;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		int j = 0;
		Iterator<T> i = (Iterator<T>) iterator();
		while (i.hasNext())
			a[j++] = i.next();
		return a;
	}

	@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;
	}
}
```


```
import static org.junit.jupiter.api.Assertions.*;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class LinkedSetTest {
	LinkedSet<Integer> set = null;

	@BeforeEach
	void setUp() throws Exception {
		set = new LinkedSet<Integer>();
	}

	@AfterEach
	void tearDown() throws Exception {
		set.clear();
		set = null;
	}

	@Test
	void testMain() {
		LinkedSet.main(null);
	}

	@Test
	void testIterToString() {
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		String s = LinkedSet.iterToString(i);
		assertNotNull(i);
		System.out.println(s);
	}

	@Test
	void testLinkedSet() {
		assertNotNull(set);
	}

	@Test
	void testIterator() {
		set.add(new Random().nextInt(5));
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		assertTrue(i.hasNext());
	}

	@Test
	void testAdd() {
		for (int i = 0; i < 12; i++) {
			assertTrue(set.add(new Random().nextInt(5)));
		}
	}

	@Test
	void testAddAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
	}

	@Test
	void testClear() {
		set.clear();
		assertTrue(set.isEmpty());
	}

	@Test
	void testContains() {
		assertTrue(set.add(2));
		assertTrue(set.contains(2));
	}

	@Test
	void testContainsAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.containsAll(Arrays.asList(2, 3, 4)));
	}

	@Test
	void testIsEmpty() {
		assertTrue(set.isEmpty());
		assertTrue(set.add(1));
		assertFalse(set.isEmpty());
	}

	@Test
	void testRemove() {
		assertTrue(set.add(2));
		assertTrue(set.remove(2));
		assertFalse(set.remove(3));
	}

	@Test
	void testRemoveAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.removeAll(Arrays.asList(2, 3, 4)));
	}

	@Test
	void testRetainAll() {
		fail("Not yet implemented");
	}

	@Test
	void testSize() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.size() == 3);
	}

	@Test
	void testToArray() {
		assertNotNull(set.toArray());
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertNotNull(set.toArray());
	}

	@Test
	void testToArrayTArray() {
		assertNotNull(set.toArray(new Integer[0]));
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.toArray(new Integer[set.size()]).getClass().equals(Integer[].class));
	}

	@Test
	void testComparator() {
		assertTrue(set.comparator() instanceof Comparator<?>);
	}

	@Test
	void testFirst() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.first() == 2);
	}

	@Test
	void testHeadSet() {
		fail("Not yet implemented");
	}

	@Test
	void testLast() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.last() == 4);
	}

	@Test
	void testSubSet() {
		fail("Not yet implemented");
	}

	@Test
	void testTailSet() {
		fail("Not yet implemented");
	}
}
```


@mrBrown Wie soll ich auf diesen qualifizierten Kommetar antworten?


----------



## mrBrown (3. Jun 2019)

Tobias-nrw hat gesagt.:


> ```
> @Test
> void testAdd() {
> for (int i = 0; i < 12; i++) {
> ...


Mindestens dieser Test (und auch die Implementierung von add) sind falsch. true darf nur zurückgegeben werden, wenn das Element nicht schon existierte.


----------



## Xyz1 (3. Jun 2019)

mrBrown hat gesagt.:


> Mindestens dieser Test (und auch die Implementierung von add) sind falsch. true darf nur zurückgegeben werden, wenn das Element nicht schon existierte.


Ja das ist ein alter Schuh. Mein Set erlaubt (immer noch  ) doppelte Elemente (ich müsste das alles "umschreiben"). Das ist quasi nicht im Sinne von @Meniskusschaden . 

Deswegen werden auch nicht alle Methoden funktionieren... 

Aber Danke das es dir aufgefallen ist..

Bearbeitung: Beitrag #64 bitte wieder entfernen falls möglich.


----------



## mrBrown (3. Jun 2019)

Na die Änderung hin zu einem "korrekten" Set sollte doch nicht mehr als eine neue Zeile erfordern...


----------



## Xyz1 (3. Jun 2019)

mrBrown hat gesagt.:


> Na die Änderung hin zu einem "korrekten" Set sollte doch nicht mehr als eine neue Zeile erfordern...


Theoretisch schon, praktisch ist aber schon


Tobias-nrw hat gesagt.:


> public boolean add(T t) {


Etwas zu lang...


----------



## mihe7 (3. Jun 2019)

Ohne das jetzt getestet zu haben:

```
public boolean add(T e) {
        if (e == null) {
            throw new NullPointerException();
        }

        boolean result = true;
        if (isEmpty()) {
            anchor.value = e;
        } else if (contains(e)) {
            result = false;
        } else if (e.compareTo(getValue(anchor)) < 0) {
            anchor = insertBefore(anchor, e);
        } else {
            Cell current = anchor.succ;
            while (current != anchor && getValue(current).compareTo(e) < 0) {
                current = current.succ;                
            }
            insertBefore(current, e);
        }
        return result;
    }

    private Cell insertBefore(Cell cell, T e) {
        Cell result = new Cell();
        result.pred = cell.pred;
        result.succ = cell;
        cell.pred.succ = result;
        cell.pred = result;
        return cell;
    }
```


----------



## Xyz1 (4. Jun 2019)

Moin,


mihe7 hat gesagt.:


> getestet


habe s getestet. Es funktioniert noch nicht, es fügt nicht ein, die Verknüpfungen sind noch nicht richtig.

Die Hälfte der Tests sind nun rot.


----------



## mihe7 (4. Jun 2019)

Woran liegts?

EDIT: LOL, hab beim insert wohl den Wert vergessen  

```
private Cell insertBefore(Cell cell, T e) {
        Cell result = new Cell();
        result.value = e;
        result.pred = cell.pred;
        result.succ = cell;
        cell.pred.succ = result;
        cell.pred = result;
        return cell;
    }
```


----------



## mrBrown (4. Jun 2019)

Vermutlich, weil in insertBefore der Wert der neuen Cell nicht gesetzt wird


----------



## mihe7 (4. Jun 2019)

Das sind die Momente, in denen man sich denkt: Herr, schmeiß Hirn vom Himmel.


----------



## Xyz1 (4. Jun 2019)

mihe7 hat gesagt.:


> LOL, hab beim insert wohl den Wert vergessen


Ohman.... 

Damit funktionierts, ich habe die Tests nochmal etwas verbessert....


```
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 void remove() {
				a.pred.pred.succ = a;
				a.pred = a.pred.pred;
			}

		};
	}

	public boolean add(T e) {
		if (e == null) {
			throw new NullPointerException();
		}

		if (isEmpty()) {
			anchor.value = e;
		} else if (contains(e)) {
			return false;
		} else if (((Comparable) e).compareTo(anchor.value) < 0) {
			anchor = insertBefore(anchor, e);
		} else {
			Cell current = anchor.succ;
			while (current != anchor && ((Comparable) current.value).compareTo(e) < 0) {
				current = current.succ;
			}
			insertBefore(current, e);
		}
		return true;
	}

	private Cell insertBefore(Cell cell, T e) {
		Cell result = new Cell();
		result.value = e;
		result.pred = cell.pred;
		result.succ = cell;
		cell.pred.succ = result;
		cell.pred = result;
		return result;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		for (T t : c) {
			add(t);
		}
		return true;
	}

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

	@Override
	public boolean contains(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o))
				return true;
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object o : c) {
			if (!contains(o))
				return false;
		}
		return true;
	}

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

	@Override
	public boolean remove(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o)) {
				i.remove();
				return true;
			}
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		for (Object o : c) {
			if (!remove(o)) {
				return false;
			}
		}
		return true;
	}

	@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++;
			a = a.succ;
		}
		return s;
	}

	@Override
	public Object[] toArray() {
		Object[] a = new Object[size()];
		int j = 0;
		Iterator<T> i = iterator();
		while (i.hasNext())
			a[j++] = i.next();
		return a;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		int j = 0;
		Iterator<T> i = (Iterator<T>) iterator();
		while (i.hasNext())
			a[j++] = i.next();
		return a;
	}

	@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;
	}
}
```


```
import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class LinkedSetTest {
	LinkedSet<Integer> set = null;

	@BeforeEach
	void setUp() throws Exception {
		set = new LinkedSet<Integer>();
	}

	@AfterEach
	void tearDown() throws Exception {
		set.clear();
		set = null;
	}

	@Test
	void testMain() {
		LinkedSet.main(null);
	}

	@Test
	void testIterToString() {
		testAdd();
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		String s = LinkedSet.iterToString(i);
		assertNotNull(i);
		System.out.println(s);
	}

	@Test
	void testLinkedSet() {
		assertNotNull(set);
	}

	@Test
	void testIterator() {
		assertTrue(set.add(new Random().nextInt(5)));
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		assertTrue(i.hasNext());
	}

	@Test
	void testAdd() {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i = 0; i < 12; i++) {
			l.add(i);
		}
		for (int j = 0; j < 12; j++) {
			set.clear();
			Collections.shuffle(l);
			for (int i = 0; i < 12; i++) {
				assertTrue(set.add(l.get(i)));
			}
		}
	}

	@Test
	void testAddAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
	}

	@Test
	void testClear() {
		set.clear();
		assertTrue(set.isEmpty());
	}

	@Test
	void testContains() {
		assertTrue(set.add(2));
		assertTrue(set.contains(2));
	}

	@Test
	void testContainsAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.containsAll(Arrays.asList(2, 3, 4)));
	}

	@Test
	void testIsEmpty() {
		assertTrue(set.isEmpty());
		assertTrue(set.add(1));
		assertFalse(set.isEmpty());
	}

	@Test
	void testRemove() {
		assertTrue(set.add(2));
		assertTrue(set.remove(2));
		assertFalse(set.remove(3));
	}

	@Test
	void testRemoveAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.removeAll(Arrays.asList(2, 3, 4)));
	}

	@Test
	void testRetainAll() {
		fail("Not yet implemented");
	}

	@Test
	void testSize() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.size() == 3);
	}

	@Test
	void testToArray() {
		assertNotNull(set.toArray());
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertNotNull(set.toArray());
	}

	@Test
	void testToArrayTArray() {
		assertNotNull(set.toArray(new Integer[0]));
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.toArray(new Integer[set.size()]).getClass().equals(Integer[].class));
	}

	@Test
	void testComparator() {
		assertTrue(set.comparator() instanceof Comparator<?>);
	}

	@Test
	void testFirst() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.first() == 2);
	}

	@Test
	void testHeadSet() {
		fail("Not yet implemented");
	}

	@Test
	void testLast() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.last() == 4);
	}

	@Test
	void testSubSet() {
		fail("Not yet implemented");
	}

	@Test
	void testTailSet() {
		fail("Not yet implemented");
	}
}
```


```
Leerzeile
2
0; 2
0; 2
0; 2; 3
0; 2; 3
0; 2; 3
0; 2; 3; 4
0; 2; 3; 4
0; 2; 3; 4
0; 2; 3; 4

4
4
2; 4
0; 2; 4
0; 2; 4
0; 2; 4
0; 2; 4
0; 1; 2; 4
0; 1; 2; 4
0; 1; 2; 3; 4
0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11
```


@mihe7 Hast Du Lust die noch verbleibenden 4 Methoden zu implementieren?


----------



## mrBrown (4. Jun 2019)

Tobias-nrw hat gesagt.:


> @mihe7 Hast Du Lust die noch verbleibenden 4 Methoden zu implementieren?





Spoiler: LinkedSet



Die Methoden des Subsets sind nicht wirklich gut getestet, da steckt bestimmt noch ein Fehler drin...

```
import java.util.*;


public class LinkedSet<T extends Comparable<T>> extends AbstractSet<T> implements SortedSet<T> {

    private Cell anchor;

    private int size = 0;

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

    public LinkedSet(Collection<T> collection) {
        this.anchor = new Cell();
        this.addAll(collection);
    }

    @SafeVarargs
    public static <T extends Comparable<T>> LinkedSet<T> of(T... ts) {
        return new LinkedSet<T>(Arrays.asList(ts));
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }

    public boolean add(T t) {
        if (contains(t)) {
            return false;
        }
        Cell newCell = new Cell(Objects.requireNonNull(t));
        Cell insertionPoint = findFloor(t);
        newCell.insertAfter(insertionPoint);
        size++;
        return true;
    }

    private Cell findFloor(T value) {
        Cell lower = anchor;
        while (lower.succ != anchor && lower.succ.value.compareTo(value) <= 0) {
            lower = lower.succ;
        }
        return lower;
    }

    private Comparator<? super T> internalComparator() {
        return Comparator.naturalOrder();
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean contains(final Object o) {
        for (final T t : this) {
            if (this.internalComparator().compare(t, (T) o) == 0) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Comparator<? super T> comparator() {
        return null;
    }

    private Cell findLower(T value) {
        Cell lower = anchor;
        while (lower.succ != anchor && lower.succ.value.compareTo(value) < 0) {
            lower = lower.succ;
        }
        return lower;
    }

    private Cell findCeiling(T value) {
        Cell greater = anchor;
        while (greater.succ != anchor && !(greater.succ.value.compareTo(value) > 0)) {
            greater = greater.succ;
        }
        return greater;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public SortedSet<T> subSet(final T fromElement, final T toElement) {
        return new LinkedSubSet(fromElement, toElement);
    }

    @Override
    public SortedSet<T> headSet(final T toElement) {
        return new LinkedSubSet(null, toElement);
    }

    @Override
    public SortedSet<T> tailSet(final T fromElement) {
        return new LinkedSubSet(fromElement, null);

    }

    @Override
    public T first() {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return anchor.succ.value;
    }

    @Override
    public T last() {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return anchor.pred.value;
    }

    private final class Cell {

        final T value;

        Cell pred;

        Cell succ;

        private Cell() {
            this(null);
            this.pred = this;
            this.succ = this;
        }

        private Cell(final T value) {
            this.value = value;
        }

        private void insertAfter(Cell insertionPoint) {
            this.pred = insertionPoint;
            this.succ = insertionPoint.succ;
            this.pred.succ = this;
            this.succ.pred = this;
        }

        private void unlink() {
            this.pred.succ = this.succ;
            this.succ.pred = this.pred;
        }

        @Override
        public String toString() {
            return "Cell{"
                   + "value=" + value
                   + '}';
        }

    }

    private final class LinkedSetIterator implements Iterator<T> {

        final Cell last;

        Cell current;

        private LinkedSetIterator() {
            this(anchor, anchor);
        }

        private LinkedSetIterator(final Cell beforeFirst, final Cell last) {
            this.current = beforeFirst;
            this.last = last;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            current = current.succ;
            return current.value;
        }

        public boolean hasNext() {
            return current.succ != last;
        }

        @Override
        public void remove() {
            current.unlink();
        }

    }

    private final class LinkedSubSet extends AbstractSet<T> implements SortedSet<T> {

        final T from;

        final T to;

        private final Cell fromCell;

        private final Cell toCell;

        private LinkedSubSet(final T from, final T to) {
            this.from = from;
            this.to = to;

            fromCell = from != null ? findLower(from) : anchor;
            toCell = to != null ? findCeiling(to) : anchor;
        }

        @Override
        public Iterator<T> iterator() {
            return new LinkedSetIterator(fromCell, toCell);
        }

        @Override
        public int size() {
            int size = 0;
            for (final T t : this) {
                size++;
            }
            return size;
        }

        @Override
        public Comparator<? super T> comparator() {
            return LinkedSet.this.comparator();
        }

        @Override
        public boolean add(final T t) {
            checkRange(t);
            return LinkedSet.this.add(t);
        }

        private void checkRange(final T t) {
            if (!isGreaterEqualThanFrom(t) || !isLowerThanTo(t)) {
                throw new IllegalArgumentException("Value out of range [" + from + "," + to + "): " + t);
            }
        }

        private boolean isLowerThanTo(final T t) {
            return to != null && t.compareTo(to) < 0;
        }

        private boolean isGreaterEqualThanFrom(final T t) {
            return from != null && t.compareTo(from) >= 0;
        }

        @Override
        public SortedSet<T> subSet(final T fromElement, final T toElement) {
            return LinkedSet.this.subSet(fromElement, toElement);
        }

        @Override
        public SortedSet<T> headSet(final T toElement) {
            return LinkedSet.this.subSet(from, toElement);
       }

       @Override
       public SortedSet<T> tailSet(final T fromElement) {
           return LinkedSet.this.subSet(fromElement, to);
       }

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

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

       @Override
       @SuppressWarnings("unchecked")
       public boolean contains(final Object o) {
           for (final T t : this) {
               if (LinkedSet.this.internalComparator().compare(t, (T) o) == 0) {
                   return true;
               }
           }
           return false;
       }

    }

}
```


----------



## Xyz1 (4. Jun 2019)

@mrBrown Das sieht schon professioneller aus.  Ja richtig gute Tests schreiben, ist genauso schwer wie die Implementierung...


----------



## mihe7 (4. Jun 2019)

mrBrown hat gesagt.:


> private int size = 0;


Mit size kann ja jeder.  Bei Dir ist anchor.value immer null?


----------



## mrBrown (4. Jun 2019)

mihe7 hat gesagt.:


> Mit size kann ja jeder.



Bin überrascht, dass das nicht einfach in AbstractSet/AbstractCollection ganz primitiv über iterieren gelöst ist



mihe7 hat gesagt.:


> Bei Dir ist anchor.value immer null?


Ja, spart halt den einen Sonderfall.


----------



## mihe7 (4. Jun 2019)

mrBrown hat gesagt.:


> Bin überrascht, dass das nicht einfach in AbstractSet/AbstractCollection ganz primitiv über iterieren gelöst ist


LOL, ich weiß auch nicht, was die gegen O(n) haben.



mrBrown hat gesagt.:


> Ja, spart halt den einen Sonderfall.


Das würde ich bei einem Ring immer machen: das Geschiss mit den Prüfungen wegen eines Elements...


----------



## mrBrown (4. Jun 2019)

mihe7 hat gesagt.:


> LOL, ich weiß auch nicht, was die gegen O(n) haben.


Ist ja bei anderen Methoden genauso gelöst  





Spoiler: Gefixte Version und Tests





```
import java.util.*;


public class LinkedSet<T extends Comparable<T>> extends AbstractSet<T> implements SortedSet<T> {

    private Cell anchor;

    private int size = 0;

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

    public LinkedSet(Collection<T> collection) {
        this.anchor = new Cell();
        this.addAll(collection);
    }

    @SafeVarargs
    public static <T extends Comparable<T>> LinkedSet<T> of(T... ts) {
        return new LinkedSet<T>(Arrays.asList(ts));
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }

    public boolean add(T t) {
        if (contains(t)) {
            return false;
        }
        Cell newCell = new Cell(Objects.requireNonNull(t));
        Cell insertionPoint = findFloor(t);
        newCell.insertAfter(insertionPoint);
        size++;
        return true;
    }

    private Cell findFloor(T value) {
        Cell lower = anchor;
        while (lower.succ != anchor && lower.succ.value.compareTo(value) <= 0) {
            lower = lower.succ;
        }
        return lower;
    }

    private Comparator<? super T> internalComparator() {
        return Comparator.naturalOrder();
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean contains(final Object o) {
        for (final T t : this) {
            if (this.internalComparator().compare(t, (T) o) == 0) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Comparator<? super T> comparator() {
        return null;
    }

    private Cell findLower(T value) {
        Cell lower = anchor;
        while (lower.succ != anchor && lower.succ.value.compareTo(value) < 0) {
            lower = lower.succ;
        }
        return lower;
    }

    private Cell findCeiling(T value) {
        Cell greater = anchor;
        while (greater.succ != anchor && !(greater.succ.value.compareTo(value) > 0)) {
            greater = greater.succ;
        }
        return greater;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public SortedSet<T> subSet(final T fromElement, final T toElement) {
        return new LinkedSubSet(fromElement, toElement);
    }

    @Override
    public SortedSet<T> headSet(final T toElement) {
        return new LinkedSubSet(null, toElement);
    }

    @Override
    public SortedSet<T> tailSet(final T fromElement) {
        return new LinkedSubSet(fromElement, null);

    }

    @Override
    public T first() {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return anchor.succ.value;
    }

    @Override
    public T last() {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return anchor.pred.value;
    }

    private final class Cell {

        final T value;

        Cell pred;

        Cell succ;

        private Cell() {
            this(null);
            this.pred = this;
            this.succ = this;
        }

        private Cell(final T value) {
            this.value = value;
        }

        private void insertAfter(Cell insertionPoint) {
            this.pred = insertionPoint;
            this.succ = insertionPoint.succ;
            this.pred.succ = this;
            this.succ.pred = this;
        }

        private void unlink() {
            this.pred.succ = this.succ;
            this.succ.pred = this.pred;
        }

        @Override
        public String toString() {
            return "Cell{"
                   + "value=" + value
                   + '}';
        }

    }

    private final class LinkedSetIterator implements Iterator<T> {

        final Cell last;

        Cell current;

        private LinkedSetIterator() {
            this(anchor, anchor);
        }

        private LinkedSetIterator(final Cell beforeFirst, final Cell last) {
            this.current = beforeFirst;
            this.last = last;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            current = current.succ;
            return current.value;
        }

        public boolean hasNext() {
            return current.succ != last;
        }

        @Override
        public void remove() {
            current.unlink();
            size--;
        }

    }

    private final class LinkedSubSet extends AbstractSet<T> implements SortedSet<T> {

        final T from;

        final T to;

        private final Cell fromCell;

        private final Cell toCell;

        private LinkedSubSet(final T from, final T to) {
            this.from = from;
            this.to = to;

            fromCell = from != null ? findLower(from) : anchor;
            toCell = to != null ? findCeiling(to) : anchor;
        }

        @Override
        public Iterator<T> iterator() {
            return new LinkedSetIterator(fromCell, toCell);
        }

        @Override
        public int size() {
            int size = 0;
            for (final T t : this) {
                size++;
            }
            return size;
        }

        @Override
        public Comparator<? super T> comparator() {
            return LinkedSet.this.comparator();
        }

        @Override
        public boolean add(final T t) {
            checkRange(t);
            return LinkedSet.this.add(t);
        }

        private void checkRange(final T t) {
            if (!isGreaterEqualThanFrom(t) || !isLowerThanTo(t)) {
                throw new IllegalArgumentException("Value out of range [" + from + "," + to + "): " + t);
            }
        }

        private boolean isLowerThanTo(final T t) {
            return to != null && t.compareTo(to) < 0;
        }

        private boolean isGreaterEqualThanFrom(final T t) {
            return from != null && t.compareTo(from) >= 0;
        }

        @Override
        public SortedSet<T> subSet(final T fromElement, final T toElement) {
            return LinkedSet.this.subSet(fromElement, toElement);
        }

        @Override
        public SortedSet<T> headSet(final T toElement) {
            return LinkedSet.this.subSet(from, toElement);
        }

        @Override
        public SortedSet<T> tailSet(final T fromElement) {
            return LinkedSet.this.subSet(fromElement, to);
        }

        @Override
        public T first() {
            if (this.isEmpty()) {
                throw new NoSuchElementException();
            }
            return fromCell.succ.value;
        }

        @Override
        public T last() {
            if (this.isEmpty()) {
                throw new NoSuchElementException();
            }
            return toCell.pred.value;
        }

        @Override
        @SuppressWarnings("unchecked")
        public boolean contains(final Object o) {
            for (final T t : this) {
                if (LinkedSet.this.internalComparator().compare(t, (T) o) == 0) {
                    return true;
                }
            }
            return false;
        }

    }

}
```



```
import java.util.*;

import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;
import static org.assertj.core.api.Assumptions.assumeThat;


class LinkedSetTest {

    @Test
    void shouldReturnNullComparator() {
        assertThat(new LinkedSet<>().comparator()).isNull();
    }

    @Test
    void firstShouldReturnSmallest() {
        LinkedSet<Integer> integers = LinkedSet.of(4, 2, 3, 1);
        assertThat(integers.first()).isEqualTo(1);
    }

    @Test
    void firstOnEmptySetShouldThrow() {
        LinkedSet<Integer> integers = LinkedSet.of();
        assertThatThrownBy(integers::first)
                .isInstanceOf(NoSuchElementException.class);
    }

    @Test
    void lastShouldReturnGreatest() {
        LinkedSet<Integer> integers = LinkedSet.of(4, 2, 3, 1);
        assertThat(integers.last()).isEqualTo(4);
    }

    @Test
    void lastOnEmptySetShouldThrow() {
        LinkedSet<Integer> integers = LinkedSet.of();
        assertThatThrownBy(integers::last)
                .isInstanceOf(NoSuchElementException.class);
    }

    @Test
    void shouldContainElementsInCorrectOrderAfterAdd() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);
        integers.add(4);
        integers.add(3);
        integers.add(2);

        assertThat(integers).containsExactly(1, 2, 3, 4);
    }

    @Test
    void tailSet() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);
        integers.add(4);
        integers.add(3);
        integers.add(2);
        assumeThat(integers).containsExactly(1, 2, 3, 4);
        assertThat(integers.tailSet(2)).containsExactly(2, 3, 4);
    }

    @Test
    void headSet() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);
        integers.add(4);
        integers.add(3);
        integers.add(2);

        assumeThat(integers).containsExactly(1, 2, 3, 4);
        assertThat(integers.headSet(3)).containsExactly(1, 2);
    }

    @Test
    void removeShouldRemoveElement() throws Exception {
        LinkedSet<Integer> integers = LinkedSet.of(1, 4, 3, 2);
        assumeThat(integers).containsExactly(1, 2, 3, 4);
        assertThat(integers.remove(2)).isTrue();
        assertThat(integers).containsExactly(1, 3, 4);
    }

    @Test
    void repeatedRemoveShouldReturnFalse() throws Exception {
        LinkedSet<Integer> integers = LinkedSet.of(1, 4, 3, 2);
        assumeThat(integers).containsExactly(1, 2, 3, 4);
        assumeThat(integers.remove(2)).isTrue();
        assumeThat(integers).containsExactly(1, 3, 4);

        assertThat(integers.remove(2)).isFalse();
    }

    @Test
    void emptySetShouldHaveSizeZero() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();

        assertThat(integers).hasSize(0).isEmpty();
    }

    @Test
    void oneElementSetShouldNotBeEmptyAndHaveSizeOne() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);

        assertThat(integers).hasSize(1).isNotEmpty();
    }

    @Test
    void shouldReturnCorrectSizeAfterRemove() {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);
        assumeThat(integers).hasSize(1).isNotEmpty();

        assertThat(integers.remove(1)).isTrue();
        assumeThat(integers).hasSize(0).isEmpty();
    }

    @Nested
    class SubSetTest {

        LinkedSet<Integer> integers = LinkedSet.of(1, 2, 4, 5);

        @Test
        void shouldReturnCorrectSubSet() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assertThat(subSet).containsExactly(2, 4);
        }

        @Test
        void addOnSubSetShouldAddOnSet() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            subSet.add(3);
            subSet.add(2);
            subSet.add(4);
            assertThat(subSet).containsExactly(2, 3, 4);
            assertThat(integers).containsExactly(1, 2, 3, 4, 5);
        }

        @Test
        void shouldThrowIfLowerThanRange() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            assertThatThrownBy(() -> subSet.add(1))
                    .isInstanceOf(IllegalArgumentException.class)
                    .hasMessage("Value out of range [2,5): 1");
        }

        @Test
        void shouldThrowIfGreaterThanRange() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            assertThatThrownBy(() -> subSet.add(5))
                    .isInstanceOf(IllegalArgumentException.class)
                    .hasMessage("Value out of range [2,5): 5");
        }

        @Test
        void shouldReturnEmptySet() {
            SortedSet<Integer> subSet = integers.subSet(2, 2);

            assertThat(subSet).isEmpty();
        }


        @Test
        void shouldReturnCorrectHeadSetFromSubSet() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            assumeThat(subSet.headSet(4)).containsExactly(2);
            assumeThat(subSet.headSet(2)).isEmpty();

        }
        @Test
        void shouldReturnCorrectTailSetFromSubSet() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            assumeThat(subSet.tailSet(2)).containsExactly(2, 4);
            assumeThat(subSet.tailSet(4)).containsExactly(4);

        }

        @Test
        void shouldReturnNullComparator() {
            assertThat(new LinkedSet<>().comparator()).isNull();
        }

        @Test
        void firstShouldReturnSmallest() {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);
            assertThat(subSet.first()).isEqualTo(2);
        }

        @Test
        void firstOnEmptySetShouldThrow() {
            SortedSet<Integer> subSet = integers.subSet(2, 2);
            assumeThat(subSet).isEmpty();
            assertThatThrownBy(subSet::first)
                    .isInstanceOf(NoSuchElementException.class);
        }

        @Test
        void lastShouldReturnGreatest() {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);
            assertThat(subSet.last()).isEqualTo(4);
        }

        @Test
        void lastOnEmptySetShouldThrow() {
            SortedSet<Integer> subSet = integers.subSet(2, 2);
            assumeThat(subSet).isEmpty();
            assertThatThrownBy(subSet::last)
                    .isInstanceOf(NoSuchElementException.class);
        }
    }

}
```


----------



## mihe7 (4. Jun 2019)

mrBrown hat gesagt.:


> Ist ja bei anderen Methoden genauso gelöst


Hm... das ließe sich doch auch in quadratischer Laufzeit hinbekommen.


----------



## Xyz1 (4. Jun 2019)

Mit size spart man sich natürlich eine Laufzeit von n zu 1...
Aber hier ging/geht es doch auch darum, dass TE etwas dabei "lernt/mitnimmt".
Und da finde ich unterschiedliche Möglichkeiten nicht schlecht zum lernen...

Genauso wie mit den Tests... meine sind nicht wirklich gut. Aber hab halt noch nicht so viele Erfahrungen damit.


----------



## Xyz1 (4. Jun 2019)

BTW es ist nicht ganz richtig, den Begriff "Set" mit Menge zu übersetzen, denn unter einer Menge versteht man etwas anderes, denn eine Menge erlaubt z.B auch doppelte Elemente - "Sets" hingegen nicht. Es gibt dafür keine "adäquate" Übersetzung...


----------



## thecain (4. Jun 2019)

Erlaubt ist relativ. {1, 2, 3, 3} == {1, 2, 3} Ich finde es also eigtl schon passend


----------



## kneitzel (4. Jun 2019)

Tobias-nrw hat gesagt.:


> BTW es ist nicht ganz richtig, den Begriff "Set" mit Menge zu übersetzen, denn unter einer Menge versteht man etwas anderes, denn eine Menge erlaubt z.B auch doppelte Elemente - "Sets" hingegen nicht. Es gibt dafür keine "adäquate" Übersetzung...


Hier wird natürlich nicht der mathematische Begriff der Menge verwendet sondern wenn wir von Datenstrukturen reden, dann wird natürlich auch die entsprechende Definition benutzt.

Siehe:
https://de.wikipedia.org/wiki/Menge_(Datenstruktur) 
https://de.wikipedia.org/wiki/Menge_(Mathematik)


----------



## mihe7 (4. Jun 2019)

Ich kenne das so: Menge enthält keine Duplikate, Multimenge schon.


----------



## mrBrown (4. Jun 2019)

Tobias-nrw hat gesagt.:


> BTW es ist nicht ganz richtig, den Begriff "Set" mit Menge zu übersetzen, denn unter einer Menge versteht man etwas anderes, denn eine Menge erlaubt z.B auch doppelte Elemente - "Sets" hingegen nicht. Es gibt dafür keine "adäquate" Übersetzung...



Du kannst auch ein Set schreiben, welches intern doppelte Elemente enthält. Das muss sich nur identisch zu dem verhalten, welches keine doppelten enthält....


----------



## ocsme (4. Jun 2019)

wow da habe ich ja eine Aufgabe gepostet 

 Freut mich so viel Feedback 

Eine Frage hätte ich aber noch.


```
public void remove() {
                a.pred.pred.succ = a;
                a.pred = a.pred.pred;
            }
```

Das ganze habe ich verstanden. Doch wie soll man das machen wenn man nach einem Object o gefragt wird das dieses Element entfernt werden soll?
Also 





> public void remove(Object o)


Könnte mir dabei noch jemand auf die Sprünge Helfen vielleicht?
"Ich dachte mit einem Vergleich auf das Überquerte Object und dann könnte man ja den remove von oben nutzen? macht sowas Sinn?"

Liebe Grüße


----------



## mrBrown (4. Jun 2019)

Die Methode ist in beiden Varianten vorhanden 

In meinem Code nur im AbstractSet, wovon ich erbe, in @Tobias-nrw aber direkt implementiert. (wobei ich grad merke, dass das bei mir noch falsch ist...)


Aber ja - deine Idee passt. Mit dem Iterator den Wert suchen und dann damit löschen.


----------



## mihe7 (4. Jun 2019)

ocsme hat gesagt.:


> wow da habe ich ja eine Aufgabe gepostet


Da sieht man erst einmal wie viele Möglichkeiten es gibt, ein und dasselbe Problem anzugehen.


----------



## Xyz1 (4. Jun 2019)

@ocsme stimmt, das war jetzt eine Menge. 

Du musst dir das bildlich vorstellen. a1, a2 und a3. a2 soll gelöscht werden. rot = zu löschen, grün = hinzuzufügen, a1 und a3 können natürlich noch weitere Kanten haben:


----------



## mrBrown (4. Jun 2019)

Wir sind aber vermutlich völlig übers Ziel der Aufgabe hinausgeschossen...


Set inklusive der SubSet-methoden ist zumindest nicht wirklich das, was ich im ersten/zweiten Semester Java erwarten würde.


----------



## mihe7 (4. Jun 2019)

Ein klarer YAGNI-Verstoß!


----------



## Xyz1 (4. Jun 2019)

WOOOBEI, man die aus a2 ausgehenden Kanten nicht extra löschen muss, da a2 nicht mehr referenziert wird nachher...


----------



## ocsme (4. Jun 2019)

Das remove(Object o) finde ich bei euren Daten jetzt nicht auf anhieb.
Dachte mir so etwas wenn wir ja nun die ganzen Methoden im Iterator hätten 


```
public boolean remove(Object x) {
             while(hasNext()) {
                 Object next = next();
                 if(x.equals(next)) {
                     this.next();
                     this.remove();
                     return true;
                 }
             }
            
             return false;
         }
```

bei dem this.next() und this.remove() bin ich mir nicht sicher :?


----------



## mihe7 (4. Jun 2019)

ocsme hat gesagt.:


> Dachte mir so etwas wenn wir ja nun die ganzen Methoden im Iterator hätten


Die remove(o)-Methode ist aber keine Methode, die vom Iterator-Interface spezifiziert wird.

Unabhängig davon sähe die remove(o)-Methode im Set fast identisch zu Deiner aus, wenn man mittels Iterator arbeiten will:

```
Iterator<T> it = iterator();
while (it.hasNext()) {
    T next = it.next();
    if (next.equals(o)) {
        it.remove();
        return true;
    }
}
return false;
```


----------



## Xyz1 (4. Jun 2019)

@ocsme Ich hatte das an den Iterator delegiert, es geht natürlich auch ohne.... Zum Bleistift: 

```
@Override
	public boolean remove(Object o) {
		if (isEmpty())
			return false;
		Cell a = anchor;
		do {
			if (Objects.equals(a.value, o)) {
				a.pred.pred.succ = a;
				a.pred = a.pred.pred;
				return true;
			}
			a = a.succ;
		} while (a != anchor);
		return false;
//		Iterator<T> i = iterator();
//		while (i.hasNext())
//			if (i.next().equals(o)) {
//				i.remove();
//				return true;
//			}
//		return false;
	}
```


----------



## mrBrown (4. Jun 2019)

Wobei bei einem SortedSet compareTo (oder Comparator#compare) statt equals benutzt werden sollte (bzw: muss).


----------



## Xyz1 (4. Jun 2019)

mrBrown hat gesagt.:


> Wobei bei einem SortedSet compareTo


Wo steht das 

Es gibt doch die Übereinkunft, dass a.equals(b) = true, gdw a.compareTo(b) = 0.


----------



## mrBrown (4. Jun 2019)

Tobias-nrw hat gesagt.:


> Wo steht das
> 
> Es gibt doch die Übereinkunft, dass a.equals(b) = true, gdw a.compareTo(b) = 0.


Im Javadoc:



> Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be _consistent with equals_ if the sorted set is to correctly implement the Set interface. (See the Comparable interface or Comparator interface for a precise definition of _consistent with equals_.) This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. The behavior of a sorted set _is_ well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.


----------



## Xyz1 (4. Jun 2019)

Du hast das falsch gelesen,


> must be consistent with equals




mihe lag richtig...


----------



## mrBrown (4. Jun 2019)

Tobias-nrw hat gesagt.:


> Du hast das falsch gelesen,
> 
> 
> 
> mihe lag richtig...


Den Rest hast du auch gelesen?


----------



## mihe7 (5. Jun 2019)

Tobias-nrw hat gesagt.:


> mihe lag richtig...


@mrBrown hat Recht.


----------



## Xyz1 (5. Jun 2019)

Ok, verstehe, Danke


----------



## kneitzel (5. Jun 2019)

Tobias-nrw hat gesagt.:


> Du hast das falsch gelesen,
> mihe lag richtig...



Das " but a sorted set performs all element comparisons using its compareTo " hast Du auch gelesen?


----------



## Xyz1 (5. Jun 2019)

Nein, hatte ich nicht gelesen....
Man muss dazu sagen, dass es sich um einen Java doc handelt, der nur beschreibt, wie eine Klasse implementiert ist - und nur *Empfehlungen* ausspricht, wie eine das Interface implementierende Klasse zu implementieren _wäre_....
Möchte man das Interface anders implementieren, erwähnt man eben *im eigenem Kommentar*, dass zwingend neben compareTo() auch equals() konform zu compareTo() zu implementieren ist....
(So wird es auch bei vielen anderen Collections gehandhabt.)

Aber jetzt müsst ihr mir mal helfen, eine binäre Suche ist aufgrund der Verlinkungen nicht möglich oder? Man bleibt also so oder so bei O(n) beim Entfernen oder?


----------



## ocsme (5. Jun 2019)

Ein letztes mal. So sieht jetzt die ganze Klasse aus. Wäre dort die remove(Object) Methode nun richtig? Irgendwie liest es sich komisch 


```
class LinkedSetIterator implements Iterator<T> {
        Cell current;

        LinkedSetIterator() {
            current = anchor;
        }
        
        @Override
        public boolean hasNext() {
            return (current.succ != anchor);
        }

         public T next() {
                if (hasNext()) {
                    T next = (T) current.value;
                    current = current.succ;
                    return next;
                    
                }
                throw new IllegalStateException("No more elements");
            }
        
         public boolean remove(Object x) {
             while(hasNext()) {
                 Object next = next();
                 if(x.equals(next)) {
                     this.next();
                     this.remove();
                     return true;
                 }
             }
            
             return false;
         }
        
         public void remove() {
             current.pred.pred.succ = current;
             current.pred = current.pred.pred;
         }
        
    }
```


----------



## Xyz1 (5. Jun 2019)

ocsme hat gesagt.:


> Wäre dort die remove(Object) Methode nun richtig


Nein, noch nicht....
Diese steht nun in dem Iterator, dass heißt, sie muss sich konform zu dem Iterator verhalten - und Du hast mit dem Iterieren im Iterator etwas übers Ziel hinaus geschossen...

Bearbeitung: Und da steht noch immer equals()....


----------



## mrBrown (5. Jun 2019)

ocsme hat gesagt.:


> Wäre dort die remove(Object) Methode nun richtig?


Ne, ein Iterator braucht nur remove(). Die sieht aber passend aus.

Allerdings sind next und hasNext falsch - da hast du irgendwie das schlechteste aller Varianten zusammengemixt.


----------



## kneitzel (5. Jun 2019)

Tobias-nrw hat gesagt.:


> Aber jetzt müsst ihr mir mal helfen, eine binäre Suche ist aufgrund der Verlinkungen nicht möglich oder? Man bleibt also so oder so bei O(n) beim Entfernen oder?


Ja, das ist richtig. Und sorry - hatte nicht gesehen, dass da ja noch mehr Antworten auf einer weiteren Seite waren. Das Thema war ja bereits soweit abgehandelt...

@ocsme Ja, Dein Code wirkt etwas seltsam, da Du im if noch einmal next() aufrufst (Problem: was ist, wenn es kein nächstes Element gibt?) und Du daher current weiter gesetzt hast und dann current.pred.pred und so kommt. Das ist nicht ganz intuitiv lesbar finde ich.


----------



## ocsme (5. Jun 2019)

wieso ist hasNext() Falsch? ich Frage doch ab ob der current.zeiger != anchor ist. Wie sollte er sonst aussehen?
Und bei Next() was ist dort Falsch?

LG


----------



## mrBrown (5. Jun 2019)

ocsme hat gesagt.:


> wieso ist hasNext() Falsch? ich Frage doch ab ob der current.zeiger != anchor ist. Wie sollte er sonst aussehen?
> Und bei Next() was ist dort Falsch?


next und hasNext und der initialwert von current passen einfach nicht zusammen.

Zu Anfang ist current=anchor
hasNext prüft dann, ob es noch einen Nachfolger gibt, next gibt dann aber den aktuellen Wert von current (also im ersten Aufruf anchor) zurück.

Spiel das einfach mal mit einem Schreibtischtest mit einem Set mit einem Element durch


----------



## Xyz1 (5. Jun 2019)

@ocsme Nochmal...

```
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 void remove() {
			a.pred.pred.succ = a;
			a.pred = a.pred.pred;
		}

	};
}
```


ist nicht falsch, die Frage wäre nur, ob es noch kürzer ginge....

Zudem kannst Du remove() in LinkedSet auch beliebig/anders implementieren.


----------



## kneitzel (5. Jun 2019)

Was Du bei Tobias sehr gut sehen kannst ist die Implementation des Iterators. Implementiert auch genau den Iterator und macht nicht mehr. Ein eigener Iterator kann zwar mehr implementieren, aber wenn jemand später iterator() aufruft, erwartet diese Person lediglich einen Iterator mit genau diesen Funktionen.

Und das remove(obj) wird somit nicht vom Iterator erwartet sondern diese Funktion kommt von Deiner Hauptklasse.

Da ein Iterator hat tolle Funktionen, mit denen man diese Funktionalität abdecken kann:
Solange Elemente verfügbar sind holst Du Dir das nächste Element. Ist dieses das gesuchte Element rufst Du remove() auf und beendest den Durchgang.

Bei der Implementation, die Tobias jetzt eben noch mal gebracht hat, scheint das remove aber nicht korrekt zu sein. Das remove() der Iterator-Implementation soll das current Element löschen. Das bedeutet, dass danach das aktuelle Element (da "a" genannt) nicht mehr referenziert ist.

Daher müsste da sowas drin stehen wie:
a.pref.suc = a.suc; a.suc.pref = a.pref; Also der Nachfolger vom Vorgänger vom aktuellen Element wird zum Nachfolger des aktuellen Element.. Und der Vorgänger vom Nachfolger vom aktuellen Element wird zum Vorgänger des aktuellen Elements ....

Der Code selbst hätte für deine remove(obj) Methode aber wohl funktioniert, weil Du da nicht das aktuelle Objekt gelöscht hast sondern den Vorgänger. Aber wenn man die Iterator Implementation getestet hätte, dann wäre da ein Fehler aufgetreten.


----------



## mrBrown (5. Jun 2019)

kneitzel hat gesagt.:


> Bei der Implementation, die Tobias jetzt eben noch mal gebracht hat, scheint das remove aber nicht korrekt zu sein. Das remove() der Iterator-Implementation soll das current Element löschen. Das bedeutet, dass danach das aktuelle Element (da "a" genannt) nicht mehr referenziert ist.


Das „aktuelle“ Element ist dabei nicht a, sondern a.pred


----------



## kneitzel (5. Jun 2019)

mrBrown hat gesagt.:


> Das „aktuelle“ Element ist dabei nicht a, sondern a.pred


Ohh, stimmt. Hatte ich jetzt übersehen. Wenn man selbst eine andere Implementierung vor sich hat, dann vertut man sich da leicht ... (Ein Grund für sprechende Namen, so dass man weiß, was man vor sich hat.)


----------



## Xyz1 (5. Jun 2019)

Ich habe die Tests nochmal umgeschrieben und einige Methoden der Klasse LinkedSet auch...
Kann bitte nochmal jemand danach sehen, die Tests werden grün, aber die Methoden removeAll() und iterToString() halten nicht mehr an. Mist...

```
import java.lang.reflect.Array;
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("; ");
		j.setEmptyValue("");
		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() {
				@SuppressWarnings("unchecked")
				T t = (T) a.value;
				a = a.succ;
				return t;
			}

			@Override
			public void remove() {
				if (size() == 1) {
					a.value = null;
					a.pred = a;
					a.succ = a;
				} else if (a == anchor) {
					anchor = a.succ;
					a.pred.pred.succ = a;
					a.pred = a.pred.pred;
				} else {
					a.pred.pred.succ = a;
					a.pred = a.pred.pred;
				}
			}

		};
	}

	@SuppressWarnings("unchecked")
	public boolean add(T e) {
		if (e == null) {
			throw new NullPointerException();
		}

		if (isEmpty()) {
			anchor.value = e;
		} else if (contains(e)) {
			return false;
		} else if (((Comparable<T>) e).compareTo((T) anchor.value) < 0) {
			anchor = insertBefore(anchor, e);
		} else {
			Cell current = anchor.succ;
			while (current != anchor && ((Comparable<T>) current.value).compareTo(e) < 0) {
				current = current.succ;
			}
			insertBefore(current, e);
		}
		return true;
	}

	private Cell insertBefore(Cell cell, T e) {
		Cell result = new Cell();
		result.value = e;
		result.pred = cell.pred;
		result.succ = cell;
		cell.pred.succ = result;
		cell.pred = result;
		return result;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		for (T t : c) {
			add(t);
		}
		return true;
	}

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

	@Override
	public boolean contains(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o))
				return true;
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object o : c) {
			if (!contains(o))
				return false;
		}
		return true;
	}

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

	@SuppressWarnings("unchecked")
	@Override
	public boolean remove(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().compareTo((T) o) == 0) {
				i.remove();
				return true;
			}
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		for (Object o : c) {
			if (!remove(o)) {
				return false;
			}
		}
		return true;
	}

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

	@Override
	public int size() {
		if (isEmpty())
			return 0;
		int s = 0;
		Iterator<?> i = iterator();
		while (i.hasNext()) {
			s++;
			i.next();
		}
		return s;
	}

	@Override
	public Object[] toArray() {
		Object[] a = new Object[size()];
		int j = 0;
		Iterator<T> i = iterator();
		while (i.hasNext())
			a[j++] = i.next();
		return a;
	}

	@SuppressWarnings({ "hiding", "unchecked" })
	@Override
	public <T> T[] toArray(T[] a) {
		T[] b = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
		int j = 0;
		Iterator<T> i = (Iterator<T>) iterator();
		while (i.hasNext())
			b[j++] = i.next();
		return b;
	}

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

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

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

	@SuppressWarnings("unchecked")
	@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;
	}
}
```



```
import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class LinkedSetTest {
	LinkedSet<Integer> set = null;

	@BeforeEach
	void setUp() throws Exception {
		set = new LinkedSet<Integer>();
	}

	@AfterEach
	void tearDown() throws Exception {
		set.clear();
		set = null;
	}

	@Test
	void testMain() {
		LinkedSet.main(null);
	}

	@Test
	void testIterToString() {
		testAdd();
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		String s = LinkedSet.iterToString(i);
		assertNotNull(s);
		System.out.println(s);
	}

	@Test
	void testLinkedSet() {
		assertNotNull(set);
	}

	@Test
	void testIterator() {
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		assertFalse(i.hasNext());
		assertTrue(set.add(new Random().nextInt(5)));
		i = set.iterator();
		assertNotNull(i);
		assertTrue(i.hasNext());
	}

	@Test
	void testAdd() {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i = 0; i < 12; i++) {
			l.add(i);
		}
		for (int j = 0; j < 12; j++) {
			set.clear();
			assertTrue(set.isEmpty());
			Collections.shuffle(l);
			for (int i = 0; i < 12; i++) {
				assertTrue(set.add(l.get(i)));
				assertFalse(set.isEmpty());
			}
		}
	}

	@Test
	void testAddAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testClear() {
		set.clear();
		assertTrue(set.isEmpty());
	}

	@Test
	void testContains() {
		assertTrue(set.add(2));
		assertTrue(set.contains(2));
	}

	@Test
	void testContainsAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.containsAll(Arrays.asList(2, 3, 4)));
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testIsEmpty() {
		assertTrue(set.isEmpty());
		assertTrue(set.add(1));
		assertFalse(set.isEmpty());
	}

	@Test
	void testRemove() {
		assertFalse(set.remove(2));
		assertTrue(set.add(2));
		assertTrue(set.remove(2));
		assertFalse(set.remove(3));
	}

	@Test
	void testRemoveAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
		assertTrue(set.removeAll(Arrays.asList(2, 3, 4)));
		assertEquals("", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testRetainAll() {
		fail("Not yet implemented");
	}

	@Test
	void testSize() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals(3, set.size());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testToArray() {
		assertNotNull(set.toArray());
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertNotNull(set.toArray());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testToArrayTArray() {
		assertNotNull(set.toArray(new Integer[0]));
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals(3, set.toArray(new Integer[0]).length);
		assertEquals(Integer[].class, set.toArray(new Integer[0]).getClass());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testComparator() {
		assertTrue(set.comparator() instanceof Comparator<?>);
	}

	@Test
	void testFirst() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals(2, set.first());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testHeadSet() {
		fail("Not yet implemented");
	}

	@Test
	void testLast() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals(4, set.last());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testSubSet() {
		fail("Not yet implemented");
	}

	@Test
	void testTailSet() {
		fail("Not yet implemented");
	}
}
```


----------



## mrBrown (5. Jun 2019)

Tobias-nrw hat gesagt.:


> die Tests werden grün, aber die Methoden removeAll() und iterToString() halten nicht mehr an


Das widerspricht sich doch....


Zu removeAll: wenn das nicht anhält, ist remove(Object o) falsch - und wenn die nicht anhält, ist der iterator falsch. Also würde ich den an deiner Stelle einfach mal gesondert testen.
Gleiches gilt für iterToString.


Abgesehen davon sind da noch einige verstoße gegen das Set-Interface drin, mindestens in removeAll ("fail fast"), first und last (die beide eine Exception schmeißen müssten), und in contains (das sollte compareTo nutzen).



(BTW, setUp und tearDown brauchst du in diesem Fall nicht, kannst das Feld auch direkt initialisieren und aufräumen musst du nichts)


----------



## Xyz1 (5. Jun 2019)

remove() im Iterator ist falsch. Da müssen zusätzliche Fälle bedacht werden, wenn der Anker entfernt werden soll. Das ist mir erst aufgefallen, nachdem ich die Tests umschrieb...

UNd glaub mir, das ist Eclipse... und das kann auch nicht anhalten, wenngleich alle Tests "grün" werden.


----------



## mrBrown (5. Jun 2019)

Tobias-nrw hat gesagt.:


> UNd glaub mir, das ist Eclipse... und das kann auch nicht anhalten, wenngleich alle Tests "grün" werden.


Mindestens der nicht-anhaltende Test sollte nicht grün werden?


Ansonsten die @Timeout dran und gut ist


----------



## Xyz1 (5. Jun 2019)

Geschafft!

```
@Override
            public void remove() {
                if (size() == 1) {
                    a.value = null;
                    a.pred = a;
                    a.succ = a;
                } else {
                    if (a.pred == anchor) {
                        anchor = a;
                    }
                    a.pred.pred.succ = a;
                    a.pred = a.pred.pred;
                }
            }
```



```
import java.lang.reflect.Array;
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("; ");
        j.setEmptyValue("");
        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;
            }

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

            @Override
            public void remove() {
                if (size() == 1) {
                    a.value = null;
                    a.pred = a;
                    a.succ = a;
                } else {
                    if (a.pred == anchor) {
                        anchor = a;
                    }
                    a.pred.pred.succ = a;
                    a.pred = a.pred.pred;
                }
            }
        };
    }

    @SuppressWarnings("unchecked")
    public boolean add(T e) {
        if (e == null) {
            throw new NullPointerException();
        }

        if (isEmpty()) {
            anchor.value = e;
        } else if (contains(e)) {
            return false;
        } else if (((Comparable<T>) e).compareTo((T) anchor.value) < 0) {
            anchor = insertBefore(anchor, e);
        } else {
            Cell current = anchor.succ;
            while (current != anchor && ((Comparable<T>) current.value).compareTo(e) < 0) {
                current = current.succ;
            }
            insertBefore(current, e);
        }
        return true;
    }

    private Cell insertBefore(Cell cell, T e) {
        Cell result = new Cell();
        result.value = e;
        result.pred = cell.pred;
        result.succ = cell;
        cell.pred.succ = result;
        cell.pred = result;
        return result;
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        for (T t : c) {
            add(t);
        }
        return true;
    }

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

    @Override
    public boolean contains(Object o) {
        Iterator<T> i = iterator();
        while (i.hasNext())
            if (i.next().equals(o))
                return true;
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!contains(o))
                return false;
        }
        return true;
    }

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

    @SuppressWarnings("unchecked")
    @Override
    public boolean remove(Object o) {
        Iterator<T> i = iterator();
        while (i.hasNext())
            if (i.next().compareTo((T) o) == 0) {
                i.remove();
                return true;
            }
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        for (Object o : c) {
            if (!remove(o)) {
                return false;
            }
        }
        return true;
    }

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

    @Override
    public int size() {
        if (isEmpty())
            return 0;
        int s = 0;
        Iterator<?> i = iterator();
        while (i.hasNext()) {
            s++;
            i.next();
        }
        return s;
    }

    @Override
    public Object[] toArray() {
        Object[] a = new Object[size()];
        int j = 0;
        Iterator<T> i = iterator();
        while (i.hasNext())
            a[j++] = i.next();
        return a;
    }

    @SuppressWarnings({ "hiding", "unchecked" })
    @Override
    public <T> T[] toArray(T[] a) {
        T[] b = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
        int j = 0;
        Iterator<T> i = (Iterator<T>) iterator();
        while (i.hasNext())
            b[j++] = i.next();
        return b;
    }

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

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

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

    @SuppressWarnings("unchecked")
    @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;
    }
}
```



```
import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class LinkedSetTest {
    LinkedSet<Integer> set = null;

    @BeforeEach
    void setUp() throws Exception {
        set = new LinkedSet<Integer>();
    }

    @AfterEach
    void tearDown() throws Exception {
        set.clear();
        set = null;
    }

    @Test
    void testMain() {
        LinkedSet.main(null);
    }

    @Test
    void testIterToString() {
        testAdd();
        Iterator<Integer> i = set.iterator();
        assertNotNull(i);
        String s = LinkedSet.iterToString(i);
        assertNotNull(s);
        System.out.println(s);
    }

    @Test
    void testLinkedSet() {
        assertNotNull(set);
    }

    @Test
    void testIterator() {
        Iterator<Integer> i = set.iterator();
        assertNotNull(i);
        assertFalse(i.hasNext());
        assertTrue(set.add(new Random().nextInt(5)));
        i = set.iterator();
        assertNotNull(i);
        assertTrue(i.hasNext());
    }

    @Test
    void testAdd() {
        ArrayList<Integer> l = new ArrayList<>();
        for (int i = 0; i < 12; i++) {
            l.add(i);
        }
        for (int j = 0; j < 12; j++) {
            set.clear();
            assertTrue(set.isEmpty());
            Collections.shuffle(l);
            for (int i = 0; i < 12; i++) {
                assertTrue(set.add(l.get(i)));
                assertFalse(set.isEmpty());
            }
        }
    }

    @Test
    void testAddAll() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testClear() {
        set.clear();
        assertTrue(set.isEmpty());
    }

    @Test
    void testContains() {
        assertTrue(set.add(2));
        assertTrue(set.contains(2));
    }

    @Test
    void testContainsAll() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertTrue(set.containsAll(Arrays.asList(2, 3, 4)));
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testIsEmpty() {
        assertTrue(set.isEmpty());
        assertTrue(set.add(1));
        assertFalse(set.isEmpty());
    }

    @Test
    void testRemove() {
        assertFalse(set.remove(2));
        assertTrue(set.add(2));
        assertTrue(set.remove(2));
        assertFalse(set.remove(3));
    }

    @Test
    void testRemoveAll() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
        assertTrue(set.removeAll(Arrays.asList(2, 3, 4)));
        assertEquals("", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testRetainAll() {
        fail("Not yet implemented");
    }

    @Test
    void testSize() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals(3, set.size());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testToArray() {
        assertNotNull(set.toArray());
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertNotNull(set.toArray());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testToArrayTArray() {
        assertNotNull(set.toArray(new Integer[0]));
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals(3, set.toArray(new Integer[0]).length);
        assertEquals(Integer[].class, set.toArray(new Integer[0]).getClass());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testComparator() {
        assertTrue(set.comparator() instanceof Comparator<?>);
    }

    @Test
    void testFirst() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals(2, set.first());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testHeadSet() {
        fail("Not yet implemented");
    }

    @Test
    void testLast() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals(4, set.last());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testSubSet() {
        fail("Not yet implemented");
    }

    @Test
    void testTailSet() {
        fail("Not yet implemented");
    }
}
```


----------



## ocsme (5. Jun 2019)

mrBrown hat gesagt.:


> Zu Anfang ist current=anchor
> hasNext prüft dann, ob es noch einen Nachfolger gibt, next gibt dann aber den aktuellen Wert von current (also im ersten Aufruf anchor) zurück.



Zu Anfang ist current=anchor
hasNext prüft dann, ob es noch einen Nachfolger gibt, next gibt dann aber den aktuellen Wert von current (also im ersten Aufruf anchor) zurück.

 so ein misst vergessen! Danke für die Hilfe 

Dann nehme ich einfach alles von @Tobias-nrw  

LG


----------



## mrBrown (5. Jun 2019)

ocsme hat gesagt.:


> Dann nehme ich einfach alles von @Tobias-nrw


Bitte nicht (und bitte auch nicht meine Variante...)


----------



## mrBrown (5. Jun 2019)

Tobias-nrw hat gesagt.:


> Geschafft!


Naja, "ein paar" Verstöße gegen das Interface gibts aber schon noch


----------



## ocsme (5. Jun 2019)

mrBrown hat gesagt.:


> Bitte nicht (und bitte auch nicht meine Variante...)



Variablen heißen jetzt xXge93nd = a, current = za2g9dna  Besser?  
remove(object o) im Iterator ist also eh Sinnfrei! Doch wenn ich Ihn einbauen würde könnte ich das von mir nehmen oder :O


----------



## mrBrown (5. Jun 2019)

ocsme hat gesagt.:


> Variablen heißen jetzt xXge93nd = a, current = za2g9dna  Besser?


Nop.

Versuchs einfach noch mal selbst, wenn es nur um den Iterator geht, ist das wirklich nicht schwer.



ocsme hat gesagt.:


> remove(object o) im Iterator ist also eh Sinnfrei! Doch wenn ich Ihn einbauen würde könnte ich das von mir nehmen oder :O


Wenn du das wieder einbaust, wird man dir wieder sagen, dass es da nicht hingehört ¯\_(ツ)_/¯

Die Methode hat da einfach nichts zu suchen, die ist dort völlig sinnlos.


----------



## Xyz1 (5. Jun 2019)

Genau dafür _kann_ der Iterator aber auch benutzt werden.


----------



## Xyz1 (5. Jun 2019)

@mrBrown Habe mal folgendes geändert:
1. remove nicht vollständig im Iterator,
2. eigene Methode für remove im LinkedSet,
3. nach wie vor wird bei remove (noch) der Iterator verwendet.


```
import java.lang.reflect.Array;
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("; ");
		j.setEmptyValue("");
		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;
			}

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

			@Override
			public void remove() {
				LinkedSet.this.remove(a.pred);
			}
		};
	}

	@SuppressWarnings("unchecked")
	public boolean add(T e) {
		if (e == null) {
			throw new NullPointerException();
		}

		if (isEmpty()) {
			anchor.value = e;
		} else if (contains(e)) {
			return false;
		} else if (((Comparable<T>) e).compareTo((T) anchor.value) < 0) {
			anchor = insertBefore(anchor, e);
		} else {
			Cell current = anchor.succ;
			while (current != anchor && ((Comparable<T>) current.value).compareTo(e) < 0) {
				current = current.succ;
			}
			insertBefore(current, e);
		}
		return true;
	}

	private Cell insertBefore(Cell cell, T e) {
		Cell result = new Cell();
		result.value = e;
		result.pred = cell.pred;
		result.succ = cell;
		cell.pred.succ = result;
		cell.pred = result;
		return result;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		for (T t : c) {
			add(t);
		}
		return true;
	}

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

	@Override
	public boolean contains(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o))
				return true;
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object o : c) {
			if (!contains(o))
				return false;
		}
		return true;
	}

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

	@SuppressWarnings("unchecked")
	@Override
	public boolean remove(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().compareTo((T) o) == 0) {
				i.remove();
				return true;
			}
		return false;
	}

	private void remove(Cell c) {
		Cell a = c.succ;
		if (size() == 1) {
			a.value = null;
		} else {
			if (a.pred == anchor) {
				anchor = a;
			}
			a.pred.pred.succ = a;
			a.pred = a.pred.pred;
		}
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		boolean b = true;
		for (Object o : c) {
			if (!remove(o)) {
				b = false;
			}
		}
		return b;
	}

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

	@Override
	public int size() {
		if (isEmpty())
			return 0;
		int s = 0;
		Iterator<?> i = iterator();
		while (i.hasNext()) {
			s++;
			i.next();
		}
		return s;
	}

	@Override
	public Object[] toArray() {
		Object[] a = new Object[size()];
		int j = 0;
		Iterator<T> i = iterator();
		while (i.hasNext())
			a[j++] = i.next();
		return a;
	}

	@SuppressWarnings({ "hiding", "unchecked" })
	@Override
	public <T> T[] toArray(T[] a) {
		T[] b = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
		int j = 0;
		Iterator<T> i = (Iterator<T>) iterator();
		while (i.hasNext())
			b[j++] = i.next();
		return b;
	}

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

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

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

	@SuppressWarnings("unchecked")
	@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;
	}
}
```


----------



## mrBrown (5. Jun 2019)

Tobias-nrw hat gesagt.:


> @mrBrown Habe mal folgendes geändert:
> 1. remove nicht vollständig im Iterator,
> 2. eigene Methode für remove im LinkedSet,
> 3. nach wie vor wird bei remove (noch) der Iterator verwendet.


Na da war die vorherige Lösung aber schöner 


Was aktuell nicht nach Doku implementiert ist, sind 

last: muss NoSuchElementException werfen
first: muss NSEE werfen
comparator: muss in diesem Fall null zurückgeben
toArray(T): neues Array darf nur erstellt werden, wenn übergebenes zu klein
contains: muss compareTo nutzen
Iterator#next: muss NSEE werfen
Iterator#remove: muss IllegalStateException werfen
Und halt die nicht implementierten Methoden


----------



## Xyz1 (5. Jun 2019)

Danke für diese Auflistung... ja, die Fehlerbehandlung wurde von mir komplett ignoriert, zudem war ich bei toTArray sehr faul.


----------



## ocsme (5. Jun 2019)

Wenn die Aufgabenstellung so wäre das man einen Iterator mit der Methode remove(Object) Implementieren müsste  wäre dann meine Okay? 

und die anderen Methoden hasNext und Next() könne ich ja auch von dir nehmen okay 
Eine andere Lösung fällt mir dort jetzt nicht ein.

Ich hätte aber noch eine Ähnliche Aufgabe wie diese hier und eine Frage vor ab. Darf ich wenn eine Klasse implements Collection im Iterator die Methoden bentuzen also wie z. B. to Array und isEmpty? Bestimmt oder 

Ich danke euch nochmals ganz Herzlich für euren vielen Beiträgen  super "Daumen Hoch =)"


----------



## mrBrown (5. Jun 2019)

ocsme hat gesagt.:


> Wenn die Aufgabenstellung so wäre das man einen Iterator mit der Methode remove(Object) Implementieren müsste  wäre dann meine Okay?


Keine Ahnung, das müsstest du dann den hypothetische Aufgabensteller fragen 



ocsme hat gesagt.:


> und die anderen Methoden hasNext und Next() könne ich ja auch von dir nehmen okay
> Eine andere Lösung fällt mir dort jetzt nicht ein.


Wenn du die Lösung frei erklären kannst gerne - aber dann wäre es doch sicher auch kein Problem, das selbst zu schreiben 



ocsme hat gesagt.:


> Ich hätte aber noch eine Ähnliche Aufgabe wie diese hier und eine Frage vor ab. Darf ich wenn eine Klasse implements Collection im Iterator die Methoden bentuzen also wie z. B. to Array und isEmpty? Bestimmt oder


Ich würde sagen „ja“


----------



## ocsme (5. Jun 2019)

mrBrown hat gesagt.:


> Keine Ahnung, das müsstest du dann den hypothetische Aufgabensteller fragen


Okay dann lasse ich das raus! Ist ja normalerweise auch nicht drin 



mrBrown hat gesagt.:


> Ich würde sagen „ja“


Das hört sich gut an denn dann könnte man ja auch mit der toArray Methode sich ein Array im Iterator anlegen und über das Iterieren oder wäre das auch wieder FALSCH ??



mrBrown hat gesagt.:


> Wenn du die Lösung frei erklären kannst gerne - aber dann wäre es doch sicher auch kein Problem, das selbst zu schreiben


Ich glaube das ich das nicht kann  dann lasse ich das alles weg  
Danke nochmals 

LG


----------



## Xyz1 (5. Jun 2019)

ocsme hat gesagt.:


> und die anderen Methoden hasNext und Next() könne ich ja auch von dir nehmen okay


Von meiner Seite aus stünde nix dagegen.  Ich kann aber Fehler, trotz der Tests, nicht ganz ausschließen. 




ocsme hat gesagt.:


> Darf ich wenn eine Klasse implements Collection im Iterator die Methoden bentuzen also wie z. B. to Array und isEmpty? Bestimmt oder


Kläre das am besten mit dem hypothetischen Aufgabensteller ab, wenn es nicht schon in der Aufgabe stünde...


----------



## mrBrown (5. Jun 2019)

ocsme hat gesagt.:


> Das hört sich gut an denn dann könnte man ja auch mit der toArray Methode sich ein Array im Iterator anlegen und über das Iterieren oder wäre das auch wieder FALSCH ??


Das wäre zumindest sehr abenteuerlich, aber generell müsste das Möglich sein - dürfte aber mehr Aufwand werden.


----------



## ocsme (7. Jun 2019)

So damit hat sich diese Aufgabe erst einmal Erledigt 

Ich danke ganz Herzlich allen die sich die Mühe gemacht haben und mir so sehr geholfen haben DANKE 
LG


----------

