#ifndef OctfEnum_H #define OctfEnum_H /* Last edited on 2007-02-07 12:18:42 by stolfi */ /* The Facet-Edge data structure for representing the topology of 3D maps. */ #define OctfEnum_H_copyright \ "Copyright © 1998 Universidade Estadual de Campinas (UNICAMP)" #include #define _GNU_SOURCE #include #include #include #include #include /* DATA STRUCTURE ENUMERATION A /place enumeration procedure/, such as all the {EnumXXX} functions below, starts from a given set of /root places/, and locates all places that can be reached from them by a chain of zero or more /steps/, in all possible combinations. Each procedure also /visits/ some of the places found during this process. Visiting a place means passing it to caller for arbitrary processing (see {VISIT-FUNCTIONS} below) and/or saving it in a {Place_vec_t} array provided by the caller (see {VISITATION LISTS} below). An enumeration procedure never visits the same place more than once, but may visit only a proper subset of the places it found --- e.g.only one place on each wall of the map, or only one cell among those that are incident to a given vertex. */ /* STEP-FUNCTIONS Each step of the enumeration consists of following some /step-func/, a function that maps places to places --- such as {Flip1}, {Flip23}, {NextF}, {ONext} etc.. A step-func needs not be one-to-one, and may even take a place in {M} to a place in {M*}, or to a place that is not connected to {p} by any sequence of {flp[i]} and {*} operations. The general enumeration procedures {EnumRing} and {EnumOrbits} use step-funcs provided by the caller. Other {EnumXXX} procedures use hard-wired step-funcs. */ /* VISIT-FUNCTIONS The {EnumXXX} procedures below generally take the address of a /visit-func/ (a {VisitFunc_t} parameter) to process each place found in the enumeration. The visit-func may return TRUE to abort the enumeration, or FALSE to let it continue. Unless noted otherwise, the {EnumXXX} procedure itself will return TRUE iff any visit-func call returned TRUE. (The visit-func should not try to abort the enumeration with a long jump, since doing so will create a storage leak and may even leave the structure in an invalid state.) A {NULL} visit-func is treated as a no-op that always returns {FALSE}. */ /* VISITATION LISTS The {EnumXXX} procedures below generally take a parameter {vP} of type {Place_vec_t*}. If {vP} is not {NULL}, the procedure will append to {vP}, *after* the current elements {vP->e[0..vP->ne-1]}, the places that were visited, in order of visitation. This applies even to virtual visits by a {NULL} visit-func. On the other hand, the procedure does not store in {*vP} any intermediate places that were used to reach the visited places but were not themselves visited. If the enumeration was aborted because a call to the visit-func returned TRUE, then {vP->e[vp->ne-1]} will be the argument of that call. In particular, the caller may pass the address of an empty {place_vec_t}, with {vP->e == NULL} and {vP->ne == 0}. (Note that this is different from passing {vP == NULL}.) The count {vP->ne} is updated to the number of places visited. The storage area {*(vP->e)} is expanded as needed, and trimmed at the end of the enumeration to hold precisely {vP->ne} places. */ /* THREAD-(UN)SAFETY Since the {EnumXXX} procedures modify the facet-edge data structure (by renumbering the places visited), there must never be more than one call to them excuting at any time. In particular, the visit-func shoud not try to call any {EnumXXX} procedure itself. */ /* VIEW-PRESERVING ENUMERATIONS A step-func {stp} is /view-preserving/ if {p.M == p.stp.M} for all {p}. In that case, every place {p} found in the enumeration satisfies {p.M == r.M} for some root place {r}. Thus, if all roots are on the same map, only places on that map will be visited. Of course, the places on the other map can be obtained by applying `{*}' to the visited places. All the wired-in steps used by the {EnumXXX} procedures below are view-preserving. */ /* EVEN AND ODD PATHS A step-func {stp} is /orientation-preserving/ within some submap {N} if no place {p} is oddly connected to {p.stp}, when both {p} and {p.stp} are places on {N}. (Note that this is a weaker requirement than `{p} and {p.stp} are evenly connected for every {p}'.) If {Y} is an orientable connected component of the space {X}, then any enumeration that starts from some root {r} on {Y} and uses only steps that are orientation-preserving within {Y} will only visit places that determine the same orientation on {Y} as {r}. In particular, if a place {p} is visited, then {p.flp[i]} is not visited, for any {i}; and vice-versa. In this case, the places with opposite orientation can be be obtained by applying any {flp} operation to the visited places. On the other hand, if the the starting root {r} lies on a non-orientable connected component {Y} of {X}, then both {p} and {p.flp[i]} may be visited, for some {p} and {i}. Ditto if the given root set contains two places that are oddly-connected to each other. Some of the {EnumXXX} procedures below use only orientation-preserving steps, but some don't. */ /* GLOBAL ENUMERATION */ bool_t EnumPlaces(Place_vec_t root, VisitFunc_t visit, Place_vec_t *vP); /* Enumerates all places that are evenly-connected to the places {root.e[0..root.ne-1]}. */ bool_t EnumElemsEven(Place_vec_t root, uint dimObj, VisitFunc_t visit, Place_vec_t *vP); /* Finds all places which are evenly connected to the {root} places. Among those places, visits exactly one place on every completely oriented map element of dimension {dimObj}. The procedure may visit two distinct places {p}, {q} on the same {dimObj}-dimensional element {e}. In that case {p,q} will be oddly-connected in the whole map, and will not be evenly connected among the places on {e}. This implies that the star of {e} is orientable but the map component containing it isn't, or the root set contains incongruent elements. */ bool_t EnumElemsAny(Place_vec_t root, uint dimObj, VisitFunc_t visit, Place_vec_t *vP); /* Finds all places which are reachable from the {root} places (evenly or not), and visits exactly one place on every map element of dimension {dimObj}. At most one of the places {p} and {p.flp[i]} will be visited, for any {p} and any {i} distinct from {dimObj}. This is true even if the manifold is not orientable and/or there are oddly-connected places among the roots. On the other hand, the visited places may not be evenly reachable from the root. */ /* ENUMERATION OF ELEMENT STARS The following procedures restrict the enumeration to places on a specified set of elements, the /pivots/ of the enumeration. The pivots are the elements of the root places that have a specified dimension {dimPiv}. Thus, a place {p} will be visited only if it is reachable from some root place {r = root[i]}, and has {p.elt[dimPiv] == r.elt[dimPiv]}. If {dimPiv} is 3, for example, the pivots are the cell elements of the root places, and the enumeration will be restricted to places on those cells. If {dimPiv} is 1, the pivots are the nodes of the root places. And so on. */ bool_t EnumPlacesOfElem(Place_vec_t root, uint dimPiv, VisitFunc_t visit, Place_vec_t *vP); /* Visits all places on the pivot elements that are evenly reachable from the root places. */ bool_t EnumIncidencesOfElem(Place_vec_t root, uint dimPiv, uint dimObj, VisitFunc_t visit, Place_vec_t *vP); /* Enumerates all places on each pivot element {e} that are evenly reachable from the root places. It then calls {visit(q)} once for each element {f} of dimension {dimObj} among those places, and for each time that {f} bounds or incides on {e}; where {q} is some place on {e} and {f}. More precisely, the procedure never enumerates two places {p} and {q} if one is reachable from the other by an even number of {flp[j]} steps where {j} is distinct fron {dimPiv} and {dimObj}. However, it may visit both {p} and {q} if the manifold is not orientable or there are two or more oddly-connected roots. */ bool_t EnumElemsOfElemEven(Place_vec_t root, uint dimPiv, uint dimObj, VisitFunc_t visit, Place_vec_t *vP); /* Enumerates all places on each pivot element {e} that are evenly reachable from the root places. It then visits exactly one place {q} on each totally oriented version of each element {f} with dimension {dimObj} that occurs among those places. At most one of the places {p} and {p.flp[i]} will be visited, for any {p} and any {i} distinct from {dimPiv} and {dimObj}. This is true even if the manifold is not orientable and/or there are oddly-connected places among the roots. */ bool_t EnumElemsOfElemAny(Place_vec_t root, uint dimPiv, uint dimObj, VisitFunc_t visit, Place_vec_t *vP); /* Enumerates all places on each pivot element {e} that are reachable (evenly or not) from the root places. It then visits exactly one place {q} on each element {f} with dimension {dimObj} that occurs among those places. At most one of the places {p} and {p.flp[i]} will be visited, for any {p} and any {i} distinct from {dimPiv} and {dimObj}. This is true even if the manifold is not orientable and/or there are oddly-connected places among the roots. */ /* GENERAL ENUMERATION OF PLACE RINGS */ bool_t EnumRing(Place_t p, StepFunc_t step, VisitFunc_t visit, Place_vec_t *vP); /* Enumerates every place {q} reachable from {p} by zero or more calls to {step}, and calls {visit} on each, starting with {p} itself. See {VISITATION FUNCTIONS} above for details. If {vP} is not NULL, the procedure stores into {vP->e[0..vP->ne-1]} the places that were enumerated. See {VISITATION LISTS} above for details. The function {step} must eventually lead back to {p}, otherwise the procedure will loop forever. */ /* GENERAL STRATIFIED ENUMERATION */ bool_t EnumOrbits(Place_vec_t root, uint nS, StepFunc_t step[], VisitFunc_t visit[], Place_vec_t *vP); /* Enumerates all places that can be reached from the `root' places {root.e[0..root.ne-1]} by all possible sequences of calls to the functions {step[0..nS-1]}. For each new place found in the enumeration, including the starting ones, the procedure calls {visit[k](p)}, where {k} is some integer in {0..nS}. The enumeration stops when a call to {visit[k]} returns TRUE, or when all reachable places have been visited. The {EnumOrbits} procedure itself returns TRUE if any {visit} returned TRUE, and FALSE otherwise. If {QP} is not NULL, the procedure will set {*QP} to a descriptor of a newly allocated vector containing all places visited, in order of visitation. (If {QP->e} is not NULL, the procedure calls {free(QP->e)} before overwriting {*QP}). If {visit[k](p)} is called with {k < nS}, then {step[k]} was the last step along the path that led the procedure to {p} from the {root} places. If {k==nS}, it means that the path was empty --- that is, {p} is a {root} place that is not reachable from the earlier ones through {step} chains. The first call to {visit}, in particular, always has {k==nS}. The enumeration is stratified, with {step[i]} having higher enumeration priority than {step[j]} when {0 <= i < j <= nlevels-1}. More precisely: whenever {visit[k](p)} is called, the procedure will have visited every place that is reachable from a previously visited place by chains of steps of level less than {k}. After each call {visit[k](p)}, all places that are still unvisited and are are reachable from {p} through chains of steps with levels less than {k} will be visited next, before the next {visit[j]} call with {j >= k}. In particular, if {step[k]} is one-to-one, for all {k} in {0..nS-1}, then a call {visit[k](p)} means that {p} is the first place in a new orbit of the group generated by {{step[j] : j in 0..k-1 }}. moreover, that entire orbit will be visited next, before any subsequent {visit[j]} with {j>=k}. */ /* DEGREE FUNCTIONS */ uint DegreeOfNode(Place_t p); /* Compute the degree of node that is OrgV(a) (i.e. the number of component Edges incident to node). [!!! Should replace by a more geneeral procedure !!!] */ uint DegreeOfEdge(Place_t p); /* Returns the number of faces incident to the edge of {p}, counting multiple incidences of the same face. More precisely, returns the minimum positive number of {NextF} steps that take {p} to itself. */ uint DegreeOfWall(Place_t p); /* Returns the number of edges bounding the face of {p}, counting multiple incidences on the same edge. More precisely, returns the minimum positive number of {NextE} steps that take {p} to itself. */ #define OctfEnum_H_author \ "This C interface was written jan/2007 by J.Stolfi." #endif