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


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.


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


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.


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


Models



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