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
|
-module(fqueue).
%% Creation, inspection and conversion
-export([new/0,is_queue/1,is_empty/1,len/1,to_list/1,from_list/1,member/2]).
%% Original style API
-export([in/2,in_r/2,out/1,out_r/1]).
%% Less garbage style API
%%-export([get/1,get_r/1,peek/1,peek_r/1,drop/1,drop_r/1]).
%% Higher level API
%%-export([reverse/1,join/2,split/2,filter/2]).
-export([join/2]).
-record(fq, {len, head, tail}).
new() -> #fq { len = 0, head = [], tail = [] }.
is_queue(#fq { len = L, head = H, tail = T })
when is_integer(L) andalso is_list(H) andalso is_list(T) ->
true;
is_queue(_) ->
false.
is_empty(#fq { len = 0 }) ->
true;
is_empty(_) ->
false.
len(FQ) -> FQ#fq.len.
to_list(FQ) ->
to_list(false, FQ).
to_list(true, List) when is_list(List) ->
lists:foldl(fun (#fq{} = Q, Acc) -> to_list(false, Q) ++ Acc;
(V, Acc) -> [unescape(V) | Acc]
end, [], List);
to_list(false, List) when is_list(List) ->
lists:foldr(fun (#fq{} = Q, Acc) -> to_list(true, Q) ++ Acc;
(V, Acc) -> [unescape(V) | Acc]
end, [], List);
to_list(Reverse, #fq { head = H, tail = T }) ->
to_list(Reverse, H) ++ to_list(not Reverse, T).
from_list(L) -> #fq { len = length(L), head = [escape(V) || V <- L], tail = [] }.
member(X, #fq { head = H, tail = T }) ->
member(X, H) orelse member(X, T);
member(X, List) when is_list(List) ->
lists:any(fun (E) -> member(X, unescape(E)) end, List);
member(X, X) -> true.
in(X, #fq { len = 0 } = Q) ->
Q #fq { len = 1, head = [escape(X)] };
in(X, #fq { len = L, tail = T } = Q) ->
Q #fq { len = L+1, tail = [escape(X) | T] }.
in_r(X, #fq { len = 0 } = Q) ->
Q #fq { len = 1, tail = [escape(X)] };
in_r(X, #fq { len = L, head = H } = Q) ->
Q #fq { len = L+1, head = [escape(X) | H] }.
out(#fq { len = 0 } = Q) ->
{empty, Q};
out(#fq { head = [#fq{} = IQ], tail = [] }) ->
out(IQ);
out(#fq { tail = [#fq{} = IQ], head = [] }) ->
out(IQ);
out(#fq { len = L, head = [#fq{ len = L1, tail = T1 } = IQ | H], tail = T }) ->
%% Essentially we pivot so that the IQ becomes the outer, and we
%% stuff ourselves at the end
out(IQ #fq { len = L, tail = [#fq { len = L - L1, head = H, tail = T } | T1] });
out(#fq { len = L, head = [V], tail = T }) ->
{{value, unescape(V)}, #fq { len = L-1, head = lists:reverse(T), tail = [] }};
out(#fq { len = L, head = [V | H] } = Q) ->
{{value, unescape(V)}, Q #fq { len = L-1, head = H }};
out(#fq { head = [], tail = T } = Q) ->
out(Q #fq { head = lists:reverse(T), tail = [] }).
out_r(#fq { len = 0 } = Q) ->
{empty, Q};
out_r(#fq { tail = [#fq{} = IQ], head = [] }) ->
out_r(IQ);
out_r(#fq { head = [#fq{} = IQ], tail = [] }) ->
out_r(IQ);
out_r(#fq { len = L, tail = [#fq{ len = L1, head = H1 } = IQ | T], head = H }) ->
%% Essentially we pivot so that the IQ becomes the outer, and we
%% stuff ourselves at the start
out_r(IQ #fq { len = L, head = [#fq { len = L - L1, tail = T, head = H } | H1] });
out_r(#fq { len = L, tail = [V], head = H }) ->
{{value, unescape(V)}, #fq { len = L-1, tail = lists:reverse(H), head = [] }};
out_r(#fq { len = L, tail = [V | T] } = Q) ->
{{value, unescape(V)}, Q #fq { len = L-1, tail = T }};
out_r(#fq { tail = [], head = H } = Q) ->
out_r(Q #fq { tail = lists:reverse(H), head = [] }).
join(Q, #fq { len = 0 }) ->
Q;
join(#fq { len = 0 }, Q) ->
Q;
join(Q, #fq { len = 1 } = Q1) ->
{{value, V}, _} = out(Q1),
in(V, Q);
join(#fq { len = 1 } = Q, Q1) ->
{{value, V}, _} = out(Q),
in_r(V, Q1);
join(#fq { len = L, tail = T } = Q, #fq { len = L1 } = Q1) ->
Q #fq { len = L+L1, tail = [Q1 | T] }.
-compile({inline, [{escape,1},{unescape,1}]}).
escape(#fq{} = V) -> {escaped, V};
escape({escaped, _} = V) -> {escaped, V};
escape(V) -> V.
unescape({escaped, V}) -> V;
unescape(V) -> V.
|
