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 );
}