#ifndef Octf_H #define Octf_H /* Last edited on 2007-02-04 18:21:01 by stolfi */ /* The Facet-Edge data structure for representing the topology of 3D maps. */ #define Octf_H_copyright \ "Copyright © 1998 Universidade Estadual de Campinas (UNICAMP)" #define Octf_H_author \ "The Modula-3 version of this interface was created in 1998" \ "by Luis Arturo Perez Lozada, UNICAMP, inspired on the " \ "Modula-3 implementation of the quad-edge data structure by " \ "J.Stolfi and R.M.Rosi (ca. 1994). " \ "It was converted to C and substantially revised in jan/2007 by J.Stolfi." #define _GNU_SOURCE #include #include #include #include #include /* [!!! RENAMES TO CONSIDER !!!] */ /* node -> site / knot / */ /* wall -> face */ /* edge -> link / line */ /* flag -> chip / flap / side / tile / face / trig */ /* link -> edge / bond */ /* chip -> bloc / quad */ /* knot -> site */ /* place -> spot */ /* wedge -> */ /* flow -> drip / order */ /* flux -> seep / ????? */ /* curl -> turn / whorl / clock */ /* hand -> ???? / twist / screw / helix */ /* BASIC CONCEPTS AND NOTATION A facet-edge data structure is meant to represent the topology of a map on some 3D topological space. The structure was described by D.Dobkin and J.Laszlo ("D&L" below) in the paper "Primitives for the Manipulation of Three-Dimensional Subdivisions" (/Algorithmica/, 1989). For the purpose of these comments, at any time there is a single facet-edge structure in the program's address space, representing a single map {M} over a single topological space {X}. All concepts of point-set topology used here (closure, boundary, connectedness, homeomorphic, etc.) are relative to the topology of {X}. The space {X} and the map {M} are defined by the structure up to an homeomorphism, and their topology changes implicitly as the structure gets modified. However, each connected component of the structure represents a distinct connected component of {M}, lying on a distinct connected component of {X}; and can be traversed, modified, and written out to disk without interfering with any other component. Thus, one may work with each connected component of {M} as if it were a separate instance of the data structure. The map {M} is a partition of {X} into /elements/. Each element {e} is homeomorphic to {R^k} for some {k} in {0..3}; we denote its dimension {k} by {e.dim}. We will call the element a /node/, /edge/, /wall/, or /cell of {M}/, depending on whether its dimension is 0,1,2, or 3. (In the original paper, those elements are called /vertices/, /edges/, /facets/ and /polyhedra/, respectively.) If {x} is any point of {X}, we write {x@M} for the unique element of {M} that owns {x}. The /{M}-type of a point {x}/ of {X} is the integer {x@M.dim}, the dimension of the unique element of {M} that owns {x}; which we denote by {(x,M).typ}. If {Y} is any subset of {X}, we write {Y$} for the topological closure of {Y} (in {X}). If {Y,Z} are two subsets of {X}, we say /{Y} incides on {Z}/, or equivalently that /{Z} bounds {Y}/, iff {Y$} intersects {Z}. */ /* BARYCENTRIC SUBDIVISION The facet-edge structure is defined in terms of an auxiliary map on {X}, a triangulation (`simplicial map') {S} that is a barycentric sudivision of {M}. To reduce confusion, the elements of {S} with dimensions 0,1,2,3 will be called /knots/, /links/, /flag/ and /chips/, respectively. Each element {e} of {M} contains a unique knot {e!} of {S}, the /centroid of {e}/. Conversely, each element {r} of {S} is contained in a unique element {e} of {M}, which we will denote by {r@M}. The /{M}-type of an element {r} of {S}/ is the set of integers {{ (x,M).typ : x in r$ }}. It coincides with the set {{ v@M.dim }} where {v} ranges over the knots of {S} that bound {r}. Note that a {k}-dimensional element of {S} has {k+1} distinct bounding knots, all with distinct types. We write {(r,M).knt[i]} for the bounding knot of {r} with {M}-type {i}, when it exists. It follows that each chip {s} of {S} defines a fairly precise location in a map {M}. In particular, it defines a quadruple of elements {(e[0],..e[3])} such that each {e[i]} has dimension {i} and is incident on {e[j]} for all {j0}, admits exctly two distinct consistent /internal orientations/ that specify the sense for local motions of motion WITHIN {Y} at any point of {Y}. In particular, if {Y} is a line ({k==1}), the internal orientation is a /flow/, a specific direction of travel ALONG {Y}. If {Y} is a surface ({k==2}) the orientation is a /curl/, a specific sense of turning WITHIN {Y}. If {Y} is a solid ({k==3}), the orientation is a /twist/, a specific handedness for local helical motions INSIDE {Y}. On the other hand, if {Y} is a single point ({k==0}), it has only one internal orientation. If the subset {Y} is a {k}-ball with {k<3}, and has a neighborhood in {X} that is a 3-ball, then {Y} also admits two distinct /external orientations/, which are independent of the internal ones. If {Y} is a surface, line, or isolated point, the external orientation is, respectively, a direction of motion ACROSS {Y} (a /flux/), a sense of turning AROUND {Y} (a /spin/), and a specific handedness for helical motion ABOUT {Y} (a /twist/). */ /* ORIENTATIONS OF BARYCENTRIC ELEMENTS The barycentric subdivision {S} defines a specific internal orientation for every chip {s} of {S}, and also for links of {S} with {M}-types {{0,1}} and {{2,3}} (the /edge links/), and flag of {S} with {M}-types {{0,1,2}} and {{1,2,3}} (the /wall flag/). Specifically, the /intrinsic flow/ on a link with {M}-type {{0,1}} is, by definition, the one that goes from the knot with {M}-type 0 to the knot with {M}-type 1. Dually, the intrinsic flow on a link with {M}-type {{2,3}} goes from the knot with {M}-type 3 to that of {M}-type 2. The /intrinsic curl/ on a flag with {M}-type {{0,1,2}} is, by definition, the one that traverses the flag's perimeter going through knots 0,1,2, in that order; while the intrinsic curl on a {{1,2,3}} flag goes through its bounding knots in the order 3,2,1. Also, the /intrinsic twist/ at any point inside any chip {s} is the one that agrees with the intrinsic flows on its {{0,1}} and {{2,3}} bounding links. Informally, the twist that moves with the flow on the {{0,1}} link while turning in the sense of the flow on the {{2,3}} link. Note that these definitions specify the same INTERNAL orientations on chips, edge links, and wall flag, no matter which of the two maps we use to assign types. Also, the internal orientations of those links and flag are defined without reference to a specific chip. Since the closure of any chip {s} is simply-immersed in {X} (i.e. is homeomorphic to a closed 3-ball), the intrinsic twist of {s} can be consistently extended to its closure {s$}. Note however that any two chips that share a flag will define OPPOSITE twists at any point on that flag. A specific chip {s} also determines EXTERNAL orientations for the its wall flag, its edge links, and its node knots (those with {M}-type {{0}} or {{3}}). By definition, the spin around its {{0,1}} link is the one that agrees across {s} with the intrinsic flow on the opposite {{2,3}} link; and symmetrically for the spin around the {{2,3}} link. Also, the flux deermined by {s} across its {{0,1,2}} and {{1,2,3}} flag are, by definition, those that leave the chip {s}. Note that these EXTERNAL orientations for links and flag do NOT depend on which of the two maps we use as reference, but they DO depend on the chip {s}. In particular, two chips that share a {{0,1,2}} or {{1,2,3}} flag {t} will determine opposite fluxes across {t}, and opposite spins around the shared {{0,1}} or {{2,3}} link. */ /* ORIENTATIONS OF ELEMENTS The intrinsic flow along a {{0,1}} link {r} determines by extension a flow along the map edge {e = r@M} that contains {r}. The two {{0,1}} links on an edge {e} are always distinct, and determine opposite flows along {e}. In the same way, the intrinsic curl of a {{0,1,2}} flag can be extended to a curl for the wall it belongs to. The flag that belong to any given wall {f} can be partitioned into two subsets {A,B} of equal size, such that any flag in {A} determines a specific curl within the wall, and any flag in {B} determines the opposite curl. For cells, the situation is more complicated. suppose that all the chips contained in a cell {c} can be partitioned into two subsets {A,B}, such that any two adjacent chips are always in distinct subsets. In that case, the cell {c} admits two orientations, and chip {s} in {A} of {B} determines a specific twist for the whole cell {c}: namely, the one that agrees with intrinsic twist of {s}. Moreover, all chips in {A} determine the same twist for {c}, while all chips in {B} determine the opposite twist. In that case, we say that the cell {c} is /orientable/. On the other hand, if such a partition does not exist, then the cell's centroid {c!} must be a /non-manifold point of {X}/, one that does not have a ball-like neighborhood; indeed, it must be a /non-orientable point/, one that has no orientable neighborhood. In that case, one cannot define the concept of `twist' at {c}; and all its chips are equivalent in that regard. The same considerations apply to the cells of the dual map. So a chip {s) that incides on a node {v} of {M} defines a twist inside the cell {v*} of {M*}, and hence a twist about {v} --- provided that the chips that incide on {v} can be partitioned into two sets {A,B} with the property stated above. Otherwise, {v} is a non-orientable (and non-manifold) point of {X}, and one cannot define the concept of `twist' about that point. The facet-edge data structure is such that every point of the underlying manifold {X} has ball-like neighborhood, except possibly for the nodes of {M} and {M*} (i.e.,nodes and cell centroids of {M}). Note that a cell may be orientable even if its centroid does not have a ball-like neighborhood. Note also that a connected component of {X} may be non-orientable even if all its points have ball-like neighborhoods. */ /* PLACES A /place/ in the facet-edge structure is a pair {(s,M)} where {s} is a chip of {S} (denoted {p.s}) and {M} is one the two maps represented by the structure (denoted {p.M}). The concepts defined for chips of {S} are naturally extended to places; with the advantage that, if the concept is defined relative to a map, the map {p.M} is implicitly used. Thus, for instance, if {r} is an {S}-element that bounds the chip {p.s}, the /{p}-type of {r}/ is the set {(r,p.M).typ}. The /knot of {p} with type {i}/ is knot {p.knt[i] = (p.s,p.M).knt[i]}. And so on. */ typedef struct PlaceRec_t *Place_t; /* A {Place_t} value represents a place in the facet-edge structure. */ vec_typedef(Place_vec_t,Place_vec,Place_t); /* A vector of {Place_t}s. */ /* DUAL PLACES The /dual of a place {p}/ is {p* = (p.s,p.M*)}, the place defined by the same chip on the dual map. Obviously, {p** = p} for any place {p}. */ Place_t Dual(Place_t p); /* Returns the dual {p*} of the place {p}. */ /* THE ELEMENTS OF A PLACE If {p} is a place, we define /the elements of {p}/ as the quadruple {p.elm} such that {p.elm[i] = (p.s,p.M).elm[i]} for {i} in {0..3}. We will call {p.elt[0] = p.node} /the node of {p}/, {p.elt[1] = p.edge} /the edge of {p}/, {p.elt[2] = p.wall} /the wall of {p}/, and {p.elt[3] = p.cell} /the cell of {p}/, respectively. The elements of {p} are implicitly oriented as determined by the chip {p.s}. Note that two distinct chips {s,t} of {S} may define the same element sequences {(s,M).elm == (t,M).elm}. For instance, if an edge {e} of {M} is a loop, then there are two chips in {S} (and, therefore, two places in {M}) which have the same elements. However, those two places can be distinguished by the orientations they define on those elements. Conversely, as pointed out by D&L, there is a one-to-one correspondence between the places on {M} and all pairs {(a,b)} where {a} is an internally oriented edge of {M} (an edge with a specific flow) and {b} is an internally oriented edge of {M*}, such that {a*} is incident on {b} and vice versa. In one direction, the correspondence is {(a,b) = (p.edge,p*edge)}, which we will denote by {p.pair}. In the other direction, observe that the orientation of {a} determines a unique link {r} of {M}-type {{0,1}}, namely the one at the origin end of {a}; and {b} determines a unique {{2,3}} link {t}. These two links uniquely determine the chip {p.s}, and the order of the pair {(a,b)} determines the map {p.M}. */ /* DUALITY AND ORIENTATION Note that {p*} and {p} define the same orientation on the chip {p.s==p*.s}. Indeed, the internal orientation of any element {e = p.elt[i]} as implied by {p}, agrees with the external orientation of {e* = p*.elt[3-i]}, as implied by {p*}, at their intersection point {e! == e*!}. Thus, for example, the flow along the edge {e = p.edge} of {M} agrees with the flux across the wall {e* = p*.wall} of {M*}, at the point where {e} crosses {e*}. Similarly, the curl inside the wall {f = p.wall} of {M} agrees with the spin around the edge {f* = p*.edge} of {M*}, at the point where {f*} crosses {f}. */ /* PLACE-FLIPPING OPERATIONS For each chip {s} of the barycentric subdivision {S}, and each {i} in {0..3}, there is a unique chip {t} that is distinct from {s} but shares with it a flag with {M}-type {0..3}\{i}. We call {t} the /{i}-flip of {s} relative to {M}/, denoted {(s,M).flp[i]}. The {flp} operations extend naturally to places; namely, if {p} is a place, then {p.flp[i]} is the place {((p.s,p.M).flp[i], p.M)}. Note that {p.flp[i].flp[i] == p} (i.e., {flp[i]} is its own inverse), and {p*.flp[i] == p.flp[3-i]*}, for any place {p} and type {i}. The efect of {flp[i]} on the element tuple of {p} is to exchange the {i}-dimensional element by its `natural partner', while preserving the other elements with opposite internal orientations. Se below for explanations about the `natural partner'. The {flp[i]} operators completely determine the topology of {S} and {M}, up to an homeomorphism; and vice-versa. They allow walking from place to place all over either map. For example, one can enumerate the cells of {M} that surround a given edge {e} of {M} by starting from any place {p} on {M} such that {p.s} is incident to {e}, and using {flp[2]} and {flp[3]} operations --- which vary {p.wall} and {p.cell}, respectively, while preserving {p.edge} and its endpoint {p.node}. Similary, one can visit all places with the same node {v} by stating from any such place and using {flp[1]}, {flp[2]} and {flp[3]} in all combinations. */ Place_t Flip(Place_t p, uint i); /* Given a place {p}, returns the place {p.flp[i]}. The facet-edge structure is implemented in such a way that this operation takes constant time, independent on the map's topology. */ Place_t Flip0(Place_t p); /* The same as {Flip(p,0)}. It replaces {p.node} by the node at the other endpoint of {p.edge}, while preserving {p.edge}, {p.wall}, and {p.cell}, with reversed internal orientations. */ Place_t Flip1(Place_t p); /* The same as {Flip(p,1)}. It replaces {p.edge} by another edge on the boundary of {p.wall} that is also incident to {p.node}, with flow directed away from {p.node}, while preserving {p.node}, {p.wall}, and {p.cell} --- the last two with reversed internal orientations. */ Place_t Flip2(Place_t p); /* The same as {Flip(p,2)}. It replaces {p.wall} by another wall on the boundary of {p.cell} that is also incident to {p.edge}, with curl that agrees with the flow of {p.edge}, while preserving {p.node}, {p.edge}, and {p.wall} --- the last two with reversed internal orientations. */ Place_t Flip3(Place_t p); /* The same as {Flip(p,3)}. It replaces {p.cell} by the cell on the other flag of {p}'s wall, while preserving {p.node}, {p.edge}, and {p.wall} --- the last two with reversed internal orientations. */ Place_t Spin(Place_t p); /* D&L's original name for {Flip3}. */ /* PLACE ORIENTATION A place {p} defines a unique chip {p.s} of {S}; therefore, as discussed above, it determines internal and external orientations for its elements, whenever they can be defined. In particular, {p} usually determines a a twist around the vertex {v=p.node}; a flow along the edge {e=p.edge}, and a spin around it; a curl on the wall {f=p.wall}, and a flux cross it; and a twist inside the cell {c=p.cell}. However, the twists around {v} and inside {c} are defined only if the {v} and {c!}, respectively, have orientable neighborhoods. As noted above, the places {p} and {p.flp[i]}, for anly {p} and {i}, define opposite twists on any point of their shared flag. We say that two places {p,q} on the same map are /evenly connected/ (resp. /oddly connected/) iff one can be obtained from the other by an even (resp. odd) number of {flp} operations. Note that {p.s} and {q.s} lie on the same connectred component of the space {X} iff they are either evenly connected or oddly connected. It turns out that a connected component {Y} of the space {X} is orientable only if there is no place on the corresponding component {N} of {M} that is oddly connected to itself. In that case, the set of places on the component {N} can be divided into two subsets {A,B}, such that {p} and {p.flp[i]} are on different subsets, for any {p} and {i}; and each subset defines a different consistent twist for the whole subspace {|N|}. Usually, the places {p} and {p.flp[i]} will determine opposite INTERNAL orientations for every element {p.elt[j]} with {j!=i}. Thus, for example, doing {p = p.flp[0]} may or may not change the node {p.node}, but always reverses the implied flow on the edge {p.edge}, the implied curl on the wall {p.wall}, and the implied twist on the cell {p.cell} (provided that the cell is orientable). The EXTERNAL orientations of {p}'s elements, on the other hand, are affected only in some cases. The twist around {p.node} is reversed by {flp[1],flp[2],flp[3]}; the spin around {p.edge} is preserved by {flp[0]} but reversed by {flp[2],flp[3]}; and the flux across {p.wall} is preserved by {flp[0],flp[1]} but reversed by {flp[3]}. */ /* NEARBY ELEMENTS The flow on {p.edge} determined by {p} always moves away from {p.node}; so {p.node} will also be called the /origin (node)/ of {p}, {p.orig}, while the node at the other endpoint of {p.edge}, which is {p.flp[0].node}, will be called {p}'s /destination (node)/, writen {p.dest}. Dually, the flux across {p.wall} is directed outwards from {p.cell}; so {p.cell} will be called the /hither (cell)/ of {p}, denoted {p.hith}, while the cell on the other flag of {p.wall}, namely {p.flp[3].cell}, is {p}'s /yonder (cell)/, written {p.yond}. We will also define {p}'s /back wall/, {p.back}, as {p.flp[2].wall}; and {p}'s /fork edge/, {p.fork}, as {p.flp[1].edge}. By definition, the internal and external orientations of the elements {p.dest}, {p.yond}, {p.back} and {p.fork} are defined by these formulas. */ /* DERIVED WALKING OPERATIONS By combining two or more {flp} operations, one obtains a variety of `walking operators' that move from place to place in a regular way. Walking operators that combine two (or an even number of) {flp} steps are interesting because they will transport the local twist of the manifold from the given place to the result place, coherently, across the flag traversed by those {flp}s. Thus, if the manifold {X} is orientable, they will preserve the twist of {X} that was defined by the argument {p}. */ Place_t FlipIJ(Place_t p, uint i, uint j); /* Returns {Flip(Flip(p,i), j) == p.flp[i].flp[j]}. */ Place_t Clock(Place_t p); Place_t Flip03(Place_t p); Place_t Flip30(Place_t p); /* "Double orientation flip". In D&L terms, reverses both orientation and spin of the edge pair {p.pair}. Exchanges {p.orig} with {p.dest}, but with reversed twists. Exchanges {p.hith} with {p.yond}, but with reversed twists. Preserves {p.edge}, but with reversed flow and spin. Preserves {p.wall}, but with reversed flux and curl. Equivalent to {Flip0(Flip3(p)) = p.flp[0].flp[3]}, and also to {Flip3(Flip0(p)) = p.flp[3].flp[0]}. Note that {Clock(Clock(p)) = p}. */ Place_t NextF(Place_t p); Place_t Flip32(Place_t p); /* "Next wall". In D&L terms, rotates {p.pair} one step arount {p.edge}, in its spin sense. Replaces {p.wall} by the next wall around {p.edge}, in {p.edge}'s spin sense. Replaces {p.cell} by the next cell in that sense, namely {p.yond}. Preserves {p.edge} and {p.node}. Equivalent to {Flip2(Flip3(p)) = p.flp[3].flp[2]}. */ Place_t PrevF(Place_t p); Place_t Flip23(Place_t p); /* "Previous wall". Inverse of {NextF}. Equivalent to {Flip3(Flip2(p)) = p.flp[2].flp[3]}. */ Place_t NextE(Place_t p); Place_t Flip01(Place_t p); /* "Next edge". In D&L terms, rotates {p.pair} one step arount {p.wall}, in its orientation sense. Replaces {p.edge} by the next edge around {p.wall}, in {p.wall}'s curl sense. Replaces {p.node} by the next vertex in that sense, namely {p.dest}. Preserves {p.wall} and {p.cell}, including orientations. Equivalent to {Flip1(Flip0(p)) = p.flp[0].flp[1]}. */ Place_t PrevE(Place_t p); Place_t Flip10(Place_t p); /* "Previous edge". Inverse of {NextE}. Equivalent to {Flip0(Flip1(p)) = p.flp[1].flp[0]}. */ Place_t SymVF(Place_t p); Place_t Flip02(Place_t p); Place_t Flip20(Place_t p); /* "Symmetric node and wall". In D&L terms, rotates {p.pair} by half a turn around the link that connects {p*.orig} and the centroid of {p.edge}. Reverses the flow and spin of {p.edge}. Replaces {p.node} by the opposite node, {p.dest}, with reversed twist. Replaces {p.wall} by the opposite wall, {p.back}, with reversed curl. Preserves {p.cell} and its twist. Equivalent to {Flip0(Flip2(p)) = p.flp[2].flp[0]} and also to {Flip2(Flip0(p)) = p.flp[0].flp[2]}. Note that {SymNF(SymNF(p)) = p}. */ Place_t SymEC(Place_t p); Place_t Flip31(Place_t p); Place_t Flip13(Place_t p); /* "Symmetric edge and cell". In D&L terms, rotates {p.pair} by half a turn around the link that connects {p.orig} with the centroid of {p*.edge}. Reverses the curl and flux of {p.wall}. Replaces {p.cell} by the opposite cell, {p.yond}, with reversed twist. Replaces {p.edge} by the opposite edge, {p.fork}, with reversed spin. Preserves {p.node} and its twist. Equivalent to {Flip3(Flip1(p)) = p.flp[1].flp[3]} and also to {Flip1(Flip3(p)) = p.flp[3].flp[1]}. Note that {SymEC(SymEC(p)) = p}. */ Place_t ONext(Place_t p); Place_t Flip21(Place_t p); /* "Next edge around the origin". In D&L terms, rotates {p.pair} around the link that connects {p.orig} to {p*.orig}, in the sense of the midpoint of {p*.edge} to the midpoint of {p.edge}, until the next wall-edge pair. In terms of the quad-edge structure, replace {p.edge} by the next edge on the boundary of {p.cell} that flows out of {p.orig}, turning around {p.orig} in the positive sense as seen from inside {p.cell}. Preserves {p.node} and {p.cell}, with their twists. Replaces {p.wall} by the opposite face {p.back}, with reversed spin. Replaces {p.edge} by {p.flp[2].fork}. Equivalent to {Flip1(Flip2(p)) = p.flp[2].flp[1]}. */ Place_t OPrev(Place_t p); Place_t Flip12(Place_t p); /* "Previous edge around the origin". The inverse of {ONext}. Equivalent to {Flip2(Flip1(p)) = p.flp[1].flp[2]}. */ Place_t NextEK(Place_t p, int k); /* Returns {NextE^k(p)}. If {k} is negative, returns {PrevE^(-k)(p)}. */ Place_t NextFK(Place_t p, int k); /* Returns {NextF^k(p)}. If {k} is negative, returns {PrevF^(-k)(p)}. */ /* FLIP-DUAL OPERATORS */ Place_t Srot(Place_t p); /* "D&L pair rotation". In D&L's terms, exchanges the two components of {p.pair}, and then reverses the spin of {p.edge} (i.e. the flow of {p*.edge}). Equivalent to {Spin(Dual(p)) = p*.flp[3] = p.flp[0]*}. Observe that {Srot(Srot(p)) = Clock(p)}. */ Place_t Tors(Place_t p); /* "D&L reverse pair rotation". The inverse of {Srot}. Equivalent to {Dual(Spin(p)) = p.flp[3]* = p*.flp[0] = Spin(Clock(Dual(p))).}. Observe that {Tors(p) = Srot(Srot(Srot(p)))}. */ /* TUPLES OF PLACES */ typedef struct TwoPlaces_t { Place_t p[2]; } TwoPlaces_t; typedef struct FourPlaces_t { Place_t p[4]; } FourPlaces_t; typedef struct SixPlaces_t { Place_t p[6]; } SixPlaces_t; typedef struct EightPlaces_t { Place_t p[8]; } EightPlaces_t; typedef struct TwelvePlaces_t { Place_t p[12]; } TwelvePlaces_t; typedef struct TwentyPlaces_t { Place_t p[8]; } TwentyPlaces_t; typedef struct FiveByTwoPlaces_t { Place_t p[5][2]; } FiveByTwoPlaces_t; typedef struct TwelveByFivePlaces_t { Place_t p[12][5]; } TwelveByFivePlaces_t; /* Fixed-length tuples of places. */ vec_typedef(TwoPlaces_vec_t,TwoPlaces_vec,TwoPlaces_t); vec_typedef(FourPlaces_vec_t,FourPlaces_vec,FourPlaces_t); vec_typedef(SixPlaces_vec_t,SixPlaces_vec,SixPlaces_t); /* Arbitrary-length vectors of fixed-length tuples of places. */ /* ENUMERATION TOOLS */ typedef Place_t (*StepFunc_t)(Place_t p); /* A function from places to places. */ typedef bool_t (*VisitFunc_t)(Place_t p); /* A client-provided place visitation procedure. */ /* PLACE HASHING */ uint PHash(Place_t p); /* A hash function that maps places to pseudo-random unsigned integers. */ /* DISTINCTION AXIOMS In a proper facet-edge structure, one has {s.flp[i] != s} for any {s} and {i}. Also {s.flp[i].flp[j] != s} for any {i,j} such that {|i-j| >= 2}. The chips {s} and {t = s.flp[i]} specify the same sequence of elements of {M} except possibly for the element of dimension {i}; that is, {t.elm[j] == s.elm[j]} for all {j != i}. In a proper facet-edge structure, the the local orientations of {X} implied by {s} and {t} *always disagree* when compared across the shared wall of type {0..3}\{i}. */ #endif