  |
|
 |
|
|
|||||
 |
|
Ein weiterer Konstruktor erlaubt ein beliebiges Objekt vom Typ Collection als Parameter. Wir werden uns später näher mit Collections auseinander setzen.
Die eingefügte Zahl macht deutlich, dass als Elemente nur Objekte akzeptiert werden, und keine primitiven Datentypen. Eine Unterklasse könnte jedoch Vector erweitern und die Daten für den Benutzer unsichtbar in Objekten kapseln.
11.3.2 Funktionen
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
class java.util.Vector extends AbstractList |
 |
void addElement( Object o ) Fügt das Objekt o dem Vektor hinter dem letzten hinzugefügten Element an. Reicht der interne Puffer nicht aus, wird gegebenenfalls der Vektor vergrößert. |
| |
int capacity() Liefert die aktuelle Kapazität des Vektors. capacity() ist in der Praxis eher unwichtig, denn das Kapazitätsmanagement soll die Klasse selber machen. |
| |
Object clone() Die Klasse implementiert die clone()-Methode von Object, das heißt eine Referenz auf eine Kopie des aufrufenden Vektors wird zurückgegeben. Es handelt sich um eine flache Kopie; Original-Vektor und Kopie referenzieren also dieselben Element-Objekte. |
| |
boolean contains( Object o ) Sucht das Element. Liefert true zurück, wenn ein mit o inhaltlich gleiches Objekt im Vektor enthalten ist. |
| |
void copyInto( Object array[] ) Kopiert die Elemente des Vektors in das Array array. |
| |
Object elementAt( int index ) Das an der Stelle index befindliche Vektorelement wird zurückgegeben. |
| |
Enumeration elements() Gibt ein Aufzählungs-Objekt zurück. Somit können wir die Elemente eines Vektors aufzählen. |
| |
Object firstElement() Gibt das erste Element des Vektors zurück. |
| |
int indexOf( Object o ) Sucht im Vektor nach dem Objekt o. Liefert den Index des passenden Vektorelements zurück oder -1, falls kein gleiches Element vorkommt. |
| |
int indexOf( Object o, int index ) Sucht im Vektor ab der Position index nach dem Objekt o. Liefert den Index des passenden Vektorelements zurück oder -1, falls kein gleiches Element vorkommt. |
| |
void insertElementAt( Object o, int index ) Fügt Objekt o an der Stelle index in den Vektor ein und verschiebt die anderen Elemente um eine Position nach hinten. Auch das ursprünglich an der Position index befindliche Element wird verschoben. |
| |
boolean isEmpty() Gibt true zurück, falls der Vektor kein Element enthält. |
| |
Object lastElement() Gibt das letzte Element des Vektors (das mit dem größten Index) zurück. |
| |
int lastIndexOf( Object o ) Sucht rückwärts durch dem Vektor nach o und gibt die Position des passenden Elements zurück. Existiert kein zu o gleiches Element im Vektor, wird -1 zurückgegeben. |
| |
int lastIndexOf( Object o, int index ) Sucht rückwärts ab Position index durch den Vektor nach o und gibt die Position des passenden Elements zurück. Existiert kein zu o gleiches Element im Vektor, wird -1 zurückgegeben. |
| |
void removeAllElements() Entfernt alle Elemente aus dem Vektor. |
| |
boolean removeElement( Object o ) Entfernt das erste mit o übereinstimmende Element aus dem Vektor. Das Funktionsergebnis signalisiert, ob ein passendes Element gefunden (und gelöscht) wurde. |
| |
void removeElementAt( int index ) Entfernt das Element an der Stelle index. Alle nachfolgenden Elemente rücken um eine Position vor. |
| |
void setElementAt( Object o, int index ) Das Objekt o wird an der Stelle index im Vektor platziert. Das vorher an dieser Position befindliche Element wird aus dem Vektor entfernt. |
| |
void setSize( int size ) Setzt die Größe des Vektors. Überzählige Elemente werden aus dem Vektor entfernt bzw. Null-Referenzen als neue Einträge angehängt. |
| |
int size() Gibt die Anzahl der Elemente im Vektor zurück. Es gilt stets: v.size() <= v.capacity(). |
| |
String toString() Konvertiert den Vektor in einen String; eine textuelle Aufzählung seiner Elemente. |
| |
void trimToSize() Übersteigt die Kapazität eines Vektors die Anzahl der enthaltenen Elemente, so beseitigt diese Methode die überzählige Kapazitätsreserve. Dadurch wird der Speicherbedarf minimiert. |
Ein Vektor muss zwei Größen verwalten: Zum einen die Anzahl der gespeicherten Elemente nach außen, zum anderen die interne Größe des Felds. Ist die Kapazität des Felds größer als die Anzahl der Elemente, so können noch Elemente aufgenommen werden, ohne dass der Vektor etwas unternehmen muss. Die Anzahl der Elemente im Vektor, die Größe, liefert die Methode size() und Kapazität des darunter liegenden Arrays liefert capacity().
Der Vector vergrößert sich automatisch, falls mehr Elemente aufgenommen werden, als ursprünglich an Platz vorgesehen war. Diese Operation heißt Resizing. Dabei spielen die Größen initialCapacity und capacityIncrement besonders für ein effizientes Arbeiten eine wichtige Rolle. Sie sollten passend gewählt sein. Schauen wir uns daher zunächst einmal die Funktionsweise des Vektors an, falls das interne Array zu klein ist.
Wenn das Array zehn Elemente fasst, nun aber ein elftes eingefügt werden soll, so muss das Laufzeitsystem einen neuen Speicherbereich reservieren und jedes Element des alten Felds in das neue kopieren. Dies kostet Zeit. Schon aus diesem Grunde sollte der Konstruktor Vector(int initialCapacity) gewählt werden, da dieser eine Initialgröße festsetzt. Das Wissen über unsere Daten hilft dann der Datenstruktur. Falls kein Wert voreingestellt wurde, so werden zehn Elemente angenommen. In vielen Fälle ist dieser Wert zu klein.
Nun haben wir zwar darüber gesprochen, dass ein neues Feld angelegt wird und die Elemente kopiert werden, haben aber nichts über die Größe des neuen Felds gesagt. Hier gilt die »Verdopplungsmethode«. Wird der Vector vergrößert, so ist das neue Feld doppelt so groß wie das alte. Dies ist eine Vorgehensweise, die für kleine und schnell wachsende Felder eine clevere Lösung darstellt, für große Felder aber schnell zum Verhängnis werden kann. In dem Fall, wo wir die Vergrößerung selbst bestimmen wollen, nutzen wir den Konstruktor Vector(int initialCapacity, int capacityIncrement) oder ändern die Größe über Methoden.
Mit capacity() gelangen wir an die interne Größe des Arrays. Sie kann mit ensureCapacity() geändert werden. Ein Aufruf von ensureCapacity(int minimumCapacity) bewirkt beim Vektor, dass er insgesamt mindestens minimumCapacity Elemente aufnehmen kann, ohne dass ein Resizing nötig wird. Ist die aktuelle Kapazität des Vektors kleiner als minimumCapacity, so wird mehr Speicher angefordert. Der Vektor verkleinert nicht die aktuelle Kapazität, falls sie schon höher als minimumCapacity ist. Um aber auch diese Größe zu ändern, und somit ein nicht mehr wachsendes Vektorarray so groß wie nötig zu machen, gibt es, ähnlich wie beim String mit Leerzeichen, die Methode trimToSize(). Sie reduziert die Kapazität des Vektors auf die Anzahl der Elemente, die gerade im Vector sind. Mit size() lässt sich die Anzahl der Elemente im Vektor erfragen. Sie gibt die wirkliche Anzahl der Elemente zurück. Wollen wir diese ändern, so nutzen wir dazu setSize(int newSize). Ist die neue Größe kleiner als die alte, so werden die Elemente am Ende des Vektors abgeschnitten. Ist newSize größer als die alte Größe, werden die neu angelegten Elemente mit null initialisiert.5 Vorsicht ist bei newSize=0 geboten, denn setSize(0) bewirkt das Gleiche wie removeAllElements().
Die Vector-Klasse bietet uns für die Konvertierung von Vector-Objekten in Felder eine Methode an.
class java.util.Vector extends AbstractList |
| |
final synchronized void copyInto( Object[] obArray ) Kopiert die Elemente des Vektors in das Array. Falls das bereitgestellte Objektfeld nicht so groß ist wie der Vektor, so tritt eine ArrayIndexOutOfBoundsException auf. |
Der folgende Programmausschnitt erzeugt ein Array für Objektreferenzen und kopiert Referenzen für alle Elemente eines Vektors hinein:
Object obArray[] = new Object[myVector.size()];
myVector.copyInto( obArray );
Noch vor einem weiteren Fehler bei der Aufzählung von Elementen eines Vectors muss gewarnt werden. Da dieser Fehler allerdings in der Version 1.2 behoben wurde, ist nachfolgendes Beispiel nur von historischer Bedeutung. Das folgende Programm fügt einem Vector drei Integer hinzu. Nach dem Hinzufügen besorgen wir uns eine Aufzählung, geben das erste Element aus und löschen es dann. Anschließend geben wir das nächste Element aus.
Listing 11.3 VectorEnumerator.javaimport java.util.*;
public class VectorEnumerator
{
public static void main( String args[] )
{
Vector temp = new Vector();
int i = 0;
temp.addElement( new Integer(i++) );
temp.addElement( new Integer(i++) );
temp.addElement( new Integer(i++) );
Enumeration e = temp.elements();
System.out.println( e.nextElement() );
temp.removeElementAt( 0 );
System.out.println( e.nextElement() );
}
}
Die Programmausführung ergibt folgende Ausgabe:
Exemplarisch sehen wir, wie problematisch es ist, wenn in einer existierenden Aufzählung die Datenstruktur geändert wird. In diesem Fall werden beim Löschen des i-ten Elements die Elemente ab der Position i+1 bis zur Größe des Vektors um eine Stelle verschoben. Damit haben wir aber das Problem, dass jede Aufzählung auf dem Vektor das aktuelle Argument überspringt. In dem oberen Beispiel fehlt uns das Element 1. Mit den Möglichkeiten der Aufzählung unter Verwendung der Schnittstelle Enumeration ist das Problem auch unter 1.2 nicht behoben.
Mit dem Iterator-Interface, das unter 1.2 im Collection-Framework eingeführt worden ist, werden diese Probleme umgangen. Ohne dieses neue Iterator-Interface bleibt uns nichts anderes übrig, als sehr aufmerksam den Vektor zu füllen oder eine eigene Implementierung des Vektors vorzunehmen, der die Löschoperationen sichert, bevor die Aufzählung durch den Vektor vollständig ist.
Enumeration und Iterator verbieten beide Modifikationen an der zu Grunde liegenden Datenstruktur während über die Elemente iteriert wird. Die Iteratoren für die Collection-Klassen aus JDK 1.2 erkennen diesen Verstoß allerdings mit sehr hoher Wahrscheinlichkeit und lösen einen entsprechenden Laufzeitfehler aus. Enumerations verhalten sich einfach nur stillschweigend undefiniert, so wie oben im Beispiel gezeigt. Die obige Konstruktion mit removeElementAt() löst auch mit einem Iterator nur eine Exception aus. Umgangen wird das Problem nur, wenn die remove()-Methode des Iterators verwendet wird. Falls gleichzeitig mehrere Iteratoren über denselben Vektor laufen, gibt es aber immer noch Ausnahmen von anderen Iteratoren, außer dem, dessen remove()-Methode aufgerufen wurde.
Die Vector-Klasse wird, wie wir im nächsten Kapitel sehen werden, von der Klasse Stack erweitert. Dies ist sicherlich aus Sicht des OO-Entwurfs nicht besonders sinnvoll. Was jedoch noch einschränkender ist, ist die Tatsache, dass alle Methoden der Vector-Klasse final sind. Damit gibt es zwar ein wenig mehr Laufzeiteffizienz, was jedoch bei synchronized-Methoden keine große Rolle mehr spielt; es hindert aber dennoch, die Klasse zu erweitern.
Die Klasse Stack repräsentiert einen Stapelspeicher, auch »Keller« genannt, der als LIFO (Last-In-First-Out) Datenstruktur bekannt ist. Beim Hinzufügen von Elementen wächst die Datenstruktur dynamisch. Die Klasse Stack ist eine Erweiterung der Klasse Vector – wir diskutieren später noch einmal diese prickelnde Entscheidung –, womit die Klasse noch zusätzliche Funktionalität besitzt, beispielsweise die Fähigkeit der Aufzählung und des wahlfreien Zugriffs auf Kellerelemente.
Beispiel Füge in den Stack zwei Strings ein und lese sie wieder aus.
Stack s = new Stack(); s.push( "Michaela" ); |
Stack besitzt nur wenig zusätzliche Methoden gegenüber dem Vektor.
class java.util.Stack |
| |
Stack() Der Konstruktor erzeugt einen Stack der Größe null. |
| |
boolean empty() Testet, ob Elemente auf dem Stapel vorhanden sind. |
| |
Object push( Object ) Element vom Typ Object wird auf den Stapel gebracht. |
| |
Object pop( Object ) Holt das letzte Element vom Stapel. EmptyStackException signalisiert einen leeren Stapel. |
| |
Object peek() Das oberste Element wird nur vom Stapel gelesen, aber nicht wie bei pop() entfernt. Beim leeren Stapel wird eine EmptyStackException ausgelöst. |
| |
int search( Object o ) Sucht im Stapel nach dem obersten Eintrag, der mit dem Objekt o übereinstimmt. Gibt den Index zurück oder -1, falls das Objekt nicht im Stapel ist. 1 bedeutet, dass der gesuchte Eintrag ganz oben auf dem Stapelspeicher liegt, 2 bezeichnet die zweitoberste Position usw. Die Zählweise ist ungewöhnlich, denn sie ist nicht null-basiert wie alle anderen Funktionen, die mit Positionen arbeiten. |
| Hinweis Exceptions von Stack: Im Gegensatz zu Vector kann Stack die Exception EmptyStackException erzeugen, um einen leeren Stapel zu signalisieren. Durch einen Rückgabewert null ist ein Fehlschlag nicht angezeigt, da null ein gültiger Rückgabewert sein kann. |
Die Klasse Stack besitzt zwar die Basisfunktionalität, die ein Stapel besitzen sollte, aber auch nicht mehr. Hin und wieder wünschen wir uns aber eine Funktion, die das oberste Stack-Element dupliziert, kurz dup(). Bei der Implementierung treten allerdings zwei Fragen auf, mit denen zwei völlig unterschiedliche Lösungsansätze verbunden sind. Da die Klasse Stack wie die anderen Datenstrukturen auf Objekte ausgelegt ist, müssen wir uns darüber Klarheit verschaffen, wie das obere Objekt dupliziert werden soll. Soll eine Kopie der Objekt-Referenz neu auf den Stapel gelegt werden oder etwa das gesamte Objekt geklont werden?
Die einfachste Lösung besteht darin, das oberste Objekt einfach mittels der schon vorhandenen Stack-Methoden push() und peek() draufzulegen. So sieht die erste Variante so aus:
void dup() throws EmptyStackException
{
st.push( st.peek() );
peek() gibt aber lediglich eine Referenz auf das Objekt zurück. Und das anschließende push() speichert diese Referenz dann auf dem Stapel. Nehmen wir an, wir haben zwei StringBuffer-Objekte auf dem Stapel. Wenn wir nun dup() aufrufen und den String ändern, der oben auf dem Stapel liegt, so ändern wir automatisch das zweite Element gleich mit. Dies ist aber nicht unbedingt beabsichtigt, und wir müssen uns Gedanken über eine alternative Lösung machen. Wir sehen, dass dup() in der Klasse Stack fehlt, weil seine Implementierung davon abhängt, ob eine Referenz- oder eine Wertsemantik für Kellerelemente gewünscht ist.
Um das oberste Stack-Element zu kopieren, bietet sich die clone()-Methode von Object an. All die Objekte, die sich klonen lassen, und das sind längst nicht alle, implementieren das Interface Cloneable. Nun ließe sich einfach folgern: Wenn das zu duplizierende Objekt ein Exemplar von Cloneable ist, dann können wir einfach die clone()-Methoden aufrufen und das zurückgegebene Objekt mittels push() auf den Stapel bringen.
void dup() throws CloneNotSupportedException
{
try {
Objekt top = peek();
if ( top instanceof Cloneable )
push( top.clone() );
} catch ( EmptyStackException e ) { }
void dup() throws CloneNotSupportedException, EmptyStackException
{
push(peek().clone());
Dies funktioniert für die meisten Objekte, allerdings nicht für Objekte der Klasse Object. Denn clone() der Klasse Object ist protected – wir dürfen also von außen nicht dran, nur eine Unterklasse und die Klasse selbst. Hier haben wir also zwei Probleme.
| |
Leider lässt sich nur mit Aufwand überprüfen, ob das Objekt auf dem Stapel auch wirklich ein pures Object ist, denn alle Objekte sind instanceof Object. Glücklicherweise gibt es kaum eine Anwendung, wo reine Object-Elemente gesichert werden müssen. |
| |
Was machen wir mit Objekten, die nicht klonbar sind? Leider gibt es für diese Frage keine direkte Antwort. Eine universelle Stack-Klasse mit einer uneingeschränkten dup()-Methode gibt es nicht. Wir müssen als Stack-Benutzer festlegen, dass das oberste Element Clonable ist, um zumindest eine eigene Implementierung nutzen zu können. Oder wir bleiben dabei, bei nicht klonbaren Objekten doch nur die Referenz zu duplizieren. Das wäre zumindest für eineindeutige Objekte mit Wertsemantik die ideale Lösung. |
Eine genaue Betrachtung der Klasse Stack zeigt den unsinnigen und falschen Einsatz der Vererbung. Stack erbt alle Methoden von Vector und damit viele Funktionen, die im krassen Gegensatz zu den charakteristischen Eigenschaften eines Stapels stehen. Dazu zählen add(), addAll(), addElement(), capacity(), clear(), clone(), contains(), copyInto(), elementAt(), elements(), ensureCapacity(), firstElement(), get(), indexOf(), insertElement-At(), isEmpty(), lastElement(), lastIndexOf(), remove(), removeAllElements(), removeElement(), removeElementAt(), removeRange(), set(), setElementAt(), setSize(), size(), toArray(), trimToSize().
|
Für eine Änderung ist es aber nun auf Grund der Wahrung der Abwärtskompatibilität zu spät und die Implementierung bleibt. Sie hätte mit einem internen Vector oder einer ähnlichen Datenstruktur erfolgen müssen. Bleibt die Frage, warum sich der Autor Jonathan Payne für jene Variante entschieden hat. Aus Sicht der Softwaretechnik ist die Frage nicht so leicht zu beantworten. Hier stehen sich Kaufen (Delegation oder Komposition, also Verwenden eines Objekts) oder Erben (also Erweitern einer Klasse) gegenüber. Das Einzige, was wir als Programmierer aus diesem Missgeschick lernen können, ist die gründliche Analyse der Klassenbeziehungen. In einem Konflikt zwischen Kaufen und Erben sollte immer Kaufen statt Erben eingesetzt werden. Im Übrigen ist Jonathan Payne auch Autor der Klasse Vector.
Die Klasse BitSet bietet komfortable Möglichkeiten zur bitweisen Manipulation von Daten. Das Datum kann beliebig groß sein, und über Methoden von BitSet, lassen sich die einzelnen Bits leicht ändern. Zudem lassen sich Bits wie in einem Vektor zufügen, und das Objekt verwaltet selbstständig die Größe. Ein leeres BitSet wird mit dem Standard-Konstruktor angelegt. Ein weiterer Konstruktor erlaubt eine Startgröße, die ein Vergrößern aufschiebt.
Jedes Bit besitzt zwei Zustände: gesetzt oder nicht gesetzt. Dies bringt sie in die Nähe der booleschen Werte, die ebenso zwei Zustände besitzen. Mit zwei Methoden lassen sich die Bits des BitSet leicht ändern: set(bitNummer) und clear(bitNummer). Da der Bit-Container automatisch wächst, ist es problemlos möglich, in einem BitSet-Exemplar mit 100 Bits, das Bit 300 zu setzen. Das Objekt wird automatisch mit 200 Null-Bits aufgefüllt, bevor das Bit 300 gesetzt wird.
Über die Methode size() erfahren wir, wie viele Bits das Objekt umfasst. Spannender ist die Methode length(). Sie liefert die Position des höchsten gesetzten Bits In size() werden überzählige führende Null-Bits mitgezählt, ähnlich wie ungenutzte Array-Elemente im capacity()-Wert eines Vektors. Die Abfrage, ob ein Bit gesetzt ist, erfolgt mit der Methode get(bitNummer). Sie gibt true zurück, falls das Bit gesetzt ist, andernfalls false.
|
Beispiel Setze in einem BitSet das erste und dritte Bit.
BitSet bs = new BitSet(); bs.set( 0 ); |
Das BitSet erlaubt mengenorientierte Operationen mit einer weiteren Menge. Jedes Bit, der im Parameter übergebenen Menge, wird mit dem Objekt in einer bestimmten Weise verknüpft. Das Ergebnis der Operation wird dem aktuellen Objekt zugewiesen. Drei Operationen sind verfügbar: Die Oder-Operation setzt das Bit, falls es im Objekt gesetzt ist oder das Bit im zweiten BitSet gesetzt ist. Die Und-Operation setzt das Bit, falls es im Objekt gesetzt ist und das Bit im zweiten BitSet gesetzt ist. Die Xor-Operation setzt das Bit, falls es nur in einem der beiden Objekte gesetzt ist. Damit werden die Operationen Mengenvereinigung, Durchschnitt und symmetrischer Durchschnitt implementiert.
Die Funktionen von BitSet sind überschaubar. Leider existieren keine Methoden, die Bits aus anderen Quellen, etwa einem Bitfeld aus byte[], übernehmen und einfügen. Da BitSet nicht final ist, können wir diese Zusatzfunktionalität in einer Unterklasse realisieren.
class java.util.BitSet |
| |
BitSet() Erzeugt ein neues BitSet-Objekt. |
| |
BitSet( int ) Erzeugt ein BitSet mit vorgegebener Größe. Alle Bits sind am Anfang auf false gesetzt. Ist die Größe kleiner Null, so wird eine NegativeArraySizeException ausgelöst. |
| |
void andNot( BitSet set ) Löscht alle Bits im Bitset, die dort set gesetzt sind. |
| |
void set( int ) void clear( int ) Setzt oder löscht ein Bit. Ist der Index negativ, wird eine IndexOutOfBoundsException ausgelöst6 . |
| |
boolean get( int ) Liefert der Wert des Bits am übergebenen Index. Kann bei negativem Index wieder IndexOutOfBoundsException auslösen. |
| |
void and( BitSet ) void or( BitSet) void xor( BitSet ) Verknüpft dieses BitSet-Exemplar per Und-, Oder-, Xor-Operation mit dem angegebenen BitSet-Objekt. |
| |
boolen equals( Object o ) Vergleicht sich mit einem anderen BitSet-Objekt o. |
Eine Optimierung der Geschwindigkeit war es, die Methoden der Klasse BitSet nicht zu synchronisieren. Greift also ein Thread auf die Daten zu, während ein anderer modifiziert, kommt es zu möglichen Inkonsistenzen. Witzigerweise ist in der API-Dokumentation die Methode hashCode() im Quellcode als synchronized abgedruckt. In der echten Implementierung fehlt aber diese Synchronisation.
Das folgende Programm zeigt die Anwendung der Klasse BitSet am Beispiel der Konstruktion der Menge von Primzahlen. Jedes gesetzte Bit entspricht einer Primzahl. In diesem Fall ist der Einsatz der Klasse BitSet angebracht, da eine Zahl in einem Wertebereich nur eine Primzahl oder keine sein kann.
Listing 11.4 Primtest.javaimport java.util.*;
class Primtest
{
final static int MAXPRIM = 30;
public static void main( String args[] )
{
BitSet b = new BitSet();
for ( int i = 2; i <= MAXPRIM; i++ )
{
boolean ok = true;
for ( int j = 2; j < i; j++ )
if ( b.get(j) && (i % j) == 0 ) {
ok = false;
break;
}
if ( ok )
b.set(i);
}
for ( int i = 1; i <= MAXPRIM; i++ )
if ( b.get(i) )
System.out.println( "" + i );
}
