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

% A scalable strucure based on a number of BSTs
% For this to work there are two caveats:-
% - The range of the keys must be known
% - Key distribution must be balanced within the range

-module(dbst).
-export([createStruct/2, insertKey/2, deleteKey/2, containsKey/2, dumpAll/1, printSorted/1]).
-compile(export_all). % For debugging



% Creates a structure that is expected to have a maximum key value as specified,
% and distributes this key over NoProcesses of binary search trees.
%
% NoProcesses should be at least equal to the number of processors in the system
% From my experiments 8 times the number of processors seems to be ideal
%
% Returns a list of processes and the upper value for each process.
% TODO: handle the case where NoProcesses is too high
createStruct(KeyMax, NoProcesses) ->
    KeyRange = trunc(KeyMax/NoProcesses),
    [{spawn(fun() -> treeServer({}) end), Index * KeyRange} || Index <- lists:seq(1, NoProcesses)].


% Inserts a new key into the strucuture (if it doesn't exist)
insertKey(Struct, Key) ->
    operationKey(Key, Struct, fun(P, K) -> rpcInsert(P, K) end).


% Deletes an existing key from the structure (if it exists)
deleteKey(Struct, Key) ->
    operationKey(Key, Struct, fun(P, K) -> rpcDelete(P, K) end).


% Returns whether the key exists or not
containsKey(Struct, Key) ->
    operationKey(Key, Struct, fun(P, K) -> rpcContains(P, K) end).


% Dumps the contents of all the trees in the structure
dumpAll([]) ->
    true;

dumpAll([{Pid, _}| Rest]) ->
    io:format("~w~n", [rpcDump(Pid)]),
    dumpAll(Rest).


% Prints a sorted list of all the keys in the structure
printSorted([]) ->
    true;

printSorted([{Pid, _}| Rest]) ->
    Tree = rpcDump(Pid),
    printKeys(Tree),
    printSorted(Rest).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Perform an operation with the given key
operationKey(_, [], _) ->
    error;

operationKey(Key, [{Pid, Max} | _], Op) when Key < Max ->
    Op(Pid, Key);

operationKey(Key, [_| Rest], Op)  ->
    operationKey(Key, Rest, Op).


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


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


% Asks the server to check if the node exists within the tree
rpcContains(Pid, Key) ->
    Pid ! {self(), contains, Key},
    receive
        Result -> Result
    end.


% Asks the server to send the contents of the whole tree
% Used for debugging
rpcDump(Pid) ->
    Pid ! {self(), dump},
    receive
        Tree -> Tree
    end.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% A server that maintains the state of a binary search tree and services
% requests for the tree
treeServer(Tree) ->
    receive
        {Requester, insert, Key} ->
            Requester ! ok,
            treeServer(insert(Key, Tree));

        {Requester, delete, Key} ->
            Requester ! ok,
            treeServer(delete(Key, Tree));

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

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

%%%%%%%%%%%%5%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Basic bst implementation similar to the code in
% Concurrent Programming in Erlang
% http://erlang.org/download/erlang-book-part1.pdf

% Node: {Key, Left, Right}


% Does the 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 (if it doesn't exist)
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 (it it exists)
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)}.


% Print all the keys of the tree (in order)
printKeys({Key, Left, Right}) ->
    printKeys(Left),
    io:format("~w ", [Key]),
    printKeys(Right);

printKeys({}) ->
    true.


% Find the maximum value in a tree (for use for delete)
max({Key, _, {}}) ->
    Key;

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

%%%%%%%%%%%%5%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Test functions

% Populates the structure randomly with values selected from the range
% Afterwards, the structure is expected to be roughly half full
%
% Struct: is the structure to populate
% KeyRange: The range from which to uniformly choose keys
randPopulate(Struct, KeyRange) ->
    Operations = KeyRange,
    lists:foreach(fun(_) -> insertKey(Struct, random:uniform(KeyRange)) end, lists:seq(1, Operations)),
    Struct.


% First creates a and populates a random structure, then performs random
% operations on it being run on N threads.
%
% Returns a tuple containing; the root of the tree, the total runtime, and
% the wall clock time
%
% ContainsFactor: How many contains() to perform for every insert and delete
%   i.e. the ratio of contains:inserts:deletes will be ContainsFactor:1:1
% NoClients: Number of client that perform requests
% NoProcesses: Number of processes that maintain the structure
testTree(KeyRange, Operations, ContainsFactor, NoClients, NoProcesses) ->
    Struct = createStruct(KeyRange, NoProcesses),
    randPopulate(Struct, KeyRange),

    OpsPerThread = trunc(Operations/NoClients),
    Self = self(),
    statistics(runtime),
    statistics(wall_clock),

    lists:foreach(fun(_) -> spawn(fun() -> testThread(Struct, KeyRange, OpsPerThread, ContainsFactor, Self) end) end,
        lists:seq(1, NoClients)),
    lists:foreach(fun(_) -> receive done -> done end end, lists:seq(1, NoClients)),

    {_,Run} = statistics(runtime),
    {_,Wall} = statistics(wall_clock),
    {Struct, Run, Wall}.


% Function for the spawned process that performs a certain number of random
% operaions.
testThread(Struct, KeyRange, Operations, ContainsFactor, Requester) ->
    lists:foreach(fun(_) -> randOperation(Struct, KeyRange, ContainsFactor) end, lists:seq(1, Operations)),
    Requester ! done.


% Choose a random operation on the tree
randOperation(Struct, KeyRange, ContainsFactor) ->
    Op = random:uniform(2 + ContainsFactor),
    Key = random:uniform(KeyRange),

    case Op of
         1 -> insertKey(Struct, Key);
         2 -> deleteKey(Struct, Key);
         _ -> containsKey(Struct, Key)
    end.