JAVA stellt einige Standard-Klassen für Collections zur
Verfügung. Um aber Interfaces noch einmal zu illustrieren,
implementieren wie hier selber zwei.
Eine Collection nach unserer Vorstellung sollte die im folgenden Interface
zusammengefaßten Funktionen zur Verfügung stellen:
- interface collection
{
void addElement(Object o); // Element einfügen
boolean contains(Object o); // ist Element enthalten?
void deleteElement(Object o); // Element löschen
void toStart(); // Cursor an den Anfang
Object getNext(); // ein Element lesen, Cursor weitersetzen
}
Neben den selbstverständlichen Funktionen zum Einfügen, Testen und
Löschen fordern wir also die letzten beiden, mit deren Hilfe man die ganze
Collection durchlaufen kann, ohne ihren inneren Aufbau kennen zu müssen.
Es gibt durchlaufbare Stukturen in JAVA, sogenannte
Enumerations. Wenn man aber beispielsweise eine Hashtabelle vorliegen
hat, muß sie zum Durchlaufen zunächst in eine Enumeration
umgewandelt werden. Wir wollen hier die Möglichkeiten zum
Einfügen/Löschen und zum Durchlaufen miteinander verbinden.
Als einfachste Collection-Klasse folgt nun simpleVector, der intern
mit einem Array von Object arbeitet, das bei Bedarf
vergrößert wird -- wobei also alle enthaltenen Referenzen (nicht
Objekte!) kopiert werden müssen.
- class simpleVector implements collection
{
private int size;
private int numObj;
private Object[] theData;
private int cursor;
public simpleVector(int s)
{
theData=new Object[size=s];
numObj=cursor=0;
}
public simpleVector() { this(16); }
public boolean contains(Object o)
{
for (int i=0;i<numObj;++i)
if (theData[i].equals(o)) return true;
return false;
}
public void addElement(Object o)
{
if (numObj==size)
{
int newsize=size+(size<<1);
Object[] newArray=new Object[newsize];
System.arraycopy(theData,0,newArray,0,size);
theData=newArray;
size=newsize;
}
theData[numObj++]=o;
}
public void deleteElement(Object o)
{
for (int i=0;i<numObj;++i)
if (theData[i].equals(o))
{
System.arraycopy(theData,i+1,theData,i,size-i-1);
--numObj;
return;
}
}
public void toStart() { cursor=-1; }
public Object getNext()
{
return (++cursor>=numObj)?null:theData[cursor];
}
}
Für Datentypen mit einer linearen Ordnung bietet sich eher eine Collection
an, die diese Ordnung in ihrem inneren Aufbau ausnutzt. Bei Vergleichen
(in contains(),
deleteElement()) kann dann
gegebenenfalls frühzeitig abgebrochen werden.
Zum Suchen und Löschen müssen wir die Elemente lediglich auf
Gleichheit testen, wie wir es in simpleVector mit
equals() getan haben.
Für eine Relation <= definieren wir zusätzlich ein Interface
ordered mit einer Vergleichsfunktion
compare(), die Werte
<0, 0, >0 ähnlich wie strcmp()
zurückgeben soll:
- interface ordered
{
int compare(ordered o2);
}
Wenn wir (zum Testen der Collections) eine Klasse oInt für
Integers definieren wollen, die dieses Interface implementiert, können wir
leider nicht von der Klasse Integer erben, da diese (aus
Effizienzgründen) final ist. Wir definieren oInt
deshalb der Einfachheit halber direkt mit einem int-Datenmember.
- class oInt implements ordered
{
public int i;
public oInt(int j) { i=j; }
public oInt() { this(0); }
public boolean equals(Object j) { return i==((oInt)j).i; }
public int compare(ordered j) { return i-((oInt)j).i; }
public String toString() { return (new Integer(i)).toString(); }
}
Außerdem überschreiben wir hier equals() und
toString() von Object.
Entsprechend folgt noch eine Collection, die auf einer linearen Ordnung
aufbaut, nämlich eine (einfache) sortierte Liste.
In den collection-Schnittstellen muß sie selbstverständlich
mit Object-Argumenten arbeiten. Intern verwendet sie dagegen
ordered, wobei sie gelegentlich auf entsprechende Downcasts
Object -> ordered zurückgreifen muß.
Natürlich kann man keine ordered-Objekte anlegen. Das Interface
wird hier wie eine abstrakte Basisklasse verwendet.
Wenn wir dagegen oInt-Objekte in die Liste eintragen, brauchen wir die
Upcasts oInt -> Object bzw.
oInt -> ordered
nicht explizit anzugeben.
- class sortedList implements collection
{
class sortedNode
{
public ordered data;
public sortedNode next;
public sortedNode(ordered o, sortedNode n) { data=o; next=n; }
}
private sortedNode root,cursor;
public sortedList() { root=null; }
public void addElement(Object o)
{
ordered oo=(ordered)o;
if (root==null) root=new sortedNode(oo,null);
else if (oo.compare(root.data)<=0) root=new sortedNode(oo,root);
else
{
sortedNode run=root;
while (run.next!=null && oo.compare(run.next.data)>0)
run=run.next;
run.next=new sortedNode(oo,run.next);
}
}
public boolean contains (Object o)
{
ordered oo=(ordered)o;
for (sortedNode run=root;run!=null;run=run.next)
{
int c=run.data.compare(oo);
if (c==0) return true;
if (c<0) return false;
}
return false;
}
public void deleteElement(Object o)
{
ordered oo=(ordered)o;
if (oo.compare(root.data)==0) root=root.next;
else
for (sortedNode run=root;run!=null;run=run.next)
{
int c=oo.compare(run.next.data);
if (c>=0)
{
if (c==0) run.next=run.next.next;
break;
}
}
}
public void toStart() { cursor=null; }
public Object getNext()
{
cursor=(cursor==null)?root:cursor.next;
return (cursor==null)?null:(Object)cursor.data;
}
}
Als letztes schreiben wir eine Test-Klasse ctest, die zum Testen
jeder Collection im obigen Sinn dienen kann:
- public class ctest
{
public static void test_collection(collection c)
{
System.out.println("\nTest mit "+c.getClass());
c.addElement(new oInt(2));
c.addElement(new oInt(1));
c.addElement(new oInt(3));
for (int i=0;i<=1;++i)
{
Object o;
System.out.println("Inhalt:");
for (c.toStart();(o=c.getNext())!=null;)
System.out.println("\t"+o);
System.out.println("1 ist "
+(c.contains(new oInt(1))?" ":"nicht ")+"enthalten");
if (i==0)
{
c.deleteElement(new oInt(1));
System.out.println("1 gel[["]]oscht");
}
}
}
public static void main(String[] args)
{
test_collection(new simpleVector());
test_collection(new sortedList());
}
}
Beide Collections bestehen den Test mit unserer Testklasse.
In der Ausgabe unten sieht man gut, wie die erste Collection die Elemente
in der Reihenfolge speichert, wie sie eingefügt wurden, die zweite in der
dem Typ zugrundeliegenden Ordnung.
-
|
Test mit class simpleVector
Inhalt:
2
1
3
1 ist enthalten
1 gelöscht
Inhalt:
2
3
1 ist nicht enthalten
|
Test mit class alphaList
Inhalt:
1
2
3
1 ist enthalten
1 gelöscht
Inhalt:
2
3
1 ist nicht enthalten
|
25.5: Abstrakte Methoden
