1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
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.
|
