%%-------------------------------------------------------------------- %% Copyright (c) 2018-2024 EMQ Technologies Co., Ltd. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at %% %% http://www.apache.org/licenses/LICENSE-2.0 %% %% Unless required by applicable law or agreed to in writing, software %% distributed under the License is distributed on an "AS IS" BASIS, %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. %%-------------------------------------------------------------------- -module(emqx_pqueue_SUITE). -compile(export_all). -compile(nowarn_export_all). -include_lib("eunit/include/eunit.hrl"). -define(PQ, emqx_pqueue). -define(SUITE, ?MODULE). all() -> emqx_common_test_helpers:all(?SUITE). t_is_queue(_) -> Q = ?PQ:new(), ?assertEqual(true, ?PQ:is_queue(Q)), Q1 = ?PQ:in(a, 1, Q), ?assertEqual(true, ?PQ:is_queue(Q1)), ?assertEqual(false, ?PQ:is_queue(bad_queue)). t_is_empty(_) -> Q = ?PQ:new(), ?assertEqual(true, ?PQ:is_empty(Q)), ?assertEqual(false, ?PQ:is_empty(?PQ:in(a, Q))). t_len(_) -> Q = ?PQ:new(), Q1 = ?PQ:in(a, Q), ?assertEqual(1, ?PQ:len(Q1)), Q2 = ?PQ:in(b, 1, Q1), ?assertEqual(2, ?PQ:len(Q2)). t_plen(_) -> Q = ?PQ:new(), Q1 = ?PQ:in(a, Q), ?assertEqual(1, ?PQ:plen(0, Q1)), ?assertEqual(0, ?PQ:plen(1, Q1)), Q2 = ?PQ:in(b, 1, Q1), Q3 = ?PQ:in(c, 1, Q2), ?assertEqual(2, ?PQ:plen(1, Q3)), ?assertEqual(1, ?PQ:plen(0, Q3)), ?assertEqual(0, ?PQ:plen(0, {pqueue, []})). t_to_list(_) -> Q = ?PQ:new(), ?assertEqual([], ?PQ:to_list(Q)), Q1 = ?PQ:in(a, Q), L1 = ?PQ:to_list(Q1), ?assertEqual([{0, a}], L1), Q2 = ?PQ:in(b, 1, Q1), L2 = ?PQ:to_list(Q2), ?assertEqual([{1, b}, {0, a}], L2). t_from_list(_) -> Q = ?PQ:from_list([{1, c}, {1, d}, {0, a}, {0, b}]), ?assertEqual({pqueue, [{-1, {queue, [d], [c], 2}}, {0, {queue, [b], [a], 2}}]}, Q), ?assertEqual(true, ?PQ:is_queue(Q)), ?assertEqual(4, ?PQ:len(Q)). t_in(_) -> Q = ?PQ:new(), Els = [a, b, {c, 1}, {d, 1}, {e, infinity}, {f, 2}], Q1 = lists:foldl( fun ({El, P}, Acc) -> ?PQ:in(El, P, Acc); (El, Acc) -> ?PQ:in(El, Acc) end, Q, Els ), ?assertEqual( {pqueue, [ {infinity, {queue, [e], [], 1}}, {-2, {queue, [f], [], 1}}, {-1, {queue, [d], [c], 2}}, {0, {queue, [b], [a], 2}} ]}, Q1 ). t_out(_) -> Q = ?PQ:new(), {empty, Q} = ?PQ:out(Q), {empty, Q} = ?PQ:out(0, Q), try ?PQ:out(1, Q) of _ -> ct:fail(should_throw_error) catch error:Reason -> ?assertEqual(Reason, badarg) end, {{value, a}, Q} = ?PQ:out(?PQ:from_list([{0, a}])), {{value, a}, {queue, [], [b], 1}} = ?PQ:out(?PQ:from_list([{0, a}, {0, b}])), {{value, a}, {queue, [], [], 0}} = ?PQ:out({queue, [], [a], 1}), {{value, a}, {queue, [c], [b], 2}} = ?PQ:out({queue, [c, b], [a], 3}), {{value, a}, {queue, [e, d], [b, c], 4}} = ?PQ:out({queue, [e, d, c, b], [a], 5}), {{value, a}, {queue, [c], [b], 2}} = ?PQ:out({queue, [c, b, a], [], 3}), {{value, a}, {queue, [d, c], [b], 3}} = ?PQ:out({queue, [d, c], [a, b], 4}), {{value, a}, {queue, [], [], 0}} = ?PQ:out(?PQ:from_list([{1, a}])), {{value, a}, {queue, [c], [b], 2}} = ?PQ:out(?PQ:from_list([{1, a}, {0, b}, {0, c}])), {{value, a}, {pqueue, [{-1, {queue, [b], [], 1}}]}} = ?PQ:out(?PQ:from_list([{1, b}, {2, a}])), {{value, a}, {pqueue, [{-1, {queue, [], [b], 1}}]}} = ?PQ:out(?PQ:from_list([{1, a}, {1, b}])). t_out_2(_) -> {empty, {pqueue, [{-1, {queue, [a], [], 1}}]}} = ?PQ:out(0, ?PQ:from_list([{1, a}])), {{value, a}, {queue, [], [], 0}} = ?PQ:out(1, ?PQ:from_list([{1, a}])), {{value, a}, {pqueue, [{-1, {queue, [], [b], 1}}]}} = ?PQ:out(1, ?PQ:from_list([{1, a}, {1, b}])), {{value, a}, {queue, [b], [], 1}} = ?PQ:out(1, ?PQ:from_list([{1, a}, {0, b}])). t_out_p(_) -> {empty, {queue, [], [], 0}} = ?PQ:out_p(?PQ:new()), {{value, a, 1}, {queue, [b], [], 1}} = ?PQ:out_p(?PQ:from_list([{1, a}, {0, b}])). t_join(_) -> Q = ?PQ:in(a, ?PQ:new()), Q = ?PQ:join(Q, ?PQ:new()), Q = ?PQ:join(?PQ:new(), Q), Q1 = ?PQ:in(a, ?PQ:new()), Q2 = ?PQ:in(b, Q1), Q3 = ?PQ:in(c, Q2), {queue, [c, b], [a], 3} = Q3, Q4 = ?PQ:in(x, ?PQ:new()), Q5 = ?PQ:in(y, Q4), Q6 = ?PQ:in(z, Q5), {queue, [z, y], [x], 3} = Q6, {queue, [z, y], [a, b, c, x], 6} = ?PQ:join(Q3, Q6), PQueue1 = ?PQ:from_list([{1, c}, {1, d}]), PQueue2 = ?PQ:from_list([{1, c}, {1, d}, {0, a}, {0, b}]), PQueue3 = ?PQ:from_list([{1, c}, {1, d}, {-1, a}, {-1, b}]), {pqueue, [ {-1, {queue, [d], [c], 2}}, {0, {queue, [z, y], [x], 3}} ]} = ?PQ:join(PQueue1, Q6), {pqueue, [ {-1, {queue, [d], [c], 2}}, {0, {queue, [z, y], [x], 3}} ]} = ?PQ:join(Q6, PQueue1), {pqueue, [ {-1, {queue, [d], [c], 2}}, {0, {queue, [z, y], [a, b, x], 5}} ]} = ?PQ:join(PQueue2, Q6), {pqueue, [ {-1, {queue, [d], [c], 2}}, {0, {queue, [b], [x, y, z, a], 5}} ]} = ?PQ:join(Q6, PQueue2), {pqueue, [ {-1, {queue, [d], [c], 2}}, {0, {queue, [z, y], [x], 3}}, {1, {queue, [b], [a], 2}} ]} = ?PQ:join(PQueue3, Q6), {pqueue, [ {-1, {queue, [d], [c], 2}}, {0, {queue, [z, y], [x], 3}}, {1, {queue, [b], [a], 2}} ]} = ?PQ:join(Q6, PQueue3), PQueue4 = ?PQ:from_list([{1, c}, {1, d}]), PQueue5 = ?PQ:from_list([{2, a}, {2, b}]), {pqueue, [ {-2, {queue, [b], [a], 2}}, {-1, {queue, [d], [c], 2}} ]} = ?PQ:join(PQueue4, PQueue5). t_filter(_) -> {pqueue, [ {-2, {queue, [10], [4], 2}}, {-1, {queue, [2], [], 1}} ]} = ?PQ:filter( fun (V) when V rem 2 =:= 0 -> true; (_) -> false end, ?PQ:from_list([{0, 1}, {0, 3}, {1, 2}, {2, 4}, {2, 10}]) ). t_highest(_) -> empty = ?PQ:highest(?PQ:new()), 0 = ?PQ:highest(?PQ:from_list([{0, a}, {0, b}])), 2 = ?PQ:highest(?PQ:from_list([{0, a}, {0, b}, {1, c}, {2, d}, {2, e}])).