diff options
Diffstat (limited to 'aoc2023/build/packages/pqueue/src/pqueue2.erl')
| -rw-r--r-- | aoc2023/build/packages/pqueue/src/pqueue2.erl | 483 |
1 files changed, 483 insertions, 0 deletions
diff --git a/aoc2023/build/packages/pqueue/src/pqueue2.erl b/aoc2023/build/packages/pqueue/src/pqueue2.erl new file mode 100644 index 0000000..bbdeaaf --- /dev/null +++ b/aoc2023/build/packages/pqueue/src/pqueue2.erl @@ -0,0 +1,483 @@ +%-*-Mode:erlang;coding:utf-8;tab-width:4;c-basic-offset:4;indent-tabs-mode:()-*- +% ex: set ft=erlang fenc=utf-8 sts=4 ts=4 sw=4 et nomod: +%%% +%%%------------------------------------------------------------------------ +%%% @doc +%%% ==Skew Heap Priority Queue.== +%%% Ulf Wiger suggested pursuing a skew heap as an optimal Erlang priority +%%% queue implementation. Unfortunately, testing has shown this solution to +%%% be more than 2 times slower than pqueue. +%%% @end +%%% +%%% MIT License +%%% +%%% Copyright (c) 2011-2020 Michael Truog <mjtruog at protonmail dot com> +%%% +%%% Permission is hereby granted, free of charge, to any person obtaining a +%%% copy of this software and associated documentation files (the "Software"), +%%% to deal in the Software without restriction, including without limitation +%%% the rights to use, copy, modify, merge, publish, distribute, sublicense, +%%% and/or sell copies of the Software, and to permit persons to whom the +%%% Software is furnished to do so, subject to the following conditions: +%%% +%%% The above copyright notice and this permission notice shall be included in +%%% all copies or substantial portions of the Software. +%%% +%%% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +%%% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +%%% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +%%% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +%%% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +%%% FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +%%% DEALINGS IN THE SOFTWARE. +%%% +%%% @author Michael Truog <mjtruog at protonmail dot com> +%%% @copyright 2011-2020 Michael Truog +%%% @version 2.0.1 {@date} {@time} +%%%------------------------------------------------------------------------ + +-module(pqueue2). +-author('mjtruog at protonmail dot com'). + +%% external interface +-export([in/2, + in/3, + is_empty/1, + is_queue/1, + len/1, + new/0, + out/1, + out/2, + pout/1, + to_list/1, + test/0]). + +%%%------------------------------------------------------------------------ +%%% External interface functions +%%%------------------------------------------------------------------------ + +-ifdef(ERLANG_OTP_VERSION_16). +-type pqueue2() :: + empty | + {integer(), pqueue2(), pqueue2(), element, term()} | + {integer(), pqueue2(), pqueue2(), queue, queue()}. +-else. +-type pqueue2() :: + empty | + {integer(), pqueue2(), pqueue2(), element, term()} | + {integer(), pqueue2(), pqueue2(), queue, queue:queue()}. +-endif. + +%%------------------------------------------------------------------------- +%% @doc +%% ===Append an item to the tail of the 0 priority queue.=== +%% @end +%%------------------------------------------------------------------------- + +-spec in(term(), pqueue2()) -> pqueue2(). + +in(Value, H) -> + in(Value, 0, H). + +%%------------------------------------------------------------------------- +%% @doc +%% ===Append an item to the tail of a specific priority queue.=== +%% @end +%%------------------------------------------------------------------------- + +-spec in(term(), integer(), pqueue2()) -> pqueue2(). + +in(Value, P, H) -> + merge({P, empty, empty, element, Value}, H). + +%%------------------------------------------------------------------------- +%% @doc +%% ===Check if the priority queue is empty.=== +%% @end +%%------------------------------------------------------------------------- + +-spec is_empty(pqueue2()) -> 'true' | 'false'. + +is_empty(empty) -> + true; +is_empty({_, HL, HR, queue, Queue}) -> + is_empty(HL) andalso is_empty(HR) andalso queue:is_empty(Queue); +is_empty(_) -> + false. + +%%------------------------------------------------------------------------- +%% @doc +%% ===Check if the priority queue type is as expected.=== +%% @end +%%------------------------------------------------------------------------- + +-spec is_queue(pqueue2()) -> 'true' | 'false'. + +is_queue(empty) -> + true; +is_queue({P, _, _, element, _}) + when is_integer(P) -> + true; +is_queue({P, _, _, queue, Queue}) + when is_integer(P) -> + queue:is_queue(Queue); +is_queue(_) -> + false. + +%%------------------------------------------------------------------------- +%% @doc +%% ===Determine the length of a priority queue.=== +%% @end +%%------------------------------------------------------------------------- + +-spec len(pqueue2()) -> non_neg_integer(). + +len(H) -> + len(0, out(H)). +len(I, {empty, _}) -> + I; +len(I, {{value, _}, H}) -> + len(I + 1, out(H)). + +%%------------------------------------------------------------------------- +%% @doc +%% ===Create a new priority queue.=== +%% @end +%%------------------------------------------------------------------------- + +-spec new() -> pqueue2(). + +new() -> + empty. + +%%------------------------------------------------------------------------- +%% @doc +%% ===Take an item from the head of the priority queue.=== +%% @end +%%------------------------------------------------------------------------- + +-spec out(pqueue2()) -> + {{'value', term()}, pqueue2()} | {'empty', pqueue2()}. + +out(empty) -> + {empty, empty}; +out({_, HL, HR, element, Value}) -> + {{value, Value}, merge(HL, HR)}; +out({P, HL, HR, queue, Queue}) -> + case queue:out(Queue) of + {{value, _} = Result, NewQueue} -> + {Result, {P, HL, HR, queue, NewQueue}}; + {empty, _} -> + out(merge(HL, HR)) + end. + +%%------------------------------------------------------------------------- +%% @doc +%% ===Take an item of a specific priority from the head of the queue.=== +%% @end +%%------------------------------------------------------------------------- + +-spec out(integer(), pqueue2()) -> + {{'value', term()}, pqueue2()} | {'empty', pqueue2()}. + +out(_, empty) -> + {empty, empty}; +out(P, {P1, _, _, _, _} = H) when P < P1 -> + {empty, H}; +out(P, {P1, HL1, HR1, T, D}) when P > P1 -> + case out(P, HL1) of + {{value, _} = Result, HL2} -> + {Result, {P1, HL2, HR1, T, D}}; + {empty, HL2} -> + case out(P, HR1) of + {{value, _} = Result, HR2} -> + {Result, {P1, HL2, HR2, T, D}}; + {empty, HR2} -> + {empty, {P1, HL2, HR2, T, D}} + end + end; +out(P, {P, HL, HR, element, Value}) -> + {{value, Value}, merge(HL, HR)}; +out(P, {P, HL, HR, queue, Queue}) -> + case queue:out(Queue) of + {{value, _} = Result, NewQueue} -> + {Result, {P, HL, HR, queue, NewQueue}}; + {empty, _} -> + out(P, merge(HL, HR)) + end. + +%%------------------------------------------------------------------------- +%% @doc +%% ===Take an item from the head of the priority queue.=== +%% Includes the priority in the return value. +%% @end +%%------------------------------------------------------------------------- + +-spec pout(pqueue2()) -> + {{'value', term(), integer()}, pqueue2()} | {'empty', pqueue2()}. + +pout(empty) -> + {empty, empty}; +pout({P, HL, HR, element, Value}) -> + {{value, Value, P}, merge(HL, HR)}; +pout({P, HL, HR, queue, Queue}) -> + case queue:out(Queue) of + {{value, Value}, NewQueue} -> + {{value, Value, P}, {P, HL, HR, queue, NewQueue}}; + {empty, _} -> + pout(merge(HL, HR)) + end. + +%%------------------------------------------------------------------------- +%% @doc +%% ===Convert the priority queue to a list.=== +%% @end +%%------------------------------------------------------------------------- + +-spec to_list(pqueue2()) -> list(term()). + +to_list(H) -> + to_list([], out(H)). +to_list(L, {empty, _}) -> + lists:reverse(L); +to_list(L, {{value, Value}, H}) -> + to_list([Value | L], out(H)). + +%%------------------------------------------------------------------------- +%% @doc +%% ===Regression test.=== +%% @end +%%------------------------------------------------------------------------- + +test() -> + Q0 = pqueue2:new(), + true = pqueue2:is_queue(Q0), + Q1 = pqueue2:in(20, 20, Q0), + Q2 = pqueue2:in(19, 19, Q1), + Q3 = pqueue2:in(18, 18, Q2), + Q4 = pqueue2:in(17, 17, Q3), + Q5 = pqueue2:in(16, 16, Q4), + Q6 = pqueue2:in(15, 15, Q5), + Q7 = pqueue2:in(14, 14, Q6), + Q8 = pqueue2:in(13, 13, Q7), + Q9 = pqueue2:in(12, 12, Q8), + Q10 = pqueue2:in(11, 11, Q9), + Q11 = pqueue2:in(10, 10, Q10), + Q12 = pqueue2:in(9, 9, Q11), + Q13 = pqueue2:in(8, 8, Q12), + Q14 = pqueue2:in(7, 7, Q13), + Q15 = pqueue2:in(6, 6, Q14), + Q16 = pqueue2:in(5, 5, Q15), + Q17 = pqueue2:in(4, 4, Q16), + Q18 = pqueue2:in(3, 3, Q17), + Q19 = pqueue2:in(2, 2, Q18), + Q20 = pqueue2:in(1, 1, Q19), + Q21 = pqueue2:in(0, 0, Q20), + Q22 = pqueue2:in(-1, -1, Q21), + Q23 = pqueue2:in(-2, -2, Q22), + Q24 = pqueue2:in(-3, -3, Q23), + Q25 = pqueue2:in(-4, -4, Q24), + Q26 = pqueue2:in(-5, -5, Q25), + Q27 = pqueue2:in(-6, -6, Q26), + Q28 = pqueue2:in(-7, -7, Q27), + Q29 = pqueue2:in(-8, -8, Q28), + Q30 = pqueue2:in(-9, -9, Q29), + Q31 = pqueue2:in(-10, -10, Q30), + Q32 = pqueue2:in(-11, -11, Q31), + Q33 = pqueue2:in(-12, -12, Q32), + Q34 = pqueue2:in(-13, -13, Q33), + Q35 = pqueue2:in(-14, -14, Q34), + Q36 = pqueue2:in(-15, -15, Q35), + Q37 = pqueue2:in(-16, -16, Q36), + Q38 = pqueue2:in(-17, -17, Q37), + Q39 = pqueue2:in(-18, -18, Q38), + Q40 = pqueue2:in(-19, -19, Q39), + Q41 = pqueue2:in(-20, -20, Q40), + Q42 = pqueue2:in(-20, -20, Q41), + Q43 = pqueue2:in(-19, -19, Q42), + Q44 = pqueue2:in(-18, -18, Q43), + Q45 = pqueue2:in(-17, -17, Q44), + Q46 = pqueue2:in(-16, -16, Q45), + Q47 = pqueue2:in(-15, -15, Q46), + Q48 = pqueue2:in(-14, -14, Q47), + Q49 = pqueue2:in(-13, -13, Q48), + Q50 = pqueue2:in(-12, -12, Q49), + Q51 = pqueue2:in(-11, -11, Q50), + Q52 = pqueue2:in(-10, -10, Q51), + Q53 = pqueue2:in(-9, -9, Q52), + Q54 = pqueue2:in(-8, -8, Q53), + Q55 = pqueue2:in(-7, -7, Q54), + Q56 = pqueue2:in(-6, -6, Q55), + Q57 = pqueue2:in(-5, -5, Q56), + Q58 = pqueue2:in(-4, -4, Q57), + Q59 = pqueue2:in(-3, -3, Q58), + Q60 = pqueue2:in(-2, -2, Q59), + Q61 = pqueue2:in(-1, -1, Q60), + Q62 = pqueue2:in(0, 0, Q61), + Q63 = pqueue2:in(1, 1, Q62), + Q64 = pqueue2:in(2, 2, Q63), + Q65 = pqueue2:in(3, 3, Q64), + Q66 = pqueue2:in(4, 4, Q65), + Q67 = pqueue2:in(5, 5, Q66), + Q68 = pqueue2:in(6, 6, Q67), + Q69 = pqueue2:in(7, 7, Q68), + Q70 = pqueue2:in(8, 8, Q69), + Q71 = pqueue2:in(9, 9, Q70), + Q72 = pqueue2:in(10, 10, Q71), + Q73 = pqueue2:in(11, 11, Q72), + Q74 = pqueue2:in(12, 12, Q73), + Q75 = pqueue2:in(13, 13, Q74), + Q76 = pqueue2:in(14, 14, Q75), + Q77 = pqueue2:in(15, 15, Q76), + Q78 = pqueue2:in(16, 16, Q77), + Q79 = pqueue2:in(17, 17, Q78), + Q80 = pqueue2:in(18, 18, Q79), + Q81 = pqueue2:in(19, 19, Q80), + Q82 = pqueue2:in(20, 20, Q81), + true = pqueue2:is_queue(Q82), + 82 = pqueue2:len(Q82), + [-20, -20, -19, -19, -18, -18, -17, -17, -16, -16, -15, -15, -14, -14, + -13, -13, -12, -12, -11, -11, -10, -10, -9, -9, -8, -8, -7, -7, -6, -6, + -5, -5, -4, -4, -3, -3, -2, -2, -1, -1, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, + 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, + 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20] = pqueue2:to_list(Q82), + {{value, -20}, Q83} = pqueue2:out(Q82), + {{value, -20}, Q84} = pqueue2:out(Q83), + {{value, -19}, Q85} = pqueue2:out(Q84), + {{value, -19}, Q86} = pqueue2:out(Q85), + {{value, -18}, Q87} = pqueue2:out(Q86), + {{value, -18}, Q88} = pqueue2:out(Q87), + {{value, 0}, Q89} = pqueue2:out(0, Q88), + {{value, 0}, Q90} = pqueue2:out(0, Q89), + {empty, _} = pqueue2:out(0, Q90), + {{value, -17, -17}, Q91} = pqueue2:pout(Q90), + {{value, -17, -17}, Q92} = pqueue2:pout(Q91), + {{value, -16, -16}, Q93} = pqueue2:pout(Q92), + {{value, -16, -16}, Q94} = pqueue2:pout(Q93), + {{value, -15, -15}, Q95} = pqueue2:pout(Q94), + {{value, -15, -15}, Q96} = pqueue2:pout(Q95), + {{value, -14, -14}, Q97} = pqueue2:pout(Q96), + {{value, -14, -14}, Q98} = pqueue2:pout(Q97), + {{value, -13, -13}, Q99} = pqueue2:pout(Q98), + {{value, -13, -13}, Q100} = pqueue2:pout(Q99), + {{value, -12, -12}, Q101} = pqueue2:pout(Q100), + {{value, -12, -12}, Q102} = pqueue2:pout(Q101), + {{value, -11, -11}, Q103} = pqueue2:pout(Q102), + {{value, -11, -11}, Q104} = pqueue2:pout(Q103), + {{value, -10, -10}, Q105} = pqueue2:pout(Q104), + {{value, -10, -10}, Q106} = pqueue2:pout(Q105), + {{value, -9, -9}, Q107} = pqueue2:pout(Q106), + {{value, -9, -9}, Q108} = pqueue2:pout(Q107), + {{value, -8, -8}, Q109} = pqueue2:pout(Q108), + {{value, -8, -8}, Q110} = pqueue2:pout(Q109), + {{value, -7, -7}, Q111} = pqueue2:pout(Q110), + {{value, -7, -7}, Q112} = pqueue2:pout(Q111), + {{value, -6, -6}, Q113} = pqueue2:pout(Q112), + {{value, -6, -6}, Q114} = pqueue2:pout(Q113), + {{value, -5, -5}, Q115} = pqueue2:pout(Q114), + {{value, -5, -5}, Q116} = pqueue2:pout(Q115), + {{value, -4, -4}, Q117} = pqueue2:pout(Q116), + {{value, -4, -4}, Q118} = pqueue2:pout(Q117), + {{value, -3, -3}, Q119} = pqueue2:pout(Q118), + {{value, -3, -3}, Q120} = pqueue2:pout(Q119), + {{value, -2, -2}, Q121} = pqueue2:pout(Q120), + {{value, -2, -2}, Q122} = pqueue2:pout(Q121), + {{value, -1, -1}, Q123} = pqueue2:pout(Q122), + {{value, -1, -1}, Q124} = pqueue2:pout(Q123), + {{value, 1, 1}, Q125} = pqueue2:pout(Q124), + {{value, 1, 1}, Q126} = pqueue2:pout(Q125), + {{value, 2, 2}, Q127} = pqueue2:pout(Q126), + {{value, 2, 2}, Q128} = pqueue2:pout(Q127), + {{value, 3, 3}, Q129} = pqueue2:pout(Q128), + {{value, 3, 3}, Q130} = pqueue2:pout(Q129), + {{value, 4, 4}, Q131} = pqueue2:pout(Q130), + {{value, 4, 4}, Q132} = pqueue2:pout(Q131), + {{value, 5, 5}, Q133} = pqueue2:pout(Q132), + {{value, 5, 5}, Q134} = pqueue2:pout(Q133), + {{value, 6, 6}, Q135} = pqueue2:pout(Q134), + {{value, 6, 6}, Q136} = pqueue2:pout(Q135), + {{value, 7, 7}, Q137} = pqueue2:pout(Q136), + {{value, 7, 7}, Q138} = pqueue2:pout(Q137), + {{value, 8, 8}, Q139} = pqueue2:pout(Q138), + {{value, 8, 8}, Q140} = pqueue2:pout(Q139), + {{value, 9, 9}, Q141} = pqueue2:pout(Q140), + {{value, 9, 9}, Q142} = pqueue2:pout(Q141), + {{value, 10, 10}, Q143} = pqueue2:pout(Q142), + {{value, 10, 10}, Q144} = pqueue2:pout(Q143), + {{value, 11, 11}, Q145} = pqueue2:pout(Q144), + {{value, 11, 11}, Q146} = pqueue2:pout(Q145), + {{value, 12, 12}, Q147} = pqueue2:pout(Q146), + {{value, 12, 12}, Q148} = pqueue2:pout(Q147), + {{value, 13, 13}, Q149} = pqueue2:pout(Q148), + {{value, 13, 13}, Q150} = pqueue2:pout(Q149), + {{value, 14, 14}, Q151} = pqueue2:pout(Q150), + {{value, 14, 14}, Q152} = pqueue2:pout(Q151), + {{value, 15, 15}, Q153} = pqueue2:pout(Q152), + {{value, 15, 15}, Q154} = pqueue2:pout(Q153), + {{value, 16, 16}, Q155} = pqueue2:pout(Q154), + {{value, 16, 16}, Q156} = pqueue2:pout(Q155), + {{value, 17, 17}, Q157} = pqueue2:pout(Q156), + {{value, 17, 17}, Q158} = pqueue2:pout(Q157), + {{value, 18, 18}, Q159} = pqueue2:pout(Q158), + {{value, 18, 18}, Q160} = pqueue2:pout(Q159), + {{value, 19, 19}, Q161} = pqueue2:pout(Q160), + {{value, 19, 19}, Q162} = pqueue2:pout(Q161), + {{value, 20, 20}, Q163} = pqueue2:pout(Q162), + {{value, 20, 20}, Q164} = pqueue2:pout(Q163), + true = pqueue2:is_empty(Q164), + {empty, Q165} = pqueue2:pout(Q164), + true = pqueue2:is_empty(Q165), + % test case 1, based on proper testing + C1V0 = pqueue2:in(-18, pqueue2:new()), + C1V1 = pqueue2:in(9, C1V0), + C1V2 = pqueue2:in(-10, -4, C1V1), + C1V3 = pqueue2:in(-29, C1V2), + C1V4 = pqueue2:in(11, C1V3), + 5 = pqueue2:len(C1V4), + [-10, -18, 9, -29, 11] = pqueue2:to_list(C1V4), + % test case 2, based on proper testing + C2V0 = pqueue2:in(-4, -15, pqueue2:new()), + C2V1 = pqueue2:in(13, C2V0), + C2V2 = pqueue2:in(2, C2V1), + [-4, 13, 2] = to_list(C2V2), + ok. + +%%%------------------------------------------------------------------------ +%%% Private functions +%%%------------------------------------------------------------------------ + +merge(empty, empty) -> + empty; +merge(empty, {_, _, _, _, _} = H) -> + H; +merge({_, _, _, _, _} = H, empty) -> + H; +merge({P1, HL1, HR1, T, D}, {P2, _, _, _, _} = H2) when P1 < P2 -> + {P1, HL1, merge(HR1, H2), T, D}; +merge({P1, _, _, _, _} = H1, {P2, HL2, HR2, T, D}) when P1 > P2 -> + {P2, HL2, merge(H1, HR2), T, D}; +merge({P, HL1, HR1, element, Value1}, {P, HL2, HR2, element, Value2}) -> + {P, merge(HL1, HR1), merge(HL2, HR2), queue, + queue:from_list([Value2, Value1])}; +merge({P, HL1, HR1, queue, Queue}, {P, HL2, HR2, element, Value}) -> + {P, merge(HL1, HR1), merge(HL2, HR2), queue, queue:in(Value, Queue)}; +merge({P, HL1, HR1, element, Value}, {P, HL2, HR2, queue, Queue}) -> + {P, merge(HL1, HR1), merge(HL2, HR2), queue, queue:in(Value, Queue)}. + +-ifdef(TEST). +-include_lib("eunit/include/eunit.hrl"). + +-include("pqueue_test.hrl"). + +module_test_() -> + {timeout, ?TEST_TIMEOUT, [ + {"internal tests", ?_assertOk(test())} + ]}. + +long_test_() -> + test_condition([ + {"proper tests", ?_assert(pqueue_proper:qc_pq2())} + ], ?CLOUDI_LONG_TEST_TIMEOUT). + +-endif. + |