Back to index

wims  3.65+svn20090927
edgelist.c
Go to the documentation of this file.
00001 
00002 /*** EDGELIST.C ***/
00003 
00004 #include "vdefs.h"
00005 
00006 int ELhashsize ;
00007 Site * bottomsite ;
00008 Freelist hfl ;
00009 Halfedge * ELleftend, * ELrightend, **ELhash ;
00010 
00011 int ntry, totalsearch ;
00012 
00013 void
00014 ELinitialize(void)
00015     {
00016     int i ;
00017 
00018     freeinit(&hfl, sizeof(Halfedge)) ;
00019     ELhashsize = 2 * sqrt_nsites ;
00020     ELhash = (Halfedge **)myalloc( sizeof(*ELhash) * ELhashsize) ;
00021     for (i = 0  ; i < ELhashsize  ; i++)
00022         {
00023         ELhash[i] = (Halfedge *)NULL ;
00024         }
00025     ELleftend = HEcreate((Edge *)NULL, 0) ;
00026     ELrightend = HEcreate((Edge *)NULL, 0) ;
00027     ELleftend->ELleft = (Halfedge *)NULL ;
00028     ELleftend->ELright = ELrightend ;
00029     ELrightend->ELleft = ELleftend ;
00030     ELrightend->ELright = (Halfedge *)NULL ;
00031     ELhash[0] = ELleftend ;
00032     ELhash[ELhashsize-1] = ELrightend ;
00033     }
00034 
00035 Halfedge *
00036 HEcreate(Edge * e, int pm)
00037     {
00038     Halfedge * answer ;
00039 
00040     answer = (Halfedge *)getfree(&hfl) ;
00041     answer->ELedge = e ;
00042     answer->ELpm = pm ;
00043     answer->PQnext = (Halfedge *)NULL ;
00044     answer->vertex = (Site *)NULL ;
00045     answer->ELrefcnt = 0 ;
00046     return (answer) ;
00047     }
00048 
00049 void
00050 ELinsert(Halfedge * lb, Halfedge * new)
00051     {
00052     new->ELleft = lb ;
00053     new->ELright = lb->ELright ;
00054     (lb->ELright)->ELleft = new ;
00055     lb->ELright = new ;
00056     }
00057 
00058 /* Get entry from hash table, pruning any deleted nodes */
00059 
00060 Halfedge *
00061 ELgethash(int b)
00062     {
00063     Halfedge * he ;
00064 
00065     if ((b < 0) || (b >= ELhashsize))
00066         {
00067         return ((Halfedge *)NULL) ;
00068         }
00069     he = ELhash[b] ;
00070     if ((he == (Halfedge *)NULL) || (he->ELedge != (Edge *)DELETED))
00071         {
00072         return (he) ;
00073         }
00074     /* Hash table points to deleted half edge.  Patch as necessary. */
00075     ELhash[b] = (Halfedge *)NULL ;
00076     if ((--(he->ELrefcnt)) == 0)
00077         {
00078         makefree((Freenode *)he, (Freelist *)&hfl) ;
00079         }
00080     return ((Halfedge *)NULL) ;
00081     }
00082 
00083 Halfedge *
00084 ELleftbnd(Point * p)
00085     {
00086     int i, bucket ;
00087     Halfedge * he ;
00088 
00089     /* Use hash table to get close to desired halfedge */
00090     bucket = (p->x - xmin) / deltax * ELhashsize ;
00091     if (bucket < 0)
00092         {
00093         bucket = 0 ;
00094         }
00095     if (bucket >= ELhashsize)
00096         {
00097         bucket = ELhashsize - 1 ;
00098         }
00099     he = ELgethash(bucket) ;
00100     if  (he == (Halfedge *)NULL)
00101         {
00102         for (i = 1 ; 1 ; i++)
00103             {
00104             if ((he = ELgethash(bucket-i)) != (Halfedge *)NULL)
00105                 {
00106                 break ;
00107                 }
00108             if ((he = ELgethash(bucket+i)) != (Halfedge *)NULL)
00109                 {
00110                 break ;
00111                 }
00112             }
00113         totalsearch += i ;
00114         }
00115     ntry++ ;
00116     /* Now search linear list of halfedges for the corect one */
00117     if (he == ELleftend || (he != ELrightend && right_of(he,p)))
00118         {
00119         do  {
00120             he = he->ELright ;
00121             } while (he != ELrightend && right_of(he,p)) ;
00122         he = he->ELleft ;
00123         }
00124     else
00125         {
00126         do  {
00127             he = he->ELleft ;
00128             } while (he != ELleftend && !right_of(he,p)) ;
00129         }
00130     /*** Update hash table and reference counts ***/
00131     if ((bucket > 0) && (bucket < ELhashsize-1))
00132         {
00133         if (ELhash[bucket] != (Halfedge *)NULL)
00134             {
00135             (ELhash[bucket]->ELrefcnt)-- ;
00136             }
00137         ELhash[bucket] = he ;
00138         (ELhash[bucket]->ELrefcnt)++ ;
00139         }
00140     return (he) ;
00141     }
00142 
00143 /*** This delete routine can't reclaim node, since pointers from hash
00144  : table may be present.
00145  ***/
00146 
00147 void
00148 ELdelete(Halfedge * he)
00149     {
00150     (he->ELleft)->ELright = he->ELright ;
00151     (he->ELright)->ELleft = he->ELleft ;
00152     he->ELedge = (Edge *)DELETED ;
00153     }
00154 
00155 Halfedge *
00156 ELright(Halfedge * he)
00157     {
00158     return (he->ELright) ;
00159     }
00160 
00161 Halfedge *
00162 ELleft(Halfedge * he)
00163     {
00164     return (he->ELleft) ;
00165     }
00166 
00167 Site *
00168 leftreg(Halfedge * he)
00169     {
00170     if (he->ELedge == (Edge *)NULL)
00171         {
00172         return(bottomsite) ;
00173         }
00174     return (he->ELpm == le ? he->ELedge->reg[le] :
00175         he->ELedge->reg[re]) ;
00176     }
00177 
00178 Site *
00179 rightreg(Halfedge * he)
00180     {
00181     if (he->ELedge == (Edge *)NULL)
00182         {
00183         return(bottomsite) ;
00184         }
00185     return (he->ELpm == le ? he->ELedge->reg[re] :
00186         he->ELedge->reg[le]) ;
00187     }
00188