diff options
Diffstat (limited to 'aoc2023/build/dev/erlang/pqueue/src/pqueue3.erl')
| -rw-r--r-- | aoc2023/build/dev/erlang/pqueue/src/pqueue3.erl | 404 |
1 files changed, 0 insertions, 404 deletions
diff --git a/aoc2023/build/dev/erlang/pqueue/src/pqueue3.erl b/aoc2023/build/dev/erlang/pqueue/src/pqueue3.erl deleted file mode 100644 index 03b370a..0000000 --- a/aoc2023/build/dev/erlang/pqueue/src/pqueue3.erl +++ /dev/null @@ -1,404 +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 -%%% ==A Large Priority Queue.== -%%% This priority queue implementation depends on layered tuples, so that tuple -%%% access times can be exploited for quick in/out priority queue operations -%%% when using 64 or more total priorities. This implementation was created -%%% to avoid the slowness within the priority queue used by -%%% both RabbitMQ and Riak -%%% (https://github.com/basho/riak_core/blob/master/src/priority_queue.erl). -%%% @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(pqueue3). --author('mjtruog at protonmail dot com'). - -%% external interface --export([in/2, % O(1) - in/3, % O(1) - is_empty/1, % O(1) - is_queue/1, % O(1) - len/1, % O(N) - new/0, % O(1) - new/1, % O(1) - out/1, % O(1) amortized, O(N) worst case - out/2, % O(1) amortized, O(N) worst case - pout/1, % O(1) amortized, O(N) worst case - to_list/1]). % O(N) - -%%%------------------------------------------------------------------------ -%%% External interface functions -%%%------------------------------------------------------------------------ - --type pqueue3() :: {integer(), integer(), empty | integer(), tuple()}. --type pqueue3_empty() :: {integer(), integer(), empty, tuple()}. - -%%------------------------------------------------------------------------- -%% @doc -%% ===Append an item to the tail of the 0 priority queue.=== -%% O(1) -%% @end -%%------------------------------------------------------------------------- - --spec in(term(), pqueue3()) -> pqueue3(). - -in(Value, Q) -> - in(Value, 0, Q). - -%%------------------------------------------------------------------------- -%% @doc -%% ===Append an item to the tail of a specific priority queue.=== -%% O(1) -%% @end -%%------------------------------------------------------------------------- - --spec in(term(), integer(), pqueue3()) -> pqueue3(). - -in(_, P, {Size, Offset, _, _}) - when (P + Offset) < 0; (P + Offset) > Size -> - erlang:exit(badarg); -in(Value, P, {Size, Offset, empty, Bins}) -> - PriorityIndex = P + Offset, - {Size, Offset, PriorityIndex, - in_queue(layer_indexes(Size, PriorityIndex), Value, Bins)}; -in(Value, P, {Size, Offset, I, Bins}) - when (P + Offset) < I -> - PriorityIndex = P + Offset, - {Size, Offset, PriorityIndex, - in_queue(layer_indexes(Size, PriorityIndex), Value, Bins)}; -in(Value, P, {Size, Offset, I, Bins}) -> - {Size, Offset, I, - in_queue(layer_indexes(Size, P + Offset), Value, Bins)}. - -%%------------------------------------------------------------------------- -%% @doc -%% ===Check if the priority queue is empty.=== -%% O(1) -%% @end -%%------------------------------------------------------------------------- - --spec is_empty(pqueue3()) -> 'true' | 'false'. - -is_empty({_, _, empty, _}) -> - true; -is_empty({_, _, _, _} = Q) -> - case out(Q) of - {empty, _} -> - true; - {{value, _}, _} -> - false - end. - -%%------------------------------------------------------------------------- -%% @doc -%% ===Check if the priority queue type is as expected.=== -%% O(1) -%% @end -%%------------------------------------------------------------------------- - --spec is_queue(pqueue3()) -> 'true' | 'false'. - -is_queue({Size, Offset, I, Bins}) - when is_integer(Size), is_integer(Offset), is_tuple(Bins) -> - (I =:= empty) or is_integer(I); -is_queue(_) -> - false. - -%%------------------------------------------------------------------------- -%% @doc -%% ===Determine the length of a priority queue.=== -%% O(N) -%% @end -%%------------------------------------------------------------------------- - --spec len(pqueue3()) -> non_neg_integer(). - -len(Q) -> - len(0, out(Q)). -len(I, {empty, _}) -> - I; -len(I, {{value, _}, Q}) -> - len(I + 1, out(Q)). - -%%------------------------------------------------------------------------- -%% @doc -%% ===Create a new priority queue.=== -%% O(1) -%% @end -%%------------------------------------------------------------------------- - --spec new() -> pqueue3_empty(). - -new() -> - new([]). - -%%------------------------------------------------------------------------- -%% @doc -%% ===Create a new priority queue with customization options.=== -%% O(1) -%% @end -%%------------------------------------------------------------------------- - --spec new(list({atom(), term()})) -> pqueue3(). - -new(Options) -> - Size = proplists:get_value(priorities, Options, 256), - MiddleZero = proplists:get_value(middle_priority_zero, Options, true), - Offset = if - MiddleZero =:= true -> - erlang:round((Size / 2) + 0.5) - 1; - true -> - 0 - end, - {Size, Offset, empty, create(layer_sizes(Size))}. - -%%------------------------------------------------------------------------- -%% @doc -%% ===Take an item from the head of the priority queue.=== -%% O(1) amortized, O(N) worst case -%% @end -%%------------------------------------------------------------------------- - --spec out(pqueue3()) -> - {{'value', term()}, pqueue3()} | {'empty', pqueue3()}. - -out({_, _, empty, _} = Q) -> - {empty, Q}; -out({Size, Offset, I, Bins}) -> - {Result, NewI, NewBins} = out_check( - I, Size, out_queue(layer_indexes(Size, I), Bins) - ), - {Result, {Size, Offset, NewI, NewBins}}. - -%%------------------------------------------------------------------------- -%% @doc -%% ===Take an item of a specific priority from the head of the queue.=== -%% O(1) amortized, O(N) worst case -%% @end -%%------------------------------------------------------------------------- - --spec out(integer(), pqueue3()) -> - {{'value', term()}, pqueue3()} | {'empty', pqueue3()}. - -out(P, {Size, Offset, _, _}) - when (P + Offset) < 0; (P + Offset) > Size -> - erlang:exit(badarg); -out(_, {_, _, empty, _} = Q) -> - {empty, Q}; -out(P, {Size, Offset, I, Bins}) -> - {Result, NewBins} = out_queue(layer_indexes(Size, P + Offset), Bins), - {Result, {Size, Offset, I, NewBins}}. - -%%------------------------------------------------------------------------- -%% @doc -%% ===Take an item from the head of the priority queue.=== -%% Includes the priority in the return value. -%% O(1) amortized, O(N) worst case -%% @end -%%------------------------------------------------------------------------- - --spec pout(pqueue3()) -> - {{'value', term(), integer()}, pqueue3()} | {'empty', pqueue3()}. - -pout({_, _, empty, _} = Q) -> - {empty, Q}; -pout({Size, Offset, I, Bins}) -> - {Result, NewI, NewBins} = pout_check( - I, Size, Offset, out_queue(layer_indexes(Size, I), Bins) - ), - {Result, {Size, Offset, NewI, NewBins}}. - -%%------------------------------------------------------------------------- -%% @doc -%% ===Convert the priority queue to a list.=== -%% O(N) -%% @end -%%------------------------------------------------------------------------- - --spec to_list(pqueue3()) -> list(term()). - -to_list(Q) -> - to_list([], out(Q)). -to_list(L, {empty, _}) -> - lists:reverse(L); -to_list(L, {{value, Value}, Q}) -> - to_list([Value | L], out(Q)). - -%%%------------------------------------------------------------------------ -%%% Private functions -%%%------------------------------------------------------------------------ - -create([]) -> - queue:new(); - -create([I | Is]) -> - erlang:make_tuple(I + 1, create(Is)). - -in_queue({I1}, Value, Bins1) -> - erlang:setelement(I1, Bins1, queue:in(Value, erlang:element(I1, Bins1))); - -in_queue({I1, I2}, Value, Bins1) -> - Bins2 = erlang:element(I1, Bins1), - erlang:setelement(I1, Bins1, - erlang:setelement(I2, Bins2, queue:in(Value, erlang:element(I2, Bins2)))); - -in_queue({I1, I2, I3}, Value, Bins1) -> - Bins2 = erlang:element(I1, Bins1), - Bins3 = erlang:element(I2, Bins2), - erlang:setelement(I1, Bins1, - erlang:setelement(I2, Bins2, - erlang:setelement(I3, Bins3, queue:in(Value, erlang:element(I3, Bins3))))); - -in_queue({I1, I2, I3, I4}, Value, Bins1) -> - Bins2 = erlang:element(I1, Bins1), - Bins3 = erlang:element(I2, Bins2), - Bins4 = erlang:element(I3, Bins3), - erlang:setelement(I1, Bins1, - erlang:setelement(I2, Bins2, - erlang:setelement(I3, Bins3, - erlang:setelement(I4, Bins4, queue:in(Value, erlang:element(I4, Bins4)))))). - -pout_check(Size, Size, _, {empty, Bins}) -> - {empty, empty, Bins}; -pout_check(I, _, Offset, {{value, Value}, Bins}) -> - {{value, Value, I - Offset}, I, Bins}; -pout_check(I, Size, Offset, {empty, Bins}) -> - NewI = I + 1, - pout_check(NewI, Size, Offset, out_queue(layer_indexes(Size, NewI), Bins)). - -out_check(Size, Size, {empty, Bins}) -> - {empty, empty, Bins}; -out_check(I, _, {{value, _} = Result, Bins}) -> - {Result, I, Bins}; -out_check(I, Size, {empty, Bins}) -> - NewI = I + 1, - out_check(NewI, Size, out_queue(layer_indexes(Size, NewI), Bins)). - -out_queue({I1}, Bins1) -> - {Result, NewQueue} = queue:out(erlang:element(I1, Bins1)), - {Result, - erlang:setelement(I1, Bins1, NewQueue)}; - -out_queue({I1, I2}, Bins1) -> - Bins2 = erlang:element(I1, Bins1), - {Result, NewQueue} = queue:out(erlang:element(I2, Bins2)), - {Result, - erlang:setelement(I1, Bins1, - erlang:setelement(I2, Bins2, NewQueue))}; - -out_queue({I1, I2, I3}, Bins1) -> - Bins2 = erlang:element(I1, Bins1), - Bins3 = erlang:element(I2, Bins2), - {Result, NewQueue} = queue:out(erlang:element(I3, Bins3)), - {Result, - erlang:setelement(I1, Bins1, - erlang:setelement(I2, Bins2, - erlang:setelement(I3, Bins3, NewQueue)))}; - -out_queue({I1, I2, I3, I4}, Bins1) -> - Bins2 = erlang:element(I1, Bins1), - Bins3 = erlang:element(I2, Bins2), - Bins4 = erlang:element(I3, Bins3), - {Result, NewQueue} = queue:out(erlang:element(I4, Bins4)), - {Result, - erlang:setelement(I1, Bins1, - erlang:setelement(I2, Bins2, - erlang:setelement(I3, Bins3, - erlang:setelement(I4, Bins4, NewQueue))))}. - -layer_indexes(Size, PriorityIndex) -> - if - Size =< 127 -> - {PriorityIndex + 1}; - Size =< 255 -> - <<I1:4, I2:4>> = <<PriorityIndex:8>>, - {I1 + 1, I2 + 1}; - Size =< 511 -> - <<I1:4, I2:5>> = <<PriorityIndex:9>>, - {I1 + 1, I2 + 1}; - Size =< 1023 -> - <<I1:3, I2:3, I3:4>> = <<PriorityIndex:10>>, - {I1 + 1, I2 + 1, I3 + 1}; - Size =< 2047 -> - <<I1:3, I2:4, I3:4>> = <<PriorityIndex:11>>, - {I1 + 1, I2 + 1, I3 + 1}; - Size =< 4095 -> - <<I1:4, I2:4, I3:4>> = <<PriorityIndex:12>>, - {I1 + 1, I2 + 1, I3 + 1}; - Size =< 8191 -> - <<I1:4, I2:4, I3:5>> = <<PriorityIndex:13>>, - {I1 + 1, I2 + 1, I3 + 1}; - Size =< 16383 -> - <<I1:4, I2:5, I3:5>> = <<PriorityIndex:14>>, - {I1 + 1, I2 + 1, I3 + 1}; - Size =< 32767 -> - <<I1:3, I2:4, I3:4, I4:4>> = <<PriorityIndex:15>>, - {I1 + 1, I2 + 1, I3 + 1, I4 + 1}; - Size =< 65535 -> - <<I1:4, I2:4, I3:4, I4:4>> = <<PriorityIndex:16>>, - {I1 + 1, I2 + 1, I3 + 1, I4 + 1} - end. - -layer_sizes(Size) -> - if - Size =< 127 -> - <<I1:7>> = <<127:7>>, - [I1]; - Size =< 255 -> - <<I1:4, I2:4>> = <<255:8>>, - [I1, I2]; - Size =< 511 -> - <<I1:4, I2:5>> = <<511:9>>, - [I1, I2]; - Size =< 1023 -> - <<I1:3, I2:3, I3:4>> = <<1023:10>>, - [I1, I2, I3]; - Size =< 2047 -> - <<I1:3, I2:4, I3:4>> = <<2047:11>>, - [I1, I2, I3]; - Size =< 4095 -> - <<I1:4, I2:4, I3:4>> = <<4095:12>>, - [I1, I2, I3]; - Size =< 8191 -> - <<I1:4, I2:4, I3:5>> = <<8191:13>>, - [I1, I2, I3]; - Size =< 16383 -> - <<I1:4, I2:5, I3:5>> = <<16383:14>>, - [I1, I2, I3]; - Size =< 32767 -> - <<I1:3, I2:4, I3:4, I4:4>> = <<32767:15>>, - [I1, I2, I3, I4]; - Size =< 65535 -> - <<I1:4, I2:4, I3:4, I4:4>> = <<65535:16>>, - [I1, I2, I3, I4] - end. - |