extend LinkedList für Matrosenkiller ;-)

[guni]

Hallo,

vielleicht kennt ihr die Aufgabe:
wir stellen eine beliebige Matrosenanzahl m im Kreis auf und definieren eine Schrittweite n.
vom ersten Matrosen wegzählend lassen wir jeden n-ten Matrosen über Bord springen und wiederholen das Ganze so lange, bis nur mehr ein Matrose überbleibt.
Wenn die Anzahl der Matrosen kleiner der Schrittweite n ist, so wird nach dem ersten Durchgang durch den Kreis einfach weitergezählt.

Falls es wen interessiert, der kann es gern nachprogrammieren. Und nein - ich brauch das nicht für Schule oder Uni - das ist nur interessensmäßig.

Na ja - meine Frage ist eigentlich eh Problemunabhängig:

die Matrosen will ich in einer LinkedList speichern.
jetzt will ich noch meinen Iterator überschreiben und einen CircularIterator erstellen.
Seine Methoden müssen wie folgt überschrieben werden:

next() - wenn (ende_der_Linked_List_erreicht) dann next = first
hasNext() - false wenn listsize = 1

meine Frage ist:
wenn ich den Iterator extende, wie sag ich dann in der next(), dass das nächste Element einer LinkedList gewählt werden soll. Der Iterator ist doch eigentlich unabhängig von dem Objekt, dass er durchläuft, oder? woher weiß er denn, dass er eine LinkedList durchlaufen soll?!

lg, guni

 

[0x7F800000]

wenn ich den Iterator extende, wie sag ich dann in der next(), dass das nächste Element einer LinkedList gewählt werden soll. Der Iterator ist doch eigentlich unabhängig von dem Objekt, dass er durchläuft, oder? woher weiß er denn, dass er eine LinkedList durchlaufen soll?!

Iteratoren sind afaik als innere member-klassen definiert, und werden in den collections bei der Nachfrage mit .iterator() erzeugt, sie haben zugriff auf praktisch alle "innereien" d.h. member-avriablen der jeweiligen collection.
extenden? Wäre imho eher problematisch, wer soll denn so einen Iterator dann instantiieren? LinkedList lässt sich dazu nicht direkt überreden, dann müsstest du die auch noch überschreiben.
Wrappen erscheint mir da schon einfacher.

Auf die aufgabe bezogen: wäre ein boolean array da nicht irgendwie billiger?

 

[guni]

Auf die aufgabe bezogen: wäre ein boolean array da nicht irgendwie billiger?

ja. billiger wärs schon, aber nicht so schön, oder?
wenn ich eine List mit einem CircledIterator durchlaufe und dann einfach solange entferne bis nur mehr ein Element überbleibt, dann ist mein Algorithmus viel näher am "echten Leben" / eigentlich am "echten Sterben" der Matrosen dran ;-)

mich hätten ja weniger ein komplexe Algorithmen sondern mehr die Möglichkeiten von Java interessiert!

 

[0x7F800000]

mich hätten ja weniger ein komplexe Algorithmen sondern mehr die Möglichkeiten von Java interessiert!

nunja, hier wirft Java einem zum Glück keinerlei unnötige Stolpersteine unter die Füße:
[highlight=Java]
import java.util.*;

class _{

public static <T> Iterator<T> createCircularIterator(final Collection<T> c){
return new Iterator<T>(){
private Collection<T> collection;
private Iterator<T> wrappedIterator;
{
collection=c;
wrappedIterator=collection.iterator();
}
@Override
public boolean hasNext() {
return collection.size()>0;
}
@Override
public T next() {
if(!wrappedIterator.hasNext()){
wrappedIterator=collection.iterator();
}
return wrappedIterator.next();
}
@Override
public void remove() {
wrappedIterator.remove();
}
};
}

public static void main(String[] args){
LinkedList<String> matrosen=new LinkedList<String>();
matrosen.add("Pedro");
matrosen.add("Diogo");
matrosen.add("Antonio");
matrosen.add("Christoph");

int step=3;

System.out.println("Matrosen: "+matrosen+" Schritt:"+step);
for(Iterator<String> it=createCircularIterator(matrosen); it.hasNext(); ){
String name="";
for(int i=0; i<step; i++){
name=it.next();
}
System.out.println(name);
it.remove();
}
}
}
[/highlight]
so akzeptabel?

 

[guni]

ja. das ist genau was ich meine.
allerdings versteh ich den code leider nur zu 70%.
ach ja: wie kann ich in diesem Forum eigentlich Code als Code kennzeichnen?

lg, guni

 

[0x7F800000]

ja. das ist genau was ich meine.
allerdings versteh ich den code leider nur zu 70%.

Stress mit inneren und lokalen Klassen (oder wie sie da alle heißen...)? Ja, kann etwas ungewohnt erscheinen. Ich mag die schreibweise jedenfalls... Oder welche 30% genau sind denn unklar, vielleicht kann ich ja noch was sinnvolles dazu sagen...

ach ja: wie kann ich in diesem Forum eigentlich Code als Code kennzeichnen?

[noparse][HIGHLIGHT=Java][/noparse]/*der code*/[noparse][/HIGHLIGHT][/noparse]
Beim WYSIWYG-editor (im Kontrollzentrum einstellbar (Kontrollzentrum ist oben links verlinkt)) einfach auf die Java-Tasse klicken.

 

[guni]

[highlight=Java]public static <T> Iterator<T> createCircularIterator(final Collection<T> c){[/highlight]
- eine Factory-Methode, oder?!
- aber wieso steht hier 2 mal <T>???

[highlight=Java]return new Iterator<T>(){[/highlight]
- eine anonyme Klasse, oder?!

... dann wären das hier
[highlight=Java]private Collection<T> collection;
private Iterator<T> wrappedIterator;[/highlight]
die Attribute ...

... und das hier ...
[highlight=Java]
{
collection=c;
wrappedIterator=collection.iterator();
}
[/highlight]
... der Konstruktor, oder?
... ich habe diese Schreibweise eines Konstruktors noch nie gesehen!
... wieso kennt dieser Codeblock meine Variable c??

... ja. soweit mein unverständnis. der rest is eigentlich eh klar.
ach ja - und gibt es vielleicht eine schönere Möglichkeit als 2 Schleifen ineinander?
ich hätte das Ganze so, dass der Kreis immer um step "weitergedreht wird", bis und nach jedem mal drehen dann einfach der erste springt (stellen wir uns vor, die Matrosen stehen im Kreis und drehen sich solang, bis der nächstgereihte wieder am sprungbrett ins meer steht ;-)

lg, guni

 

[0x7F800000]

- eine Factory-Methode, oder?!

hmm, jain... Diese Methode construiert und gibt zwar irgendein Objekt zurück, aber ich wüsste nicht, wieso man das als "factory methode" bezeichnen sollte. Factory-Pattern ist was größeres, da gehören mehrere Interfaces und mehrere Klassen dazu, daher stiftet imho der Begriff "factory methode" in diesem Zusammenhang nur verwirrung.

- aber wieso steht hier 2 mal <T>

3 Mal...
Das erste <T> gibt an, dass die methode generisch ist, hier kommen normalerweise einschränkungen an T rein (in diesem Fall gibt es keine)
Das zweite <T> hängt am Rückgabetyp (könnte ja auch ein Iterator<List<T>> sein oder sonstwas)
Das dritte <T> gibt den Typ des Argumenten an, klar...

- eine anonyme Klasse, oder?!

So nennt man die Dinger glaube ich, ja.

... dann wären das hier [..] die Attribute ...
... und das hier [..] der Konstruktor, oder?

Ja, im wesentlichen richtig. Um das etwas feiner zu differenzieren nennt man das Ding "Exemplarinitialisierer" Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 6.6 Klassen- und Objektinitialisierung

... ich habe diese Schreibweise eines Konstruktors noch nie gesehen!

Jetzt hast du sie gesehen, war doch nicht so schlimm, oder?
Habe diese schreibweise eigentlich auch relativ vor kurzem entdeckt, seitdem benutze ich anonyme innere klassen wesentlich lieber

... wieso kennt dieser Codeblock meine Variable c??

bemerke dass c als final deklariert ist. Auf final-variablen darf ich in solchen anonymen inneren klassen zugreifen. Wieso das so sein muss... ähm... es muss wohl irgendwas damit zu tun haben, wie eine solche klasse beim kompiliervorgang herausgetrennt und als normale klasse umgeschrieben wird. Was da der compiler genau macht weiß ich nicht, aber um das tun zu dürfen benötigt er jedenfalls "final". Öhm, ja...

ach ja - und gibt es vielleicht eine schönere Möglichkeit als 2 Schleifen ineinander?
ich hätte das Ganze so, dass der Kreis immer um step "weitergedreht wird", bis und nach jedem mal drehen dann einfach der erste springt

Genau das tut das programm doch. Weiterdrehen ist die innere schleife, springen ist das "remove", und das ganze wird wiederholt bis alle baden gegangen sind, das ist die äußere schleife.
Wenn du an deinen Iterator so einer art "skip(n)"-methode drankleben willst, dann musst du eine neue nicht anonyme klasse anlegen, weil die anonyme klassen das interface nach außen nicht verändern können, d.h. sie können keine zusätzliche öffentliche methoden zur verfügung stellen.

 

[Landei]

Zu dem Problem gibt es jede Menge Links, wenn man den richtigen Namen kennt: Josephus problem - Wikipedia, the free encyclopedia

 

[guni]

Zu dem Problem gibt es jede Menge Links, wenn man den richtigen Namen kennt: Josephus problem - Wikipedia, the free encyclopedia

ahh - danke.
wenn man die Legende dazu kennt, dann ist das gleich nochmal interessanter ...

lg, guni

PS.: vor allem weil mir Flavius Josephus mir aus biblischem Zusammenhang bekannt ist ...