-module(sg).
-export([start/0, start/1, get_node/0, find_/1, put_/2, get_/1, get_/2]).
 
-define(error(X), (begin io:format("*** ERROR ~p ~p   ~p~n", [?MODULE, ?LINE, X]) end)).
-define(debug(X), (begin io:format("*** DEBUG ~p ~p   ~p~n", [?MODULE, ?LINE, X]) end)).

start() -> register(node_loop, spawn(fun() -> node_loop(boot(dummy_node(), 0, 0)) end)).
start(Init) ->
   Pid = rpc:call(Init, sg, get_node, []),
   register(node_loop, spawn(fun() -> node_loop(Pid) end)).

node_loop(Pid) ->
   receive {From, get} -> From ! {ok, Pid}; _ -> pass end,
   node_loop(Pid).

get_node() ->
   node_loop ! {self(), get},
   receive {ok, Pid} -> Pid; _ -> pass end.

init(Membership_Vector, Init, Key) ->    % initialize function
   Init ! {self(), {join, Key}},
   [[LKey, LNode], [RKey, RNode]] = receive
                                       {reply, {join, Left, Right}} -> [Left, Right];
                                       Any -> ?error({init, {receive_error, Any}})
                                    end,
   [[[LKey, LNode], [RKey, RNode]] | init_join(Membership_Vector, LNode, RNode, Key, 2)].
 
init_join([], _, _, _, _) -> [];
init_join([Vector|T], LNode, RNode, Key, Level) ->
   RNode ! {self(), {join_level, Key, Level, Vector, right}},
   [NRKey, NRNode] = receive
                        {reply, {join_level, RKey_Node}} -> RKey_Node;
                        RAny -> ?error({init, {receive_error, right, RAny}})
                     end,
   LNode ! {self(), {join_level, Key, Level, Vector, left}},
   [NLKey, NLNode] = receive
                        {reply, {join_level, LKey_Node}} -> LKey_Node;
                        LAny -> ?error({init, {receive_error, left, LAny}})
                     end,
   [[[NLKey, NLNode], [NRKey, NRNode]] | init_join(T, NLNode, NRNode, Key, Level + 1)].

boot(Init_Node, Key, Value) ->
   From = self(),
   Pid = spawn(fun() -> boot_(From, Init_Node, Key, Value) end),
   receive {ok} -> Pid; Any -> ?error(Any) end.

boot_(From, Init_Node, Key, Value) ->    % boot new peer
   Level_Max = 127,
   {A1, A2, A3} = now(),
   random:seed(A1, A2, A3),
   Membership_Vector = [random:uniform(2) - 1 || _ <- lists:duplicate(Level_Max, 0)],
   Skip_List = init(Membership_Vector, Init_Node, Key),
   From ! {ok},
   loop([1 | Membership_Vector], Key, Value, Skip_List).

loop(Membership_Vector, Key, Value, Skip_List) ->
   receive
      {put, Value2} ->
         loop(Membership_Vector, Key, Value2, Skip_List);
      
      {From, {find, Key2}} ->
         [Next_Key, Next_Node] = get_next(Skip_List, Key, Key2),
         if
            Next_Key == undef__ -> From ! {reply, {find, Key, self()}};
            true -> Next_Node ! {From, {find, Key2}}
         end,
         loop(Membership_Vector, Key, Value, Skip_List);
         
      {From, {get, End_Key, Lis}} ->
         if
            End_Key < Key -> From ! {reply, {get, Lis}};
            true ->
               [_Left, [_Right_Key, Right_Node]] = lists:nth(1, Skip_List),
               Right_Node ! {From, {get, End_Key, [Value | Lis]}}
         end,
         loop(Membership_Vector, Key, Value, Skip_List);
      
      {From, {join, From_Key}} ->
         [[Left_Key, Left_Node], [Right_Key, Right_Node]] = lists:nth(1, Skip_List),
         [Next_Key, Next_Node] = get_next(Skip_List, Key, From_Key),
         case Next_Key of
            undef__ ->
               if
                  From_Key < Key ->
                     From ! {reply, {join, [Left_Key, Left_Node], [Key, self()]}},
                     Left_Node ! {From, {set, right, From_Key, 1}},
                     self() ! {From, {set, left, From_Key, 1}};
                  Key < From_Key ->
                     From ! {reply, {join, [Key, self()], [Right_Key, Right_Node]}},
                     Right_Node ! {From, {set, left, From_Key, 1}},
                     self() ! {From, {set, right, From_Key, 1}};
                  true ->
                     ?error({loop, {join, {key, Key}, {from_key, From_Key}}})
               end;
            _ ->
               Next_Node ! {From, {join, From_Key}}
         end,
         loop(Membership_Vector, Key, Value, Skip_List);
      
      {From, {join_level, From_Key, Level, Vector, LR}} ->
         My_Vector = lists:nth(Level, Membership_Vector),
         [[_LKey, LNode], [_RKey, RNode]] = lists:nth(Level - 1, Skip_List),
         if
            My_Vector /= Vector ->
               case LR of
                  right -> RNode ! {From, {join_level, From_Key, Level, Vector, LR}};
                  left -> LNode ! {From, {join_level, From_Key, Level, Vector, LR}}
               end;
            true ->
               From ! {reply, {join_level, [Key, self()]}},
               [[_, SLNode], [_, SRNode]] = lists:nth(Level, Skip_List),
               case LR of
                  right ->
                     SLNode ! {From, {set, right, From_Key, Level}},
                     self() ! {From, {set, left, From_Key, Level}};
                  left ->
                     SRNode ! {From, {set, left, From_Key, Level}},
                     self() ! {From, {set, right, From_Key, Level}}
               end
         end,
         loop(Membership_Vector, Key, Value, Skip_List);
      
      {From, {set, LR, From_Key, Level}} ->
         Iter  =  case LR of
                     right -> fun([Left, _Right]) -> [Left, [From_Key, From]] end;
                     left -> fun([_Left, Right]) -> [[From_Key, From], Right] end
                  end,
         loop(Membership_Vector, Key, Value, n_map(Iter, Skip_List, Level));
      
      Any ->
         ?error({loop_Any, Any}),
         loop(Membership_Vector, Key, Value, Skip_List)
   end.

dummy_node() -> spawn(fun dummy_node_/0).
dummy_node_() ->
   receive
      {put, _} -> pass;
      {From, {get, _, Lis}} -> From ! {reply, {get, Lis}};
      {From, {join, _}} -> From ! {reply, {join, [dummy__, self()], [dummy__, self()]}};
      {From, {join_level, _, _, _, _}} -> From ! {reply, {join_level, [dummy__, self()]}};
      {_From, {set, _, _, _}} -> pass;
      Any -> ?error(Any)
   end,
   dummy_node_().
 
n_map(Func, [H | T], 1) -> [Func(H) | T];
n_map(Func, [H | T], N) -> [H | n_map(Func, T, N - 1)].
 
get_next(Skip_List, Key, Key2) -> get_next_iter(Skip_List, Key, Key2, [undef__, undef__]).
get_next_iter([], _, _, [Key, Node]) -> [Key, Node];
get_next_iter([[[Left_Key, Left_Node], [Right_Key, Right_Node]] | T], Key, Key2, [Key3, Node]) ->
   [Next_Key, Next_Node] = if
      Key < Key2 andalso (Right_Key < Key2 orelse Right_Key == Key2) andalso Right_Key /= dummy__-> [Right_Key, Right_Node];
      Key2 < Key andalso (Key2 < Left_Key orelse Left_Key == Key2) andalso Left_Key /= dummy__ -> [Left_Key, Left_Node];
      true -> [Key3, Node]
   end,
   get_next_iter(T, Key, Key2, [Next_Key, Next_Node]).

find_(Key) ->
   get_node() ! {self(), {find, Key}},
   receive
      {reply, {find, Key2, Value}} -> [Key2, Value];
      Any -> ?error({find, reply, any, Any})
   end.

put_(Key, Value) ->
   [Key2, Node] = find_(Key),
   if
      Key2 == Key -> Node ! {put, Value};
      true -> boot(get_node(), Key, Value)
   end.

get_(Key) -> get_(Key, Key).
get_(Start_Key, End_Key) ->
   [_, Node] = find_(Start_Key),
   Node ! {self(), {get, End_Key, []}},
   receive
      {reply, {get, Lis}} -> lists:reverse(Lis);
      Any -> ?error(Any)
   end.