BeginPackage["CSM`Tape`"]

emptyTape::usage = "emptyTape[b] is an empty tape with blank b."
update::usage = "update[tape, sym, i] is a tape differing from tape at position i
	where its value is sym."
newTape::usage = "newTape[list, b, p0:1] is a tape taken from a list.
	The first element is at position p0."
low::usage = "low[tape] is the least index of a nonempty cell."
high::usage = "high[tape] is the largest index of a nonempty cell."

Begin["`Private`"]

(* list[[j]] is the position i = offset + j *)

emptyTape[b_] := tape[{}, 0, b]

tape[list_, offset_, b_][i_Integer]/; 0 < i-offset <= Length[list] :=
        list[[i-offset]]
tape[list_, offset_, b_][i_Integer] := b

tape/: update[ tape[list_, offset_, b_], new_, i_Integer ] :=
    Which[ i-offset <= 0,
              tape[ Join[ {new}, Table[b, {offset-i}], list ], i-1, b ],
           i-offset > Length[list],
              tape[ Join[ list, Table[b, {i-offset-Length[list]-1}], {new} ],
                    offset, b ],
           True,
              tape[  ReplacePart[list, new, i-offset], offset, b ] ]

newTape[l_List, b_, p0_:1] := tape[ l, p0-1, b]

tape/: low[tape[list_, offset_, b_]] :=
    Module[{j = 1},
        While[ j <= Length[list] && list[[j]] === b, j++ ];
        If[ j <= Length[list], offset + j, Infinity ] ]

tape/: high[tape[list_, offset_, b_]] :=
    Module[{j = Length[list]},
        While[ j >= 1 && list[[j]] === b, j-- ];
        If[ j >= 1, offset + j, -Infinity ] ]

Format[t_tape] := SequenceForm[ "< ", Infix[Array[t, 6, 1], " "], " ...>" ]
Protect[ tape ]

End[]
Protect[ emptyTape, update, newTape, low, high ]
EndPackage[]
