PFDSの演習問題8.3の解答案 (コンパイルが通ることは確認、未実行)

hood_melville_queue.erl

-module(hood_melville_queue). % Exercise 8.3 version

-export([empty/0, snoc/2, tail/1]).

empty() ->
    {0, [], idle, []}.

snoc({Diff, F, State, R}, X) ->
    check({Diff-1, F, State, [X | R]}).

tail({Diff, [_ | F], State, R}) ->
    check({Diff-1, F, invalidate(State), R}).

invalidate({reversing, Ok, F0, F1, R0, R1}) -> {reversing, Ok-1, F0, F1, R0, R1};
invalidate({appending, 0, _F1, [_X | R1]})  -> {done, R1};
invalidate({appending, Ok, F1, R1})         -> {appending, Ok-1, F1, R1};
invalidate(State)                           -> State.

check({-1, F, State, R}) ->
    idle = State, % assertion
    NewState = {reversing, 0, F, [], R, []},
    exec2({0, F, NewState, []});
check(Q) ->
    exec2(Q).

exec2({Diff0, F, State0, R}) ->
    {Diff1, State1} = exec(exec({Diff0, State0})),
    case State1 of
        {done, NewF} -> {Diff1, NewF, idle, R};
        _            -> {Diff1, F, State1, R}
    end.

exec({Diff, {reversing, Ok, [X | F0], F1, [Y | R0], R1}}) ->
    {Diff+2, {reversing, Ok+1, F0, [X | F1], R0, [Y | R1]}}; % 旧`lenf + lenr`の値をインクリメンタルに求める
exec({Diff, {reversing, Ok, [], F1, [Y], R1}}) ->
    {Diff+1, {appending, Ok, F1, [Y | R1]}};                 % 同上
exec({Diff, {appending, 0, _F1, R1}}) ->
    {Diff, {done, R1}};
exec({Diff, {appending, Ok, [X | F1], R1}}) ->
    {Diff, {appending, Ok-1, F1, [X | R1]}};
exec({Diff, State}) ->
    {Diff, State}.