Pattern Concept

For our purposes, a Pattern represents the logical arrangement of cells in a maze. None of the cells or their connections can fit outside this Pattern.

Before a Pattern can be used to create a maze, it must first be initialized. The arguments used for initialization vary with each class or class template that models the Pattern concept, though typically one of the arguments is an instance of a type that models the Pattern Former concept.

Notation

P is a type that models the Pattern concept.
pattern is an object of type P.

Associated Types

Name Expression Description

Cell type P::Cell The type of the objects to be connected together in the Pattern.

Cell equality policy type P::CellEqualityPolicy The type of the function object that determines equality between any two cells in the Pattern. This type must model the Default Constructible and Binary Predicate concepts, accepting P::Cell as both the first and second argument types.

Cell index type P::CellIndex An unsigned integral type for representing either the index of a cell in the Pattern or the number of such cells.

Graph type P::Graph The type of the underlying object that represents the manner in which the cells are connected together. Each vertex in the graph represents a single cell, and each edge represents a connection between its source and target cells. This type must model the Adjacency List Graph concept.

Edge directed category type P::EdgeDirectedCategory The type that represents whether the edges in the underlying graph are undirected (in which case this type is boost::undirectedS), directed (in which case this type is boost::directedS), or bidirectional (in which case this type is boost::bidirectionalS).

Direction type P::Direction A type for representing the course or bearing that is followed when traversing an edge in the underlying graph.

Out-degree type P::OutDegree A type for representing the number of edges from a source vertex in the underlying graph.

Indexability type P::HasIndexableEndpointCells A cell is indexable if it has a corresponding index by which it can be accessed. The entrance and exit cells are considered to be endpoint cells. This Boolean Constant indicates whether or not they are indexable.

Name	Expression	Description
Cell type	`P::Cell`	The type of the objects to be connected together in the Pattern.
Cell equality policy type	`P::CellEqualityPolicy`	The type of the function object that determines equality between any two cells in the Pattern. This type must model the Default Constructible and Binary Predicate concepts, accepting `P::Cell` as both the first and second argument types.
Cell index type	`P::CellIndex`	An unsigned integral type for representing either the index of a cell in the Pattern or the number of such cells.
Graph type	`P::Graph`	The type of the underlying object that represents the manner in which the cells are connected together. Each vertex in the graph represents a single cell, and each edge represents a connection between its source and target cells. This type must model the Adjacency List Graph concept.
Edge directed category type	`P::EdgeDirectedCategory`	The type that represents whether the edges in the underlying graph are undirected (in which case this type is `boost::undirectedS`), directed (in which case this type is `boost::directedS`), or bidirectional (in which case this type is `boost::bidirectionalS`).
Direction type	`P::Direction`	A type for representing the course or bearing that is followed when traversing an edge in the underlying graph.
Out-degree type	`P::OutDegree`	A type for representing the number of edges from a source vertex in the underlying graph.
Indexability type	`P::HasIndexableEndpointCells`	A cell is indexable if it has a corresponding index by which it can be accessed. The entrance and exit cells are considered to be endpoint cells. This Boolean Constant indicates whether or not they are indexable.

Valid Expressions

The following expressions must be valid.

Name Expression Type Requirements Return Type

Initialization pattern.initialize(model-specific arguments)

Packed-argument initialization pattern.initialize_with_named_params(p) p must be an Argument Pack object.

Graph access pattern.getGraph() const P::Graph&

Cell count pattern.getCellCount() P::CellIndex

Cell access pattern.getCell(i) i must be convertible to P::CellIndex. const P::Cell&

Entrance cell access pattern.getEntranceCell() const P::Cell&

Source cell access pattern.getSourceCell() const P::Cell&

Target cell access pattern.getTargetCell() const P::Cell&

Exit cell access pattern.getExitCell() const P::Cell&

Edge direction pattern.getEdgeDirection(source_index, target_index) Both source_index and target_index must be convertible to P::CellIndex. P::Direction

Maximum out-degree pattern.getMaxOutDegree() P::OutDegree

Name	Expression	Type Requirements	Return Type
Initialization	`pattern.initialize(`model-specific arguments`)`
Packed-argument initialization	`pattern.initialize_with_named_params(p)`	`p` must be an Argument Pack object.
Graph access	`pattern.getGraph()`		`const P::Graph&`
Cell count	`pattern.getCellCount()`		`P::CellIndex`
Cell access	`pattern.getCell(i)`	`i` must be convertible to `P::CellIndex`.	`const P::Cell&`
Entrance cell access	`pattern.getEntranceCell()`		`const P::Cell&`
Source cell access	`pattern.getSourceCell()`		`const P::Cell&`
Target cell access	`pattern.getTargetCell()`		`const P::Cell&`
Exit cell access	`pattern.getExitCell()`		`const P::Cell&`
Edge direction	`pattern.getEdgeDirection(source_index, target_index)`	Both `source_index` and `target_index` must be convertible to `P::CellIndex`.	`P::Direction`
Maximum out-degree	`pattern.getMaxOutDegree()`		`P::OutDegree`

Expression Semantics

After initialization, the following semantics must apply.

Name Expression Precondition Semantics Postcondition

Initialization pattern.initialize(model-specific arguments) This function must be able to accept arguments by name. Initializes the Pattern. The parameters to be recognized are model-specific; consult the documentation for that model for details.

Packed-argument initialization pattern.initialize_with_named_params(p) This function must be able to accept arguments by name. Initializes the Pattern. The parameters to be recognized are model-specific; consult the documentation for that model for details.

Graph access pattern.getGraph() Returns the underlying graph that represents the manner in which the cells are connected together. If the entrance and exit cells are indexable, then exactly one edge will exist between the vertices representing the entrance and source cells, and exactly one edge will exist between the vertices representing the target and exit cells.

Cell count pattern.getCellCount() Returns the number of cells in the Pattern.

Cell access pattern.getCell(i) 0 < i && i <= pattern.getCellCount() Returns the (i + 1)th indexable cell in the Pattern.

Entrance cell access pattern.getEntranceCell() Returns the entrance cell in the solution path of an overlying maze. If P::HasIndexableEndpointCells::value == true, then there exists an index i such that 0 < i && i <= pattern.getCellCount() && pattern.getCell(i) == pattern.getEntranceCell().

Source cell access pattern.getSourceCell() Returns the cell that topologically follows the entrance cell in the solution path of an overlying maze.

Target cell access pattern.getTargetCell() Returns the cell that topologically precedes the exit cell in the solution path of an overlying maze.

Exit cell access pattern.getExitCell() Returns the exit cell in the solution path of an overlying maze. If P::HasIndexableEndpointCells::value == true, then there exists an index i such that 0 < i && i <= pattern.getCellCount() && pattern.getCell(i) == pattern.getExitCell().

Edge direction pattern.getEdgeDirection(i1, i2)

The underlying graph must contain an edge between the corresponding vertices.

To retrieve the direction from the entrance cell to the source cell, i1 == i2. To retrieve the direction from the target cell to the exit cell, i2 == pattern.getCellCount(). Otherwise, 0 < i1 && i1 <= pattern.getCellCount() && 0 < i2 && i2 <= pattern.getCellCount().

Returns a representation of the course or bearing that is followed when traversing the corresponding edge in the underlying graph, with the source vertex representing the (i1 + 1)th cell and the target vertex representing the (i2 + 1)th cell.

Maximum out-degree pattern.getMaxOutDegree() Returns the maximum number of edges from any source vertex in the underlying graph.

Name	Expression	Precondition	Semantics	Postcondition
Initialization	`pattern.initialize(`model-specific arguments`)`	This function must be able to accept arguments by name.	Initializes the `Pattern`. The parameters to be recognized are model-specific; consult the documentation for that model for details.
Packed-argument initialization	`pattern.initialize_with_named_params(p)`	This function must be able to accept arguments by name.	Initializes the `Pattern`. The parameters to be recognized are model-specific; consult the documentation for that model for details.
Graph access	`pattern.getGraph()`		Returns the underlying graph that represents the manner in which the cells are connected together.	If the entrance and exit cells are indexable, then exactly one edge will exist between the vertices representing the entrance and source cells, and exactly one edge will exist between the vertices representing the target and exit cells.
Cell count	`pattern.getCellCount()`		Returns the number of cells in the `Pattern`.
Cell access	`pattern.getCell(i)`	`0 < i && i <= pattern.getCellCount()`	Returns the `(i + 1)`th indexable cell in the `Pattern`.
Entrance cell access	`pattern.getEntranceCell()`		Returns the entrance cell in the solution path of an overlying maze.	If `P::HasIndexableEndpointCells::value == true`, then there exists an index `i` such that `0 < i && i <= pattern.getCellCount() && pattern.getCell(i) == pattern.getEntranceCell()`.
Source cell access	`pattern.getSourceCell()`		Returns the cell that topologically follows the entrance cell in the solution path of an overlying maze.
Target cell access	`pattern.getTargetCell()`		Returns the cell that topologically precedes the exit cell in the solution path of an overlying maze.
Exit cell access	`pattern.getExitCell()`		Returns the exit cell in the solution path of an overlying maze.	If `P::HasIndexableEndpointCells::value == true`, then there exists an index `i` such that `0 < i && i <= pattern.getCellCount() && pattern.getCell(i) == pattern.getExitCell()`.
Edge direction	`pattern.getEdgeDirection(i1, i2)`	The underlying graph must contain an edge between the corresponding vertices. To retrieve the direction from the entrance cell to the source cell, `i1 == i2`. To retrieve the direction from the target cell to the exit cell, `i2 == pattern.getCellCount()`. Otherwise, `0 < i1 && i1 <= pattern.getCellCount() && 0 < i2 && i2 <= pattern.getCellCount()`.	Returns a representation of the course or bearing that is followed when traversing the corresponding edge in the underlying graph, with the source vertex representing the `(i1 + 1)`th cell and the target vertex representing the `(i2 + 1)`th cell.
Maximum out-degree	`pattern.getMaxOutDegree()`		Returns the maximum number of edges from any source vertex in the underlying graph.

Invariants and Runtime Complexity Guarantees

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

Name Invariants Runtime complexity

Initialization Quadratic time

Packed-argument initialization Quadratic time

Graph access Valid after initialization; strongly connected. Amortized constant time

Cell count Valid after initialization; 0 < pattern.getCellCount(). Linear time

Cell access Valid after initialization. Amortized constant time

Entrance cell access Valid after initialization. Amortized constant time

Source cell access Valid after initialization. Amortized constant time

Target cell access Valid after initialization. Amortized constant time

Exit cell access Valid after initialization. Amortized constant time

Edge direction Valid after initialization. Amortized constant time

Maximum out-degree Valid after initialization. Amortized constant time

Name	Invariants	Runtime complexity
Initialization		Quadratic time
Packed-argument initialization		Quadratic time
Graph access	Valid after initialization; strongly connected.	Amortized constant time
Cell count	Valid after initialization; `0 < pattern.getCellCount()`.	Linear time
Cell access	Valid after initialization.	Amortized constant time
Entrance cell access	Valid after initialization.	Amortized constant time
Source cell access	Valid after initialization.	Amortized constant time
Target cell access	Valid after initialization.	Amortized constant time
Exit cell access	Valid after initialization.	Amortized constant time
Edge direction	Valid after initialization.	Amortized constant time
Maximum out-degree	Valid after initialization.	Amortized constant time

Models

All models of the Physical Pattern concept.
The following class templates deriving from BasePattern:
- NBitPattern

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