FSM Input Maker Concept

An FSM Input Maker assists an FSM Builder in building a transition function by calculating the number of possible inputs and by calculating the corresponding input required for each possible state change.

Notation

FSMInputMaker is a type that models the FSM Input Maker concept.

Associated Types

Name Expression Description

Single layer required FSMInputMakerTraits<FSMInputMaker>::RequiresSingleLayer A Boolean Constant indicating whether or not the underlying Physical Pattern of an FSM Builder needs to have exactly one layer. If the underlying pattern is not physical, this FSM Input Maker cannot be used.

Last-visited map required FSMInputMakerTraits<FSMInputMaker>::RequiresLastVisitedMap A Boolean Constant indicating whether or not this FSM Input Maker needs to use the last-visited map stored in the maze graph. If the value of this constant is true, then this FSM Input Maker cannot be used together with a Maze Maker that does not build a last-visited map.

Name	Expression	Description
Single layer required	`FSMInputMakerTraits<FSMInputMaker>::RequiresSingleLayer`	A Boolean Constant indicating whether or not the underlying Physical Pattern of an FSM Builder needs to have exactly one layer. If the underlying pattern is not physical, this FSM Input Maker cannot be used.
Last-visited map required	`FSMInputMakerTraits<FSMInputMaker>::RequiresLastVisitedMap`	A Boolean Constant indicating whether or not this FSM Input Maker needs to use the last-visited map stored in the maze graph. If the value of this constant is `true`, then this FSM Input Maker cannot be used together with a Maze Maker that does not build a last-visited map.

Valid Expressions

The following expressions must be valid.

Name Expression Type Requirements Return Type

Input count calculation FSMInputMaker::getInputCount(pattern)

pattern must be a const reference to a Pattern object.

varies with each FSM Input Maker

Input calculation FSMInputMaker::getInput(pattern, previous_cell_i, current_cell_i, next_cell_i)

pattern must be a const reference to a Pattern object.

The value types of previous_cell_i, current_cell_i, and next_cell_i must be Pattern::CellIndex.

varies with each FSM Input Maker

Name	Expression	Type Requirements	Return Type
Input count calculation	`FSMInputMaker::getInputCount(pattern)`	`pattern` must be a const reference to a Pattern object.	varies with each FSM Input Maker
Input calculation	`FSMInputMaker::getInput(pattern, previous_cell_i, current_cell_i, next_cell_i)`	`pattern` must be a const reference to a Pattern object. The value types of `previous_cell_i`, `current_cell_i`, and `next_cell_i` must be `Pattern::CellIndex`.	varies with each FSM Input Maker

Expression Semantics

Name Expression Precondition Semantics Postcondition

Input count calculation FSMInputMaker::getInputCount(pattern) Returns the number of possible inputs that the FSM can process.

Input calculation FSMInputMaker::getInput(pattern, previous_cell_i, current_cell_i, next_cell_i) All three cells at the specified indices must be part of the specified pattern. Returns the input required for the finite state machine to change state from pointing to the cell at index current_cell_i to pointing to the cell at index next_cell_i. If this FSM Input Maker does not require a last-visited map, then it will ignore the previous_cell_i parameter. 0 <= FSMInputMaker::getInput(pattern, previous_cell_i, current_cell_i, next_cell_i) && FSMInputMaker::getInput(pattern, previous_cell_i, current_cell_i, next_cell_i) < FSMInputMaker::getInputCount(pattern)

Name	Expression	Precondition	Semantics	Postcondition
Input count calculation	`FSMInputMaker::getInputCount(pattern)`		Returns the number of possible inputs that the FSM can process.
Input calculation	`FSMInputMaker::getInput(pattern, previous_cell_i, current_cell_i, next_cell_i)`	All three cells at the specified indices must be part of the specified pattern.	Returns the input required for the finite state machine to change state from pointing to the cell at index current_cell_i to pointing to the cell at index next_cell_i. If this FSM Input Maker does not require a last-visited map, then it will ignore the previous_cell_i parameter.	`0 <= FSMInputMaker::getInput(pattern, previous_cell_i, current_cell_i, next_cell_i) && FSMInputMaker::getInput(pattern, previous_cell_i, current_cell_i, next_cell_i) < FSMInputMaker::getInputCount(pattern)`

Invariants and Runtime Complexity Guarantees

Runtime complexity is measured in turms of cell and connection count. The following invariants must hold.

Name Invariants Runtime complexity

Input count calculation Linear time with respect to cell count

Input calculation Amortized constant time

Name	Invariants	Runtime complexity
Input count calculation		Linear time with respect to cell count
Input calculation		Amortized constant time

Models

Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.