1 files changed, 118 insertions, 0 deletions
diff --git a/src/fqueue.erl b/src/fqueue.erl
new file mode 100644
index 0000000000..39a2fe9782
--- /dev/null
+++ b/src/fqueue.erl
@@ -0,0 +1,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.