trashtatur trashtatur - 4 months ago
177 0

Erlang splaytree (not really splaytree tho) implementation. Blah

Erlang

splaytree.erl

%%%-------------------------------------------------------------------
%%% @author Andreas Hoerster
%%% @copyleftRotate (C) 2017, <Team 8>
%%% @doc HAW BAI-3 ADP-P4
%%%
%%% @end
%%% Created : 09. June 2017 12:28
%%%-------------------------------------------------------------------
%%% This module functions to implement a self sorting binary tree.
%%% Whichs is also called a splaytree.
%%%-------------------------------------------------------------------
-module(splaytree).
-export([initBT/0,isEmptyBT/1,equalBT/2,isBT/1,insertBT/2,deleteBT/2,printBT/2,findSBT/2,findBT/2,findTP/2,correctHeight/1]).

-type splayTree() :: bTree:binTree().
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% MAIN FUNCTIONS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
% initBT: ∅ → btree
% Creates an empty splaytree and returns it
%%%%%%%%%%%%%%%
-spec initBT() -> splayTree().

initBT() -> btree:initBT().

%%%%%%%%%%%%%%%
% isEmptyBT: btree → bool
% Determines if the given tree is empty and returns an according boolean.
%%%%%%%%%%%%%%%
-spec isEmptyBT(splayTree()) -> boolean().

isEmptyBT(Tree) -> btree:isEmptyBT(Tree).

%%%%%%%%%%%%%%%
% equalBT: btree × btree → bool
% Determines if two splaytrees are structurally equal and returns an according boolean.
%%%%%%%%%%%%%%%
-spec equalBT(splayTree(),splayTree()) -> boolean().

equalBT(Tree,OTree) -> btree:equalBT(Tree,OTree).

%%%%%%%%%%%%%%%
% isBT: btree → bool
% Determines if the given structure is a binaryTree / splayTree by definition, and returns an according boolean.
%%%%%%%%%%%%%%%
-spec isBT(any()) -> boolean().

isBT(Tree) -> btree:isBT(Tree).

%%%%%%%%%%%%%%%
% insertBT: btree × elem → btree
% Inserts an element into a binary Tree and returns the new tree.
%%%%%%%%%%%%%%%
-spec insertBT(splayTree,integer()) -> splayTree().

%% The reason I rewrote this is because I did not write the one for btree, my partner did.
%% I wanted to get a good feeling for the datastructure and insert proved to be a good
%% practice for this. So I chose to write my own one.

insertBT(nulltree,ToInsert) -> {ToInsert,1,initBT(),initBT()};
insertBT({Value,Height,LeftChild,RightChild},ToInsert) ->
  if
    ToInsert=:=Value -> correctHeight({Value,Height,LeftChild,RightChild});
    ToInsert > Value -> correctHeight({Value,Height,LeftChild,insertBT(RightChild,ToInsert)});
    ToInsert < Value -> correctHeight({Value,Height,insertBT(LeftChild,ToInsert),RightChild})
  end.

%%%%%%%%%%%%%%%
% deleteBT: btree × elem → btree
% Deletes an element form a tree and returns the new tree.
%%%%%%%%%%%%%%%
-spec deleteBT(splayTree,integer()) -> splayTree().

deleteBT(nulltree,_ToDelete) -> nulltree;
deleteBT({Value,Height,LeftChild,RightChild},ToDelete) ->
  if
    ToDelete=:=Value -> correctHeight(deleteActual({Value,Height,LeftChild,RightChild}));
    ToDelete > Value -> correctHeight({Value,Height,LeftChild,deleteBT(RightChild,ToDelete)});
    ToDelete < Value -> correctHeight({Value,Height,deleteBT(LeftChild,ToDelete),RightChild})
  end.


deleteActual({_,_,nulltree,nulltree}) -> nulltree;
deleteActual({_,H,nulltree,RightChild}) ->
  Min=getMin(RightChild),
  {Min,H,nulltree,deleteBT(RightChild,Min)};

deleteActual({_,H,LeftChild,RightChild}) ->
  Max=getMax(LeftChild),
  {Max,H,deleteBT(LeftChild,Max),RightChild}.

%%%%%%%%%%%%%%%
% findSBT: btree × elem → int
% Finds an element and returns only its height in the tree
%%%%%%%%%%%%%%%
-spec findSBT(splayTree(),integer()) -> integer().

findSBT(nulltree,_ToFind) -> -1;
findSBT({Value,Height,LeftChild,RightChild},ToFind) ->
  if
    ToFind=:=Value -> Height;
    ToFind > Value -> findSBT(RightChild,ToFind);
    ToFind < Value -> findSBT(LeftChild,ToFind)
  end.

%%%%%%%%%%%%%%%
% findBT: btree × elem → {int,btree}
% Finds an element and rearranges it using the move to front (root) strategy. Returns its new height and the new tree.
%%%%%%%%%%%%%%%
-spec findBT(splayTree(),integer()) -> {integer(),splayTree()}.


findBT(Tree,ToFind) ->
{NewTree,_Path}=findBTUtil(Tree,ToFind,[]), NewHeight=findSBT(NewTree,ToFind), {NewHeight,NewTree}.

findBTUtil(nulltree,_ToFind,Path) -> {nulltree,Path};
findBTUtil({Value,Height,nulltree,nulltree},_,Path) -> {{Value,Height,nulltree,nulltree},Path};
findBTUtil({Value,Height,LeftChild,RightChild},ToFind,Path) ->

  if

    ToFind  >  Value ->
      {SubRightTree,SubRightPath}=findBTUtil(RightChild,ToFind,[leftRotate|Path]),
      splay({Value,Height,LeftChild,SubRightTree},SubRightPath,ToFind);

    ToFind  <  Value ->
      {SubLeftTree,SubLeftPath}=findBTUtil(LeftChild,ToFind,[rightRotate|Path]),
      splay({Value,Height,SubLeftTree,RightChild},SubLeftPath,ToFind);

    ToFind =:= Value ->  {{Value,Height,LeftChild,RightChild},Path}

  end.

%%%%%%%%%%%%%%%
% splay: btree × list → {btree,list}
% Reparses the tree after the element is found, using a stack and then applies propper rotations.
%%%%%%%%%%%%%%%
-spec splay(splayTree(),list(),integer()) -> {splayTree(),list()}.

%% The way went left two times. So zig-zig rotation must be done
splay({GFVal,GFHeight,{PVal,PHeight,{ToFind,CHeight,CDownL,CDownR},PCRight},GFCRight},[rightRotate,rightRotate|PathRest],ToFind) ->
{zig(zig({GFVal,GFHeight,{PVal,PHeight,{ToFind,CHeight,CDownL,CDownR},PCRight},GFCRight})),PathRest};

%The way went left and then right. So zig-zag rotation must be done
splay({GFVal,GFHeight,{PVal,PHeight,PCLeft,{ToFind,CHeight,CDownL,CDownR}},GFCRight},[leftRotate,rightRotate|PathRest],ToFind) ->
{zig({GFVal,GFHeight,zag({PVal,PHeight,PCLeft,{ToFind,CHeight,CDownL,CDownR}}),GFCRight}),PathRest};

%The way went right two times. So zag-zag rotation must be done
splay({GFVal,GFHeight,PCLeft,{PVal,PHeight,CLeft,{ToFind,CHeight,CdownL,CDownR}}},[leftRotate,leftRotate|PathRest],ToFind) ->
{zag(zag({GFVal,GFHeight,PCLeft,{PVal,PHeight,CLeft,{ToFind,CHeight,CdownL,CDownR}}})),PathRest};

%The way went right and then left. So zag-zig rotation must be done
splay({GFVal,GFHeight,GFCLeft,{PVal,PHeight,{ToFind,CHeight,CDownL,CDownR},PCRight}},[rightRotate,leftRotate|PathRest],ToFind) ->
{zag({GFVal,GFHeight,GFCLeft,zig({PVal,PHeight,{ToFind,CHeight,CDownL,CDownR},PCRight})}),PathRest};

%This is to assure that a zigzig or zagzag rotation always evaluates before a zig or zag rotation.
splay(Tree,[One,Two|PathRest],_ToFind) ->
{Tree,[One,Two|PathRest]};

%The way went left only once. A zig rotation must be done
splay({PVal,PHeight,{ToFind,CHeight,CDownL,CDownR},PCRight},[rightRotate|PathRest],ToFind) ->
{zig({PVal,PHeight,{ToFind,CHeight,CDownL,CDownR},PCRight}),PathRest};

%The way went right only once. A zag rotation must be done
splay({PVal,PHeight,PCLeft,{ToFind,CHeight,CDownL,CDownR}},[leftRotate|PathRest],ToFind) ->
{zag({PVal,PHeight,PCLeft,{ToFind,CHeight,CDownL,CDownR}}),PathRest};

%Nothing can be rotated cause the tree wont match anywhere.
splay(FailTree,Path,_ToFind) -> {FailTree,Path}.



%%%%%%%%%%%%%%%
% findTP: btree × elem → {int,btree}
% Finds an element and rearranges it using the transpose Strategy. Returns its new height and the new tree.
%%%%%%%%%%%%%%%
-spec findTP(splayTree,integer()) -> splayTree().

findTP(Tree,ToFind) -> NewTree=findTPUtil(Tree,ToFind), NewHeight=findSBT(NewTree,ToFind),{NewHeight,NewTree}.

findTPUtil(nulltree,_ToFind) -> nulltree;
findTPUtil({Value,Height,LeftChild,RightChild},ToFind) ->
  if
    ToFind =:= Value -> {Value,Height,LeftChild,RightChild};
    ToFind > Value   -> leftRotateTranspose({Value,Height,LeftChild,RightChild},ToFind);
    ToFind < Value   -> rightRotateTranspose({Value,Height,LeftChild,RightChild},ToFind)
  end.

  rightRotateTranspose({Value,Height,LeftChild,RightChild},ToFind) ->
    IsInLeft=isIn(LeftChild,ToFind),
    if
      IsInLeft=:=true -> zig({Value,Height,LeftChild,RightChild});
      true            -> correctHeight({Value,Height,findTPUtil(LeftChild,ToFind),RightChild})
    end.

  leftRotateTranspose({Value,Height,LeftChild,RightChild},ToFind) ->
    IsInRight=isIn(RightChild,ToFind),
    if
      IsInRight=:=true -> zag({Value,Height,LeftChild,RightChild});
      true             -> correctHeight({Value,Height,LeftChild,findTPUtil(RightChild,ToFind)})
    end.
%%%%%%%%%%%%%%%
% printBT: btree × filename → dot
% prints a binary tree into a .dot file, that is readable by GraphViz Software
%%%%%%%%%%%%%%%
-spec printBT(splayTree,any()) -> any().

printBT(Tree,Filename) -> avltree:printBT(Tree,Filename).

%%%%%%%%%%%%%%%%%%%%%%%
%% HELP FUNCTIONS
%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
% isIn: btree × integer → bool
% Determines if an object is the value of a node and returns an according boolean
%%%%%%%%%%%%%%%
-spec isIn(splayTree(),integer()) -> boolean().

isIn({ToFind,_,_,_},ToFind) -> true;
isIn(_,_ToFind) -> false.

%%%%%%%%%%%%%%%
% correctHeight: btree → btree
% Corrects the height after doing an operation on a binary tree
%%%%%%%%%%%%%%%
-spec correctHeight(splayTree()) -> splayTree().

correctHeight(nulltree) -> nulltree;
correctHeight({Value,_,LeftChild,RightChild}) ->
  {Value,max(getHeight(LeftChild),getHeight(RightChild))+1,LeftChild,RightChild}.

%%%%%%%%%%%%%%%
% getHeight: btree → integer.
% gets the Height of the currently viewed tree
%%%%%%%%%%%%%%%
-spec getHeight(splayTree()) -> integer().

getHeight(nulltree) -> 0;
getHeight({_,Height,_,_}) -> Height.

%%%%%%%%%%%%%%%
% getMax: binTree → integer.
% Gets the maximum value from a tree
%%%%%%%%%%%%%%%.
-spec getMax(splayTree()) -> integer().

getMax({V,_,_,R}) ->
if
  R=:=nulltree ->  V;
  true         ->  getMax(R)
end.

%%%%%%%%%%%%%%%
% getMin: binTree → integer.
% Gets the minimum value from a tree
%%%%%%%%%%%%%%%.
-spec getMin(splayTree()) -> integer().

getMin({V,_,L,_}) ->
if
  L=:=nulltree ->  V;
  L=/=nulltree        ->  getMin(L)
end.

%%%%%%%%%%%%%%%%%%
%% These two functions were taken from avltree.erl
%% and renamed to zig and zag to better suit
%% the defined names.
%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
% zag: splayTree → integer.
% Applies a zag (rightRotate) rotation to the tree.
%%%%%%%%%%%%%%%.

zag({V, _H, L, {RV, _, RTL, RTR}}) ->
  PH = max(getHeight(L),getHeight(RTL)) + 1,
  {RV, max(PH, getHeight(RTR)) + 1, {V, PH, L, RTL}, RTR}.

%%%%%%%%%%%%%%%
% zig: binTree → integer.
% Applies a zig (leftRotate) rotation to the tree.
%%%%%%%%%%%%%%%.
zig({V, _H, {LV, _, LTL, LTR}, RT}) ->
  PH = max(getHeight(RT),getHeight(LTR)) + 1,
  {LV, max(PH, getHeight(LTL)) + 1, LTL, {V, PH, LTR, RT}}.