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, 0 insertions, 483 deletions
diff --git a/aoc2023/build/packages/pqueue/src/pqueue2.erl b/aoc2023/build/packages/pqueue/src/pqueue2.erl deleted file mode 100644 index bbdeaaf..0000000 --- a/aoc2023/build/packages/pqueue/src/pqueue2.erl +++ /dev/null @@ -1,483 +0,0 @@ -%-*-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. - |