Forcing a Tgraph requires conversion to a BoundaryState (which records extra data) and then to a ForceState (which keeps track of possible updates during forcing). Thus we introduce a Forcible class which will have Tgraph, BoundaryState, ForceState as instances.

Forcible class has operations to (indirectly) implement forcing and single step forcing for any Forcible. The class operations are more general to allow for other force related operations to be generalised for use on any Forcible. For example tryAddHalfKite and tryAddHalfDart are implemented using tryChangeBoundaryWith.

Note that these operations are parameterised on an UpdateGenerator, which encapsulates the forcing rules to be used.

The main force (partial) function using defaultAllUGen representing all 10 rules for updates. This raises an error on discovering a stuck/incorrect Forcible.

forceWith ugen: force using the given UpdateGenerator This raises an error on discovering a stuck/incorrect Forcible.

A try version of the main force function using defaultAllUGen representing all 10 rules for updates. This returns Left report on discovering a stuck Tgraph and Right a (with a the resulting forcible) otherwise.

try forcing using a given UpdateGenerator. tryForceWith uGen fs - does updates using uGen until there are no more updates. It produces Left report if it encounters a Forcible representing a stuck/incorrect Tgraph.

stepForce n a - produces an intermediate Forcible after n steps (n face additions) starting from Forcible a. It raises an error if it encounters a stuck/incorrect Forcible within n steps. If forcing finishes successfully in n or fewer steps, it will return that final Forcible.

tryStepForce n a - produces a (Right) intermediate Forcible after n steps (n face additions) starting from Forcible a. or a Left report if it encounters a stuck/incorrect Forcible within n steps. If forcing finishes successfully in n or fewer steps, it will return that final Forcible.

try a given number of force steps using a given UpdateGenerator.

A version of tryFSOpWith using defaultAllUGen representing all 10 rules for updates.

initialize a force state with the default UpdateGenerator. Raises an error if it finds a stuck Forcible.

try to initialize a force state with the default UpdateGenerator. Returns a Left report if it finds a stuck Forcible.

specialises tryChangeBoundaryWith to the default update generator.

special case of forcing only half tiles to whole tiles

Forced a is a newtype (for a) to explicitly indicate that a is fully forced. This enables restriction of some functions that should only be applied to a fully forced Forcible.

To access the Forcible use: forgetF :: Forced a -> a

Create an explicitly Forced Forcible using forceF or tryForceF

forget the explicit Forced labelling

tryForceF is the same as tryForce except that the successful result is explitly indicated as Forced.

forceF is the same partial function as force except that the (successful) result is explitly indicated as Forced.

recoverGraphF is an explicitly forced version of recoverGraph

boundaryStateF is an explicitly forced version of boundaryState

makeBoundaryStateF is an explicitly forced version of makeBoundaryState

initFSF is an explicitly forced version of initFS

Constructs an explicitly Forced type.

WARNING: this should only be used when the argument is known to be a fully forced Forcible. Consider using forceF or tryForceF instead for safety reasons.

addHalfKite is for adding a single half kite on a chosen boundary Dedge of a Forcible. The Dedge must be a boundary edge but the direction is not important as the correct direction is automatically calculated. It will raise an error if the edge is a dart join or if a conflict (stuck graph) is detected or if the edge is not a boundary edge.

tryAddHalfKite is a version of addHalfKite which returns a Try with a Left report if it finds a stuck/incorrect graph, or if the edge is a dart join, or if the edge is not a boundary edge.

addHalfDart is for adding a single half dart on a chosen boundary Dedge of a Forcible. The Dedge must be a boundary edge but the direction is not important as the correct direction is automatically calculated. It will raise an error if the edge is a dart short edge or kite join or if a conflict (stuck graph) is detected or if the edge is not a boundary edge.

tryAddHalfDart is a version of addHalfDart which returns a Try with a Left report if it finds a stuck/incorrect graph, or if the edge is a dart short edge or kite join, or if the edge is not a boundary edge.

tryOneStepWith uGen fs does one force step (used for debugging purposes). It returns either (1) a Right(Just (f,bc)) with a new ForceState f paired with a BoundaryChange bc (using uGen to revise updates in the final ForceState), or (2) a Right Nothing indicating forcing has finished and there are no more updates, or (3) a Left report for a stuck/incorrect graph.

tryOneStepForce is a special case of tryOneStepWith using defaultAllUGen (used for debugging).

A BoundaryState records the boundary directed edges (directed so that faces are on LHS and exterior is on RHS) plus a mapping of boundary vertices to their incident faces, plus a mapping of boundary vertices to positions (using Tgraph.Prelude.locateVertices). It also keeps track of all the faces and the next vertex label to be used when adding a new vertex.

ForceState: The force state records information between executing single face updates during forcing (a BoundaryState and an UpdateMap).

After a face addition to a BoundaryState (by either trySafeUpdate or tryUnsafeUpdate), a BoundaryChange records (1) the new BoundaryState (2) the list of directed edges that were, but are no longer on the boundary (1,2,or 3), (3) a list of boundary edges requiring updates to be recalculated - i.e the new boundary edges and their immediate neighbours (4,3,or 0). (4) the face that has been added.

An Update is either safe or unsafe. A safe update has a new face involving 3 existing vertices. An unsafe update has a makeFace function to create the new face when given a fresh third vertex.

UpdateMap: partial map associating updates with (some) boundary directed edges. (Any boundary directed edge will have the opposite direction in some face.)

UpdateGenerator is a newtype for functions which capture one or more of the forcing rules. The functions can be applied using the unwrapper applyUG and produce a (Try) UpdateMap when given a BoundaryState and a focus list of particular directed boundary edges. Each forcing rule has a particular UpdateGenerator, but they can also be combined (e.g in sequence - allUGenerator or otherwise - defaultAllUGenerator).

UFinder (Update case finder functions). Given a BoundaryState and a list of (focus) boundary directed edges, such a function returns each focus edge satisfying the particular update case paired with the tileface matching that edge. For example, if the function is looking for dart short edges on the boundary, it will return only those focus edges which are half-dart short edges, each paired with its half-dart face.

UChecker (Update checker functions). Given a BoundaryState and a particular tileface (on the boundary), such functions try to produce particular updates on the boundary edge of the given tileface. [They are called update checkers because they may uncover an incorrect/stuck tiling when creating the update.] As an example, addKiteShortE will try to produce an update to add a half-kite with short edge against the boundary. Such a function can be used with a UFinder that either returns dart halves with short edge on the boundary (nonKDarts in rule 2) or returns kite halves with short edge on the boundary (kitesWingDartOrigin in rule 3).

Calculates BoundaryState information from a Tgraph.

Converts a BoundaryState back to a Tgraph

facesAtBV bd v - returns the faces found at v (which must be a boundary vertex)

return a list of faces which have a boundary vertex from a BoundaryState

Given a BoundaryState with a list of one boundary edge or two adjacent boundary edges (or exceptionally no boundary edges), it extends the list with adjacent boundary edges (to produce 3 or 4 or none). It will raise an error if given more than 2 or 2 non-adjacent boundary edges. (Used to calculate revisedEdges in a BoundaryChange. (N.B. When a new face is fitted in to a hole with 3 sides there is no new boundary. Hence the need to allow for an empty list.)

tryReviseUpdates uGen bdChange: revises the UpdateMap after boundary change (bdChange) using uGen to calculate new updates.

tryReviseFSWith ugen bdC fs tries to revise fs after a boundary change (bdC) by calculating the revised updates with ugen (and using the new boundary state in bdC).

finds the first safe update - Nothing if there are none (ordering is directed edge key ordering)

tryUnsafes: Should only be used when there are no Safe updates in the UpdateMap. tryUnsafes works through the unsafe updates in (directed edge) key order and completes the first unsafe update that is not blocked (by a touching vertex), returning Right (Just bdC) where bdC is the resulting boundary change (if there is one). It returns Right Nothing if there are no unsafe updates but Left report if there are unsafes but all unsafes are blocked, where report describes the problem.

checkUnsafeUpdate bd u, calculates the resulting boundary change for an unsafe update (u) with a new vertex (raising an error if u is a safe update). It performs a touching vertex check with the new vertex returning Nothing if there is a touching vertex (blocked case). Otherwise it returns Just bdc with bdc a boundary change. [Note: Try is not used as a conflict cannot be found in the unsafe case, and blocking is only a problem when all unsafe updates are blocked (and there is at least one) - see tryUnsafes]

trySafeUpdate bd u adds a new face by completing a safe update u on BoundaryState bd (raising an error if u is an unsafe update). It returns a Right BoundaryChange (containing a new BoundaryState, removed boundary edges and revised boundary edge list), unless a stuck/incorrect graph is found. It checks that the new face is not in conflict with existing faces, producing (Left report) if there is a conflict. It should cater for the exceptional case where the update removes 3 boundary edges in a triangle (and removes 3 boundary vertices), closing a hole.

tryUpdate: tries a single update (safe or unsafe), producing Left report if the update creates a touching vertex in the unsafe case, or if a stuck/incorrect Tgraph is discovered in the safe case.

A version of force that recalibrates at 20,000 step intervals by recalculating boundary vertex positions from scratch. This is needed to limit accumulation of errors when large numbers of faces are added in forcing. This raises an error on discovering a stuck/incorrect Forcible.

A version of tryForce that recalibrates at 20,000 step intervals by recalculating boundary vertex positions from scratch. This is needed to limit accumulated inaccuracies when large numbers of faces are added in forcing.

This recalibrates a BoundaryState by recalculating boundary vertex positions from scratch with locateVertices. (Used at intervals in tryRecalibratingForce and recalibratingForce).

The default all update generator (see also allUGenerator). It uses the 10 rules (and the same UCheckers as allUGenerator), but makes decisions based on the EdgeType of a boundary edge (instead of trying each UFinder in turn). If there are any Left..(fail reports) for the given boundary edges the result is a single Left, concatenating all the failure reports (unlike allUGenerator).

combineUpdateGenerators combines a list of update generators into a single update generator. When used, the generators are tried in order on each boundary edge (in the supplied focus edges), and will return a Left..(fail report) for the first generator that produces a Left..(fail report) if any.

allUGenerator was the original generator for all updates. It combines the individual update generators for each of the 10 rules in sequence using combineUpdateGenerators (See also defaultAllUGen which is defined without using combineUpdateGenerators)

Update generator for rule (1)

Find faces with missing opposite face (mirror face)

Update generator for rule (2)

Find half darts with boundary short edge

Update generator for rule (3) queen and king vertices add a missing kite half (on a boundary kite short edge)

Find kites with boundary short edge where the wing is also a dart origin

Update generator for rule (4) (for deuce vertices = largeKiteCentres) Kites whose short edge (b,a) matches a boundary edge (a,b) where their oppV has 2 other kite halves sharing a shortE. These need a dart adding on the short edge.

Find kite halves with a short edge on the boundary where there are 2 other kite halves sharing a short edge at oppV of the kite half.

Update generator for rule (5) jackDartUpdates - jack vertex add a missing second dart

Find kite halves with a short edge on the boundary where oppV must be a jack vertex The function mustbeJack finds if a vertex must be a jack.

Update generator for rule (6) sunStarUpdates is for vertices that must be either sun or star almostSunStar finds half-kites/half-darts with a long edge on the boundary where their origin vertex has 8 total half-kites/half-darts respectively or their origin vertex has 6 total half-kites in the case of kites only completeSunStar will add a new face of the same type (dart/kite) sharing the long edge.

Find a boundary long edge of either a dart where there are at least 7 dart origins (mustbeStar), or a kite where there are at least 5 kite origins (mustbeSun).

Update generator for rule (7) jack vertices with dart long edge on the boundary - add missing kite top. The function mustbeJack finds if a vertex must be a jack.

Find a boundary long edge of a dart where the wingV is a jack vertex. The function mustbeJack finds if a vertex must be a jack.

Update generator for rule (8) king vertices with 2 of the 3 darts - add another half dart on a boundary long edge of existing darts

Find a dart long edge on the boundary where the originV must be a king vertex. The function mustbeKing finds if a vertex must be a king (2 of the 3 darts at the origin plus a kite wing at the origin).

Update generator for rule (9) queen vertices (more than 2 kite wings) with a boundary kite long edge - add a half dart

Find a boundary kite long edge where the wingV must be a queen vertex (more than 2 kite wings at the wingV).

Update generator for rule (10) queen vertices with more than 2 kite wings -- add missing half kite on a boundary kite short edge

Find a kite short edge on the boundary where the wingV must be a queen vertex (more than 2 kite wings at the wingV).

completeHalf will check an update to add a symmetric (mirror) face for a given face at a boundary join edge.

add a (missing) half kite on a (boundary) short edge of a dart or kite

add a half dart top to a boundary short edge of a half kite.

add a kite half to a kite long edge or dart half to a dart long edge

add a kite to a long edge of a dart or kite

add a half dart on a boundary long edge of a dart or kite

A vertex on the boundary must be a star if it has 7 or more dart origins

A vertex on the boundary must be a sun if it has 5 or more kite origins

A vertex on the boundary which is an oppV of a kite must be a deuce if there is a shared kite short edge at the vertex.

A boundary vertex which is a kite wing and has 4 dart origins must be a king vertex

isKiteWing bd v - Vertex v is a kite wing in BoundaryState bd

isKiteOppV bd v - Vertex v is a kite oppV in BoundaryState bd

isDartOrigin bd v - Vertex v is a dart origin in BoundaryState bd

A boundary vertex with >2 kite wings is a queen vertex (needing a fourth kite on a kite short edge or dart on a kite long edge)

kiteWingCount bd v - the number of kite wings at v in BoundaryState bd

mustbeJack is true of a boundary vertex if it is the wing of two darts not sharing a long edge or it is a wing of a dart and also a kite origin (false means it is either undetermined or is a deuce).

newUpdateGenerator combines an update case finder (UFinder) with its corresponding update checker (UChecker) to produce an update generator. This is used to make each of the 10 update generators corresponding to 10 rules.

When the generator is applied (with applyUG) to a BoundaryState and list of focus edges, the finder produces a list of pairs of dedge and face, the checker is used to convert the face in each pair to an update (which can fail with a Left report), and the new updates are returned as a map (with the dedges as keys) in a Right result.

This is a general purpose filter (previously used to create UFinder functions for each force rule). It requires a face predicate where the face predicate takes a BoundaryState bd, a boundary Dedge (a,b) and the TileFace with the edge (b,a) and decides whether the face is wanted or not (True = wanted) This will be used to filter all the faces at the focus edges (when given a BoundaryState and list of focus edges). For some predicates the BoundaryState argument is not used (eg boundaryJoin in incompleteHalves), but for others it is used to look at other faces at b or at a besides the supplied face (eg in kitesWingDartOrigin)

This is a general purpose filter used to create UFinder functions for each force rule. It requires an edgeType and a face predicate. The face predicate takes a BoundaryState bd, and a TileFace and (assuming the boundary edge of the face matches the given edgeType) decides whether the face is wanted or not (True = wanted). This will be used to filter all the faces at the focus edges (when given a BoundaryState and list of focus edges). For some predicates the BoundaryState argument is not used (eg boundaryJoin in incompleteHalves), but for others it is used to look at other faces besides the supplied face (eg in kitesWingDartOrigin)

makeUpdate f x constructs a safe update if x is Just(..) and an unsafe update if x is Nothing

externalAngle bd v - calculates the external angle at boundary vertex v in BoundaryState bd as an integer multiple of tt (tenth turn), so 1..9. It relies on there being no crossing boundaries, so that there is a single external angle at each boundary vertex.

touchCheck p vpMap - check if a vertex location p touches (is too close to) any other vertex location in the mapping vpMap