diff options
Diffstat (limited to 'src/lqueue.erl')
| -rw-r--r-- | src/lqueue.erl | 128 |
1 files changed, 128 insertions, 0 deletions
diff --git a/src/lqueue.erl b/src/lqueue.erl new file mode 100644 index 0000000000..9f58b25017 --- /dev/null +++ b/src/lqueue.erl @@ -0,0 +1,128 @@ +%% The contents of this file are subject to the Mozilla Public License +%% Version 1.1 (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.mozilla.org/MPL/ +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and +%% limitations under the License. +%% +%% The Original Code is RabbitMQ. +%% +%% The Initial Developer of the Original Code is VMware, Inc. +%% Copyright (c) 2011-2011 VMware, Inc. All rights reserved. +%% + +-module(lqueue). + +-export([new/0, is_empty/1, len/1, in/2, in_r/2, out/1, out_r/1, join/2, + foldl/3, foldr/3, from_list/1, to_list/1, peek/1, peek_r/1]). + +-define(QUEUE, queue). + +-ifdef(use_specs). + +-export_type([?MODULE/0]). + +-opaque(?MODULE() :: + {non_neg_integer(), ?QUEUE(), maybe_value(), maybe_value()}). +-type(value() :: any()). +-type(maybe_value() :: {'value', value()} | 'empty'). +-type(result() :: {maybe_value(), ?MODULE}). + +-spec(new/0 :: () -> ?MODULE()). +-spec(is_empty/1 :: (?MODULE()) -> boolean()). +-spec(len/1 :: (?MODULE()) -> non_neg_integer()). +-spec(in/2 :: (value(), ?MODULE()) -> ?MODULE()). +-spec(in_r/2 :: (value(), ?MODULE()) -> ?MODULE()). +-spec(out/1 :: (?MODULE()) -> result()). +-spec(out_r/1 :: (?MODULE()) -> result()). +-spec(join/2 :: (?MODULE(), ?MODULE()) -> ?MODULE()). +-spec(foldl/3 :: (fun ((value(), B) -> B), B, ?MODULE()) -> B). +-spec(foldr/3 :: (fun ((value(), B) -> B), B, ?MODULE()) -> B). +-spec(from_list/1 :: ([value()]) -> ?MODULE()). +-spec(to_list/1 :: (?MODULE()) -> [value()]). +-spec(peek(?MODULE) -> maybe_value()). +-spec(peek_r(?MODULE) -> maybe_value()). + +-endif. + +new() -> {0, ?QUEUE:new(), empty, empty}. + +is_empty({0, _Q, _I, _O}) -> true; +is_empty(_ ) -> false. + +in(V, {0, Q, empty, empty}) -> {1, Q, empty, {value, V}}; +in(V, {1, Q, empty, V1 }) -> {2, Q, {value, V}, V1}; +in(V, {1, Q, V1, empty}) -> {2, Q, {value, V}, V1}; +in(V, {N, Q, {value, V1}, V2 }) -> {N+1, ?QUEUE:in(V1, Q), {value, V}, V2}. + +in_r(V, {0, Q, empty, empty }) -> {1, Q, {value, V}, empty}; +in_r(V, {1, Q, V1, empty }) -> {2, Q, V1, {value, V}}; +in_r(V, {1, Q, empty, V1 }) -> {2, Q, V1, {value, V}}; +in_r(V, {N, Q, V1, {value, V2}}) -> {N+1, ?QUEUE:in_r(V2, Q), V1, {value, V}}. + +out({0, _Q, _I, _O} = Q) -> {empty, Q}; +out({1, Q, empty, V}) -> {V, {0, Q, empty, empty}}; +out({1, Q, V, empty}) -> {V, {0, Q, empty, empty}}; +out({2, Q, V1, V2}) -> {V2, {1, Q, empty, V1}}; +out({N, Q, V1, V2}) -> {V3 = {value, _V}, Q1} = ?QUEUE:out(Q), + {V2, {N-1, Q1, V1, V3}}. + +out_r({0, _Q, _I, _O} = Q) -> {empty, Q}; +out_r({1, Q, empty, V}) -> {V, {0, Q, empty, empty}}; +out_r({1, Q, V, empty}) -> {V, {0, Q, empty, empty}}; +out_r({2, Q, V1, V2}) -> {V1, {1, Q, V2, empty}}; +out_r({N, Q, V1, V2}) -> {V3 = {value, _V}, Q1} = ?QUEUE:out_r(Q), + {V1, {N-1, Q1, V3, V2}}. + +join({0, _, _, _}, Q) -> Q; +join(Q, {0, _, _, _}) -> Q; + +join({1, _, empty, {value, V} }, Q) -> in_r(V, Q); +join({1, _, {value, V}, empty }, Q) -> in_r(V, Q); +join({2, _, {value, V1}, {value, V2}}, Q) -> in_r(V2, in_r(V1, Q)); + +join(Q, {1, _, empty, {value, V} }) -> in(V, Q); +join(Q, {1, _, {value, V}, empty }) -> in(V, Q); +join(Q, {2, _, {value, V1}, {value, V2}}) -> in(V1, in(V2, Q)); + +join({L1, Q1, {value, InV}, Out}, {L2, Q2, In, {value, OutV}}) -> + {L1+L2, ?QUEUE:join(?QUEUE:in(InV, Q1), ?QUEUE:in_r(OutV, Q2)), In, Out}. + +to_list({0, _, _, _}) -> []; +to_list({1, _, empty, {value, V}}) -> [V]; +to_list({1, _, {value, V}, empty}) -> [V]; +to_list({_, Q, {value, InV}, {value, OutV}}) -> + [OutV | ?QUEUE:to_list(Q) ++ [InV]]. + +from_list([]) -> new(); +from_list([V]) -> in(V, new()); +from_list([V1, V2]) -> in(V2, in(V1, new())); +from_list([V1 | Vs] = L) -> Q = ?QUEUE:from_list(Vs), + {V2, Q1} = ?QUEUE:out_r(Q), + {length(L), Q1, V2, V1}. + +foldl(Fun, Init, Q) -> + case out(Q) of + {empty, _Q} -> Init; + {{value, V}, Q1} -> foldl(Fun, Fun(V, Init), Q1) + end. + +foldr(Fun, Init, Q) -> + case out_r(Q) of + {empty, _Q} -> Init; + {{value, V}, Q1} -> foldr(Fun, Fun(V, Init), Q1) + end. + +len({L, _Q, _I, _O}) -> + L. + +peek({0, _, _, _}) -> empty; +peek({1, _, V, empty}) -> V; +peek({_L, _Q, _I, O}) -> O. + +peek_r({0, _, _, _}) -> empty; +peek_r({1, _, empty, V}) -> V; +peek_r({_L, _Q, I, _O}) -> I. |