program avlBaum;

Uses Crt;

type NodePtr = ^Node;
     PTree   = ^Tree;

     Node = record
               SVNR:         String[10];
               Groesse:      Integer;
               Geschlecht    :Char;
               Name:         string[80];
               links,rechts: NodePtr;
               higher:       (left,none,right)
            end;

     Tree = object
                  root: NodePtr;
                  Search,Rot,Depth,Dat    :integer;

                  constructor init;
                  Destructor DisposeTree(Hp,Hptr:NodePtr);
                  procedure Insert(Var Hp,neu: NodePtr; Var grow: Boolean);
                  function Knoten (svnr :string;groesse :integer; geschlecht :char; name:string):NodePtr;
                  Procedure AusgRek(P:NodePtr);
                  Procedure MaxTiefe(P:NodePtr;Var Temp, Max:Integer);
                  Procedure Checkhight(P:Nodeptr);
                  procedure Ausgabe;
                  Function SearchTree(Var Hptr:NodePtr;SVNR:String):NodePtr;
            end;
     Datei = object
                  command       :Char;
                  SVNR          :String[10];
                  Name          :string;
                  Geschlecht    :Char;
                  Groesse       :integer;
                  F             :Text;
                  Temp          :Node;

                  constructor init;
                  destructor done;
                  function openLog(Filename: string):Boolean;
                  function readcommand: Boolean;
                  function readSVNR: Boolean;
                  function readGes: Boolean;
                  function readGr: Boolean;
                  function readName: Boolean;
                  function ignorespace: char;
                  function readLog:integer;
             end;

constructor Tree.init;
begin
     root:= Nil;
     Dat:=0;
end;

constructor Datei.init;
begin
     command:=' ';
     SVNR:='          ';
     Groesse:=0;
     Name:='unbekannt';
     Geschlecht:=' ';
end;

destructor Datei.done;
begin
end;

Procedure Tree.MaxTiefe(P:Nodeptr;Var Temp, Max:Integer);

Begin
 If P<>Nil then Begin
  Inc(Temp);
  If Temp>Max then Max:=Temp;
  MaxTiefe(P^.links,Temp,Max);
  MaxTiefe(P^.rechts,Temp,Max);
  Dec(Temp);
 End;
End;

Procedure Tree.Checkhight(P:Nodeptr);
Var R,L,Max,Temp:Integer;
Begin
  Max:=0;
  Temp:=0;
  MaxTiefe(P^.rechts,Temp,MAX);
  R:=Max;
  Max:=0;
  Temp:=0;
  MaxTiefe(P^.links,Temp,MAX);
  L:=Max;
  If L>R then P^.higher:=left else
   If L=R then P^.higher:=none else
     P^.higher:=right;
End;

function Tree.Knoten (svnr :string;groesse :integer; geschlecht :char; name:string):NodePtr;
var
   HP :NodePtr;
begin
  New(HP);
  HP^.SVNR:=svnr;
  HP^.Groesse:=groesse;
  HP^.Geschlecht:=geschlecht;
  HP^.Name:=name;
  HP^.links:=Nil;
  HP^.rechts:=Nil;
  HP^.higher:=none;
  Knoten:=HP;
end;

Procedure Tree.Insert(Var Hp,neu: NodePtr; Var grow: Boolean);
Var Hptr: NodePtr;
Begin
 Search:=Search+1;
 If (Hp=nil) Then Begin
  Hp:=neu;
  Dat:=Dat+1;
  grow:=True;
 End Else
  With Hp^ do Begin
   If (neu^.SVNR > SVNR) Then Begin
    Insert(rechts,neu,grow);
    If grow Then
     Case higher of
      left : Begin
             higher:=none;
             grow:=False;
             End;
      none: higher:=right;
      right : Begin
              If HP^.rechts^.higher=right Then Begin
               Inc(Rot);
               Hptr:=Hp^.rechts;
               Hp^.rechts:=Hptr^.links;
               Hp^.higher:=none;
               Hptr^.links:=Hp;
               Hp:=Hptr;
               Hp^.higher:=none;
              End Else Begin
               Rot:=Rot+2;
               (* Dplt. Rotation *);
               Hptr:=Hp^.rechts;
               Hp^.rechts:=Hp^.rechts^.links;
               Hptr^.links:=Hp^.rechts^.rechts;
               Hp^.rechts^.rechts:=Hptr;

               Hptr:=Hp^.rechts;
               Hp^.rechts:=Hp^.rechts^.links;
               Hptr^.links:=Hp;

               Hp:=Hptr;
               (* H”he richtig setzen*)
               checkhight(Hp);
               checkhight(Hp^.rechts);
               checkhight(Hp^.links);
              End;
              grow:=False;
              End;
     End; (* Case *)
   End Else Begin  (* symmetrisch zum Then-Zweig *)
    Insert(links,neu,grow);
    If grow Then
     Case higher of
      right: Begin
             higher:=none;
             grow:=False;
             End;
      none: higher:=left;
      left: Begin
              If HP^.links^.higher=left Then Begin
               Inc(Rot);
               Hptr:=Hp^.links;
               Hp^.links:=Hptr^.rechts;
               Hp^.higher:=none;
               Hptr^.rechts:=Hp;
               Hp:=Hptr;
               Hp^.higher:=none;
              End Else Begin
               Rot:=Rot+2;
               (* Dplt. Rotation *)
               Hptr:=Hp^.links;
               Hp^.links:=Hp^.links^.rechts;
               Hptr^.rechts:=Hp^.links^.links;
               Hp^.links^.links:=Hptr;

               Hptr:=Hp^.links;
               Hp^.links:=Hp^.links^.rechts;
               Hptr^.rechts:=Hp;
               Hp:=Hptr;

               (*H”he richtig setzen*)
               checkhight(Hp);
               checkhight(Hp^.rechts);
               checkhight(Hp^.links);
              End;
              grow:=False;
              End;
     End;
    End;
   End;
End;

Procedure Tree.AusgRek(P:NodePtr);
Var i:Integer;
    Hptr:NodePtr;
Begin
 If P<>Nil Then Begin
  AusgRek(P^.rechts);
  Search:=0;
  Hptr:=SearchTree(Root,P^.SVNR);
  If Search>Depth then Depth:=Search;
  For i:=1 to Search do write('  ');
  Write(P^.SVNR);
  GotoXY(30,Wherey);
  Write(P^.Name);
  GotoXY(43,Wherey);Write(P^.Groesse);
  GotoXY(50,Wherey);Write(P^.Geschlecht,'  h”her: ');
           case P^.higher of
            right:Write('R');
            left:Write('L');
            none:Write('N');
           End;
  Writeln('   Schritte: ',Search);
  AusgRek(P^.links);
 End;
End;

Function Tree.SearchTree(Var Hptr:NodePtr;SVNR:String):NodePtr;
Begin
 Inc(Search);
 SearchTree:=Nil;
 If HPtr<>Nil then
   If (SVNR=HPtr^.SVNR) Then SearchTree:=Hptr
   Else Begin
    If (SVNR<HPtr^.SVNR) Then SearchTree:=SearchTree (HPtr^.links,SVNR)
    Else SearchTree:=SearchTree (HPtr^.rechts,SVNR);
   End;
End;

Procedure Tree.Ausgabe;
Var
   i:integer;
Begin
 Depth:=0;
 writeln('Sozialversicherungsnummer     Name       GrӇe Geschl.');
 AusgRek(Root);
 writeln('Tiefe: ',Depth,', Datens„tze: ',Dat);
 Readln;
End;

Destructor Tree.DisposeTree(Hp,Hptr:NodePtr);
Begin
 IF Hp<>Nil Then Begin
  DisposeTree(Hp^.links,Hp);
  DisposeTree(Hp^.rechts,Hp);
     inc(search);
     if Hptr^.links=Hp then Hptr^.links:=Nil
      else Hptr^.rechts:=Nil;
     Dispose(Hp);
 End;
End;

function Datei.openLog(Filename:string):Boolean;
begin
  Assign(F, Filename);
  Reset(F);
  openLog := (IOResult = 0) and (Filename <> '');
end;

function Datei.ignorespace:char;
Var
   c:char;
begin
     Read(F,c);
     while (c=' ') do Read (F,c);
     ignorespace:=c;
end;

function Datei.readcommand:Boolean;
begin
     command:=ignorespace;
     if ((command='#') or
         (command=#0#10) or
         (command='s') or
         (command='e') or
         (command='a')) then readcommand:=False
     else readcommand:=True;
end;

function Datei.readGes:Boolean;
begin
     Geschlecht:=ignorespace;
     if ((Geschlecht<>'W') and (Geschlecht<>'M')) then readGes:=True
     else readGes:=False;
end;

function Datei.readName: Boolean;
Var c:char;
    Error:Boolean;
begin
Error:=False;
c:=ignorespace;
Readln(F,Name);
Name:=c+Name;
ReadName:=Error;
end;

function Datei.readGr: Boolean;
Var
   Zahl: Integer;
   c:char;
   Error:Boolean;
begin
     Error:=False;
     c:=ignorespace;
     Zahl:=ord(c)-ord('0');
     if ((Zahl>=0) and (Zahl<=9)) then
     Begin
       Groesse:=Zahl*100;
       Read(F,c);
       Zahl:=ord(c)-ord('0');
       if ((Zahl>=0) and (Zahl<=9)) then
          Begin
            Groesse:=Groesse+Zahl*10;
            Read(F,c);
            Zahl:=ord(c)-ord('0');
            if ((Zahl>=0) and (Zahl<=9)) then Groesse:=Groesse+Zahl
            else Error:=True;
          end
       else Error:=True;
     end
     else Error:=True;
     readGr:=Error;
end;

function Datei.readSVNR: Boolean;
Var Error:Boolean;
    Zahl,i :Integer;
begin
     Error:=False;
     SVNR[1]:=ignorespace;
     if ((SVNR[1]>='0') and (SVNR[1]<='9')) then
     Begin
       for i:=2 to 10 do
       begin
         Read(F,SVNR[i]);
         if NOT((SVNR[i]>='0') and (SVNR[i]<='9')) then
         Begin
           Error:=True;
           i:=10;
         End;
       end;
     end else Error:=True;
     readSVNR:=Error;
end;

function Datei.readLog:integer;
var Komm:String;
    Ret:integer;
begin
   Ret:=0;
   if Not(readcommand) then
   case command of
   '#': Begin
          Readln(F,Komm);
        end;
   'e': Begin
          if not(readSVNR) then
            begin
            if not(readGr) then
              begin
              if not(readGes) then
                if not(readName) then
                begin
                 writeln('Einf�gen: ',SVNR,'  ',Groesse,'  ',Geschlecht,'  ',Name);
                 Ret:=1;
                end
                else Ret:=-1
              end else Ret:=-1
            end else Ret:=-1;
        End;
   'a': Begin
        writeln ('Ausgabe');
        Ret:=2;
        End;
   's': Begin
        if not(readsvnr) then
         Begin
          writeln  ('Suche SVNR: ',SVNR);
          ret:=3
         End
          else ret:=-1;
          readln(F);
        End;
   End
   else Readln(F,Komm);
   readLog:=Ret;
end;

Var
   avl               :Tree;
   Log               :Datei;
   Ret,i,Gr          :integer;
   HP                :NodePtr;
   Grow,Ok           :Boolean;
   c,Ges             :char;
   SVN,Name          :string;
begin
avl.init;
Log.init;
if Log.openLog('bsp1.dat')=True then
begin
Ret:=0;
  while (not(Eof(Log.F)) and (Ret>-1)) do
     Begin
       Ret:=Log.ReadLog;
       case Ret of
       -1: Begin
           writeln('Fehler in Datei');
           readln;
           end;
       1: Begin
          avl.rot:=0;
          Grow:=False;
          HP:=Nil;
          HP:=avl.Knoten(Log.SVNR,Log.Groesse,Log.Geschlecht,Log.Name);
          avl.Insert(avl.root,HP,Grow);
          writeln ('Rotationen: ',avl.Rot);
          readln;
          End;
       2: Begin
            avl.ausgabe;
          End;
       3: Begin
            HP:=Nil;
            avl.search:=0;
            HP:=avl.searchtree(avl.root,Log.SVNR);
            if HP<>nil then
            writeln ('Gefunden: Schritte:',avl.search,' ',hp^.svnr,' ',hp^.groesse,' ',hp^.geschlecht,' ',hp^.name)
            else writeln('Nicht gefunden');
            readln;
          End;
       End;
     end;
end;
if (Ret>-1) then
begin
  writeln ('Datei eingelesen');
  readln;
  clrscr;
  c:='w';
  while c<>'q' do
  begin
    writeln ('Commando<q=Ende a=Ausgabe e=Eingabe s=Suchen>:');
    readln(c);
    case c of
     'a': Begin
           avl.ausgabe
          End;
     's': Begin
           write('Sozialversicherungsnummer:');
           readln(SVN);
           Ok:=False;
           for i:=1 to 10 do
             if (SVN[i]<='0') and (SVN[i]<='9') then Ok:=TRUE;
           if Ok=True then Log.SVNR:=SVN;
           SVN:='         ';
           HP:=Nil;
           avl.search:=0;
           HP:=avl.searchtree(avl.root,Log.SVNR);
           if HP<>nil then
           writeln ('Gefunden: Schritte:',avl.search,' ',hp^.svnr,' ',hp^.groesse,' ',hp^.geschlecht,' ',hp^.name)
           else writeln('Nicht gefunden');
           readln;
          End;
     'e': Begin
           write('Sozialversicherungsnummer:');
           readln(SVN);
           Ok:=False;
           for i:=1 to 10 do
           if (SVN[i]>='0') and (SVN[i]<='9') then Ok:=TRUE;
           if Ok=True then
           Begin
             Log.SVNR:=SVN;
             write('Groesse:');
             readln(Gr);
             Log.Groesse:=Gr;
             if Gr<1000 then
               begin
                 write('Geschlecht:');
                 readln(Ges);
                 Log.Geschlecht:=Ges;
                 if ((Ges='M') or (Ges='W')) then
                 begin
                   write('Name:');
                   readln(Name);
                   Log.Name:=Name;
                   avl.rot:=0;
                   Grow:=False;
                   avl.search:=0;
                   HP:=nil;
                   HP:=avl.Knoten(Log.SVNR,Log.Groesse,Log.Geschlecht,Log.Name);
                   avl.Insert(avl.root,HP,Grow);
                   writeln ('Rotationen: ',avl.Rot);
                   readln;
                 end;
               end;
           end;
         End;
    End;
  End;
End;
avl.DisposeTree(avl.Root,Nil);
end.