amt.erl

-module(amt).

-compile(export_all).

-type kv() :: {Key :: integer(), Value :: term()}.
-type tree() :: {tree, orddict:orddict()} | {value, kv()}.
-type either(A) :: {ok, A} | {error, term()}.

-spec empty() -> tree().
empty() ->
    {tree, []}.

-spec find(integer(), tree()) -> either(term()).
find(Key, Tree) ->
    find(Key, Tree, 0).

-spec find(integer(), tree(), integer()) -> either(term()).
find(Key, {value, {Key, Value}}, _Level) ->
    {ok, Value};
find(_Key, {value, {_DifferentKey, _Value}}, _Level) ->
    {error, notfound};
find(Key, {tree, Mapping}, Level) ->
    case orddict:find(index_in_level(Key, Level), Mapping) of
        error ->
            {error, notfound};
        {ok, {value, {Key, Value}}} ->
            {ok, Value};
        {ok, {value, {_DifferentKey, _Value}}} ->
            {error, notfound};
        {ok, {tree, _Mapping}=Tree} ->
            find(Key, Tree, Level + 5)
    end.

insert(Key, Value, Tree) ->
    insert(Key, Value, Tree, 0).

%% overwrite
insert(Key, Value, {value, {Key, _OldVal}}, _Level) ->
    {value, {Key, Value}};
%% collision
insert(Key, Value, {value, {DifferentKey, DifferentVal}}, Level) ->
    make_collision_node({Key, Value}, {DifferentKey, DifferentVal}, Level);
insert(Key, Value, {tree, Mapping}, Level) ->
    Index = index_in_level(Key, Level),
    case orddict:find(Index, Mapping) of
        %% no collision
        error ->
            {tree, orddict:store(Index, {value, {Key, Value}}, Mapping)};
        {ok, Tree} ->
            {tree, orddict:store(Index,
                                 insert(Key, Value, Tree, Level + 5),
                                 Mapping)}
    end.

make_collision_node({AKey, AVal}, {BKey, BVal}, Level) ->
    ATree = {value, {AKey, AVal}},
    BTree = {value, {BKey, BVal}},
    WithA = orddict:store(index_in_level(AKey, Level), ATree, []),
    {tree, orddict:store(index_in_level(BKey, Level), BTree, WithA)}.

-spec index_in_level(integer(), integer()) -> integer().
index_in_level(Integer, Level) ->
    (Integer bsr Level) band 31.