Tape

final class Tape<Type>

Stateful tape container. Maintains a current position along a tape that is infinite in both directions. Provides constant-time operations at that position, and linear-time operations elsewhere.

Type: Element type. Must be default-constructible.

The data structure is arranged as two singly-linked lists about the current position, one recursing backward through elements behind the current position, the other recursing forward through elements at and ahead of the current position:

graph LR this --"previous()"--> nm1[n-1] --> nm2[n-2] --> nm3[n-3] --> nm4(...) this --"current()"--> n[n] --> np1[n+1] --> np2[n+1] --> np3(...)

The member function current() is used to retrieve the current ( $n$ th) element, which can be done in $O(1)$ time. The call previous() retrieves the previous ( $n-1$ th) element, similarly in $O(1)$ time. The call current(k) may be used to retrieve any other elements using an offset relative to the current position. For positive $k$ , retrieving the $n-k$ th element takes $O(k-1)$ time, and the $n+k$ th element $O(k)$ time. Because the tape is considered infinite, elements are default-constructed as necessary.

Changing the current position in the list (i.e. seeking) is achieved with the seek(), backward(), forward(), rewind() and fastForward() member functions. It is up to the user to seek as appropriate to ensure efficient operations, according to the use-case.

Tip

As a recursive and singly-linked data structure, Tape has excellent performance properties under Birch's lazy deep copy mechanism.

Attention

Large recursive data structures can cause an execution stack overflow on destruction that usually manifests as a segmentation fault. Possible solutions include:

Use an array (Type[_]) or Array instead.
Remove items one-by-one before the object goes out of scope.
Increase the execution stack size with the shell command ulimit.

Member Variables

Name	Description
ahead:TapeNode<Type>?	Elements at and ahead of the current position.
aheadCount:Integer	Number of elements at and ahead of the current position.
behind:TapeNode<Type>?	Elements behind the current position.
behindCount:Integer	Number of elements behind the current position.

Member Functions

Name	Description
size	Number of elements (that are set).
empty	Is this empty (no elements are set)?
clear	Clear all elements (unset all elements).
front	Get the first element (that is set).
back	Get the last element (that is set).
forward	Move the current position forward one.
backward	Move the current position backward one.
rewind	Rewind to one before the first element (that is set).
fastForward	Fast-forward to one after the last element (that is set).
seek	Seek to a new position, offset from the current position.
current	Get an element, offset from the current position.
current	Get the element at the current position.
previous	Get the element one before the current position.
next	Get the element one after the current position.
pushFront	Insert an element before the first (that is set).
pushFront	Insert a new default-constructed element before the first (that is set).
pushBack	Insert an element after the last (that is set).
pushBack	Insert a new default-constructed element after the last (that is set).
popFront	Remove the first element (that is set).
popBack	Remove the last element (that is set).
insert	Insert an element at the current position.
insert	Insert a new default-constructed element at the current position.
insertBefore	Insert an element before the current position.
insertBefore	Insert a new default-constructed element before the current position.
erase	Remove an element at the current position.
eraseBefore	Remove an element before the current position.
walk	Rewind and obtain an iterator.

Member Function Details

back

function back() -> Type

Get the last element (that is set).

backward

function backward()

Move the current position backward one. This performs the following sequence:

If the element at the current position is not initialized, it is default-constructed.
The current position is moved backward one.
If the element at the new position is not initialized, it remains uninitialized.

clear

function clear()

Clear all elements (unset all elements).

current

function current(k:Integer) -> Type

Get an element, offset from the current position.

k: Offset from the current position. May be positive, negative or zero. In the case of zero, this is equivalent to current() without arguments.

Elements are default-constructed as necessary between the current position and the requested position.

function current() -> Type

Get the element at the current position.

empty

function empty() -> Boolean

Is this empty (no elements are set)?

erase

function erase()

Remove an element at the current position. All elements ahead of it move backward one position.

eraseBefore

function eraseBefore()

Remove an element before the current position. All elements behind it move forward one position.

fastForward

function fastForward()

Fast-forward to one after the last element (that is set).

forward

function forward()

Move the current position forward one. This performs the following sequence:

If the element at the current position is not initialized, it is default-constructed.
The current position is moved forward one.
If the element at the new position is not initialized, it remains uninitialized.

front

function front() -> Type

Get the first element (that is set).

insert

function insert(x:Type)

Insert an element at the current position. All elements ahead of it move backward one position.

x: Value.

function insert()

Insert a new default-constructed element at the current position. All elements ahead of it move forward one position.

insertBefore

function insertBefore(x:Type)

Insert an element before the current position. All elements behind it move backward one position.

x: Value.

function insertBefore()

Insert a new default-constructed element before the current position. All elements behind it move backward one position.

popBack

function popBack()

Remove the last element (that is set). If this is at the current position, then all elements move forward one position, as if eraseBefore() was called instead.

popFront

function popFront()

Remove the first element (that is set). If this is at the current position, then all elements move backward one position, as if erase() was called instead.

pushBack

function pushBack(x:Type)

Insert an element after the last (that is set).

x: Value.

function pushBack()

Insert a new default-constructed element after the last (that is set).

pushFront

function pushFront(x:Type)

Insert an element before the first (that is set).

x: Value.

function pushFront()

Insert a new default-constructed element before the first (that is set).

rewind

function rewind()

Rewind to one before the first element (that is set).

seek

function seek(k:Integer)

Seek to a new position, offset from the current position.

k: Offset from the current position. May be positive, negative or zero. In the case of zero, this is a null operation.