Christian H. Kuhn
2019-08-21 10:57:24 UTC
Liebe Gemeinde,
ich hab es auf stackoverflow probiert, aber kaum kommt mal ein
wirkliches Problem, kann da auch niemand helfen ...
Implementation eines generischen Dijkstra zur Lösung von beliebigen
Spielen. Randbedingung: Kantengewichte alle 1, Kanten implizit definiert
über die Spielregeln.
Kern sind die Spielpositionen und die in ihnen möglichen Spielzüge. Die
muss der Programmierer des Spiels durch Implementierung dieses
Interfaces bereitstellen:
public interface LSElement<T> {
List<T> findLegalMoves();
LSElement<T> executeMove(T move);
}
T ist der Typ des Spielzugs. Bei Münzwürfen Boolean, bei einem Würfel
Integer, bei mehreren Würfeln List<Integer>, bei Kartenspielen eine
Karte, eine Folge von Karten, ... Ich könnte Object nehmen, dann
bräuchte ich keine generische Typisierung. Dafür müsste beim
Implementieren des Interfaces ein Hin- und Hergecaste stattfinden.
Fehleranfällig, erfordert Checks, was den Code aufbläht, und kommt mir
ganz allgemein nicht so effizient vor. Mit Generics alles schön
übersichtlich und bis hierhin unproblematisch.
Damit kann man noch keinen Dijkstra machen. Als wird LSElement<T> in
LSNote<LSElement<?>> verpackt. Vorgänger, Entfernung vom Startknoten und
andere, evtl. implementierungsabhängige Daten werden hinzugefügt. Kern
ist natürlich ein Feld vom Typ LSElement<?>. Details sind für mein
Problem unerheblich, aber man sieht an der unbounded wildcard, wohin das
geht.
LSGraph<E extends LSElement<?>> schließlich stellt Datenstruktur und
Methoden für den Dijkstra-Algorithmus bereit. Eine
PriorityQueue<LSNode<LSElement<?>>>, die nach Distanz sortiert. Ein
HashSet<LSElement<?>>, in dem die während des Algorithmus erzeugten
LSElements<> gespeichert werden. Und natürlich
public void findShortestPath(final LSNode<E> startNode, final LSNode<E>
destNode) {}
wo der eigentliche Dijkstra abläuft.
Wenn ein Knoten besucht wird, werden zunächst die Nachbarknoten
berechnet, und hier laufe ich in Probleme.
final List<?> moves = actNode.getElement().findLegalMoves();
Ich kann wegen der unbounded wildcard nicht über moves iterieren. Kurzes
Googlen fand die Methodik des wildcard capture über eine private
Hilfsmethode.
fspHelper(moves, actNode);
und außerhalb dann
private <M> void fspHelper(final List<M> moves, final LSNode<E>
actNode) {
for (final M move : moves) {
}
}
Das klappt, ich kann jetzt über die Spielzüge iterieren. Nun möchte ich
für jeden Zug die Folgeposition berechnen. Und das funktioniert nicht.
So sollte es innerhalb der for-Schleife aussehen:
final LSNode<E> newNode = new
LSNode<>(actNode.getElement().executeMove(move));
Der Compiler widerspricht aber:
The method executeMove(capture#3-of ?) in the type
LSElement<capture#3-of ?> is not applicable for the arguments (M)
Und das verstehe ich nicht. Der Typ T in LSElements<T> ist unbeschränkt
und übersetzt sich zu T extends Object. Und was immer M sein mag, es ist
ein Subtyp von Object und sollte da hineinpassen. Wenn es das nicht tut,
machen Generics irgendetwas, was ich noch nicht verstanden habe. Kann
mir jemand a) eine Erklärung b) eine Lösung geben?
Natürlich käme ich drum herum, wenn ich LSGraph als LSGraph<M,
LSElement<M>> deklarierte. Meiner Ansicht nach wird dadurch aber das
Prinzip der Kapselung verletzt. Niemand außer dem Implementor von
LSElement<T> sollte darüber nachdenken müssen, von welchem Typ ein
Spielzug ist. Oder indem ich LSElement wie oben erwähnt nicht typisiere
und auf Object als Spielzugtyp ausweiche. Das möchte ich aber nach
Möglichkeit erst machen, wenn ich begriffen habe, warum der oben
beschriebene Weg nicht funktioniert.
TIA
QNo
ich hab es auf stackoverflow probiert, aber kaum kommt mal ein
wirkliches Problem, kann da auch niemand helfen ...
Implementation eines generischen Dijkstra zur Lösung von beliebigen
Spielen. Randbedingung: Kantengewichte alle 1, Kanten implizit definiert
über die Spielregeln.
Kern sind die Spielpositionen und die in ihnen möglichen Spielzüge. Die
muss der Programmierer des Spiels durch Implementierung dieses
Interfaces bereitstellen:
public interface LSElement<T> {
List<T> findLegalMoves();
LSElement<T> executeMove(T move);
}
T ist der Typ des Spielzugs. Bei Münzwürfen Boolean, bei einem Würfel
Integer, bei mehreren Würfeln List<Integer>, bei Kartenspielen eine
Karte, eine Folge von Karten, ... Ich könnte Object nehmen, dann
bräuchte ich keine generische Typisierung. Dafür müsste beim
Implementieren des Interfaces ein Hin- und Hergecaste stattfinden.
Fehleranfällig, erfordert Checks, was den Code aufbläht, und kommt mir
ganz allgemein nicht so effizient vor. Mit Generics alles schön
übersichtlich und bis hierhin unproblematisch.
Damit kann man noch keinen Dijkstra machen. Als wird LSElement<T> in
LSNote<LSElement<?>> verpackt. Vorgänger, Entfernung vom Startknoten und
andere, evtl. implementierungsabhängige Daten werden hinzugefügt. Kern
ist natürlich ein Feld vom Typ LSElement<?>. Details sind für mein
Problem unerheblich, aber man sieht an der unbounded wildcard, wohin das
geht.
LSGraph<E extends LSElement<?>> schließlich stellt Datenstruktur und
Methoden für den Dijkstra-Algorithmus bereit. Eine
PriorityQueue<LSNode<LSElement<?>>>, die nach Distanz sortiert. Ein
HashSet<LSElement<?>>, in dem die während des Algorithmus erzeugten
LSElements<> gespeichert werden. Und natürlich
public void findShortestPath(final LSNode<E> startNode, final LSNode<E>
destNode) {}
wo der eigentliche Dijkstra abläuft.
Wenn ein Knoten besucht wird, werden zunächst die Nachbarknoten
berechnet, und hier laufe ich in Probleme.
final List<?> moves = actNode.getElement().findLegalMoves();
Ich kann wegen der unbounded wildcard nicht über moves iterieren. Kurzes
Googlen fand die Methodik des wildcard capture über eine private
Hilfsmethode.
fspHelper(moves, actNode);
und außerhalb dann
private <M> void fspHelper(final List<M> moves, final LSNode<E>
actNode) {
for (final M move : moves) {
}
}
Das klappt, ich kann jetzt über die Spielzüge iterieren. Nun möchte ich
für jeden Zug die Folgeposition berechnen. Und das funktioniert nicht.
So sollte es innerhalb der for-Schleife aussehen:
final LSNode<E> newNode = new
LSNode<>(actNode.getElement().executeMove(move));
Der Compiler widerspricht aber:
The method executeMove(capture#3-of ?) in the type
LSElement<capture#3-of ?> is not applicable for the arguments (M)
Und das verstehe ich nicht. Der Typ T in LSElements<T> ist unbeschränkt
und übersetzt sich zu T extends Object. Und was immer M sein mag, es ist
ein Subtyp von Object und sollte da hineinpassen. Wenn es das nicht tut,
machen Generics irgendetwas, was ich noch nicht verstanden habe. Kann
mir jemand a) eine Erklärung b) eine Lösung geben?
Natürlich käme ich drum herum, wenn ich LSGraph als LSGraph<M,
LSElement<M>> deklarierte. Meiner Ansicht nach wird dadurch aber das
Prinzip der Kapselung verletzt. Niemand außer dem Implementor von
LSElement<T> sollte darüber nachdenken müssen, von welchem Typ ein
Spielzug ist. Oder indem ich LSElement wie oben erwähnt nicht typisiere
und auf Object als Spielzugtyp ausweiche. Das möchte ich aber nach
Möglichkeit erst machen, wenn ich begriffen habe, warum der oben
beschriebene Weg nicht funktioniert.
TIA
QNo