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
|
%% This Source Code Form is subject to the terms of the Mozilla Public
%% License, v. 2.0. If a copy of the MPL was not distributed with this
%% file, You can obtain one at https://mozilla.org/MPL/2.0/.
%%
%% Copyright (c) 2011-2020 VMware, Inc. or its affiliates. All rights reserved.
%%
-module(lqueue).
%% lqueue implements a subset of Erlang's queue module. lqueues
%% maintain their own length, so lqueue:len/1
%% is an O(1) operation, in contrast with queue:len/1 which is O(n).
-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, drop/1, to_list/1, peek/1, peek_r/1]).
-define(QUEUE, queue).
-export_type([
?MODULE/0,
?MODULE/1
]).
-opaque ?MODULE() :: ?MODULE(_).
-opaque ?MODULE(T) :: {non_neg_integer(), queue:queue(T)}.
-type value() :: any().
-type result(T) :: 'empty' | {'value', T}.
-spec new() -> ?MODULE(_).
new() -> {0, ?QUEUE:new()}.
-spec drop(?MODULE(T)) -> ?MODULE(T).
drop({L, Q}) -> {L - 1, ?QUEUE:drop(Q)}.
-spec is_empty(?MODULE(_)) -> boolean().
is_empty({0, _Q}) -> true;
is_empty(_) -> false.
-spec in(T, ?MODULE(T)) -> ?MODULE(T).
in(V, {L, Q}) -> {L+1, ?QUEUE:in(V, Q)}.
-spec in_r(value(), ?MODULE(T)) -> ?MODULE(T).
in_r(V, {L, Q}) -> {L+1, ?QUEUE:in_r(V, Q)}.
-spec out(?MODULE(T)) -> {result(T), ?MODULE(T)}.
out({0, _Q} = Q) -> {empty, Q};
out({L, Q}) -> {Result, Q1} = ?QUEUE:out(Q),
{Result, {L-1, Q1}}.
-spec out_r(?MODULE(T)) -> {result(T), ?MODULE(T)}.
out_r({0, _Q} = Q) -> {empty, Q};
out_r({L, Q}) -> {Result, Q1} = ?QUEUE:out_r(Q),
{Result, {L-1, Q1}}.
-spec join(?MODULE(A), ?MODULE(B)) -> ?MODULE(A | B).
join({L1, Q1}, {L2, Q2}) -> {L1 + L2, ?QUEUE:join(Q1, Q2)}.
-spec to_list(?MODULE(T)) -> [T].
to_list({_L, Q}) -> ?QUEUE:to_list(Q).
-spec from_list([T]) -> ?MODULE(T).
from_list(L) -> {length(L), ?QUEUE:from_list(L)}.
-spec foldl(fun ((T, B) -> B), B, ?MODULE(T)) -> B.
foldl(Fun, Init, Q) ->
case out(Q) of
{empty, _Q} -> Init;
{{value, V}, Q1} -> foldl(Fun, Fun(V, Init), Q1)
end.
-spec foldr(fun ((T, B) -> B), B, ?MODULE(T)) -> B.
foldr(Fun, Init, Q) ->
case out_r(Q) of
{empty, _Q} -> Init;
{{value, V}, Q1} -> foldr(Fun, Fun(V, Init), Q1)
end.
-spec len(?MODULE(_)) -> non_neg_integer().
len({L, _}) -> L.
-spec peek(?MODULE(T)) -> result(T).
peek({ 0, _Q}) -> empty;
peek({_L, Q}) -> ?QUEUE:peek(Q).
-spec peek_r(?MODULE(T)) -> result(T).
peek_r({ 0, _Q}) -> empty;
peek_r({_L, Q}) -> ?QUEUE:peek_r(Q).
|
