Class to represent a tape memory. More...

#include <memory/tape.h>

Inheritance diagram for TuringSim::Memory::Tape::Tape< T >:

Collaboration diagram for TuringSim::Memory::Tape::Tape< T >:

Public Types
enum	Movement { Movement::LEFT, Movement::RIGHT, Movement::NONE, Movement::HALT }
	Enum to encode possible movements. More...

Public Types inherited from TuringSim::Memory::MemoryStructure< T, Tape< T >, TapeObserver< T >, TapeModifier< T > >
typedef TapeObserver< T >	Observer
	The type of observers.

typedef TapeModifier< T >	Modifier
	The type of modifiers.

typedef T	SymbolType
	The alphabet type. More...

Public Member Functions
constexpr	Tape ()
	Create a new tape. More...

constexpr	Tape (const T &blank)
	Create a new tape. More...

constexpr	Tape (const Tape< T > &other)
	Copy a tape. More...

constexpr	Tape (Tape< T > &&other)
	Move a tape. More...

constexpr Tape< T > &	operator= (const Tape< T > &other)
	Copy a tape. More...

constexpr Tape< T > &	operator= (Tape< T > &&other)
	Move a tape. More...

	~Tape ()=default
	Destruct the tape. More...

constexpr void	left ()
	Move the I/O head to the left. More...

constexpr void	right ()
	Move the I/O head to the right. More...

constexpr void	move (const Movement &movement)
	Move the I/O head according to the provided Movement. More...

constexpr const T &	read () const
	Read the value under the I/O head. More...

constexpr void	write (const T &symbol)
	Write a value under the I/O head. More...

constexpr void	erase ()
	Write the blank value under the I/O head. More...

Public Member Functions inherited from TuringSim::Memory::MemoryStructure< T, Tape< T >, TapeObserver< T >, TapeModifier< T > >
	~MemoryStructure ()
	Release current observers and modifier.

const std::set< Observer * > &	getObservers () const noexcept
	Gets the set of observers. More...

const std::optional< Modifier * > &	getModifier () const noexcept
	Gets the optional modifier. More...

Static Public Attributes
static constexpr size_t	MinAllocatedTapeSize = 10
	The size allocated when constructing a tape. More...

Friends
class	TapeObserver< T >
	Observer for the Tape class. More...

class	TapeModifier< T >
	Modifier for the Tape class. More...

template<typename CharT = char, typename Trait = std::char_traits<CharT>>
std::basic_ostream< CharT, Trait > &	operator<< (std::basic_ostream< CharT, Trait > &os, const Movement &movement)
	Debug printer for tape movement. More...

Additional Inherited Members
Public Attributes inherited from TuringSim::Memory::MemoryStructure< T, Tape< T >, TapeObserver< T >, TapeModifier< T > >
friend	Observer
	Observer class.

friend	Modifier
	Modifier class.

Detailed Description

template<typename T>
class TuringSim::Memory::Tape::Tape< T >

Class to represent a tape memory.

Template Parameters

T	Type representing the working alphabet

A tape is a memory structure made of consecutive boxes. Each box stores a letter of an alphabet. Here, the type T represent the alphabet and instances of T are letters. Moreover, a tape has a I/O head on one box. The only available operations are the move of the head of one box to the left or to the right, read the value under the head and write in the box under the head.

A tape is observationally infinite. Since it is impossible to store an infinite data structure, the tape is elongated when the head come close to the edges of the allocated space. The default value can be specified in the constructor. If it is not, new boxes are default initialized.

Definition at line 29 of file tape.h.

Member Enumeration Documentation

◆ Movement

template<typename T >

enum TuringSim::Memory::Tape::Tape::Movement

strong

Enum to encode possible movements.

Standard movement are LEFT and RIGHT. For practical reason, we add NONE and HALT. Both do not modify the tape. They are useful to build machines: HALT halts the machine while NONE does not.

Enumerator
LEFT	Shift the I/O head to one box to the left.
RIGHT	Shift the I/O head to one box to the right.
NONE	Do not move the I/O head.
HALT	Do not move the I/O head. Normally used to stop the machine.

Definition at line 60 of file tape.h.

Constructor & Destructor Documentation

◆ Tape() [1/4]

template<typename T >

constexpr TuringSim::Memory::Tape::Tape< T >::Tape

constexpr

Create a new tape.

The blank value is set to T(). The compilation fails if T is not default constructable.

The initial position is 0. MIN_ALLOCATED_TAPE_SIZE is allocated to the left and the right. The size factor is 2 by default.

Complexity of \(\mathcal{O}(1)\).

Definition at line 214 of file tape.h.

◆ Tape() [2/4]

template<typename T >

constexpr TuringSim::Memory::Tape::Tape< T >::Tape ( const T & blank )

constexpr

Create a new tape.

Parameters

[in] blank Blank value of the tape.

The initial position is 0. MIN_ALLOCATED_TAPE_SIZE is allocated to the left and the right. The size factor is 2 by default.

Complexity of \(\mathcal{O}(1)\).

Definition at line 220 of file tape.h.

◆ Tape() [3/4]

template<typename T >

constexpr TuringSim::Memory::Tape::Tape< T >::Tape ( const Tape< T > & other )

constexpr

Copy a tape.

Parameters

[in] other the tape to copy.

Definition at line 226 of file tape.h.

◆ Tape() [4/4]

template<typename T >

constexpr TuringSim::Memory::Tape::Tape< T >::Tape ( Tape< T > && other )

constexpr

Move a tape.

Parameters

[in,out] other the tape to move.

Definition at line 237 of file tape.h.

◆ ~Tape()

template<typename T >

TuringSim::Memory::Tape::Tape< T >::~Tape ( )

default

Destruct the tape.

Complexity of \(\mathcal{O}(n)\) where n is the size of the tape. May be optimized for trivially destructible types.

Member Function Documentation

◆ erase()

template<typename T >

constexpr void TuringSim::Memory::Tape::Tape< T >::erase

constexpr

Write the blank value under the I/O head.

Complexity of \(\mathcal{O}(c)\) where \(c\) is the copy complexity of a symbol.

Definition at line 386 of file tape.h.

◆ left()

template<typename T >

constexpr void TuringSim::Memory::Tape::Tape< T >::left

constexpr

Move the I/O head to the left.

Allocation can occur if the head come close enough to an edge of the allocated tape. In this case, the length of the current half tape is multiplied by the size factor.

Amortized complexity of \(\mathcal{O}(1)\), \(\mathcal{O}(\texttt{sizeFactor}\times h)\) where \(h\) is the size of the left half-tape in the worst case.

Definition at line 279 of file tape.h.

◆ move()

template<typename T >

constexpr void TuringSim::Memory::Tape::Tape< T >::move ( const Movement & movement )

constexpr

Move the I/O head according to the provided Movement.

Parameters

[in] movement the movement to perform.

It is equivalent to left() if movement is Movement::LEFT, and right() if movement is Movement::RIGHT. Otherwise, *this is not changed.

Definition at line 343 of file tape.h.

◆ operator=() [1/2]

template<typename T >

constexpr Tape< T > & TuringSim::Memory::Tape::Tape< T >::operator= ( const Tape< T > & other )

constexpr

Copy a tape.

Parameters

[in] other the tape to copy.

Returns: a reference to *this.

Definition at line 248 of file tape.h.

◆ operator=() [2/2]

template<typename T >

constexpr Tape< T > & TuringSim::Memory::Tape::Tape< T >::operator= ( Tape< T > && other )

constexpr

Move a tape.

Parameters

[in,out] other the tape to move.

Returns: a reference to *this.

Definition at line 263 of file tape.h.

◆ read()

template<typename T >

constexpr const T & TuringSim::Memory::Tape::Tape< T >::read

constexpr

Read the value under the I/O head.

Returns: A const reference to the element under the I/O head.

Complexity of \(\mathcal{O}(1)\).

The reference is valid as long as the cell exist. It ceases to exist if the I/O head is closer to 0, the cell is not in the minimal size, there is no non-blank cell that protects the given cell, and TapeObserver<T>::shrink().

Definition at line 374 of file tape.h.

◆ right()

template<typename T >

constexpr void TuringSim::Memory::Tape::Tape< T >::right

constexpr

Move the I/O head to the right.

Allocation can occur if the head come close enough to an edge of the allocated tape. In this case, the length of the current half tape is multiplied by the size factor.

Amortized complexity of \(\mathcal{O}(1)\), \(\mathcal{O}(\texttt{sizeFactor}\times h)\) where \(h\) is the size of the right half-tape in the worst case.

Definition at line 311 of file tape.h.

◆ write()

template<typename T >

constexpr void TuringSim::Memory::Tape::Tape< T >::write ( const T & symbol )

constexpr

Write a value under the I/O head.

Parameters

[in] symbol The letter to write

Complexity of \(\mathcal{O}(c)\) where \(c\) is the copy complexity of the e.

Definition at line 380 of file tape.h.

Friends And Related Function Documentation

◆ operator<<

template<typename T >

template<typename CharT = char, typename Trait = std::char_traits<CharT>>

std::basic_ostream<CharT, Trait>& operator<<	(	std::basic_ostream< CharT, Trait > &	os,
		const Movement &	movement
	)

friend

Debug printer for tape movement.

Template Parameters

CharT	char type.
Trait	`basic_ostream` trait.

Parameters

os	the output stream.
movement	the movement to print.

Returns: a reference to os.

Definition at line 177 of file tape.h.

◆ TapeModifier< T >

template<typename T >

friend class TapeModifier< T >

friend

Modifier for the Tape class.

The modifier allows to modify private attributes by accessing private methods. For instance, it can be useful to optimize when we know the size needed for the tape. These functions are not directly accessible because these features does not belongs to the abstract model of the tape.

The functions provided by this class are safe. However, it is possible to waste a lot of time by using poorly these features.

Definition at line 408 of file tape.h.

◆ TapeObserver< T >

template<typename T >

friend class TapeObserver< T >

friend

Observer for the Tape class.

The observer allows to access private members. For instance, it can be useful to print the content of the tape. These getters are in the observer because these features does not belongs to the abstract model of the tape.

Definition at line 408 of file tape.h.

Member Data Documentation

◆ MinAllocatedTapeSize

template<typename T >

constexpr size_t TuringSim::Memory::Tape::Tape< T >::MinAllocatedTapeSize = 10

staticconstexpr

The size allocated when constructing a tape.

This value is totally arbitrary but seems to suit.

Definition at line 53 of file tape.h.

The documentation for this class was generated from the following file:

include/memory/tape.h

Public Types

Public Member Functions

Static Public Attributes

Friends

Additional Inherited Members

Detailed Description

template<typename T> class TuringSim::Memory::Tape::Tape< T >

Member Enumeration Documentation

◆ Movement

Constructor & Destructor Documentation

◆ Tape() [1/4]

◆ Tape() [2/4]

◆ Tape() [3/4]

◆ Tape() [4/4]

◆ ~Tape()

Member Function Documentation

◆ erase()

◆ left()

◆ move()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ read()

◆ right()

◆ write()

Friends And Related Function Documentation

◆ operator<<

◆ TapeModifier< T >

◆ TapeObserver< T >

Member Data Documentation

◆ MinAllocatedTapeSize

template<typename T>
class TuringSim::Memory::Tape::Tape< T >