Skip to content

Tape

final class Tape<Type>

Tape container. The container is stateful, maintaining a current position along a tape, providing constant-time operations at that and the previous position, but linear-time operations elsewhere (which require a seek).

  • 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 --> nm1[n-1] --> nm2[n-2] --> nm3[n-3] --> nm4(...) this --> n[n] --> np1[n+1] --> np2[n+1] --> np3(...)

The call get(i) may be used to retrieve any element, with complexity linear in the offset from the current position.

Changing the current position in the list (i.e. seeking) is achieved with the seek(), backward(), forward(), rewind() and fastForward() member functions. It is not usually necessary to call these directly, however, as the container seeks as necessary.

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.
behind:TapeNode<Type>? Elements behind the current position.
aheadCount:Integer Number of elements at and ahead of the current position.
behindCount:Integer Number of elements behind the current positionl equivalent to current position minus 1.

Member Slices

Name Description
[...] Reference to an element.

Member Functions

Name Description
size Number of elements.
empty Is this empty?
clear Clear all elements.
front Get the first element.
back Get the last element.
get Get an element.
set Set an element.
pushFront Insert an element at the front.
pushFront Insert a new default-constructed element at the front and return it.
pushBack Insert an element at the back.
pushBack Insert a new default-constructed element at the back and return it.
popFront Remove the first element.
popBack Remove the last element.
insert Insert a new element.
erase Erase an element.
walk Rewind and obtain an iterator.
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.

Member Slice Details

operator [i:Integer] -> Type

Reference to an element.

Member Function Details

back

function back() -> Type

Get the last element.

backward

function backward()

Move the current position backward one.

clear

function clear()

Clear all elements.

empty

function empty() -> Boolean

Is this empty?

erase

function erase(i:Integer)

Erase an element.

  • i: Position.

fastForward

function fastForward()

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

forward

function forward()

Move the current position forward one.

front

function front() -> Type

Get the first element.

get

function get(i:Integer) -> Type

Get an element.

  • i: Position.

insert

function insert(i:Integer, x:Type)

Insert a new element.

  • i: Position.
  • x: Value.

Inserts the new element immediately before the current element at position i. To insert at the back of the container, use a position that is one more than the current size, or pushBack().

popBack

function popBack()

Remove the last element.

popFront

function popFront()

Remove the first element.

pushBack

function pushBack(x:Type)

Insert an element at the back.

  • x: Value.

function pushBack() -> Type

Insert a new default-constructed element at the back and return it.

pushFront

function pushFront(x:Type)

Insert an element at the front.

  • x: Value.

function pushFront() -> Type

Insert a new default-constructed element at the front and return it.

rewind

function rewind()

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

seek

function seek(k:Integer)

Seek to a new position.

  • k: New position.

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

set

function set(i:Integer, x:Type)

Set an element.

  • i: Position.
  • x: Value.

size

function size() -> Integer

Number of elements.

walk

function walk() -> Iterator<Type>

Rewind and obtain an iterator.

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