%% @author David Mercer <dmercer@alum.mit.edu>

%% @doc Tape - simulated finite tape.
%%
%% This module provides an abstract data structure for storing a finite ordered list as on a tape.
%% The tape has a head, which is the current position on the tape, and which can be read and written to.
%% The head can be moved forward and backward, and cells can be inserted into and deleted from the tape.
%%
%% <table align="center"><tr align="center">
%% <td style="border: 1px solid black">cell 1</td>
%% <td style="border: 1px solid black">cell 2</td>
%% <td style="border: 1px solid black">cell 3</td>
%% <td style="border: 2px solid black">cell 4</td>
%% <td style="border: 1px solid black">cell 5</td>
%% <td style="border: 1px solid black">cell 6</td>
%% </tr><tr align="center"><td colspan="3"></td>
%% <td align="center">^^^^<br/>head</td>
%% </tr></table>


-module(tape).

-export([new/1, move/2, insert_before/2, insert_after/2, prepend/2, append/2, delete/1, read/1, write/2, length/1, position/1]).

%% @type tape().  Representation of a finite tape.
-record(tape,
	{head
	,prior      = []
	,subsequent = []
	}).


%% @spec new(Contents::[any()]) -> tape()
%%
%% @doc Creates a new tape.
%%
%% Contents are specified in the list argument and may be empty.
%% The head is initialized to the beginning of the tape.
%% Empty contents produces a null tape with no contents, though such a tape may be added to using <code>insert_before/2</code>, <code>insert_after/2</code>, <code>prepend/2</code>, and <code>append/2</code>.

new([]) -> null_tape;

new([Head | Subsequent]) ->
	#tape
		{head       = Head
		,subsequent = Subsequent
		}.


%% @spec move(N::(integer() | first | last), Tape::tape()) -> tape()
%%
%% @doc Moves the tape head relative to its current position.
%%
%% Negative <code>N</code> moves the head backward, positive <code>N</code> moves the head forward.
%% Tape head does not move when <code>N</code> = 0.
%% If <code>N</code> = <code>first</code>, tape head moves to beginning of tape.
%% If <code>N</code> = <code>last</code>, tape head moves to end of tape.

move(0, Tape) -> Tape;

move(first, #tape{head = Head, prior = Prior, subsequent = Subsequent}) ->
	[First | Rest] = lists:reverse(Prior, [Head | Subsequent]),
	#tape
		{head       = First
		,subsequent = Rest
		};

move(last, #tape{head = Head, prior = Prior, subsequent = Subsequent}) ->
	[Last | Rest] = lists:reverse(Subsequent, [Head | Prior]),
	#tape
		{head       = Last
		,prior      = Rest
		};

move(-1, #tape{head = Head, prior = [Prev | Prior], subsequent = Subsequent}) ->
	#tape
		{head       = Prev
		,prior      = Prior
		,subsequent = [Head | Subsequent]
		};

move(+1, #tape{head = Head, prior = Prior, subsequent = [Next | Subsequent]}) ->
	#tape
		{head       = Next
		,prior      = [Head | Prior]
		,subsequent = Subsequent
		};

move(N, Tape) when N < -1 ->
	move(N + 1, move(-1, Tape));

move(N, Tape) when N > 1 ->
	move(N - 1, move(+1, Tape)).


%% @spec insert_before(any(), tape()) -> tape()
%%
%% @doc Inserts a cell onto the tape in the position immediately preceding the tape head.
%%
%% When the tape is empty, the head of the resulting tape is set to the new cell.
%% Otherwise, the tape head remains in its existing position.

insert_before(X, null_tape) -> #tape{head = X};

insert_before(X, Tape = #tape{prior = Prior}) ->
	Tape#tape{prior = [X | Prior]}.


%% @spec insert_after(any(), tape()) -> tape()
%%
%% @doc Inserts a cell onto the tape in the position immediately following the tape head.
%%
%% When the tape is empty, the head of the resulting tape is set to the new cell.
%% Otherwise, the tape head remains in its existing position.

insert_after(X, null_tape) -> #tape{head = X};

insert_after(X, Tape = #tape{subsequent = Subsequent}) ->
	Tape#tape{subsequent = [X | Subsequent]}.


%% @spec prepend(any(), tape()) -> tape()
%%
%% @doc Inserts a cell onto the beginning of the tape regardless of the position of the tape head.
%%
%% When the tape is empty, the head of the resulting tape is set to the new cell.
%% Otherwise, the tape head remains in its existing position.

prepend(X, null_tape) -> #tape{head = X};

prepend(X, Tape = #tape{prior = Prior}) ->
	Tape#tape{prior = Prior ++ [X]}.


%% @spec append(any(), tape()) -> tape()
%%
%% @doc Inserts a cell onto the end of the tape regardless of the position of the tape head.
%%
%% When the tape is empty, the head of the resulting tape is set to the new cell.
%% Otherwise, the tape head remains in its existing position.

append(X, null_tape) -> #tape{head = X};

append(X, Tape = #tape{subsequent = Subsequent}) ->
	Tape#tape{subsequent = Subsequent ++ [X]}.


%% @spec delete(tape()) -> tape()
%%
%% @doc Deletes the cell on the tape under the tape head.
%%
%% The resulting tape's head will be positioned on the cell immediately following the deleted cell unless the deleted cell is the last cell, in which case the head will be positioned at the last cell of the resulting tape.
%% If the last cell of the tape is deleted, the resulting tape is empty.

delete(#tape{prior = [], subsequent = []}) -> null_tape;

delete(#tape{prior = Prior, subsequent = [Next | Subsequent]}) ->
	#tape
		{head       = Next
		,prior      = Prior
		,subsequent = Subsequent
		};

delete(#tape{prior = [Prev | Prior], subsequent = []}) ->
	#tape
		{head  = Prev
		,prior = Prior
		}.


%% @spec read(tape()) -> ( {ok, any()} | null_tape )
%%
%% @doc Returns the contents of the tape cell under the tape head.
%%
%% If tape is null, returns <code>null_tape</code>.

read(null_tape) -> null_tape;

read(#tape{head = Head}) -> Head.


%% @spec write(any(), tape()) -> ( {ok, tape()} | null_tape )
%%
%% @doc Overwrites the contents of the cell under the tape head.
%%
%% If tape is null, returns <code>null_tape</code>.

write(_, null_tape) -> null_tape;

write(X, Tape) ->
	Tape#tape{head = X}.


%% @spec length(tape()) -> integer()
%%
%% @doc Returns the length of the tape.

length(null_tape) -> 0;

length(#tape{prior = Prior, subsequent = Subsequent}) ->
	erlang:length(Prior) + 1 + erlang:length(Subsequent).


%% @spec position(tape()) -> integer()
%%
%% @doc Returns the current position of the tape head.
%%
%% The first cell is numbered 1.
%% Returns 0 when tape is null.

position(null_tape) -> 0;

position(#tape{prior = Prior}) ->
	erlang:length(Prior) + 1.