'1e_sort'.erl

-module('1e_sort').

-compile(export_all).

-define(max_scope, 100000000).
-define(start_step, 1000000).
-define(user_table_num, 10).

start(N) ->
    ets:new(scope_total_table, [named_table, ordered_set, public]),
    [ets:new(erlang:list_to_atom(lists:concat(["user_table_", X])), [named_table, set, public]) || X <- lists:seq(0, ?user_table_num - 1)],
    Data = [{lists:concat(["user", X]), rand:uniform(?max_scope)} || X <- lists:seq(1, N)],
    [begin
        ScopeTableIndex = Scope div ?start_step,
        ScopeTableName = erlang:list_to_atom("scope_table_" ++ erlang:integer_to_list(ScopeTableIndex)),
        UserTableName = erlang:list_to_atom(lists:concat(["user_table_", erlang:phash2(User, ?user_table_num)])),
        ets:insert(UserTableName, {User, Scope}),
        case ets:info(ScopeTableName) of
            undefined ->
                ScopeTableName = ets:new(ScopeTableName, [named_table, ordered_set, public]),
                ets:update_counter(scope_total_table, ScopeTableIndex, 1, {ScopeTableIndex, 0}),
                ets:update_counter(ScopeTableName, Scope, 1, {Scope, 0}),
                ok;
            _ ->
                ets:update_counter(scope_total_table, ScopeTableIndex, 1, {ScopeTableIndex, 0}),
                ets:update_counter(ScopeTableName, Scope, 1, {Scope, 0}),
                ok
        end
     end || {User, Scope} <- Data],

    UserX = lists:concat(["user", rand:uniform(N)]),
    [{_, UserScope}] = ets:lookup(erlang:list_to_atom(lists:concat(["user_table_", erlang:phash2(UserX, ?user_table_num)])), UserX),
    ScopeTableIndex = UserScope div ?start_step,
    ScopeTableName = erlang:list_to_atom("scope_table_" ++ erlang:integer_to_list(ScopeTableIndex)),
    {timer:tc(fun() -> topN(ScopeTableName, UserScope) + topNN(scope_total_table, ScopeTableIndex) end)}.
     % listtopN(UserScope, Data),
     % ets:tab2list(scope_total_table)}.

topN(OrderedSetTable, Key) ->
    case ets:next(OrderedSetTable, Key) of
        '$end_of_table' ->
            1;
        NewKey ->
            1 + topN(OrderedSetTable, NewKey)
    end.

topNN(Table, Key) ->
    case ets:next(Table, Key) of
        '$end_of_table' ->
            0;
        NewKey ->
            [{NewKey, Num}] = ets:lookup(Table, NewKey),
            Num + topNN(Table, NewKey)
    end.

listtopN(Key, List) ->
    erlang:length([X || {_, X} <- List, X > Key]) + 1.