least_busy.erl

%%% @author sergey <[email protected]>
%%% @copyright (C) 2018, sergey
%%% @doc
%%% Given a liast of resources M and list of users N, N > M;
%%% Any resourse might be acquired by one or more users (by request from user).
%%% There is no bound on how many users can acquire single resource.
%%% User may release resource at any time.
%%% User must get resource that is used by least amount of other users.
%%% @end
%%% Created :  8 Oct 2018 by sergey <[email protected]>

-module(least_busy).
-export([new/1,
         add_resources/2,
         remove_resource/2,
         get/2,
         return/3]).

-record(manager,
        {primary,
         buckets}).

-type count() :: non_neg_integer().
-type primary(R, User) :: #{R => {count(), [User]}}.
-type count_buckets(R) :: gb_trees:tree(count(), [R]).

-type manager(Resource, User) ::
        #manager{
           primary :: primary(Resource, User),
           buckets :: count_buckets(Resource)
          }.
-type manager() :: manager(any(), any()).


-spec new(any()) -> manager().
new(Resources) ->
    Primary = maps:from_list([{R, 0} || R <- Resources]),
    Buckets = gb_trees:from_orddict([{0, Resources}]),
    #manager{primary = Primary,
             buckets = Buckets}.


-spec add_resources([any()], manager()) -> manager().
add_resources(Resources, #manager{primary = Primary,
                                  buckets = Buckets} = St) ->
    %% We believe that new resources are not exist in curent state
    NewPrimary = maps:from_list([{R, 0} || R <- Resources]),
    Primary1 = maps:merge(Primary, NewPrimary),
    Buckets1 = case gb_trees:smallest(Buckets) of
        {0, OldResources} ->
            gb_trees:update(0, Resources ++ OldResources, Buckets);
        none ->
            gb_trees:insert(0, Resources, Buckets)
    end,
    St#manager{primary = Primary1,
               buckets = Buckets1}.


-spec remove_resource(any(), manager()) -> {Users :: list(), manager()}.
remove_resource(R, St) ->
    {[], St}.


-spec get(any(), manager()) -> {any(), count(), manager()}.
get(User, #manager{primary = Primary,
                   buckets = Buckets} = St) ->
    {N, [R | Resources]} = gb_trees:smallest(Buckets),
    %% Move resource from bucket N to bucket N + 1
    NewN = N + 1,
    Buckets1 = add_to_bucket(R, NewN, Buckets),
    Buckets2 = case Resources of
                   [] -> gb_trees:delete(N, Buckets1);
                   _ -> gb_trees:update(N, Resources, Buckets1)
               end,
    %% Update resource counter and user list
    {N, Users} = maps:get(R, Primary),  % assert N
    Primary1 = Primary#{R => {NewN, [User | Users]}},
    {R, N, St#manager{primary = Primary1,
                      buckets = Buckets2}}.


-spec return(any(), any(), manager()) -> manager().
return(User, R, #manager{primary = Primary,
                         buckets = Buckets} = St) ->
    {N, Users} = maps:get(R, Primary),
    %% Move resource from bucket N to bucket N - 1
    NewN = N - 1,
    Buckets1 = add_to_bucket(R, NewN, Buckets),
    Resources = gb_trees:get(N, Buckets),
    NewResources = lists:delete(R, Resources),
    Buckets2 = case NewResources of
                   [] -> gb_trees:delete(N, Buckets1);
                   _ -> gb_trees:update(N, NewResources, Buckets1)
               end,
    %% Update resource counter and user list
    Primary1 = Primary#{R => {NewN, lists:delete(User, Users)}},
    St#manager{primary = Primary1,
               buckets = Buckets2}.

%% Internal
add_to_bucket(R, N, Buckets) ->
    case gb_trees:lookup(N, Buckets) of
        {value, Resources} ->
            gb_trees:update(N, [R | Resources], Buckets);
        none ->
            gb_trees:insert(N, [R], Buckets)
    end.