Improved documentation and added additional tests for bpqueue

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) ->