% Fuad Tabba
% cs.auckland.ac.nz AT fuad

% A naive implementation of a concurrent shared binary search tree strucuture.
% Several calls to contains can run concurrently with at most one insert/delete.


-module(bst).
-export([rpcInsert/2, rpcDelete/2, rpcContains/2, rpcDump/1, startSequential/1,
startParallel/1, createTree/0]).
-compile(export_all). % for debugging

% As a starting point, try:-
% Pid = bst:startParallel(bst:createTree()).
% Then use the rpcs...


% Adds a node to the tree
rpcInsert(Pid, Key) ->
    Pid ! {self(), insert, Key},
    receive
        Result -> Result
    end.


% Removes a node from the tree
rpcDelete(Pid, Key) ->
    Pid ! {self(), delete, Key},
    receive
        Result -> Result
    end.


% Checks if the node exists within the tre
rpcContains(Pid, Key) ->
    Pid ! {self(), contains, Key},
    receive
        Result -> Result
    end.


% Dumps to the screen the contents of the tree (without any beautification)
% Used for debugging
rpcDump(Pid) ->
    Pid ! {self(), dump},
    receive
        Tree -> Tree
    end.


% Starts the sequential server, all operations are serialized
startSequential(Tree) ->
    spawn(fun() -> sequentialServer(Tree) end).


% Starts the parallel server, contains and dump can and do run concurrently with
% insert and delete but that's it. All other operations are serialized.
startParallel(Tree) ->
    spawn(fun() -> parallelServer(Tree, stable, void) end).


% All is sequential
sequentialServer(Tree) ->
    receive
        {Requester, insert, Key} ->
            NewTree = insert(Key, Tree),
            Requester ! done,
            sequentialServer(NewTree);

        {Requester, delete, Key} ->
            NewTree = delete(Key, Tree),
            Requester ! done,
            sequentialServer(NewTree);

        {Requester, contains, Key} ->
            Requester ! contains(Key, Tree),
            sequentialServer(Tree);

        {Requester, dump} ->
            Requester ! Tree,
            sequentialServer(Tree)
    end.


% Contains is parallelized

% No changes pending for the tree
parallelServer(Tree, stable, _) ->
    receive
        {Requester, insert, Key} ->
            Self = self(),
            spawn(fun() -> insertProcessor(Self, Key, Tree) end),
            parallelServer(Tree, changing, Requester);

        {Requester, delete, Key} ->
            Self = self(),
            spawn(fun() -> deleteProcessor(Self, Key, Tree) end),
            parallelServer(Tree, changing, Requester);

        {Requester, contains, Key} ->
            spawn(fun() -> containsProcessor(Requester, Key, Tree) end),
            parallelServer(Tree, stable, void);

        {Requester, dump} ->
            Requester ! Tree,
            parallelServer(Tree, stable, void)
    end;

% Tree is being modified
parallelServer(Tree, changing, Requester) ->
    receive
        {Requester, contains, Key} ->
            spawn(fun() -> containsProcessor(Requester, Key, Tree) end),
            parallelServer(Tree, changing, Requester);

        {Requester, dump} ->
            Requester ! Tree,
            parallelServer(Tree, changing, Requester);

        {update, NewTree} ->
            Requester ! done,
            parallelServer(NewTree, stable, void)
    end.


% insertProcessor and deleteProcessor cannot notify the requester directly to
% ensure that parallelServer knows what the new tree is like first for
% consistency.

insertProcessor(Server, Key, Tree) ->
    Server ! {update, insert(Key, Tree)}.


deleteProcessor(Server, Key, Tree) ->
    Server ! {update, delete(Key, Tree)}.


containsProcessor(Requester, Key, Tree) ->
    Requester ! contains(Key, Tree). % Can report it directly


% Node: {Key, Left, Right}

% Does that key exist in the tree?

contains(_, {}) ->
    false;

contains(Key, {Key, _, _}) ->
    true;

contains(Key, {Key2, Left, _}) when Key < Key2 ->
   contains(Key, Left);

contains(Key, {Key2, _, Right}) when Key > Key2 ->
    contains(Key, Right).


% Insert the key into the tree

insert(Key, {}) ->
    {Key, {}, {}};

insert(Key, {Key2, Left, Right}) when Key < Key2 ->
    {Key2, insert(Key, Left), Right};

insert(Key, {Key2, Left, Right}) when Key > Key2 ->
    {Key2, Left, insert(Key, Right)};

insert(Key, {Key, Left, Right}) ->
    {Key, Left, Right}.


% Remove the key from the tree

delete(_, {}) ->
    {};

delete(Key, {Key, Left, {}}) ->
    Left;

delete(Key, {Key, {}, Right}) ->
    Right;

delete(Key, {Key, Left, Right}) ->
    Km = max(Left), % Not the most efficient way, but clearer
    {Km, delete(Km, Left), Right};

delete(Key, {Key2, Left, Right}) when Key < Key2 ->
    {Key2, delete(Key, Left), Right};

delete(Key, {Key2, Left, Right}) when Key > Key2 ->
    {Key2, Left, delete(Key, Right)}.


% Find the maximum value in a tree (for use for delete)

max({Key, _, {}}) ->
    Key;

max({_, _, Right}) ->
    max(Right).


% Create a test tree

createTree() ->
    S1 = {},
    S2 = insert(260,S1),
    S3 = insert(240,S2),
    S4 = insert(140,S3),
    S5 = insert(320,S4),
    S6 = insert(250,S5),
    S7 = insert(170,S6),
    S8 = insert(60,S7),
    S9 = insert(100,S8),
    S10 = insert(20,S9),
    S11 = insert(40,S10),
    S12 = insert(290,S11),
    S13 = insert(280,S12),
    S14 = insert(270,S13),
    S15 = insert(30,S14),
    S16 = insert(265,S15),
    S17 = insert(275,S16),
    S18 = insert(277,S17),
    insert(278,S18).