Die Realisierung orientiert sich eng an der Aufgabenformulierung, d.h. die Funktionalität ist auf die geforderten Eigenschaften beschränkt:
Das Applet kennt grundsätzlich zwei Betriebsmodi:
Verschieben:
Knoten hinzu:
Der Grundmodus ist Verschieben.
Verwendete Strukturen/Algorithmen:
(werfen Sie auch einen Blick auf den kommentierten Quellcode)
Das Applet realisiert einen endlichen Automaten, der 2 Zustände einnehmen kann: "Verschieben" und "Knoten hinzufügen" (Variable modus).
Die zugrundeliegende Datenstruktur besteht aus 2 Feldern, dem Knotenfeld und dem Verbindungsfeld. Im Knotenfeld existiert fuer jeden Knoten eine Instanz von class _Knoten {int x, int y, boolean Markiert, int nummer}. Diese Basisklasse enthält keine eigenen Methoden, da beim Entfernen von Verbindungen (siehe unten) Knoten-Methoden aufgerufen werden müssen. Aufgrund der niedrigen Komplexität des Gesamtprogramms wurden die Knotenmethoden als Methoden des Applets deklariert (prozedurale Programmierung), anstatt entwicklungsaufwendige Zugriffsmechanismen zu entwickeln.
Das Knotenfeld kann also als einfaches Array vom typ _Knoten bezeichnet werden.
Die Verbindungen (Kanten) werden im Verbindungsfeld verwaltet. Der Basistyp ist class _Verbindung { int von, int nach }. In den beiden Datenfeldern wird jeweils ein Start- und eine Endknoten eingetragen, jede Verbindung zwischen zwei Knoten befindet sich nur einmal im Feld.
Beide Felder sind einfache lineare Arrays, bei denen beginnend mit Index 0 num_knoten bzw. num_verb Felder belegt sind, alle restlichen Felder sind null. Um beim Löschen eines Arrayelements die Liste "sauber", d.h. lückenfrei zu halten, wird folgender 3-Zeiler verwendet:
// Löschen eines Feldes mitten im Array an Position i. // num enthält die absolute Anzahl an belegten Feldern, // das Array selbst hat eine Indexierung ab [0]. feld[i] = feld[num-1]; // letztes Element an Position i kopieren feld[num-1] = null; num--;
Beim Löschen von Verbindungen müssen die Knotenindices bei den verschobenen Feldelementen korrigiert werden. Darauf hatten wir anfangs verzichtet, und brauchten dann peinlich lange um den Algorithmen-Fehler zu finden. Die Korrektur geschieht mittels Knoten_refreshen(...) - dieser Methode wird die Positionsangabe i sowie num-- übergeben. Die Methode geht alle Verbinungen durch und ändert alle Verweise auf Knoten[num--] um in Verweise auf Knoten[i], denn der letzte Knoten der Liste wurde an Position [i] verschoben.
Optimierte Grafikausgabe: Zu Anfangs hatten wir bei jeder Grafikänderung das Bild mit der Methode paint() im sichtbaren Bereich komplett immer neu aufgebaut. Es flimmerte katastrofal, und eine Optimierung mußte her.
Ein gängiges Prinzip der Grafik-Optimierung besteht darin, das Neuzeichnen im Hintergrund (unsichtbar) durchzuführen, was schneller geht als der Aufbau im sichtbaren Bereich, und dann den neugezeichneten Bereich komplett als Ganzes in den sichtbaren Bereich zu kopieren. Dies geht systemintern meist über optimierte Prozeduren, die immer schneller sind als ein Aufbau im sichtbaren Bereich.
Der Neuaufbau findet statt in offscreen, einer Instanz von Image. Wie das im Einzelnen funktioniert schaut man am besten im Quellcode nach - kompliziert ist es nicht! Suchen Sie nach der Methode public void offpaint().
Diese Optimierung reichte jedoch nicht aus. Wenn man einen Knoten verschob, folgte der Knoten dem Mauszeiger wie ein verspielter tapsiger Welpe. Das sah ganz lustig aus, verfehlte aber etwas das Ziel der Aufgabe. Also fügten wir eine Methode hinzu, die auch in einen nicht-sichtbaren Bereich zeichnet, dann aber nur einen kleinen Bereich (nur den, in dem es vermutlich Änderungen gab) in den sichtbaren Bereich kopiert. Die zugehörige Methode ist offpaint_clip(), sie läßt sicher noch Platz für Optimierungen (der Geschwindigkeitsvorteil hält sich momentan erstaunlicherweise in Grenzen :-)).
Copyright 1997,1998 by Tjabo Kloppenburg and
Thomas Börngen.
This page and this applet may be copied for non commercial proposes only.