/**
Die Klasse "AngeboteTree" hält eine Liste von Instanzen der Klasse
"Angebot".

Die Verwaltung der Liste funktioniert über einen binären Baum.

Anmerkung: Dieser Code ist nicht zeitoptimiert, um ein hohes Maß an
           Verständlichkeit für den Quelltext zu erreichen.

Interface AngeboteTree:

    public double bestesAngebot( )
    public double bestesAngebot( boolean DeleteIfEmpty )
    public int Count()
    public void einfuegen(double Preis, int Anzahl)
**/

class AngeboteTree {

        // ********** public **********

        /*
        Diese Methode ist zur Abwärtskompatibilität enthalten.
        */
        public double bestesAngebot( ) {
            return bestesAngebot( false );
        }

        /*
        Liefert das billigste verfuegbare Angebot.
        Der Zähler für die Anzahl wird dabei um 1 dekrementiert.
        Wird (DeleteIfEmpty) übergeben, wird das Angebot gelöscht, wenn
        der Zähler den Wert 0 erreichen sollte.

        Liefert -1 zurück, wenn kein einziges Angebot lieferbar ist

        Die Methode profitiert davon, daß jedes Angebot in einer Anzahl > 1
        vorliegen muß.
        */
        public double bestesAngebot( boolean DeleteIfEmpty ) {

            double result = -1;
            Angebot entry = fFirstEntry;
            Angebot LastEntry = null;

            // Das Angebot "links unten" suchen
            if (entry != null) {
                while (entry.left != null) {
                    LastEntry = entry;
                    entry = entry.left;
                }

                result = entry.preis();
                // Referenzzähler erniedrigen
                entry.DecVerfuegbarkeit();
                // Wenn Referenzzähler==0 -> löschen
                if (entry.verfuegbarkeit() == 0)
                    LastEntry.left = entry.right;
            }

            return result;
		}

		// Fuegt ein neues Angebot ein, das in Anzahl Stueck verfuegbar ist.
		// Weil die Liste sortiert ist, wird es entsprechend seinem Preis
		// einsortiert.
		public void einfuegen(double Preis, int Anzahl)
		{
            // Fehlerprüfung
            if (Anzahl > 0) {
                // Position des Elementes suchen
                Angebot entry = fFirstEntry;
                Angebot LastEntry = null;

                boolean done = false;

                while ((! done) & (entry != null)) {
                    // entscheiden, ob linker oder rechter Pfad verfolgt wird
                    if ( Preis < entry.preis() ) {
                        LastEntry = entry;
                        entry = entry.left;
                    }
                      else
                        if (Preis>entry.preis()) {
                            LastEntry = entry;
                            entry = entry.right;
                        }
                          else
                        if (Preis == entry.preis()) {
                            LastEntry = entry;
                            done = true;
                         }

                    if (entry == null)
                        done = true;
                }

                // neuen Eintrag einfügen
                Angebot NewEntry = new Angebot( Preis, Anzahl );


                if (LastEntry != null) {
                    if (Preis < LastEntry.preis())
                        LastEntry.left = NewEntry;
                      else
                        if (Preis > LastEntry.preis())
                            LastEntry.right = NewEntry;
                          else
                            if (Preis == LastEntry.preis()) {
                                NewEntry.right = LastEntry.right;
                                LastEntry.right = NewEntry;
                            }
                }
                  else
                    fFirstEntry = NewEntry;


            }
		}

		// liefert die Anzahl der belegten Einträge im Ordner. Diesen Wert
		// später evtl. in einer Variable buffern.
		public int Count() {
                int i = 0;
                if (fFirstEntry != null)
                    i++;
                i = i + ChildrenCount( fFirstEntry );
		    return i;
		}

        // ********** private **********

        // hält die Angebote
		private Angebot fFirstEntry;

		// Liefert die Anzahl der Unterelemente eines Knotens zurück
		private int ChildrenCount( Angebot entry ) {
		    int result = 0;
		    if (entry != null) {
  		        if (entry.left != null)
  		            result++;
  		        if (entry.right != null)
  		            result++;
  		        result = result + ChildrenCount( entry.left );
  		        result = result + ChildrenCount( entry.right );
		    }

		    return result;
		}

		// Sucht ein Angebot nach dem Preiskriterium.
		// Es wird der Index zurückgegeben, den ein neues Element mit dem
		// angegebenen Preis erhalten muß.
		// Ist die Liste leer, wird 0 zurückgegeben.
		private int fListPosition( double preis ) {
		    int result = 0;

		    if (Count() > 0) {
		        Angebot entry = fFirstEntry;
		        // erhöhen, wenn noch ein Angebot existiert, und dieses Angebot
		        // einen höheren Preis hat.
                while ((entry != null) && (entry.preis() < preis)) {
                    result++;
                    entry = entry.next;
                }
		    }
  		    return result;
		}

}