1428

%% coding: latin-1
%Quellen:
%http://erlang.org/documentation/doc-5.3/doc/getting_started/getting_started.html
%2.
%https://erlang.org/doc/reference_manual/expressions.html#:~:text=Erlang%20uses%20single%20assignment,%20that,its%20value%20can%20be%20ignored.&text=Variables%20starting%20with%20underscore%20(_),are%20normal%20variables,%20not%20anonymous
%3.
%VL vom 03.11.2020
%4.
%util.erl
-module(btree).
-export([initBT/0,isEmptyBT/1,isBT/1,isEqualBT/2, insertBT/2, findBT/2, inOrderBT/1, deleteBTree/2]).

%initBT() erzeugt einen leeren Baum.
%Doku: 2.2 Abbildung 1
%Stelligkeit: 0, Sichtbarkeit: public, Rückgabewert: Tupel

initBT() ->
        {}.

%isEmptyBT() überpürft ob ein Baum ein leerer Baum ist.
%Doku: 2.2 Abbildung 2
%Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: bool

isEmptyBT(BTree) ->
        BTree == {}.

%isBT() überprüft einen Baum auf seine Korrekt nach Definition
%Die einzelnen Constraints für einen korrekten Baum werden im folgenden noch detaillierter beschrieben
%Entwurf: 2.2 Abbildung 3
%Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: bool

%BTree wird um ein Minimum und Maximum erweitert.
isBT(BTree) ->
        isBT(BTree, 0, inf).

%Sollte der betrachtete Baum leer sein, spielt das MInimum und Maximum keine weitere Rolle - der Baum ist korrekt.
isBT(_BTree = {}, _Minimum, _Maximum) ->
        true;

%Sortierung:
    %Minimum und Maximum bilden nun ein Intervall in dem das Element des übergebenen Baumes liegen darf.
%Die Syntaktische Korrektheit wird überprüft:
    %Ist das Tupel als die richtige Datenstruktur verwendet?
        %Ist das Element eines jeden Teilbaumes vom Typ Ganzzahl (Integer)?
%Ist die Höhe im Baum richtig angegeben?
    %Die richtige Höhe nach Definition (siehe findHeight) wird errechnet und mit der übergebenen Höhe verglichen.
%Rekursiver Aufruf der Teilbäume:
%   Sind die Bedingungen für einen korrekten BST in allen Teilbäumen erfüllt?
isBT(_BTree = {ElementAtom,Height,Leftsub,Rightsub}, Minimum, Maximum) when ElementAtom>Minimum, ElementAtom<Maximum ->
        (util:type_is(ElementAtom) == integer) and
        (findHeight(Leftsub,Rightsub) == Height) and
        isBT(Leftsub, Minimum, ElementAtom) and
        isBT(Rightsub, ElementAtom, Maximum);

%Sollte Unsinn als Baum übergeben werden, der nicht der richtigen Datenstruktur folgt, wird false returned.
isBT(_BTree, _Minimum, _Maximum) ->
        false.


%Private Hilfsfunktion zum Errechnen der Höhe eines Teilbaumes für die folgende Funktion
%Wenn die Höhe zweier, nicht leerer Unterbäume gefunden werden soll, wird die Höhe der beiden Unterbäume verglichen und der "höhere" wird mit 1 addiert. [nach Definition Höhe (siehe VL)]
findHeight(_Leftsub = {_ElementLeft,HeightLeft,_Leftsubsub,_Rightsubsub},
        _Rightsub = {_ElementRight,HeightRight,_Leftsubsub,_Rightsubsub}) ->
            max(HeightLeft, HeightRight) + 1;

%Wenn beide Unterbäume leer sind, sind beide leeren Bäume mit Höhe 0 zu interpretieren und 1 wird returned.
findHeight(_Leftsub = {}, _Rightsub = {}) ->
            1;

%Sollte nur einer der beiden Unterbäume leer sein, muss dies als Höhe 0 interpretiert werden.
%Der jeweils andere Baum ist also auch ohne Vergleich der "höhere".
findHeight(_Leftsub = {}, _Rightsub = {_ElementRight,_HeightRight,_Leftsubsub,_Rightsubsub}) ->
            _HeightRight + 1;

findHeight(_Leftsub = {_ElementLeft,_HeightLeft,_Leftsubsub,_Rightsubsub}, _Rightsub = {}) ->
            _HeightLeft + 1.

%isEqual überprüft die semantische Gleicheit zweier Bäume.
%Sollte keiner der beiden Bäume leer sein, wird inOrderBT benutzt um die beiden Bäume als sortierte Liste umzuformen
%und im Folgenden auf syntaktische Gleichheit zu überprüfen.
%Doku: 2.2 Abbildung 4
%Stelligkeit: 2, Sichtbarkeit: public, Rückgabewert: bool

isEqualBT({},{}) ->
        true;

isEqualBT(_BaumEins, {}) ->
        false;

isEqualBT({}, _BaumZwei) ->
        false;

isEqualBT(_BaumEins,_BaumZwei) ->
        inOrderBT(_BaumEins)==inOrderBT(_BaumZwei).

%Hilfsmethode für Hoehe
getHoehe({_Zahl, Hoehe, _Liniks, _Rechts}) -> Hoehe;
getHoehe ({}) -> 0.


%insertBT fügt einen neuen Node dem BTree hinzu und positioniert es an der richtigen stelle
%Stelligkeit: 2, Sichtbarkeit: Public, Rückgabewert: Tupel
%Doku: TODO
insertBT({},Element) ->
    {Element, 1, {}, {}};

insertBT(BTree= {Zahl, Hoehe, Links, Rechts}, Element) ->
    BTree = {Zahl, Hoehe, Links, Rechts},
    if Element < Zahl ->
        NeuerLinks = insertBT(Links, Element),
        Hanoi = 1+max(getHoehe(NeuerLinks),getHoehe(Rechts)),
        {Zahl, Hanoi, NeuerLinks, Rechts};
    Element > Zahl ->
        NeuerRechts = insertBT(Rechts,Element),
        Hanoi = 1+max(getHoehe(NeuerRechts),getHoehe(Links)),
        {Zahl, Hanoi, Links, NeuerRechts};
    true ->
        BTree
    end.



%findBT() wird ein Baum und ein Element übergeben.
%Daraufhin wird das Element im Baum gesucht.
%Falls es im Baum existiert wird die Höhe returned, falls nicht ein Error.
%Entwurf: 2.2 Abbildung 7
%Stelligkeit: 2, Sichtbarkeit: public, Rückgabewert: int
%Wenn der Baum leer ist, kann das Element nicht darin vorkommen und Error (-1) wird returned.
%Das leere Element wird hier ignoriert.

findBT({}, _Element) ->
        -1;

%BTree Tupel wird zur weiteren Bearbeitung in mehreren Atomen definiert. (ElementAtom = <ELEMENT>, Height = <HÖHE>)
%Das Übergebene Element wird mit dem Element des aktuellen Nodes verglichen
%Sollten die ELement übereinstimmen, wurde das gesuchte Element gefunden und seine Höhe wird returned.
%Falls nicht, werden die beiden Elemente verglichen:
%Ist das gesuchte Element größer als das Element unseres aktuellen Nodes,
%müssen wir im Folgen den im rechten Unterbaum unseres aktuellen Nodes weitersuchen.
%Wenn das gesuchte Element kleiner ist, suchen wir im linken Unterbaum weiter.
%Die Funktion wird erneut mit dem jeweiligen Unterbaum aufgerufen, bis das gesuchte Element gefunden ist oder wir an einem Blatt angekommen sind.
findBT(BTree, Element) ->
        {ElementAtom, Height, Leftsub, Rightsub} = BTree,
            if Element == ElementAtom ->
                Height;
            Element > ElementAtom ->
                findBT(Rightsub, Element);
            Element < ElementAtom ->
                findBT(Leftsub,Element)
            end.

%inOrderBT() gibt den Baum in einer aufsteigend sortierten Liste zurück.
%Entwurf: 2.2 Abbildung 8
%Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: list

%Ist der Baum leer wird eine leere Liste returned.
inOrderBT({}) ->
        [];

%Ist das aktuelle Node ein Blatt wird das Element des aktuellen Elements in die Liste eingefügt und die Liste wird zurückgegeben.
inOrderBT({ElementAtom,_Height,{},{}}) ->
        [ElementAtom];

%Wenn das aktuelle Node nur einen rechten Unterbaum hat, können wir davon ausgehen, dass kein kleineres Element mehr gefunden wir dals das Element in dem aktuellen Node.
%Also wird es in die Liste eingefügt und die Funktion wird nachfolgend mit dem rechten Unterbaum, der auschließlich größere ELemente enthalten wird, aufgerufen.
inOrderBT({ElementAtom,_Height,{},Rightsub}) ->
        [ElementAtom] ++ inOrderBT(Rightsub);
%Falls das aktuelle Node keinen rechten Unterbaum, dafür aber einen linken besitzt, können wir das Element des aktuellen noch nicht in die liste einfügen,
%da sich mit Sicherheit noch ein kleineres Element im Baum befindet.
%Wir müssen also zunächst den linken Unterbaum an inOrderBT übergeben und können danach das Element des aktuellen Nodes in die Liste einfügen.
inOrderBT({ElementAtom,_Height,Leftsub,{}}) ->
        inOrderBT(Leftsub) ++ [ElementAtom];

%Im Falle, dass das aktuelle Node sowohl einen linken als auch einen rechten Unterbaum besitzt, müssen wir zunächst den linken Unterbaum an inOrderBT übergeben um die kleineren ELement zu finden.
%Dann können wir das Element des aktuellen Nodes in die Liste einfügen, da es keine kleineren Element mehr im Baum gibt.
%Um sicherzustellen, dass alle Elementen ihren Platz in der sortierten Liste finden, müssen wir anschließend noch den rechten Unterbaum überprüfen.
%Wir rufen nun also noch inOrderBt mit dem rechten Unterbaum auf.
inOrderBT({ElementAtom,_Height,Leftsub,Rightsub}) ->
        inOrderBT(Leftsub) ++ [ElementAtom] ++ inOrderBT({Rightsub}).

%%Wenn wir einen Leerenbaum als Parameter erhalten, gibt es das gewünschte Element nicht im BTree
deleteBTree({}, _Element) -> {};

deleteBTree(BTree = {ElementAtom,Height,Links,Rechts}, Element) ->
    if %%Wir haben 3 Cases hier:
        %a) Element ist Größer als das ElementAtom vom root, b) es ist kleiner und c) es ist gleich groß

        %a) Hier wird "tiefer" im Baum nach dem Element gesucht, anschließend wird die Höhe korrigiert und es wird ein ErsatzKnoten zurückgegeben
        Element > ElementAtom ->
            NeuRechts = deleteBTree(Rechts, Element),
            Hanoi = findHeight(NeuRechts, Links),
            {ElementAtom,Hanoi,Links,NeuRechts};
        %b) Hier geschieht das Equivalente für den Linkenbaumteil
        Element < ElementAtom ->
            NeuLinks = deleteBTree(Links, Element),
            Hanoi = findHeight(NeuLinks, Rechts),
            {ElementAtom,Hanoi,NeuLinks,Rechts};
        %c) Hier haben wir unser Element gefunden.
        %Nun wird abgefragt ob das Node nur leere Linke und Rechte Teilbäume hat oder ob es beide hat.
        Element == ElementAtom ->
            if  %Beim Fall dass es nur einen Teilbaum gibt, wird einfach der Linke, bzw. Rechte Teilbaum zurückgegeben.
                BTree == {ElementAtom, Height, Links,{}} ->
                    Links;
                BTree == {ElementAtom, Height, {},Rechts} ->
                    Rechts;
                BTree == {ElementAtom, Height, {},{}} ->
                {} end;
                %Hier wird der richtige Ersatz des rechten Teilbaumes gesucht, die Ursprüngliche Node mit dem Ersatz gelöscht und ein korrekter Ersatzbaum wir zurückgegeben.
                BTree == {ElementAtom, Height, Links,Rechts} ->
                    Kleinster = kLZahl(Rechts), %Findet uns die Kleinste Zahl vom übergebenen Baum
                    RechtsNeu = deleteBTree(Rechts, Kleinster), %Der Node von dem wir den Ersatzwert nehmen, wird gelöscht
                    Hanoi = findHeight(RechtsNeu, Links),
                    {Kleinster, Hanoi, Links, RechtsNeu}
            end.

kLZahl({ElementAtom, _Height, {}, _Rechts}) ->
    ElementAtom;
kLZahl({_ElementAtom, _Height, Links, _Rechts}) ->
    kLZahl(Links).