Iterator für eine geordnete Menge

Bitte aktiviere JavaScript!
Hallo,

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

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

    private class Cell {
        Object value;
        Cell pred, succ;
    }
    private Cell anchor;
        
    public Iterator<T> iterator() {...    }
}
Implementiern Sie die Methode iterator(...). Diese soll einen Iterator<T> zurückgeben, mit dem man die Menge in aufsteigender Reihenfolge durchlaufen kann. Sie brauchen nur die Methoden T next() un dboolen hasNext() zu implementieren.
Meine Idee zu dieser Aufgabe war folgende:
Java:
public class LinkedSet<T extends Comparable<T>> implements SortedSet<T>{

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

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

        @Override
        public T next() {
            // TODO Auto-generated method stub
            return Cell.first();
        }
        
    }
    
    @Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }
}
Natürlich funktioniert das ganze so nicht :D bekomme es nicht mal übersetzt!
Doch denke man sieht die Idee dahinter.

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

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

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

Java:
        @Override
        public T next() {
            if (hasNext()) {
                current = current != null ? current=current.succ : anchor;
                return current.value;
            }
            
            throw new IllegalStateException("No more elements");
        }
Zumindest liess sich das bei mir übersetzen. Und wie man sieht: anchor ist direkt verfügbar.
 
Also so komme ich natürlich an die Datenelemente von Cell doch die sind dann ja null :D
Java:
@Override
        public boolean hasNext() {
            return new LinkedSet().new Cell().value != LinkedSet.this.anchor;
        }
Zumindest liess sich das bei mir übersetzen. Und wie man sieht: anchor ist direkt verfügbar.
Was ist bei dir Current? ich hab das in den Iterator eingefügt und alles ist rot :D

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

Also die Aufgabe ist ja mal mega Schrott :(

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

LG
 
Ja nur wenn du Cell current in die Iterator-Klasse als Datenelement schreibst hat es den Wert null.
Das bringt doch nichts.
Denn du fragst im bedingten Operator ob current != null ist das wird nie true werden!
Du musst current im Konstruktor des Iterators noch initialisieren ;)

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

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

Du musst current im Konstruktor des Iterators noch initialisieren ;)
Nein, das muss nicht erfolgen, denn null als Initialisierung schien mir null prinzipiell gut genug zu sein.

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

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

Initialisierung vermeiden halt den Check auf null
 
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?
 
Mal ein paar Dinge hervorheben:
Die Klasse LinkedSet repräsentiere geordnete Mengen als doppelt verkettete Ringlisten mit einer Anker-Zelle, die uach bei leeren Listen vorhanden ist.
1. Die Ordnung wird über Comparable definiert.
2. Es existiert eine Zelle, die nicht null ist, die Ankerzelle
3. Die Liste ist ein Ring.
4. Es ist nicht gesagt, dass die Ankerzelle das kleinste Element darstellt
 
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.
 
Die Frage ist aber doch, auf was Du current setzt und wie Du hasNext setzt...

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

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


4. Es ist nicht gesagt, dass die Ankerzelle das kleinste Element darstellt
Es ist auch nicht gesagt, dass der Anker einen Wert hat, oder überseh ich das?
 
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...
 
Ich verstehe "auch bei leeren Listen vorhanden" so, dass bei einer leeren Liste anchor != null gilt und dem entsprechend anchor.value == null gelten muss.

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

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

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

Denke wir sind uns über diese Methode einig das sollte Korrekt sein:
Java:
    @Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }
Meine LinkedSetIterator Klasse sieht nun so aus:
Java:
class LinkedSetIterator implements Iterator<T> {
        Cell current;
        LinkedSetIterator() {
            Cell current = anchor;
        }
        
        @Override
        public boolean hasNext() {
            return current.succ != LinkedSet.this.anchor;
        }

         public T next() {
                if (hasNext()) {
                    current = current != null ? current=current.succ : anchor;
                    return (T) current.value;
                }
                throw new IllegalStateException("No more elements");
            }
        
    }
Nun Frage ich mich ob T next() überhaupt Korrekt ist? Denn current = anchor das bedeutet ist der anchor != null setzt er current auf succ und andernfalls auf den anchor. Das bedeutet ich verliere meinen anchor oder etwa nicht und ich laufe im Kreis.

bei hasNext() gibt es auch keinen Sinn mehr.

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

LG
 
Denn current = anchor das bedeutet ist der anchor != null setzt er current auf succ und andernfalls auf den anchor.
anchor != null gilt immer ;)

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.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben