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:
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:
- 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.
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.