diff options
author | Robert Newson <rnewson@apache.org> | 2020-07-20 12:14:11 +0100 |
---|---|---|
committer | GitHub Enterprise <noreply@github.ibm.com> | 2020-07-20 12:14:11 +0100 |
commit | 9e1483ae605a031e6cf8471d127283403574984c (patch) | |
tree | c704432fb924a3fc32015079b72409618f440d11 | |
parent | 0a2eca50dc29cb3a8f9048e734e61857a475868a (diff) | |
parent | 842c116a4e76ff48e7478fbf0799eed770a0a6fb (diff) | |
download | couchdb-9e1483ae605a031e6cf8471d127283403574984c.tar.gz |
Merge pull request #25 from cloudant/group-reduce-rev
Allow group reduce in reverse order
-rw-r--r-- | src/ebtree.erl | 73 |
1 files changed, 55 insertions, 18 deletions
diff --git a/src/ebtree.erl b/src/ebtree.erl index b37963a18..94e757b3e 100644 --- a/src/ebtree.erl +++ b/src/ebtree.erl @@ -11,9 +11,11 @@ range/6, reverse_range/6, fold/4, + fold/5, reduce/4, full_reduce/2, group_reduce/7, + group_reduce/8, validate_tree/2 ]). @@ -126,47 +128,60 @@ lookup(Db, #tree{} = Tree, Key) -> fold(Db, Tree, Fun, false). +%% @equiv fold(Db, Tree, Fun, Acc, []) +-spec fold(Db :: term(), Tree :: #tree{}, Fun :: fun(), Acc :: term()) -> term(). +fold(Db, #tree{} = Tree, Fun, Acc) -> + fold(Db, Tree, Fun, Acc, []). + + %% @doc Custom traversal of the ebtree. %% @param Db An erlfdb database or transaction. %% @param Tree the ebtree. %% @param Fun A callback function as nodes are loaded that directs the traversal. %% @param Acc The initial accumulator. +%% @param Options Currently supported options are [{dir, fwd}] and [{dir, rev}] %% @returns the final accumulator. --spec fold(Db :: term(), Tree :: #tree{}, Fun :: fun(), Acc :: term()) -> term(). -fold(Db, #tree{} = Tree, Fun, Acc) -> +-spec fold(Db :: term(), Tree :: #tree{}, Fun :: fun(), Acc :: term(), Options :: list()) -> term(). +fold(Db, #tree{} = Tree, Fun, Acc, Options) -> {_, Reduce} = erlfdb:transactional(Db, fun(Tx) -> Root = get_node(Tx, Tree, ?NODE_ROOT_ID), - fold(Db, Tree, Root, Fun, Acc) + fold(Db, Tree, Root, Fun, Acc, Options) end), Reduce. -fold(Db, #tree{} = Tree, #node{} = Node, Fun, Acc) -> - fold(Db, #tree{} = Tree, Node#node.members, Fun, Acc); + +fold(Db, #tree{} = Tree, #node{} = Node, Fun, Acc, Options) -> + Dir = proplists:get_value(dir, Options, fwd), + Members = case Dir of + fwd -> Node#node.members; + rev -> lists:reverse(Node#node.members) + end, + fold(Db, #tree{} = Tree, Members, Fun, Acc, Options); -fold(_Db, #tree{} = _Tree, [], _Fun, Acc) -> +fold(_Db, #tree{} = _Tree, [], _Fun, Acc, _Options) -> {ok, Acc}; -fold(Db, #tree{} = Tree, [{K, V} | Rest], Fun, Acc0) -> +fold(Db, #tree{} = Tree, [{K, V} | Rest], Fun, Acc0, Options) -> case Fun({visit, K, V}, Acc0) of {ok, Acc1} -> - fold(Db, Tree, Rest, Fun, Acc1); + fold(Db, Tree, Rest, Fun, Acc1, Options); {stop, Acc1} -> {stop, Acc1} end; -fold(Db, #tree{} = Tree, [{F, L, P, R} | Rest], Fun, Acc0) -> +fold(Db, #tree{} = Tree, [{F, L, P, R} | Rest], Fun, Acc0, Options) -> case Fun({traverse, F, L, R}, Acc0) of {ok, Acc1} -> Node = get_node(Db, Tree, P), - case fold(Db, Tree, Node, Fun, Acc1) of + case fold(Db, Tree, Node, Fun, Acc1, Options) of {ok, Acc2} -> - fold(Db, Tree, Rest, Fun, Acc2); + fold(Db, Tree, Rest, Fun, Acc2, Options); {stop, Acc2} -> {stop, Acc2} end; {skip, Acc1} -> - fold(Db, Tree, Rest, Fun, Acc1); + fold(Db, Tree, Rest, Fun, Acc1, Options); {stop, Acc1} -> {stop, Acc1} end. @@ -234,6 +249,13 @@ do_reduce(#tree{} = Tree, MapValues, ReduceValues) when is_list(MapValues), is_l do_reduce(Tree, [], [reduce_values(Tree, MapValues, false) | ReduceValues]). +%% @equiv group_reduce(Db, Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, UserAcc0, []) +-spec group_reduce(Db :: term(), Tree :: #tree{}, StartKey :: term(), EndKey :: term(), + GroupKeyFun :: fun(), UserAccFun :: fun(), UserAcc0 :: term()) -> term(). +group_reduce(Db, #tree{} = Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, UserAcc0) -> + group_reduce(Db, Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, UserAcc0, []). + + %% @doc Calculate the reduce value for all groups in the specified range. %% @param Db An erlfdb database or transaction. %% @param Tree The ebtree. @@ -242,19 +264,24 @@ do_reduce(#tree{} = Tree, MapValues, ReduceValues) when is_list(MapValues), is_l %% @param GroupKeyFun A function that takes a key as a parameter and returns the group key. %% @param UserAccFun A function called when a new group reduction is calculated and returns an acc. %% @param UserAcc0 The initial accumulator. +%% @param Options Currently supported options are [{dir, fwd}] and [{dir, rev}] %% @returns the final accumulator. -spec group_reduce(Db :: term(), Tree :: #tree{}, StartKey :: term(), EndKey :: term(), - GroupKeyFun :: fun(), UserAccFun :: fun(), UserAcc0 :: term()) -> term(). -group_reduce(Db, #tree{} = Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, UserAcc0) -> + GroupKeyFun :: fun(), UserAccFun :: fun(), UserAcc0 :: term(), Options :: list()) -> term(). +group_reduce(Db, #tree{} = Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, UserAcc0, Options) -> + Dir = proplists:get_value(dir, Options, fwd), NoGroupYet = ?MIN, Fun = fun ({visit, Key, Value}, {CurrentGroup, UserAcc, MapAcc, ReduceAcc}) -> + BeforeStart = less_than(Tree, Key, StartKey), AfterEnd = greater_than(Tree, Key, EndKey), InRange = in_range(Tree, StartKey, Key, EndKey), KeyGroup = GroupKeyFun(Key), SameGroup = CurrentGroup =:= KeyGroup, if - AfterEnd -> + Dir == fwd andalso AfterEnd -> + {stop, {CurrentGroup, UserAcc, MapAcc, ReduceAcc}}; + Dir == rev andalso BeforeStart -> {stop, {CurrentGroup, UserAcc, MapAcc, ReduceAcc}}; SameGroup -> {ok, {CurrentGroup, UserAcc, [{Key, Value} | MapAcc], ReduceAcc}}; @@ -274,9 +301,13 @@ group_reduce(Db, #tree{} = Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, User FirstInRange = in_range(Tree, StartKey, FirstKey, EndKey), LastInRange = in_range(Tree, StartKey, LastKey, EndKey), if - BeforeStart -> + Dir == fwd andalso BeforeStart -> {skip, {CurrentGroup, UserAcc, MapAcc, ReduceAcc}}; - AfterEnd -> + Dir == rev andalso AfterEnd -> + {skip, {CurrentGroup, UserAcc, MapAcc, ReduceAcc}}; + Dir == fwd andalso AfterEnd -> + {stop, {CurrentGroup, UserAcc, MapAcc, ReduceAcc}}; + Dir == rev andalso BeforeStart -> {stop, {CurrentGroup, UserAcc, MapAcc, ReduceAcc}}; Whole andalso FirstInRange andalso LastInRange -> {skip, {CurrentGroup, UserAcc, MapAcc, [Reduction | ReduceAcc]}}; @@ -284,7 +315,7 @@ group_reduce(Db, #tree{} = Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, User {ok, {CurrentGroup, UserAcc, MapAcc, ReduceAcc}} end end, - {CurrentGroup, UserAcc1, MapValues, ReduceValues} = fold(Db, Tree, Fun, {NoGroupYet, UserAcc0, [], []}), + {CurrentGroup, UserAcc1, MapValues, ReduceValues} = fold(Db, Tree, Fun, {NoGroupYet, UserAcc0, [], []}, Options), if MapValues /= [] orelse ReduceValues /= [] -> FinalGroup = do_reduce(Tree, MapValues, ReduceValues), @@ -1099,6 +1130,12 @@ group_reduce_level_test_() -> ?_test(?assertEqual([{[1, 0], 408}, {[1, 1], 441}, {[1, 2], 376}], group_reduce(Db, Tree, [1], [2], GroupKeyFun, UserAccFun, []))), + ?_test(?assertEqual([{[1, 0], 408}, {[1, 1], 441}, {[1, 2], 376}], + group_reduce(Db, Tree, [1], [2], GroupKeyFun, UserAccFun, [], [{dir, fwd}]))), + + ?_test(?assertEqual([{[1, 2], 376}, {[1, 1], 441}, {[1, 0], 408}], + group_reduce(Db, Tree, [1], [2], GroupKeyFun, UserAccFun, [], [{dir, rev}]))), + ?_test(?assertEqual([{[0,0],432}, {[0,1],468}, {[0,2],400}, {[1,0],408}, {[1,1],441}, {[1,2],376}, {[2,0],384}, {[2,1],416}, {[2,2],450}, {[3,0],459}, {[3,1],392}, {[3,2],424}], group_reduce(Db, Tree, ebtree:min(), ebtree:max(), GroupKeyFun, UserAccFun, []))) |