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, 404 insertions, 0 deletions
diff --git a/aoc2023/build/dev/erlang/pqueue/src/pqueue3.erl b/aoc2023/build/dev/erlang/pqueue/src/pqueue3.erl new file mode 100644 index 0000000..03b370a --- /dev/null +++ b/aoc2023/build/dev/erlang/pqueue/src/pqueue3.erl @@ -0,0 +1,404 @@ +%-*-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. + |