Datenstrukturen in Java

Datenstrukturen und Java klingt im ersten Moment nach einem Widerspruch: Java hat Objekte und keine Strukturen. Bei näherer Betrachtung sieht man jedoch, dass die vermeintlichen Datenstrukturen zumindest in C++ als Klassen und somit als Objekte realisiert sind – alleine die Bezeichnung ist noch ein Ãœberbleibsel aus prozeduralen C-Zeiten.
Wir können also festhalten, dass eine Datenstruktur Attribute und Funktionen hat (um die Sprache möglichst neutral zu halten). Unterschiedliche Datenstrukturen haben unterschiedliche Attribute und Funktionen. Dies steht im Gegensatz zum objektorientierten Ansatz der Wiederverwendung von Objekten.
Java bietet von Haus aus bereits ein grosses Repertoire (JDK) wo man mit C++ die STL bemühen muss. So lässt sich in Java eine FIFO Queue bereits durch die Klassendefinition und dem Überschreiben von remove vollständig implementieren:

public class FIFOList extends LinkedList implements Queue{
    public Object remove() {
        return remove(0);
    }
}

Beispiel von: Simple Thoughts
Wenn ich jedoch den durch die Struktur beschriebenen Funktionsumfang anschaue muss ich feststellen, dass die Funktionalität zwar der einer FIFO Queue entspricht, aber bereits die Methodennamen leicht verwirrlich sind. Zudem gibt es zahlreiche Funktionen, die mit einer FiFo Queue nichts zu tun haben. Ein C++ Entwickler, der nur die Signaturen sieht kann nicht erkennen, worum es sich handelt. Zudem weiss ich mit einer solchen Umsetzung nicht wie die Queue funktioniert.
Aus diesem Grund habe ich die C++ Implementation genommen, sie für Java angepasst und mit einigen convenient Methoden ergänzt:

public class FiFoQueue {
	private FiFoNode first=null;
	private FiFoNode last=first;
	public FiFoQueue(){		
	}
	// Put a new elemnt in the queue
	public void enqueue(T element){
		FiFoNode temp = new FiFoNode();
		temp.value=element;
		temp.next=last;
		last=temp;
	}
	// Get the element from the queue that is in front
	public T dequeue(){
		FiFoNode temp = first;
		first=first.next;
		return temp.value;
	}
	// Check if the queue is empty
	public boolean isEmpty(){
		return first==last && first==null;
	}
	// Empty the queue
	public void empty(){
		first=last=null;
	}
	class FiFoNode{
		FiFoNode next;
		T value;
		FiFoNode(){
		}
	}
}

Mehrfachvererbung in Java

Im allgemeinen ist wahrscheinlich so, dass das Unterbinden von Mehrfachvererbung eher ein Segen als ein Fluch ist. Doch wie immer gibt es auch hier Fälle, wo dies unumgänglich ist. Dabei müchte ich nicht auf die Gründe eingehen. Es sei lediglich der Hinweis erlaubt: Es ist in jedem Fall weniger aufwändig, ohne Mehrfachvererbung aus zukommen. Somit ist der Aspekt ob Mehrfachvererbung tatsächlich notwendig ist zu überprüfen. Wie der Umstand von Single Inheritance umgangen werden kann soll hier am Beispiel der Programmiersprache Java erläutert werden.

  1. Beide Klassen, die Abzuleiten sind liegen im eigenen Namensraum, d.h. beide Klassen gehören zum selben Projekt wie die zu erstellende Ableitung. Hier wählt man eine Klasse aus von der man ableitet. Von der anderen Klasse erstellt man ein Interface, das man implementiert. Dieses vorgehen legt nahe, dass man für das Interface die Klasse mit weniger Implementationsaufwand verwendet. Wenn möglich sollte hier auch die erwartete API Stabilität einfliessen. D.h. eine Klasse deren API, oder zu einem geringeren Grad die Implementation, noch ändern kann sollte wo möglich nicht als Interface verwendet werden, da hier aufgrund der Anpassung der Klasse, das Interface und dann die „abgeleitete“ Klasse angepasst werden muss.
  2. Ähnlicher Fall wie oben, nur dass hier die eine Klasse ausserhalb des Projekts liegt. Liegt diese Klasse jedoch noch innerhalb des eigenen Einflussbereichs, z.B. anderes Projekt des Teams, so kann selbes vorgehen wie oben angewandt werden; andernfalls ist die externe Klasse prädestiniert für ein Interface zumal hier davon ausgegangen werden kann, dass die API stabil ist.
  3. Beide Klassen liegen Ausserhalb des Einflussbereichs. Eine der beiden Klassen implementiert ein Interface, das die essentiellen Methoden enthält. In diesem Fall kann dieses Interface implementiert werden und die andere Klasse implementiert werden.
  4. Trifft keiner der obigen Punkte zu so muss eine komplexere Lösung gefunden werden. Komplexer ist sie weil sie mehr Aufwand bedeutet, aber auch weil sie einer echten Mehrfachvererbung am nächsten kommt: Man wählt den Ansatz, dass man eine der beiden Klassen ableitet und von der anderen eine Reimplementation vornimmt. Handelt es sich hierbei um eine Klasse von Sun, so kann sie dem src.zip entnommen werden. Zum Beispiel:
    public class ObservableThread extends Thread {
        private boolean changed = false;
        private Vector obs;
        public ObservableThread() {
    	obs = new Vector();
        }
        public synchronized void addObserver(Observer o) {
            if (o == null)
                throw new NullPointerException();
    	if (!obs.contains(o)) {
    	    obs.addElement(o);
    	}
        }
        public synchronized void deleteObserver(Observer o) {
            obs.removeElement(o);
        }
        public void notifyObservers() {
    	notifyObservers(null);
        }
       public void notifyObservers(Object arg) {
            Object[] arrLocal;
    
    	synchronized (this) {
    	    if (!changed)
                    return;
                arrLocal = obs.toArray();
                clearChanged();
            }
    
            for (int i = arrLocal.length-1; i>=0; i--)
                ((Observer)arrLocal[i]).update(new HiddenObservable(this), arg);
        }
        public synchronized void deleteObservers() {
    	obs.removeAllElements();
        }
        protected synchronized void setChanged() {
    	changed = true;
        }
        protected synchronized void clearChanged() {
    	changed = false;
        }
        public synchronized boolean hasChanged() {
    	return changed;
        }
        public synchronized int countObservers() {
    	return obs.size();
        }
    

    Hierbei handelt es sich jedoch noch nicht um eine echte Mehrfachvererbung. In vielen Fällen sollte dies jedoch schon genügen. Wo nicht kann der Mehrfachvererbung mehr Authentizität verliehen werden indem von der ursprünglichen Klasse die reimplementiert wird ein Interface gebildet wird und dieses implementiert wird. Nun hat die Klasse beide Typen (Thread und Observable). Eine andere oder weitere Möglichkeit – insbesondere wenn this semantisch mit der ursprünglichen Klasse verwendet wird – besteht darin eine versteckte Inner Class zu bilden, die die reimplementierte Klasse ableitet und alle Methoden, die von dieser Klasse geerbt werden, überschreibt. Die Implementation der Methoden reicht die Ausführung an die selbe Methode in der äusseren Klasse weiter:

        private class HiddenObservable extends Observable{
        	        private ObservableThread ot;
         	        public HiddenObservable(ObservableThread obersevable){
        		       ot = obersevable;
        	        }
    		public synchronized void addObserver(Observer o) {
    			ot.addObserver(o);
    		}
    		protected synchronized void clearChanged() {
    			ot.clearChanged();
    		}
    		public synchronized int countObservers() {
    			return ot.countObservers();
    		}
    		public synchronized void deleteObserver(Observer o) {
    			ot.deleteObserver(o);
    		}
    		public synchronized void deleteObservers() {
    			ot.deleteObservers();
    		}
    		public synchronized boolean hasChanged() {
    			return ot.hasChanged();
    		}
    		public void notifyObservers() {
    			ot.notifyObservers();
    		}
    		public void notifyObservers(Object arg) {
    			ot.notifyObservers(arg);
    		}
    		protected synchronized void setChanged() {
    			ot.setChanged();
    		}
        }
    

    Zu beachten: Dies ist nötig, da im ersten Code-Teil (bereits angepasst) ein Aufruf mit this gemacht wird und this nun mal vom Typ Observable und nicht vom Typ Thread oder ObservableThread ist.
    Einziger Nachteil dieser Lösung: instanceof Observable wird immer false zurückgeben. Solange diese Abfrage jedoch im eigenen Code ist, spielt dies keine weitere Rolle.

Eclipse Wizard Plugin erstellen

Eclipse stellt bereits einen Wizard zur Verfügung, um eine Wizard zu erstellen: Über New->Plug-in Development->Plug-in Project ein neues Projekt anlegen. Auf der Folgeseite habe ich dann als Target Eclipse (in Version 3.3) angegeben; das OSGi Framework habe ich nicht ganz durchschaut, jedenfalls war mein fertiges Plug-in dann nicht kompatibel. new Plugin step 3 of 5
Auf der 3 Seite sind dann die Eckdaten zu vergeben: Plug-in ID üblicherweise der package name, Version ist selbsterklärend, der Plug-in Name hat nur bezeichnenden Charakter, sollte aber sprechend ausdrücken, wofür das Plug-in steht. Der Plug-in Provider ist üblicherweise ein Teil der Webadresse z.B. eclipse.org, ibm.com oder sahits.ch. Der Activator wird benötigt, um das Plug-in zu aktivieren.
new Plugin step 4 of 5
Auf der folgenden Seite kann zwischen den verschiedenen Plug-ins ausgewählt werden. Für einen Wizard benötigen wir ein „Plug-in with multi-page editor“; Mit Editor ist letztentlich die Grafische Oberfläche des Wizards gemeint wo die Eingaben gemacht werden, wie auf gerade dieser Schritt. Multi-page besagt lediglich, dass der Wizard aus mehreren Schritten bestehen kann, aber nicht muss.
Auf den beiden letzten Seiten werden dann die Informationen für die zu erstellenden Klassen gemacht.
Nach dem Abschluss hat man bereits ein funktionsfähiges Plug-in. Um es auszutesten wählt man das Projekt an und Run As->Eclipse Application. Dies startet eine zweite Eclipse Instanz mit eigenem Workspace (ein Workspace kann gleichzeitig nur von einer Eclipse Instanz benutzt werden). Hier kann der Wizard über New->Other->Other gestartet werden.
Nun geht es daran, den Wizard mit eigenem Code zu fällen. Ein guter Einstiegspunkt ist Eclipse Plugins Exposed, Part 1: A First Glimpse
Hat man die eigene Funktionalität integriert gibt es noch etwas Schönheitspflege zu machen:

  1. Wo in der Liste soll der Wizard erscheinen? Dies wird im plugin.xml im attribut category des tags wizard geregelt. Keine Angabe verfrachtet das Element in den Ordner other. Ein String bringt es in einem Ordner mit diesem Namen unter. Aber Achtung: Wenn bereits ein Ordner mit demselben Namen existiert, gibt aller Wahrscheinlichkeit nach einen zweiten Ordner. Soll der Wizard in einem anderen Ordner erscheinen ist hier die Klasse des Wizards einzutragen.Plugin.xml
  2. Das Plug-in soll ja nicht nur einer Eclipse Instanz verfügbar sein, sondern beim Starten verfügbar sein. Dazu muss das Plug-in in das Verzeichnis eclipse/plugins. Dies jedoch nicht in der Form, wie im Projekt. Für das Plug-in wird das plugin.xml, ein jar-File der Klassen, das Verzeichnis icons und eventuell das Verzeichnis icons, zusätzlich benötigte Bibliotheken und andere Resourcen benötigt.
    Dies gibt man im Plug-in oder Manifest Editor im Tab Build ein.
    Plugin.xml Build
    Unter Runtime Information gibt man den Namen des jar files an, das erstellt werden soll. In Binary Build wird angegeben, was alles im Build enthalten sein soll. Unter Extra Classpath Entries werden zusätzliche Bibliotheken angegeben.
    Um den aktuellen Build auszuführen gibt es mehrere Möglichkeiten: 1. Über Export->Plug-in Development->Deployable plugins and features. Dies erstellt jedoch nur ein jar-file der Klassen mit dem angegebenen Namen in einem plugins Verzeichnis. 2. Wertvoller aber auch nicht ganz optimal ist der Weg über ein Ant build script. Um das build.xml zu erhalten muss das plugin.xml angewählt sein, dann PDE Tools->Create Ant Build File. Dann kann zuerst das Default Target ausgeführt werden, um das jar-File zu erhalten, sodann das target zip.plugin was ein Zip-Archiv des Ordners plugin-ID_Version erstellt und alles unter Binary Build angegebene enthält. Leider aber zusätzlich zwei Zip-Files mit den Sourcen und das Verzeichnis bin. (Dies gilt zumindest für Eclipse 3.3). Also muss hier von Hand aussortiert werden.

Das Ganze ist nicht ganz ohne deshalb hier noch ein paar Tipps:

  • Das Plug-in wird nicht geladen/aktiviert: Erst mal schauen ob das Plug-in verfügbar ist unter Help->Ablut Eclipse SDK->Plug-in Details. Um das Problem zu eruieren kann es sinnvoll sein im Manifest das LacyLoad auf false zu setzen. Dies bewirkt, dass das Plug-in beim Start von Eclipse geladen wird. Ein Blick ins Error log (Window->Show View->Error log) enthällt das Problem
  • Im Error log erscheint die Meldung „plugin does not have valid identifier“ oder „plugin does not have valid version“. Hier habe ich mir sagen lassen, dass dies mit einer JRE < 1.5 vorkommen kann. Mein Problem war ein anderes: Das Verzeichnis META-INF fehlte.
  • Wenn der Wizard gestartet werden soll erscheint die Fehlermeldung „Error loading new wizard …“ Zum einen kann es sein, dass im plugin.xml die falsche Klasse angegeben ist, oder dass das jar-file im Classpath des Plug-ins fehlt (META-INF/Manifest.mf)
  • Wenn alles nichts nützt Eclipse von der Konsole mit eclipse -clean starten. Wenn dies auch nicht funktioniert alles im Verzeichnis eclipse/configuration/.settings/ löschen.

Vitualisierung unter Ubuntu (7.04)

Bevor ich meinen Arbeits‘ PC auf Linux – konkret Ubuntu – umstelle, wollte ich wissen, wie die gut die Virtualisierung unter Ubuntu funktioniert. Dazu habe ich das ganze auf meinem Notebook ausprobiert. Schliesslich gibt es einige Programme, die unter Linux nicht laufen, und die ich nicht missen möchte. Daher die Idee eines Linux mit einer VM auf der ein minimales Windows läuft mit einigen wenigen Programmen.
Einige Rahmenbedingungen existieren hier einfach:

  • Prozessor: 1.4 GHz
  • Arbeitspeicher: 512 MB
  • Harddisk: 80GB
  • Linux Partition: 10GB

Die Installation von VMWare geht gut von der Hand, wenn man sich an die Installationsanleitung hält.
Ich hatte das Pech, dass ich den VMware Player installiert hatte, was die Installation des VMWare Servers stört. Daher müssen die zugehörigen Pakete erst deinstalliert werden. Leider verbleibt der Ordner /etc/vmware und das skript /etc/init.d/vmware, die mit Root Berechtigungen gelöscht werden müssen.
Initial habe ich eine Grösse von 1.5 GB für die virtuelle Disk gewählt. Dies stellte sich jedoch bereits nach 11 Security Updates als zu klein heraus. Daher musste ich das File vergrössern.
vmware-vdiskmanager -x 2gb myDisk.vmdk
Siehe dazu den Bericht Expanding a virtual VMware disk.
Unglücklicherweise muss die Partition des Betriebsystems dann selbst noch vergrössert werden.
Damit ich Daten zwischen Host und Guest Betriebsystem austauschen kann musste ich eine physikalische Platte einbinden.
VMWare physical drive
Ein solches Laufwerk wird als SCSI Laufwerk eingebunden und benötigt die VMWare Tools mit einem entsprechenden Treiber. Der Treiber kann auch separat installiert werden: http://www.vmware.com/download/server/