public interface AggregatSchnittstelle {
Iterator createIterator();
}
public interface IteratorSchnittstelle {
public void start();
public void next();
public boolean finished();
public Object element();
}
public abstract class Iterator implements IteratorSchnittstelle {
}
public class Liste implements AggregatSchnittstelle, ListenSchnittstelle {
private int size;
Object list[];
// get,set and append in O(ld(n))
// delete in O(n)
// size in O(1)
Liste () {
this(1024);
}
Liste (int initSize) {
if (initSize<1) initSize=1024;
list=new Object[initSize];
size=0;
}
public Iterator createIterator() {
return new ListenIterator(this);
}
public void append( Object o ) {
size++;
if (list.length<=size) {
Object tmpList[]=new Object[ (list.length)+32768];
for (int i=0;i<list.length;i++)
tmpList[i]=list[i];
list=tmpList;
}
list[size-1]=o;
}
public Object get(int index) throws IllegalArgumentException {
if (index>=size) throw new IllegalArgumentException("Liste: Index out of bounds");
return list[index];
}
public void set(int index, Object o) throws IllegalArgumentException {
if (index>=size) throw new IllegalArgumentException("Liste: Index out of bounds");
list[index]=o;
}
public void delete(int index) throws IllegalArgumentException {
if (index>=size) throw new IllegalArgumentException("Liste: Index out of bounds");
for (int i=index;i<size-1;i++)
list[i]=list[i+1];
size--;
}
public int size() {
return size;
}
}
public class ListenIterator extends Iterator implements IteratorSchnittstelle {
ListenIterator(Liste l) {
this.l=l;
curIndex=0;
}
private Liste l;
private int curIndex;
public void start() { curIndex=0; }
public void next() { curIndex++; if (curIndex>=l.size()) curIndex--; }
public boolean finished() { return (curIndex==l.size()-1); }
public Object element() { return l.list[curIndex]; }
}
public interface ListenSchnittstelle {
/**
* Hängt ein Objekt hinten an die Liste an
*
* @param o das Objekt, das hinten angehängt werden soll
*/
public void append( Object o );
/**
* Gibt das Objekt aus der Liste zurück, das an der Stelle index in der Liste
* steht.
*
* @param index die Position des Objektes, das zurückgegeben werden soll
* @return das Objekt, das an der index-ten Stelle dieser Liste gespeichert ist
* @throws IllegalArgumentException wenn der Parameter index zu klein oder zu
* groß ist
*/
public Object get( int index ) throws IllegalArgumentException;
/**
* Ersetzt das Objekt an der Stelle index in der Liste durch das übergebene
* Objekt.
*
* @param index die Position, an der der Austausch vorgenommen werden soll
* @param o das Objekt, das eingetragen werde soll
* @throws IllegalArgumentException wenn der Parameter index zu klein oder zu
* groß ist
*/
public void set( int index, Object o ) throws IllegalArgumentException;
/**
* Löscht das Element an der Position index aus der Liste. Die nachfolgenden
* Elemente rutschen dann einen Platz nach vorne.
*
* @param index die Position, an der das element gelöscht werden soll.
* @throws IllegalArgumentException wenn der Parameter index zu klein oder zu
* groß ist
*/
public void delete( int index ) throws IllegalArgumentException;
/**
* Die Anzahl der Elemente in der Liste.
* @return eine Zahl >= 0
*/
public int size();
}
import java.lang.*;
public class Menge implements MengenSchnittstelle ,AggregatSchnittstelle {
public Iterator createIterator() {
return new MengenIterator(this);
}
class Elem {
Elem(Object o) {
this.o=o;
next=null;
}
Object o;
Elem next;
}
Elem hash[];
Menge() {
this(1024);
}
Menge(int hashSize) throws IllegalArgumentException {
if (hashSize<1) throw new IllegalArgumentException("Menge: hash size must be 1 or greater");
hash=new Elem[hashSize];
}
public void add(Object o) {
int hashval=o.hashCode() % hash.length;
if (hash[hashval]==null) {
hash[hashval]=new Elem(o);
return;
}
Elem cur=hash[hashval];
while (cur.next!=null) {
if (o.equals(cur.o)) return;
cur=cur.next;
}
if (o.equals(cur.o)) return;
cur.next=new Elem(o);
}
public void remove(Object o) {
int hashval=o.hashCode() % hash.length;
Elem cur=hash[hashval];
if (cur==null) return;
if (o.equals(cur.o)) {
hash[hashval]=cur.next;
return;
}
while (cur.next!=null) {
if (o.equals(cur.next.o)) {
cur.next=cur.next.next;
return;
}
cur=cur.next;
}
}
public boolean contains(Object o) {
int hashval=o.hashCode() % hash.length;
Elem cur=hash[hashval];
while (cur!=null) {
if (o.equals(cur.o)) return true;
cur=cur.next;
}
return false;
}
}
public class MengenIterator extends Iterator {
private int hashval;
private Menge.Elem curElem;
private Menge m;
MengenIterator(Menge m) {
this.m=m;
hashval=-1;
curElem=null;
}
public void start() {
hashval=0;
while (hashval<m.hash.length && m.hash[hashval]==null) {
hashval++;
}
if (m.hash[hashval]==null) { hashval=0; return; }
curElem=m.hash[hashval];
}
public void next() {
int startHashval=hashval;
if (curElem==null) return;
if (curElem.next==null) {
hashval++;
while (hashval<m.hash.length && m.hash[hashval]==null)
hashval++;
if (m.hash[hashval]==null) { hashval=startHashval; return; }
curElem=m.hash[hashval];
return;
}
curElem=curElem.next;
}
public boolean finished() {
if (curElem.next!=null) return false;
for (int i=hashval+1;i<m.hash.length;i++)
if (m.hash[i]!=null) return false;
return true;
}
public Object element() {
return curElem.o;
}
}
public interface MengenSchnittstelle {
/**
* Fügt ein Objet der Menge zu. Wenn es schon in der Menge enthalten ist,
* passiert nichts. Die
* Berechnung dieser Methode basiert auf Object.equals() und/oder auf
* Object.hashCode().
*
* @param o Das Objekt, das hinzugefügt werden soll
*/
public void add( Object o );
/**
* Entfernt das Objekt übergebene aus der Menge, wenn es in ihr enthalten ist.
* Wenn es nicht in der Menge enthalten ist, passiert nichts. Die Berechnung
* dieser Methode basiert auf Object.equals() und/oder auf Object.hashCode().
*
* @param o Das Objekt, das aus der Menge entfernt werden soll.
*/
public void remove( Object o );
/**
* Prüft, ob ein Objekt in einer Menge enthalten ist. Die Berechnung dieser
* Methode basiert auf Object.equals() und/oder auf Object.hashCode().
*
* @param o Das Objekt, dessen Enthaltensein geprüft werde soll
* @return Gibt true zurück, wenn das Objekt in der Menge enthalten ist, sonst
* false.
*/
public boolean contains( Object o );
}