Which Blog System?

For several years I’ve been running my own Blog software – but as I wanted to have more and more features, I realized that adding these features wasn’t justified any more, so I shopped around for other solutions. The winner is Serendipity.

Düsseldorf Java User Group geplant

Sowohl in San Francisco als auch in Boston und Philadelphia bin ich oft zu den Treffen der lokalen Java User Groups (JUGs) gegangen – es hat Spass gemacht, sich mit den Kollegen zu unterhalten, und die Vorträge waren oft hochinteressant.

Leider gibt es in Düsseldorf keine aktive JUG. Ich möchte versuchen, das zu ändern. Ab Ende Oktober werde ich beginnen, intensiv Mitglieder zu rekrutieren, um Anfang 2006 das erste Treffen veranstalten zu könnnen.

Falls Sie Interesse haben, daran mitzuwirken – als Mitglied, Vortragender oder Organisator – schicken Sie mir bitte ein Email und melden sich bei der Email-Liste an unter [email protected] . Die JUG Webseite finden Sie unter

http://www.smartgroups.com/groups/d-jug

Und zuletzt: Ich würde mich sehr freuen, wenn Sie dieses Email an alle Java-Interessierten im Raum Düsseldorf weiterschicken würden. Vielen Dank!

Maven: Einführung und Tutorial

Geschichte

Maven entstand, weil Java-Projekte, die lose zusammengehörten, untereinander nicht “kompatibel” waren. Jedes Projekt hatte sein eigenes Ant Skript (das meistens auch mehr oder weniger die selben Tasks ausführte), aber dennoch unterschiedlich aufgebaut war. Hinzu kam, dass Depenencies (meistens JAR Dateien) einfach über das Source Repository verwaltet wurden – zwar sehr effektiv und zuverlässig, aber das machte es problematisch für Projekte, Dependencies zu teilen (und eines der Grundprinzipien in der Softwareentwicklung ist DRY: Don’t Repeat Yourself!). Maven wurde entwickelt, einen Standard für die Java Softwareentwicklung zu setzen, Kollaboration einfach zu machen, und gute Praktiken zu fördern.

Aufbau

Hinweis: Ich beschreibe hier Maven Version 1.x. Version 2 ist momentan in Alpha und wird sich in vielerlei Hinsicht erheblich von 1.x unterscheiden!

Im folgenden werde ich parallelen zu Ant ziehen, wenn das sinnvoll ist. In Ant wird der Buildprozess von build.xml gesteuert. Mit Maven sind es drei Dateien, die man kennen muss:

  • project.xml – das Herzstück für ein Maven-Buildsystem. Diese Datei beschreibt Quellcode, Entwicklungsumgebung, benötigte Resourcen (JARs, Plugins), Mailinglisten, Sourcecode Repository, und alle anderen Elemente die zu einem gesunden Softwareprojekt gehören. Diese Datei wird oft mit POM (Project Object Model) bezeichnet.
  • project.properties – optional, aber eigentlich immer erforderlich. Hier werden Aspekte des Projektes konfiguriert, zum Beispiel die JVM Version.
  • maven.xml – Wenn der Rahmen, den Maven vorgibt, nicht flexibel genug ist, können Skripte über diese Datei in das Buildsystem eingeklingt werden – zum Beispiel die Generierung von Artifakten mit XDoclet.

Maven hat eine Plugin Struktur. Viele Plugins werden mit Maven mitgeliefert, aber es gibt auch viele zusätzliche Plugins. Diese müssen nicht installiert werden – wie JARs, werden diese in project.xml definiert und von Maven automatisch heruntergeladen.

Repository

Was habe ich gerade gesagt? Automatisch heruntergeladen?!? Das ist eine der Stärken von Maven. Alle extern benötigten Resourcen brauchen nicht von Hand installiert zu werden. Statt dessen werden diese in build.xml beschrieben zum Beispiel folgendermaßen:

 <dependency> <groupId>log4j</groupId> <artifactId>log4j</artifactId> <version>1.2.8</version> </dependency> 

In diesem Beispiel wird das Artifakt “log4j” im Projekt log4j heruntergeladen, Version 1.2.8. Maven sucht die Resourcen unter

http://ibiblio.org/maven/

Die heruntergeladenen Resourcen werden projektunabhängig auf der Workstation des Benutzers gespeichert, unter

$HOME/.maven/repository

Beispielprojekt

Genug Theorie - wie sieht das ganze in der Praxis aus? Ein neues Projekt mit Maven zu erstellen ist sehr einfach. Einfacher, als ein besehendes Projekt zu Maven zu migrieren, aber dazu später mehr. Ich gehe davon aus, dass Maven installiert ist, und wir uns in einem leeren Verzeichnis befinden, wo unser neues Maven-Projekt entstehen wird. Dort führen wir den folgenden Befehl aus:

$ maven genapp

"genapp" erzeugt ein leeres Maven-Projekt. Dieser Befehl ist interaktiv:

 __  __ |  \/  |__ _Apache__ ___ | |\/| / _` \ V / -_) ' \  ~ intelligent projects ~ |_|  |_\__,_|\_/\___|_||_|  v. 1.0.2 Enter a project template to use: [default] Please specify an id for your application:  [app] maven-beispiel Please specify a name for your application:  [Example Application] Maven Beispiel Please specify the package for your application:  [example.app] de.jastram.mavenbeispiel build:start: genapp: ... BUILD SUCCESSFUL Total time: 1 minutes 32 seconds Finished at: Mon Jun 06 14:43:41 EDT 2005 

Wenn wir uns jetzt das Verzeichnis anschauen, werden wir feststellen, dass 10 Unterverzeichnisse und 7 Dateien erzeugt wurden, und ich lege dem Leser ans Herz, diese Verzeichnisstruktur zu untersuchen. Unter anderem wurde ein Einstiegspunkt in die Anwenung und ein paar JUnit-Tests erzeugt.

Um einen besseren Überblick zu bekommen, Erzeugen wir HTML-Dokumentation für unser Projekt:

$ maven site

Es kann eine Weile dauern, bis Maven damit fertig ist. Alle erzeugten Objekte sind unter target zu finden, und die Dokumentation ist unter target/docs - auf jeden Fall clicken und ausprobieren!

Auf jeden Fall auch das Untermenü "Project Reports" erkunden - dort kann der Sourcecode gebrowst werden, Unit Test Ergebnisse untersucht werden, JavaDoc ist verfügbar, und vieles mehr.

Dokumentation

Beeindruckend, was Maven für uns macht. Aber die Optionen und Möglichkeiten sind so vielfältig, dass es anfangs schwierig ist, sich zurechtzufinden. Zum Beispiel, wo kommen die Argumente "genapp" und "site" her, so sind sie dokumentiert?

Zunächst: das Argument ist gar nicht "site", sondern site:site. Aber das Default-Goal (Goal ist das Maven equivalent zu Ant's Target) für das Plugin "site" heißt "site".

Alle Plugins sind auf der Maven Website dokumentiert, und die Dokumentation der Plugins enthält eine Liste der Goals. Außerdem sind dort auch Properties beschrieben, die in build.properties untergebracht werden können. Das site plugin, zum Beispiel, führt eine Reihe von Properties aus, die es erlauben, die Projektseiten per FTP auf einen Webserver hochzuladen (per site:deploy Goal).

Weiterhin lohnt es sich, die Dokumentation für build.xml, den Project Descriptor, durchzulesen.

Und noch ein wichtiger Hinweis: Maven benutzt nicht Ant, sondern Jelly als Skript-Sprache. Allerdings ist es nicht schwierig, per Jelly Ant-Skripte auszuführen.

IDE-Integration

Maven hat Goals um Projektdateien für IDEs zu generieren. Zum Beispiel erstellt der folgende Befehl ein Eclipse-Projekt:

$ maven eclipse

Love and Hate

Ein eindrucksvolles Werkzeug - warum gibt es doch eine Reihe von Leuten, die Maven hassen? Diskussionen zum Thema gibt es genug, aber hier sind meine Gedanken und Kommentare in der Hoffung, die Frustration mit Maven zu minimieren:

  • Maven ist noch nicht stabil - es hat lange gedauert, bis sich Version 1 stabilisiert hatte, und im Moment werden viele Fehler in Version 2 korrigiert - aber 2 ist auch noch im Alpha-Stadium. Wenn viele Änderungen zur Frustration fürhen können, rate ich von Maven ab.
  • Anfangs weniger Einfluß auf die Projektstruktur - Maven gibt eine gute Projektstruktur vor, aber die gefällt bestimmt nicht jedem. Die kann zwar geändert werden, aber man muss sich schon eine Weile mit Maven beschäftigen, um das ohne Frustration tun zu können. Ant ist wesentlich einfacher den eigenen Bedürfnissen anzupassen. Aber die Maven Projektstruktur besteht aus einem guten Grund - viele schlaue Leute haben sich viele Gedanken darüber gemacht. Natürlich ist es akzeptabel von dieser Struktur abzuweichen, aber ich würde mir bei jeder Änderung gut überlegen, ob die Änderung die Projektstruktur wirklich verbessert.
  • Migration von Altanwendungen lohnt sich oft nicht - ein bestehendes Projekt mit einem gut dokumentierten, funktionierendem Ant-Skript sollte nur dann zu Maven überführt werden, wenn es wirklich einen guten Grund gibt. Durch die eigenwillige Projektstruktur und die nicht elegante Ant Integrierung kann auch das zur Frustration führen. Aber zum Beispiel die Integration mit anderen Maven-Projekten wäre ein guter Grund.

Der verflixte Primary Key

Na ja, eigentlich ist das Thema kein Java Thema – aber hier werde ich Ansätze diskutieren, die Java benutzen.

Warum wollen wir überhaupt verschiedene Datenbanken unterstützen – warum legen wir uns nicht auf eine fest? In meinem Bereich hautpsächlich aus den folgenden zwei Gründen: (1) Entwickler können eine andere (“leichtere”) Datenbank zur Entwicklung benutzen, und eine andere in der Produktion, und (2) Kunden können je nach Bedarf und Preis die Datenbank auswählen (z.B. mysql für kleine Systeme und Oracle für große).

Leider ist die PK-Erzeugung bei kaum einer Datenbank perfekt. Zum einen sind die Mechanismen oft nicht kompatibel – der SQL Dialekt ist zu verschiden. Ausserdem sind fast immer zwei Datenbankoperationen notwendig, obwohl nur eine Operation ausgeführt wird:

  • (1) PK erzeugen, und dann (2) Zeile in die Datenbank einsetzen, oder:
  • (1) Zeile in die Datenbank einsetzen und dabei den PK generieren, und dann (2) den soeben erzeugten PK aus der Datenkbank holen.

Der zweite Fall kann mit manchen Datenbanken auf eine Operation reduziert werden, wenn Stored Procedures benutzt werden – aber das bindet das System noch stärker an eine bestimmte Datenbank.

Wo kommt der PK her? Wie schon angedeutet, kann der PK beim einsetzen einer Zeile in die Datenbank erzeugt werden – MySQL zum Beispiel hat das AUTO_INCREMENT Keyword, und HSQLDB statt dessen IDENTITY. Der andere übliche Weg ist eine SEQUENCE, aber MySQL kennt diesen Datentyp gar nicht.

Ein weiterer Ansatz, der Kompatibilität einfacher macht, ist eine Sequence-Tabelle – eine Tabelle mit dem einzigen Zweck, PKs zu erzeugen. Und Spring’s DataFieldMaxValueIncrementer Implementierungen nutzen diesen Ansatz. Und nun kommen wir zum eigentlichen Thema dieses Artikels: Wie sollte so eine Sequenz-Tabelle implementiert werden?

Caching

Bevor wir ins Detail der Implementierung gehen, möchte ich auf das Sequence Blocks Entwurfsmuster aufmersam machen. Diese Technik erlaubt es uns, das oben beschriebene Problem der doppelten Datenbankoperation zu beseitigen. Dieses Design Pattern wird von Floyd Marinescu in “EJB Design Patterns” beschrieben.

Bei diesem Pattern wird nicht nur eine, sondern ein Block von PKs aus der Datenbank geholt. Dieser Block wird im Speicher behalten. Wenn diese PKs aufgebraucht sind, wird ein neuer Block geholt. Der einzige Nachteil dieser Technik: Sollte der Prozess, der die PKs haelt, abstürzen, so werden die zu dem Zeitpunkt gehaltenen PKs nie benutzt, es ergibt sich also eine “Lücke” in den benutzten PKs. Für die meisten Anwendungen spielt das allerdings keine Rolle. Spring’s DataFieldMaxValueIncrementer kann dieses Muster benutzen.

Eine Sequenztabelle pro PK?

In der Spring Architektur gibt es “ein Sequenzobjekt pro PK”. Das Sequenzobjekt ist eine Tabelle für MySQL und HSQLDB, und eine Sequenz für DB2, Oracle und PostgreSQL. Das ist ein sicherer und effizienter Ansatz, den so können die Fähigkeiten der benutzten Datenbank voll ausgenutzt werden. Allerdings geht damit wieder ein Stück Portabilität verloren – aber wenigstens ist die Anwendung nach wie vor Unabhängig von der Datenbank, auch wenn der Sequenzgenerator datenbankspezifisch konfiguriert werden muss.

Und hier frage ich mich: Gibt es einen besseren, Datenbank-Unabhängingen Ansatz, den PK zu erzeugen? Wenn uns das gelingen sollte, können wir bei einfachen Anwendungen vielleicht sogar Hibernate benutzen, um die Datenbanktablellen für uns zu erzeugen. Aber das Hauptproblem ist Synchronisation. Wir wollen auf keinen Fall, dass zwei unabhängige Prozesse ausversehen den selben PK erzeugen, z.B. folgendermaßen:

  • Prozess 1 erhöht den Zähler
  • Prozess 2 erhöht den Zähler
  • Prozess 1 ließt den Zähler
  • Prozess 2 ließt den Zähler

Selbst wenn wir Transaktionen benutzen, kann dieses Szenario zu doppelten PKs führen (je nachdem, wie Locking implementiert ist, aber darauf wollen können wir uns nicht verlassen). Allerdings können wir explizit die Tabelle (oder besser, Zeile) sperren, und dann wird es funktionieren.

Die letzte Frage ist dann: brauchen wir nach wie vor eine Tabelle pro Sequenz, oder können wir alle Sequenzen mit einer Tabelle bedienen, zum Beispiel so:

 +------+-------+ | name | value | +------+-------+ | seq1 |     5 | | seq2 |   383 | +------+-------+ 

Wenn wir einzelne Zeilen sperren können, ist das ein legitimer Ansatz. Falls allerdings die gesamte Tabelle gesperrt werden muss (bei wenigen Datenbanken der Fall), kann es zu Performanzproblemen kommen, erst recht, wenn das Sequence Block Muster nicht genutzt wird.

Die Praxis

Wie sieht das ganze in der Praxis aus? Ich teste diesen Ansatz im Moment mit einer Hibernate/Spring Implementierung. Der wichtigste Aspekt ist natürlich rigeroses Testen, was gar nicht so einfach ist, da es hier ja um Raceconditions geht. Ich werde diesen Artikel in ein paar Tagen erweitern, sobald ich mit meinem Ansatz zufrieden bin.

Tricks mit Collections

Hash und Tree Implementierungen

Ich gehe mal davon aus, dass der Leser die Collection Interfaces List, Set und Map kennt. Reden wir doch mal ein bisschen über Sets:

Set fruit = new HashSet(); fruit.add("Apple"); fruit.add("Orange"); fruit.add("Banana"); fruit.add("Cherry"); System.out.println(fruit); 

[Apple, Orange, Banana, Cherry]

Soweit, so gut. Was aber, wenn wir die Früchte alphabetisch sotiert haben wollen? Das erreichen wir ganz einfach, indem wir statt einem HashSet ein TreeSet benutzen:

Set fruit = new TreeSet(); 

[Apple, Banana, Cherry, Orange]

Warum funktioniert das? Weil im zweiten Fall die Implementierung den Inhalt des Sets in einer Baumstruktur speichert, und damit garantiert, dass Einträge in log(n) gefunden werden können. Beim HashSet hingegen kann die Performanz an die Bedürfnisse gut angepaßt werden, indem beim Instantiieren die Anzahl der “Buckets” der Anwendung entsprechend gesetzt wird.

Im allgemeinen sind die Hash-Funktionen schneller, aber ein sortiertes Set zu haben, kann unbezahlbar sein. Ein paar Dinge sind zu beachten: Elemente im TreeSet müssen Comparable implementieren, sonst wird eine Exception geworfen. Außerdem kann ein HashSet null enthalten, TreeSet nicht.

Initialisierung

In dem Beispiel weiter oben wollen wir vier Früchte in unserem Set haben. leider können wir diese nicht dem Konstruktor mitgeben. Aber mit einem Trick wir können eine Klasse ableiten, die diese Werte in das Set einträgt:

Set fruit = new TreeSet() {{ add("Apple"); add("Orange"); add("Banana"); add("Cherry"); }}; 

Collections Klasse

die Collections Klasse wird oft übersehen, enthält aber einen Haufen unglaublich pratischer statischer Methoden. Diese fallen in die folgenden Kategorien:

Such- und Sortierfunktionen: Kleinstes und größtes Element, oder gleich die ganze Liste sortieren, und mit bestimmten Suchalgorithmen ein Element finden. Es können auch gezielt nur bestimmte Teile einer Liste durchsucht werden.

Kopieren, ersetzen, verdrehen: Collections können per Zufall vermischt werden, Kopien erstellt werden, oder mit einem bestimmten Objekt viele Male gefüllt werden.

Wrapping: Eine unmodifizierbare oder synchronisierte Version einer Collection können erzeugt werden. Besonders das Wrapping ist extrem nützlich. Wenn eine Funktion ein Set zurückgibt, das nicht verändert werden darf, kann das entweder dokumentiert werden (kann ignoriert werden), oder ein neues Set kann erzeugt werden:

return new TreeSet(fruit); 

Oder, die beste Lösung, wir geben ein nicht modifizierbares Set zurück:

return Collections.unmodifiableSet(fruit); 

Anfragen an das zurückgegebene Set werden an das interne Set weitergegeben – aber jeder Versuch, das Set zu ändern, wirft eine UnsupportedOperationException. Das war’s für heute! Zum Abschluß möchte ich noch herzlich den Collections Framework Overview empfehlen, der noch weiter auf die Philosophie der Architektur eingeht. Viel Spaß beim Lesen!

Unit Tests: Und private Methoden…?

Es ist eine gute Sache, daß ich mehr Unit Tests schreibe! Das hat zum einen damit zu tun, daß ich eine Menge gelernt habe; aber auch damit, daß ich viel GUI Code schreibe, und die GUI zum Testen zu starten ist extrem ineffizient.

Aber zum Thema private Methoden: Das Thema wurde für mich wieder aktuell, als ich vorgestern einen Vortrag von Andrew Glover zum Thema “Code Metrics for Targeted Code Refactoring” gehört habe (Organisiert von der Philadelphia JUG). Das Thema Unit Testing von privaten Methoden kam zur Sprache, und er erwähnte das JunitX Projekt, das dies ermöglicht.

Aber bevor wir ins Detail gehen, sollten wir uns die Frage stellen: Ist es überhaupt richtig, private Methoden zu testen, und was sind bessere Lösungen oder Alternativen?

Ich höre oft: “Wenn Du glaubst, private Methoden testen zu müssen, ist das ein Warnsignal.” Private Methoden sollten durch die nicht-privaten Methoden getestet werden, die sie benutzen. Sollte das nicht möglich sein, sollte die Architektur überdacht werden.

Ich stimme dem zu, daß diese Situationen mit Skepsis betrachtet werden sollten. Allerdings liegt meiner Meinung nach die Betonung von “Unit Test” auf “Unit”, und je kleiner die getestete Einheit, umso besser. Wenn ein Methode zu unübersichtlich wird (z.B. > 600 Zeilen), dann macht es Sinn, Teile in private Methoden auszulagern (und die Architektur zu überdenken, aber manchmal geht es eben nicht anders). Und meiner Meinung nach macht es viel Sinn, diese Teile einzeln zu prüfen. Und wenn wir diese kleinen Hilfsmethoden schreiben bevor die sie nutzende Methode geschrieben ist, dann macht es erst recht Sinn, diese zu testen. Bill Venners hat einen exellenten Aufsatz zu dem Thema geschrieben.

package private

Was können wir also tun? Das einfachste ist, die zu testenden Methoden package private zu machen. Eine package private Methode hat keine Qualifizierer (also weder private, protected oder public), und kann lediglich von Klassen in der selben Package gesehen werden. Vorteil: Extrem leicht zu implementieren; Refactoring (z.B. umbenennen) funktioniert problemlos, weil das Refactoringwerkzeug alle Referenzen finden kann. Nachteil: Wir verletzen Encapsulation. Das muß jeder für sich entscheiden, wie wichtig das ist. Aber ich finde es sehr wichtig. Zum einen gibt der Qualifizierer dem Entwickler ein starkes Signal und erlaubt, mit einem Blick die Bedeutung einer Methode einzuschätzen. Hinzu kommt, daß Eclipse mich warnt, wenn eine private Methode nicht benutzt wird. Das geht leider nicht mit package private Methoden.

Reflektion

JunitX benutzt Reflektion, um auf private Methoden zuzugreifen, und dieser Ansatz gefällt mir. Allerdings habe ich es nicht geschafft JunitX zum Laufen zu bringen (Version 5.1 schien noch nicht einmal richtig gejart worden zu sein, und 5.0 schien Bugs im Code zu haben). Aber es gibt ja genug Alternativen, und Junit Addons erfüllt diese Rolle – die Klasse junitx.util.PrivateAccessor, um genau zu sein. Diese Klasse ist sehr leicht zu nutzen. Nehmen wir mal an, wir wollen die folgende Methode testen:

 class RocketScience { private static boolean isPrime(int number) { ... } } 

Und hier ist der Test Code, der diese Methode testet:

 public void testIsPrimeExpectFalse() throws Throwable { Object isPrime = PrivateAccessor.invoke( RocketScience.class, "isPrime", new Class[] { Integer.TYPE }, new Object[] { new Integer(8) }); assertEquals(isPrime, Boolean.FALSE); } 

Diese Beispiel zeigt auch sehr schön, wie wir die Konvertierung von Primitives (int, boolean, etc.) zu Objekten durchführen, denn Reflektion funktioniert nur für Objekte. Natürlich würde man eine Methode wie diese in der Praxis nie Privat machen, sondern in einer Werkzeugklasse verfügbar machen – aber das ist ja nicht der Punkt von diesem Beispiel.

Die Sache hat einen einzigen Haken: Der Compiler (und die IDE) kann keine Korrelation zwischen diesem Test under der getesteten Methode erkennen, und wenn die Methode umbenannt wird, wird dieser Test nicht erkannt. Aber das ist in Ordnung – denn der Test wird versagen, und kann schnell und einfach repariert werden.

Ringe in Molekülen

Graf Propagations-Applet
Weiter Unten >>

Disclaimer: Den hier beschriebenen Algorithmus benutzen wir zur Zeit nicht bei meinem Arbeitgeber, und ich habe ihn in meiner Freizeit entwickelt. Die Aufgabe wurde lediglich durch meine Arbeit inspiriert.

Übrigens, Sie können per Email benachrichtigt werden, wenn ein neuer Newsletter veröffentlicht wird. Einfach ein Profil einrichten – keine Sorge, ich verspreche, nicht zu Spammen!

Was ist überhaupt das Problem? Rechts ist ein Molekül abgebildet. Falls Sie sich wundern, daß viele Verbindungen kein Atomzeichen haben: Es ist üblich, Kohlenstoff (C) implizit durch die Ecken darzustellen, und Wasserstoff (H) wird nie gezeichnet. Aber das berührt unser Problem nicht.

Wieviele Ringe hat dieses Molekül? Auf den ersten Blick wissen wir, daß es vier sind. Allerdings würde ein Algorithmus wahrscheinlich fünf sehen. Warum? Der Doppelring links oben enthält zwei kleine Ringe, und einen beide kleinen Ringe umspannenden größeren Ring. Wie ich weiter unten beschreiben werde, müssen wir diese Ringe später wieder entfernen.

Wie sollen wir Ringe repräsentieren? Dazu zog ich Robert Sedgewick’s “Algorithms in C++” zu Rate (eine uralte Edition – inzwischen gibt’s auch eine Java Ausgabe). Denn ein Molekül kann als Graf dargestellt werden. Ein Graf besteht aus Punkten (Atomen), und Kanten zwischen diesen Punkten (Bindungen). Sedgewick schlägt zwei Datenstrukturen vor, um Grafen intern zu speichern. Für dieses Problem bietet sich die “adjacency-structure” Representation an. Bei dieser Representation haben wir eine Liste mit allen Punkten, die wiederum mit einer Liste von verbundenen Punkten assoziiert sind. Zum Beispiel würden wir die folgende Datenstruktur für Wasser (H1-O-H2) bekommen:

 H1 -> [ O ] H2 -> [ O ] O  -> [ H1 H2 ] 

Beachten Sie, daß jede Bindung zweimal auftaucht. Den “verschwendeten” Speicherplatz nehmen wir gerne in Kauf. In einem Molekül sind nicht alle Bindungen gleich (einfach, doppelt, etc.). Das könnten wir speichern, indem die Einträge in der Liste Datenstrukturen sind, die diese Information auch noch aufnehmen. Um unsere Ringe zu finden, ist der Bindungstyp allerdings unwichtig.

Unser erstes Ziel ist es, den gesamten Graf abzugrasen, und zwar immer entlang der Kanten. Dabei gibt es natürlich viele, viele Wege. Sedgewick bietet zwei Algorithmen an mögliche Wege zu finden: der eine geht in die Tiefe, der andere in die Breite. Hier ist ein Diagram aus seinem Buch das den Unterschied visualisiert:

Die roten Linien zeigen die ersten Schritte eines tiefen bzw. breiten Wanderalgorithmusses. Der tiefe springt so schnell wie möglich von Punkt zu Punkt, und kehrt nur dann zu Abzweigungen zurück, wenn es nicht weiter geht. Der breite folgt allen möglichen Abzweigungen, und geht erst dann weiter vorwärts, wenn alle Abzweigungen besucht wurden. Ich denke, es ist intuitiv klar, daß der breite Algorithmus kleine, geschlossene Ringe findet. Mit dem folgenden Applet können Sie selbst Grafen erstellen, und sie mit dem gleich beschriebenen Algorithmus propagieren lassen:

Ihr Browser unterstützt nicht das <APPLET> tag!
Klicken erzeugt einen Punkt. Ziehen von einem Punkt zum anderen erzeugt eine Kante. Zum Propagieren, einen Punkt anklicken.

Weiß: Noch nicht besucht
Rot: Punkt wird besucht
Gelb: Punkt wird untersucht
Grau: Punkt wurde besucht

Aber wie funktionieren die Algorithmen, und wie benutzen wir sie? Ich werde hier nur den breiten beschreiben, weil wir den benutzen. Hier soll nur bemerkt werden, daß die Algorithmen sich ähneln, und daß der tiefe Algorithmus leicht rekursiv zu programmieren ist, während der breite sich gut als Schleife schreiben läßt. Und hier ist der Algorithmus:

Map graf; // Object -> Set von verbundenen Objekten Set visited; // Set von besuchten Objekten void visit(Object head) { List queue = new ArrayList(); queue.add(head); while (! queue.isEmpty()) { Object entry = queue.remove(0); visited.add(entry); // hier entry verarbeiten Set neighbors = (Set)graf.get(entry); for (Iterator i = neighbors.iterator(); i.hasNext();) { Object neighbor = i.next(); boolean wasVisited = visited.contains(neighbor); if (! wasVisited) queue.add(neighbor); } } } 

Ein paar Kommentare:

  • Der Graf ist in der Variablen graf in der form einer Map gespeichert. Die keys sind die Knoten, die mit einem Set assoziiert sind, welches die verbundenen Knoten enthält.
  • Das Set visited enthält die Knoten, die bereits besucht wurden, und muss vor jeder neuen iteration zurückgesetzt werden.
  • Wenn die Funktion “visit” aufgerufen wird, werden alle verbundenen Punkte entlang ihrer Kanten berührt. Sollte der Graf nicht verbunden sein, so kann man einfach für alle Punkte im Graf (also über graf.getkeys() iterieren) visit aufrufen.

Ich hoffe, daß dieser Algorithmus, im Zusammenhang mit dem Applet die Zusammenhänge verständlich macht. der gesamte Code für das Applet ist verfügbar. Falls Sie mit dem Code experimentieren möchten, können Sie weitere Implementierungen des Interfaces Crawler erstellen.

  • Crawler – ein Interface für die Implementierung von Algorithmen.
  • WidthCrawler – Implementierung eines Crawlers, der in der Breite sucht.
  • Visitor – Das Visitor Interface ist ein Argument für den Crawler, um beim Besuch eines Knoten Code ausführen zu können.
  • DrawingCanvas – Die Benutzeroberfläche: Swing Canvas der es dem Benutzer ermöglicht, Grafen zu zeichnen und die Propagation visuell auszuführen.
  • GrafDemo – Die Klasse stellt den Einstiegspunkt ins Programm zur Verfügung, das als Applet oder als Java Anwendung ausgeführt werden kann.

Wir haben zwar eine Menge geschafft heute, aber es gibt noch einiges zu tun, bis wir die Ringe haben. Vielleicht werde ich das Thema in der Zukunft noch einmal ansprechen. Falls nicht, hier sind die Schritte, die wir durchführen müssen, um die Ringe zu finden:

  • Den Propagator anhalten, sobald der Anfangspunkt wiedergefunden wurde, ohne Ecken zweimal zu benutzen (einmal vor und zurück gilt nicht!). Dann haben wir nämlich einen Ring gefunden.
  • Den Propagator für jedes Atom einmal ausführen. Damit finden wir alle Ringe, denn jeder Ring hat mindestens ein Atom, daß mit keinem anderen Ring geteilt wird.
  • Ringduplikate ausfiltern!
  • Doppelringe wie oben beschrieben rausfiltern. Das machen wir, indem wir Ringe suchen, die zwei oder mehr Kanten gemeinsam haben. Den größeren von den zweien entfernen wir.

Bleibt nur noch die Frage, ob wir mit diesem Algorithmus wirklich alle Ringe finden. Außerdem könnten wir noch die Performance des Algorithmus untersuchen. Ich überlasse dies gerne dem Leser.

Der Spring Container (oder: Dependency Injection)

Die Beispielanwendung (und warum Sie beim Start eine Warnung bekommen)
Die Beispielanwenung benötigt Java Webstart zum Laufen – und wenn Sie ein Java Entwickler sind, haben sie die Software auch schon installiert. Leider brauche ich mehr zugang zu Ihrem System, als der normale SecurityManager zuläßt. Um genau zu sein, Spring benutzt Reflektion (getDeclaredConstructors()) um Objekte zu instantiieren. Daher müssen alle jars zertifiziert sein. Das habe ich gemacht, allerdings kann ich mir im Moment keinen Schl¨ssel von Verisign leisten, und habe meinen eigenen Schlüssel erstellt, der dementsprechend in keiner zentralen Datenbank zu finden ist.

Spring Demo Ausführen >>
Code runterladen >>

Zunächst einmal: Spring ist wesentlich mehr als der Container den ich gleich beschreiben werde. Spring bietet Aspect Oriented Programming (AOP), Transaktionsmanagement, Metadata-Unterstützung (ähnlich wie JDK 1.5 Metadata, orthogonal zu XDoclet), und viel Unterstützung für Datenbankoperationen (inklusive der Unterstützung von O/R-Mappern wie Hibernate oder JDO). Die Englische Onlinedokumentation ist excellent!

Das klingt zwar so, als gäbe es hier keine Struktur; aber trotz der Vielfalt ist Spring seinen Grundprinzipien treu: (1) Den Programmierer nicht einschränken; (2) Guten Programmierstil unterstützen; (3) Das Rad nicht neu erfinden.

BeanFactory und ApplicationContext

Der grundliegenste Aspekt von Spring ist die BeanFactory – der ApplicationContext ist lediglich eine erweiterte BeanFactory mit Unterstützung für AOP, Internationalisierung, etc. Die Beispielanwenung benutzt eine XMLBeanFactory, und in der Regel werden die Beans per XML definiert. Schau’n wir uns doch erst einmal an, wie eine Bean Definition aussieht, und untersuchen dann, warum so etwas sinnvoll ist.

Die BeanFactory kann jede Art von Objekt enthalten, aber sie ist besonders für JavaBeans geeignet. Zum Experimentieren habe ich die folgende Klasse erstellt:

public class SampleBean { private String name = "(no name)"; private Set friends = new HashSet(); public Set getFriends() { return friends; } public void setFriends(Set friends) { this.friends = friends; } public String getName() { return name; } public void setName(String name) { this.name = name; } public String toString() { return name + friends; } } 

Die Klasse ist eine JavaBean, denn sie hat (1) einen Default Konstruktor und (2) Setters und Getters, die dem JavaBean Standard entsprechen. Wenn wir so eine Klasse im Spring Container erstellen wollen, dann stecken wir das folgende XML in die Containerdefinition:

<bean id="aSampleBean" class="de.jastram.SampleBean"> <property name="name"> <value>Sample Bean Name</value> </property> <property name="friends"> <set> <value>123</value> <value>Hello, World</value> </set> </property> </bean> 

Das können Sie gleich mit der Beispielanwendung ausprobieren! Wenn auf dem linken Tab das XML editiert wird, werden die Änderungen auf dem rechten Tab reflektiert.

Alles Singletons

Soweit, so gut. Wir können also über XML Java Objekte erstellen. Wir kommen auch leicht an die Objekte ran – das Interface BeanFactory hat methoden um Beans per Name zu finden. Wenn wir also eine Referenz zu unserer BeanFactory verfügbar halten, kommen wir an unsere Beans ran. Normalerweise haben wir nur Singletons im Container – und das wollen wir normalerweise auch. Allerdings ist es auch möglich, “Prototypen” im Swing Container zu haben – dann wird bei jedem Aufruf von getBean() ein neues Objekt erstellt. Dazu wird einfach singleton="false" dem <bean> Tag hinzugefügt.

Eine typische Anwendung benutzt ein DataSource Objekt, das mit einer Datenbank assoziiert ist. Es wird einmal erstellt, konfiguriert, und kann dann von überall dort benutzt werden, wo der Container verfügbar ist.

Aber gerade ein DataSource Objekt wollen wir nicht unbedingt per Constructor erstellen, oder? Und hier glänzt Spring wieder: Es gibt weitere Möglichkeiten, Objekte zu erstellen: Factories. Factories sind ganz normale Objekte. Aber diesmal ist das Objekt nicht das Endprodukt, sondern der “Objektproduzent”. Zum Beispiel, die Klasse java.lang.System hat die statische Methode currentTimeMillis(), die wir als Factory benutzen können – probieren wir das doch einfach mal aus: Kopieren Sie das folgende XML in die Beispielanwendung:

<bean id="systemTimeFactory" class="java.lang.System" factory-method="currentTimeMillis"/> 

Wenn wir uns das resultierende Objekt anschauen, was für ein Klassentyp ist es? Die Antwort ist Long (und nicht System). Übrigens können wir immer noch an das Factoryobjekt herankommen, wenn wir unbedingt wollen, indem wir einfach ein “&” vor den Namen setzen. Also factory.getBean("&systemTimeFactory") gibt uns die Factory.

In diesem Beispiel ist die Factorymethode eine statische Methode – Spring hat selbstverständlich auch die Möglichkeit, eine (nicht statische) Methode eines Singletons als Factorymethode aufzurufen.

Und jetzt…?

Wozu das ganze? Gut strukturierte Anwendungen haben eine Reihe von Singletons, die untereinander verbunden sind. Wie oben schon erwähnt, haben wir fast immer eine DataSource um mit einer Datenbank zu sprechen. Die Logik, die mit der Datenbank kommuniziert, ist normalerweise in Data Access Objects (DAOs) untergebracht. Die Geschäftslogik lebt ebenfalls in Singletons, die nur zu den DAOs sprechen, und darauf sitzt normalerweise eine weitere Schicht (oft Servlets), die zu mit der Geschäftslogik kommunizieren, und die Benutzeroberfläche bilden. Es ist also einzusehen, dass wir viel mit Singletons arbeiten, die untereinander kommunizieren. Spring macht die Verknüpfung dieser Singletons ungleich einfacher.

Und existierende Techniken? Applikation Server wie Tomcat sind zwar ähnlich leistungsfähig, aber beschränken sich auf Servlets im Container. Ein Riesenvorteil von Spring ist, daß es mit POJOs arbeiten kann. Und der Unterschied ist noch viel extremer, wenn wir uns EJB anschauen, daß ohne Codegenerierungssoftware kaum zu bewältigen ist!

Aber die Authoren von Spring sind sich dieser Technologien natürlich bewußt, und haben sehr darauf geachtet, daß Spring problemlos mit diesen Technologien zusammenarbeiten kann – es ist also keine “entweder – oder” Entscheidung notwendig.

Der Spring Container bringt den Anwender dazu, besseren Code zu schreiben. Plötzlich ist klar, wie wir Objekte konfigurieren: Mit JavaBean Setters. Und wenn alle Komponenten unseres Systems plötzlich Setters für die Konfiguration haben (die am Besten auch noch Interfaces wie DataSource statt Klassen als Argument haben), dann wird auch das Testen dieser Komponenten mit Unit Tests und Mock Objekten plötzlich viel einfacher.

Weitere Juwelen in Spring

Ist Ihnen aufgefallen, daß wir <value>1234<value> schreiben, und ein Integer Objekt erhalten? Wie geht das? Der Container hat eine erweiterbare Infrastruktur, die Text in Objekte umwandelt.

Manchmal gibt es nur ein einziges Objekt von einem bestimmten Typ im Container – zum Beispiel nur eine einzige DataSource. In diesem Fall können wir Spring’s auto-wiring (automatisches verbinden) benutzen, um automatisch alle Setters, die eine DataSource als Argument benutzen, mit diesem Objekt aufzurufen. (einfach autowire="byType" der Bean hinzufügen). Auto-wiring per Name ist auch unterstützt (autowire="byName").

Ein heißes Thema heutzutage sind “Interceptors” (Abfänger) – ein zentraler Aspekt von AOP. Ein Interceptor kann vor oder nach dem Aufruf einer Methode eingreifen. Zum Beispiel könnten wir einen Sicherheits-Interceptor entwerfen, der vor dem Aufruf einer Methode prüft, ob der Benutzer genug Befugnisse hat. In einem traditionellem Programm müßte jede Methode extra Code für diesen Zweck haben, oder wir müßten eine gute Proxy-Architektur haben. Mit Spring AOP können wir mit RegExps definieren, welche Methoden abgefangen werden sollen, und den Spring Container informieren, diesen Interceptor zu aktivieren. Die abgefangenen Objekte brauchen davon überhaupt nichts zu wissen!

Schlußbemerkung

Spring hat unglaublich viel für die Enterpriseentwicklung zu bieten – und es ist unglaublich unaufdringlich dabei. Es ist vor allem sehr einfach, Spring hier und da in einer existierenden Anwendung einzuführen, und dann langsam den Einfluß von Spring zu erweitern. Spring ist kein Allheilmittel für alles – aber es ist erfreulich, so ein Leichtgewicht im Reportoir als Alternative zu EJB et. al. zu haben,

Unit Tests: Wohin damit…?

Warum ist es überhaupt wichtig, wo wir die Unit Tests unterbringen? Weil wir die kleinste “Einheit” (Unit) des Systems testen wollen, und die kleinste Einheiten (Klassen, Methoden und Constructoren) sind oft package private oder protected, und nicht immer public. Um leicht auf diese Elemente zugreifen zu können, sollte der Testcode in der selben Package sein. Das gibt uns zwar keinen Zugang zu privaten Variablen und Funktionen, aber wenn die zum Testen notwendig wären, sollte die Architektur der Klasse überprüft werden. Die naive Klassenstruktur wäre dann folgendermaßen:

 src/de/jastram/unit/MyClass.java src/de/jastram/unit/MyClassTest.java 

Mir gefällt diese Struktur nicht (und viele andere Entwickler stimmen mir zu), weil nun der Ordner normalen und Testcode mischt. Das ist aus vielerlei Gründen schlecht: JavaDoc würde die Testklassen enthalten, es ist schwierig, eine Distributionsdatei ohne Testklassen zu erstellen, usw. Diese Probleme könnten zwar mit einem geschickten Ant Skript gelöst werden, aber das Resultat ist nicht elegant, und für neue Entwickler schwer zu verstehen.

Die zweite Lösung gfällt mir wesentlich besser, und ist meine Empfehlung: Testklassen sind in der selben Package, aber in unterschiedlichen Ordnern:

 src/de/jastram/unit/MyClass.java test/de/jastram/unit/MyClassTest.java 

Alle IDEs die ich kenne, unterstützen diese Struktur, und Ant Skripte sowieso. Es ist nicht unüblich, eine Reihe von Sourceverzeichnissen zu haben. Jetzt ist es kinderleicht, JavaDoc zu erzeugen, oder eine JAR ohne die Testklassen zu bauen. Aber diese Struktur läßt zwei Fragen offen: (1) Was tun, wenn wir aus irgendeinem Grund doch Zugang zu privaten Elementen haben wollen, und (2) ist diese Struktur nicht ein bißchen übertrieben für kleine Projekte?

Für Punkt 1 gibt es eine Lösung (auch ohne Reflektion): Wir bringen die Testklasse einfach als static Memberklasse in unserer Hauptklasse unter! Das ist auch eine gute Struktur für Demonstrationen, weil wir nur eine einzige Klasse haben:

 src/de/jastram/unit/MyClass.java 

Und wo ist die Testklasse? In der selben Datei – der Code sieht etwa folgendermaßen aus:

public class MyClass { ... public static class Test extends TestCase { ... } } 

Und wie gesagt, nun können wir sogar auf die privaten Elemente zugreifen. Wie gesagt, diese Architektur muß mit Vorsicht genossen werden, und ist nicht für größere Projekte geeignet. Es ist (fast) unmöglich, das Programm ohne den Testcode zu verarbeiten, es ist noch nicht einmal möglich, die Datei ohne den Testcode zu drucken! Dennoch, für kleine Tests und Demos ist das eine prima Architektur.

Gibt es vielleicht noch bessere Ansätze zur Codeorganisation? Schreibt Eure Meinung weiter unten ins Formum!