/** Eine Klasse fuer Queues ("Schlangen"). Eine Queue ist eine
    dynamische Datenstruktur, in die man eine beliebige hohe 
    Anzahl von Objekten einfuegen und die in ihr vorhandenen
    wieder aus herausnehmen kann. Dabei gilt das FIFO-Prinzip
    ("first in first out"): Das zuerst eingefuegte Element ist
    auch dasjenige, das zuerst herausgenommen wird - ganz wie
    bei einer Supermarkt-Schlange.
*/

public class FIFO
{
    private Object[] schlange;
    private int laenge = 1;// zunaechst hier den "magischen Wert" 10 gehabt
    private int naechsterLeseindex;
    private int naechsterSchreibindex;

    /** Erzeugt eine leere Schlange. */
    public FIFO()
    {
	schlange = new Object[laenge];
	naechsterLeseindex = 0;
	naechsterSchreibindex = 0;
	
    }

    /** Fuegt ein Element x in die Schlange ein.
	@param x das einzufuegende Element */
    public void in(Object x)
    {
	/* Was jetzt kommt, ist nicht von optimaler Effizienz - weder im
	   Hinblick auf den Speicherplatzbedarf noch auf den Rechenzeitbedarf.
	   Man könnte ja alle Speicherstellen von 0 bis vor den nächsten
	   Leseindex noch vollschreiben. Dies ist geschehen in der
	   Implementierung, die Sie zum Practical 2 auf der WWW-Seite fanden */
	
	if (naechsterSchreibindex == laenge){
	    int neueLaenge = 2 * laenge;
	    Object[] neueSchlange = new Object[neueLaenge];
	    int j =0;
	    for (int i = naechsterLeseindex; i<laenge; i++){
		neueSchlange[j] = schlange[i];
		j++;
	    }
	    schlange = neueSchlange;
	    laenge = neueLaenge;
	    naechsterLeseindex = 0;
	    naechsterSchreibindex = j;
	    /* Der Kniff mit der Variablen j erlaubt es bloß, ein klein wenig
	       Arithmetik zu vermeiden. */
	}
	schlange[naechsterSchreibindex] = x;
	naechsterSchreibindex++;
    }

    /** Liefert aus einer nicht-leeren Schlange das Element, das unter den
	in der Schlange vorhandenen zuerst eingetragen wurde. Ist die
	Schlange leer, so wird null zurueckgeliefert.
	@return das Element */
    public Object out()
    {
	if (empty()){
	    return null;
	}
	else{
	    Object x = schlange[naechsterLeseindex];
	    naechsterLeseindex++;
	    return x;
	    // viel einfacher als die 3 Zeilen wäre
	    // return schlange[naechsterLeseindex++];
	    // ++ nachgestellt besagt nämlich, daß der Index erst erhöht wird,
	    // nachdem bereits schlange an dem Index abgefragt wurde
	}
    }

    /** Testet, ob die Schlange leer ist. */
    public boolean empty()
    {
	return (naechsterLeseindex == naechsterSchreibindex);
    }
}
