/* See {OctfData.h} */ #include /* Last edited on 2007-01-25 10:05:07 by stolfi */ #include #include #include #include Edge_t MakeEdge(void) { Edge_t e = (Edge_t)notnull(malloc(sizeof(EdgeRec_t)), "no mem"); e->marks2[0] = FALSE; e->marks2[1] = FALSE; return e; } Wall_t MakeWall(void) { Wall_t e = (Wall_t)notnull(malloc(sizeof(WallRec_t)), "no mem"); e->marks2[0] = FALSE; e->marks2[1] = FALSE; return e; } #define INIT_STACK_SIZE 1024 Edge_vec_t RenumberEdges(Place_vec_t *pv) { /* [!!! ???] Note: I change the SpinBit by DualBit for purpouses of gluing octahedra. */ Edge_vec_t estack = Edge_vec_new(INIT_STACK_SIZE); Place_vec_t pstack = Place_vec_new(INIT_STACK_SIZE); uint top = 0; /* top for stack "estack" */ uint nstack = 0; /* top for stack "pstack" */ auto void VisitAndMark(Place_t t); /* If {t} is unmarked: visit, mark, and stack it. */ void VisitAndMark(Place_t t) { Wedge_t w = PWedge(t); if ((w->ind < nstack) && (PWedge(pstack.el[w->ind]) == w)) { /* Wedge of {t} is already marked, not do nothing */ } else { /* Wedge of {t} is not marked. */ Edge_t e = PWedge(t)->edge; if (! e->marks2[DualBit(t)]) { /* Edge {e} is not marked; mark it and all edges of places adjacents to {t} */ Place_t tn = t; do { Edge_t en = PWedge(tn)->edge; en->marks2[DualBit(tn)] = TRUE; tn = NextF(tn); } while (tn != t); /* Save the edge {e} in {estack}: */ Edge_vec_expand(&estack,top);; estack.el[top] = e; /* Make {t} its entry place: */ e->pa = t; e->num = top; top++; } Place_vec_expand(&pstack,nstack); w->ind = nstack; pstack.el[nstack] = t; nstack++; } } uint seen = 0; /* Number of wedges whose childeren were looked at */ /* Stack the root places: */ int i; for (i = 0; i < pv->nel; i++) { VisitAndMark (pv->el[i]); } /* Enumerate edges, number them, collect in {estack}: */ while (seen < nstack) { Place_t s = pstack.el[seen]; VisitAndMark(NextF(s)); VisitAndMark(NextF(PrevE(s))); VisitAndMark(NextE(s)); VisitAndMark(PrevF(s)); seen++; } /* Erase all marks */ while (nstack > 0) { nstack--; Place_t b = pstack.el[nstack]; Place_t atn = b; do { PWedge(atn)->edge->marks2[DualBit(atn)] = FALSE; atn= NextF(atn); } while (atn != b); } /* Reclaim {pstack}, trim {estack}, and return it: */ Place_vec_trim(&pstack,0); Edge_vec_trim(&estack,top); return estack; } Wall_vec_t RenumberWalls(Place_vec_t *pv) { Wall_vec_t estack = Wall_vec_new(INIT_STACK_SIZE); Place_vec_t pstack = Place_vec_new(INIT_STACK_SIZE); uint top = 0; /* top for stack "estack" */ uint nstack = 0; /* top for stack "pstack" */ auto void VisitAndMark(Place_t t); /* If {t} is unmarked: visit, mark, and stack it. */ void VisitAndMark(Place_t t) { Wedge_t w = PWedge(t); if ((w->ind < nstack) && (PWedge(pstack.el[w->ind]) == w)) { /* Wedge of {t} is already marked, not do nothing */ } else { /* Wedge of {t} is not marked. */ Wall_t e = PWedge(t)->wall; /* if component wall of @place "t" not are marked, then */ if (! e->marks2[DualBit(t)]) { /* Wall {e} is not marked; mark it and all walls of places adjacents to {t} */ Place_t tn = t; do { Wall_t en = PWedge(tn)->wall; en->marks2[DualBit(tn)] = TRUE; tn = PrevE(tn); } while (tn != t); /* Save the wall {e} in {estack}: */ Wall_vec_expand(&estack,top); estack.el[top] = e; /* Make {t} its entry place: */ estack.el[top]->pa = t; e->num = top; top++; } Place_vec_expand(&pstack,nstack); w->ind = nstack; pstack.el[nstack] = t; nstack++; } } uint seen = 0; /* Number of wedges whose childeren were looked at */ int i; for (i = 0; i < pv->nel; i++) { VisitAndMark (pv->el[i]); } /* Enumerate walls, number them, collect in {estack}: */ while (seen < nstack) { Place_t s = pstack.el[seen]; VisitAndMark(NextF(s)); VisitAndMark(NextF(PrevE(s))); VisitAndMark(NextE(s)); VisitAndMark(PrevF(s)); seen++; } /* Erase all marks */ while (nstack > 0) { nstack--; Place_t b = pstack.el[nstack]; Place_t atn = b; do { PWedge(atn)->wall->marks2[DualBit(atn)] = FALSE; atn= PrevE(atn); } while (atn != b); } /* Reclaim {pstack}, trim {estack}, and return it: */ Place_vec_trim(&pstack,0); Wall_vec_trim(&estack,top); return estack; } Place_vec_t RenumberEdgesOutOfNodes(Place_vec_t *pv) { Place_vec_t estack = Place_vec_new(20); Place_vec_t pstack = Place_vec_new(20); uint top = 0; /* top for stack "estack" */ uint nstack = 0; /* top for stack "nstack" */ uint seen = 0; /* Wedges already seen. */ auto void VisitAndMark(Place_t t); /* If t is unmarked: visit, mark, and stack it. */ void VisitAndMark(Place_t t) { Wedge_t w = PWedge(t); if ((w->ind < nstack) && (PWedge(pstack.el[w->ind]) == w)) { /* wedge is already marked, do nothing */ } else { if (! w->marks2[DualBit(t)]) { /* mark PWedge(t)->edge and of all places with same edge as {t}. */ Place_t tn = t; do { PWedge(tn)->marks2[DualBit(tn)] = TRUE; tn = NextF(tn); } while (tn != t); /* Assign {w} a new serial number: */ w->edge->dg = top; /* Add {t} to the list {estack}: */ Place_vec_expand(&estack,top);; estack.el[top] = t; top++; } /* Add {t} to {pstack}: */ Place_vec_expand(&pstack,nstack); w->ind = nstack; pstack.el[nstack] = t; nstack++; } } /* Stack the root pointers: */ int i; for (i = 0; i < pv->nel; i++) { VisitAndMark(pv->el[i]); } /* Enumerate reachable places: */ while (seen < nstack) { Place_t s = pstack.el[seen]; if (DualBit(s) == 0) { VisitAndMark(Onext(s)); VisitAndMark(Onext(NextF(s))); } else { VisitAndMark(Clock(Onext(s))); VisitAndMark(Clock(Onext(NextF(s)))); } seen++; } /* Erase all marks */ while (nstack > 0) { nstack--; Place_t b = pstack.el[nstack]; Place_t atn = b; do { PWedge(atn)->marks2[DualBit(atn)] = FALSE; atn = NextF(atn); } while (atn != b); } /* Reclaim {pstack}, trim {estack} and return it: */ Place_vec_trim(&pstack,0); Place_vec_trim(&estack,top); return estack; }