From bf22ced93fa82abd9e1fd1833545bf55bd68c775 Mon Sep 17 00:00:00 2001 From: Matthew Sackman Date: Wed, 12 Oct 2011 14:15:22 +0100 Subject: Cache both ends of the queue to give O(1) peek and peek_r --- src/lqueue.erl | 105 +++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 68 insertions(+), 37 deletions(-) (limited to 'src/lqueue.erl') diff --git a/src/lqueue.erl b/src/lqueue.erl index f07eec18..80fb1fd9 100644 --- a/src/lqueue.erl +++ b/src/lqueue.erl @@ -25,10 +25,11 @@ -export_type([?MODULE/0]). --opaque(?MODULE() :: {non_neg_integer(), ?MODULE()}). +-opaque(?MODULE() :: + {non_neg_integer(), ?QUEUE(), maybe_value(), maybe_value()}). -type(value() :: any()). --type(result() :: ({'empty', ?MODULE()} | - {{'value', value()}, ?MODULE()})). +-type(maybe_value() :: {'value', value()} | 'empty'). +-type(result() :: {maybe_value(), ?MODULE}). -spec(new/0 :: () -> ?MODULE()). -spec(is_empty/1 :: (?MODULE()) -> boolean()). @@ -42,38 +43,66 @@ -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) -> 'empty' | {'value',value()}). --spec(peek_r(?MODULE) -> 'empty' | {'value',value()}). +-spec(peek(?MODULE) -> maybe_value()). +-spec(peek_r(?MODULE) -> maybe_value()). -endif. -new() -> {0, ?QUEUE:new()}. - -is_empty({0, _Q}) -> true; -is_empty(_) -> false. - -in(V, {L, Q}) -> {L+1, ?QUEUE:in(V, Q)}. - -in_r(V, {L, Q}) -> {L+1, ?QUEUE:in_r(V, Q)}. - -out({0, _Q} = Q) -> - {empty, Q}; -out({L, Q}) -> - {Result, Q1} = ?QUEUE:out(Q), - {Result, {L-1, Q1}}. - -out_r({0, _Q} = Q) -> - {empty, Q}; -out_r({L, Q}) -> - {Result, Q1} = ?QUEUE:out_r(Q), - {Result, {L-1, Q1}}. - -join({L1, Q1}, {L2, Q2}) -> - {L1 + L2, ?QUEUE:join(Q1, Q2)}. - -to_list({_L, Q}) -> ?QUEUE:to_list(Q). - -from_list(L) -> {length(L), ?QUEUE:from_list(L)}. +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 @@ -87,11 +116,13 @@ foldr(Fun, Init, Q) -> {{value, V}, Q1} -> foldr(Fun, Fun(V, Init), Q1) end. -len({L, _Q}) -> +len({L, _Q, _I, _O}) -> L. -peek({0, _Q}) -> empty; -peek({_L, Q}) -> ?QUEUE:peek(Q). +peek({0, _, _, _}) -> empty; +peek({1, _, V, empty}) -> V; +peek({_L, _Q, _I, O}) -> O. -peek_r({0, _Q}) -> empty; -peek_r({_L, Q}) -> ?QUEUE:peek_r(Q). +peek_r({0, _, _, _}) -> empty; +peek_r({1, _, empty, V}) -> V; +peek_r({_L, _Q, I, _O}) -> I. -- cgit v1.2.1