diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/bpqueue.erl | 18 | ||||
| -rw-r--r-- | src/rabbit_tests.erl | 68 |
2 files changed, 80 insertions, 6 deletions
diff --git a/src/bpqueue.erl b/src/bpqueue.erl index 3010cb1182..0210436f30 100644 --- a/src/bpqueue.erl +++ b/src/bpqueue.erl @@ -31,11 +31,16 @@ -module(bpqueue). -%% Block-prefixed queue. This implements a queue of queues, but -%% supporting the normal queue interface. Each inner queue has a -%% prefix, which does not need to be unique, and it is guaranteed that -%% no two consecutive blocks have the same prefix. len/1 returns the -%% flattened length of the queue and is O(1). +%% Block-prefixed queue. From the perspective of the queue interface +%% the datastructure acts like a regular queue where each value is +%% paired with the prefix. +%% +%% This is implemented as a queue of queues, which is more space and +%% time efficient, whilst supporting the normal queue interface. Each +%% inner queue has a prefix, which does not need to be unique, and it +%% is guaranteed that no two consecutive blocks have the same +%% prefix. len/1 returns the flattened length of the queue and is +%% O(1). -export([new/0, is_empty/1, len/1, in/3, in_r/3, out/1, out_r/1, join/2, foldl/3, foldr/3, from_list/1, to_list/1, map_fold_filter_l/4, @@ -233,7 +238,8 @@ to_list1({Prefix, InnerQ}) -> %% you're not interested in. Such blocks appear in the resulting bpq %% without modification. The Fun is then used both to map the value, %% which also allows you to change the prefix (and thus block) of the -%% value, and also to modify the Init/Acc (just like a fold). +%% value, and also to modify the Init/Acc (just like a fold). If the +%% Fun returns 'stop' then it is not applied to any further items. map_fold_filter_l(_PFilter, _Fun, Init, BPQ = {0, _Q}) -> {BPQ, Init}; map_fold_filter_l(PFilter, Fun, Init, {N, Q}) -> diff --git a/src/rabbit_tests.erl b/src/rabbit_tests.erl index 9c659652e5..9e45b7584b 100644 --- a/src/rabbit_tests.erl +++ b/src/rabbit_tests.erl @@ -262,6 +262,9 @@ test_bpqueue() -> [] = bpqueue:to_list(Q), + [{bar,3},{foo,2},{foo,1}] = + bpqueue:foldr(fun(P,V,I) -> [{P,V}|I] end, [], Q2), + F1 = fun (Qn) -> bpqueue:map_fold_filter_l( fun (foo) -> true; @@ -292,6 +295,71 @@ test_bpqueue() -> {Q12, 0} = F2(Q), [] = bpqueue:to_list(Q12), + FF1 = fun (Prefixes) -> + fun (P) -> lists:member(P, Prefixes) end + end, + FF2 = fun (Prefix, Stoppers) -> + fun (Val, Num) -> + case lists:member(Val, Stoppers) of + true -> stop; + false -> {Prefix, -Val, 1 + Num} + end + end + end, + Queue_to_list = fun ({LHS, RHS}) -> {bpqueue:to_list(LHS), RHS} end, + + BPQL = [{foo,[1,2,2]}, {bar,[3,4,5]}, {foo,[5,6,7]}], + BPQ = bpqueue:from_list(BPQL), + + %% no effect + {BPQL, 0} = Queue_to_list(bpqueue:map_fold_filter_l( + FF1([none]), FF2(none, []), 0, BPQ)), + {BPQL, 0} = Queue_to_list(bpqueue:map_fold_filter_l( + FF1([foo,bar]), FF2(none, [1]), 0, BPQ)), + {BPQL, 0} = Queue_to_list(bpqueue:map_fold_filter_l( + FF1([bar]), FF2(none, [3]), 0, BPQ)), + {BPQL, 0} = Queue_to_list(bpqueue:map_fold_filter_r( + FF1([bar]), FF2(foo, [5]), 0, BPQ)), + {[], 0} = Queue_to_list(bpqueue:map_fold_filter_l( + fun(_P)-> throw(explosion) end, + fun(_V, _N) -> throw(explosion) end, 0, Q)), + + %% process 1 item + {[{foo,[-1,2,2]}, {bar,[3,4,5]}, {foo,[5,6,7]}], 1} = + Queue_to_list(bpqueue:map_fold_filter_l( + FF1([foo, bar]), FF2(foo, [2]), 0, BPQ)), + {[{foo,[1,2,2]}, {bar,[-3,4,5]}, {foo,[5,6,7]}], 1} = + Queue_to_list(bpqueue:map_fold_filter_l( + FF1([bar]), FF2(bar, [4]), 0, BPQ)), + {[{foo,[1,2,2]}, {bar,[3,4,5]}, {foo,[5,6,-7]}], 1} = + Queue_to_list(bpqueue:map_fold_filter_r( + FF1([foo, bar]), FF2(foo, [6]), 0, BPQ)), + {[{foo,[1,2,2]}, {bar,[3,4]}, {baz,[-5]}, {foo,[5,6,7]}], 1} = + Queue_to_list(bpqueue:map_fold_filter_r( + FF1([bar]), FF2(baz, [4]), 0, BPQ)), + + %% change prefix + {[{bar,[-1,-2,-2,-3,-4,-5,-5,-6,-7]}], 9} = + Queue_to_list(bpqueue:map_fold_filter_l( + FF1([foo, bar]), FF2(bar, []), 0, BPQ)), + {[{bar,[-1,-2,-2,3,4,5]}, {foo,[5,6,7]}], 3} = + Queue_to_list(bpqueue:map_fold_filter_l( + FF1([foo]), FF2(bar, [5]), 0, BPQ)), + {[{bar,[-1,-2,-2,3,4,5,-5,-6]}, {foo,[7]}], 5} = + Queue_to_list(bpqueue:map_fold_filter_l( + FF1([foo]), FF2(bar, [7]), 0, BPQ)), + {[{foo,[1,2,2,-3,-4]}, {bar,[5]}, {foo,[5,6,7]}], 2} = + Queue_to_list(bpqueue:map_fold_filter_l( + FF1([bar]), FF2(foo, [5]), 0, BPQ)), + + %% edge cases + {[{foo,[-1,-2,-2]}, {bar,[3,4,5]}, {foo,[5,6,7]}], 3} = + Queue_to_list(bpqueue:map_fold_filter_l( + FF1([foo]), FF2(foo, [5]), 0, BPQ)), + {[{foo,[1,2,2]}, {bar,[3,4,5]}, {foo,[-5,-6,-7]}], 3} = + Queue_to_list(bpqueue:map_fold_filter_r( + FF1([foo]), FF2(foo, [2]), 0, BPQ)), + passed. test_simple_n_element_queue(N) -> |