with Ada.Text_IO;
use Ada.Text_IO;

package body Search_Trees is

   procedure Create (Anchor : in out Ref_Cell)
   is
   
   begin
      Anchor := null;
   end Create;

--  Suchen ob es das gleiche Element schon gibt Ergebnis gibt aus ob es etwas
--  gefunden hat;
   function Search (Anchor : Ref_Cell; Eingabe : Ref_Cell) return Boolean
   is
      Zeiger1 : Ref_Cell;
      Gefunden : Boolean := False;
      NGefunden : Boolean := False;
      Ergebnis : Boolean := False;
      Vergleich : Integer := 0;
   begin
      Zeiger1 := Anchor;
      if Zeiger1 /= null then
         while Gefunden = False or NGefunden = False loop
            if Zeiger1.Inhalt < Eingabe.Inhalt then
               if Zeiger1.Right /= null then
                  Zeiger1 := Zeiger1.Right;
               else
                  NGefunden := True;
               end if;
               Vergleich := Vergleich + 1;
            else
               if Zeiger1.Left /= null then
                  Zeiger1 := Zeiger1.Left;
               else
                  NGefunden := True;
               end if;
               Vergleich := Vergleich + 1;
            end if;
            if Zeiger1.Inhalt = Eingabe.Inhalt then
               Gefunden := True;
            end if;
         end loop;
      end if;
      NGefunden := True;
      if Gefunden = True then
         Ergebnis := True;
      end if;
      Put ("Anzahl der benoetigten Vergleiche : " & Vergleich'Img);
      return Ergebnis;
   end Search;
   
--  Sucht nach der Stelle wo man das Zusaetzliche Element einfuegen kann und
--  fuegt es ein wenn es das Element noch nicht gibt;
   procedure Insert (Anchor : in out Ref_Cell; Eingabe : Ref_Cell)
   is
      Eingesetzt : Boolean := False;
      Ergebnis : Boolean := False;
      Zeiger1 : Ref_Cell;
      Vergleich : Integer := 0;
   begin
      Zeiger1 := Anchor;
      if Zeiger1 /= null then
         Ergebnis := Search (Anchor, Eingabe);
         if Ergebnis = False then
            while Eingesetzt = False loop
               if Zeiger1.Inhalt < Eingabe.Inhalt then
                  if Zeiger1.Right /= null then
                     Zeiger1 := Zeiger1.Right;
                  else
                     Zeiger1.Right := Eingabe;
                     Eingesetzt := True;
                  end if;
                  Vergleich := Vergleich + 1;
               else
                  if Zeiger1.Left /= null then
                     Zeiger1 := Zeiger1.Left;
                  else
                     Zeiger1.Left := Eingabe;
                     Eingesetzt := True;
                  end if;
                  Vergleich := Vergleich + 1;
               end if;
            end loop;
         end if;
      else
         Zeiger1 := Eingabe;
      end if;
      Anchor := Zeiger1;
      Put ("Anzahl der Vergleiche zum Einfuegen: " & Vergleich'Img);
   end Insert;

   procedure BaumH (Anchor : Ref_Cell)
   is
      Zeiger1 : Ref_Cell;
      ZeigerPrev : Ref_Cell;
   begin
      Zeiger1 := Anchor;
      while Zeiger1.Left /= null loop
         ZeigerPrev := Zeiger1;
         Zeiger1 := Zeiger1.Left;
         Hoehe1 := HoeheH + 1;
      end loop;
      Zeiger1 := ZeigerPrev;
      Hoehe2 := Hoehe1;
      if Zeiger1.Right /= null then
         Zeiger1 := Zeiger1.Right;
         while Zeiger1 /= null loop
            ZeigerPrev := Zeiger1;
            Zeiger1 := Zeiger1.Left;
            Hoehe2 := Hoehe2 + 1;
         end loop;
      else
--  noch nicht fertig... überlegung wie man den baum absucht..das nach der while schleife verbessern!!
         null;
      end if;
end Search_Trees;