-module(santa).
-author('ok@cs.otago.ac.nz'). % Richard A. O'Keefe
-export([start/0]).

%   This is an Erlang solution to "The Santa Claus problem",
%   as discussed by Simon Peyton Jones (with a Haskell solution using
%   Software Transactional Memory) in "Beautiful code".
%   He quotes J.A.Trono "A new exercise in concurrency", SIGCSE 26:8-10, 1994.
%
%	Santa repeatedly sleeps until wakened by either all of his
%	nine reindeer, back from their holidays, or by a group of three
%	of his ten elves.  If awakened by the reindeer, he harnesses
%	each of them to his sleight, delivers toys with them, and finally
%	unharnesses them (allowing them to go off on holiday).  If
%	awakened by a group of elves, he shows each of the group into
%	his study, consults with them on toy R&D, and finally shows them
%	each out (allowing them to go back to work).  Santa should give
%	priority to the reindeer in the case that there is both a group
%	of elves and a group of reindeer waiting.
%
%   Inspired by an old example of Dijkstra's, I solve this problem by
%   introducing two secretaries: Robin and Edna.  The reindeer ask Robin
%   for appointments.  As soon as she has nine waiting reindeer she sends
%   them as a group to Santa.  The elves as Edna for appointments.  As
%   soon as she has three waiting elves she sends them as a group to Santa.
%
%   The Haskell version is 77 SLOC of complex code.
%   The Erlang  version is 43 SLOC of straightforward code.

worker(Secretary, Message) ->
    receive after random:uniform(1000) -> ok end,  % random delay
    Secretary ! self(),			% send my PID to the secretary
    Gate_Keeper = receive X -> X end,	% await permission to enter
    io:put_chars(Message),		% do my action
    Gate_Keeper ! {leave,self()},	% tell the gate-keeper I'm done
    worker(Secretary, Message).		% do it all again

secretary(Santa, Species, Count) ->
    secretary_loop(Count, [], {Santa,Species,Count}).

secretary_loop(0, Group, {Santa,Species,Count}) ->
    Santa ! {Species,Group},
    secretary(Santa, Species, Count);
secretary_loop(N, Group, State) ->
    receive PID ->
        secretary_loop(N-1, [PID|Group], State)
    end.

santa() ->
    {Species,Group} =
	receive				% first pick up a reindeer group
	    {reindeer,G} -> {reindeer,G}% if there is one, otherwise
	after 0 ->
	        receive			% wait for reindeer or elves,
	            {reindeer,G} -> {reindeer,G}
	          ; {elves,G}    -> {elves,G}
	        end			% whichever turns up first.
	end,	        
    case Species
      of reindeer -> io:put_chars("Ho, ho, ho!  Let's deliver toys!\n")
       ; elves    -> io:put_chars("Ho, ho, ho!  Let's meet in the study!\n")
    end,
    [PID ! self() || PID <- Group],	% tell them all to enter
    [receive {leave,PID} -> ok end	% wait for each of them to leave
	|| PID <- Group],
    santa().

spawn_worker(Secretary, Before, I, After) ->
    Message = Before ++ integer_to_list(I) ++ After,
    spawn(fun () -> worker(Secretary, Message) end).

start() ->
    Santa = spawn(fun () -> santa() end),
    Robin = spawn(fun () -> secretary(Santa, reindeer, 9) end),
    Edna  = spawn(fun () -> secretary(Santa, elves,    3) end),
    [spawn_worker(Robin, "Reindeer ", I, " delivering toys.\n")
     || I <- lists:seq(1, 9)],
    [spawn_worker(Edna,  "Elf ",      I, " meeting in the study.\n")
     || I <- lists:seq(1, 10)].