Skip to content

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 (nth) element, which can be done in O(1) time. The call previous() retrieves the previous (n-1th) 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-kth element takes O(k-1) time, and the n+kth 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:

  1. Use an array (Type[_]) or Array instead.
  2. Remove items one-by-one before the object goes out of scope.
  3. 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:

  1. If the element at the current position is not initialized, it is default-constructed.
  2. The current position is moved backward one.
  3. 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:

  1. If the element at the current position is not initialized, it is default-constructed.
  2. The current position is moved forward one.
  3. 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.

next

function next() -> Type

Get the element one after the current 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.

previous

function previous() -> Type

Get the element one before the current position.

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.

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

size

function size() -> Integer

Number of elements (that are set).

walk

function walk() -> Iterator<Type>

Rewind and obtain an iterator.

Return: an iterator across elements (that are set) from front to back.