Back to index

wims  3.65+svn20090927
heap.c
Go to the documentation of this file.
00001 
00002 /*** HEAP.C ***/
00003 
00004 
00005 #include "vdefs.h"
00006 
00007 int PQmin, PQcount, PQhashsize ;
00008 Halfedge * PQhash ;
00009 
00010 void
00011 PQinsert(Halfedge * he, Site * v, float offset)
00012     {
00013     Halfedge * last, * next ;
00014 
00015     he->vertex = v ;
00016     ref(v) ;
00017     he->ystar = v->coord.y + offset ;
00018     last = &PQhash[ PQbucket(he)] ;
00019     while ((next = last->PQnext) != (Halfedge *)NULL &&
00020       (he->ystar  > next->ystar  ||
00021       (he->ystar == next->ystar &&
00022       v->coord.x > next->vertex->coord.x)))
00023         {
00024         last = next ;
00025         }
00026     he->PQnext = last->PQnext ;
00027     last->PQnext = he ;
00028     PQcount++ ;
00029     }
00030 
00031 void
00032 PQdelete(Halfedge * he)
00033     {
00034     Halfedge * last;
00035 
00036     if(he ->  vertex != (Site *) NULL)
00037         {
00038         last = &PQhash[PQbucket(he)] ;
00039         while (last -> PQnext != he)
00040             {
00041             last = last->PQnext ;
00042             }
00043         last->PQnext = he->PQnext;
00044         PQcount-- ;
00045         deref(he->vertex) ;
00046         he->vertex = (Site *)NULL ;
00047         }
00048     }
00049 
00050 int
00051 PQbucket(Halfedge * he)
00052     {
00053     int bucket ;
00054 
00055 
00056     if     (he->ystar < ymin)  bucket = 0;
00057     else if (he->ystar >= ymax) bucket = PQhashsize-1;
00058     else                    bucket = (he->ystar - ymin)/deltay * PQhashsize;
00059     if (bucket < 0)
00060         {
00061         bucket = 0 ;
00062         }
00063     if (bucket >= PQhashsize)
00064         {
00065         bucket = PQhashsize-1 ;
00066         }
00067     if (bucket < PQmin)
00068         {
00069         PQmin = bucket ;
00070         }
00071     return (bucket);
00072     }
00073 
00074 int
00075 PQempty(void)
00076     {
00077     return (PQcount == 0) ;
00078     }
00079 
00080 
00081 Point
00082 PQ_min(void)
00083     {
00084     Point answer ;
00085 
00086     while (PQhash[PQmin].PQnext == (Halfedge *)NULL)
00087         {
00088         ++PQmin ;
00089         }
00090     answer.x = PQhash[PQmin].PQnext->vertex->coord.x ;
00091     answer.y = PQhash[PQmin].PQnext->ystar ;
00092     return (answer) ;
00093     }
00094 
00095 Halfedge *
00096 PQextractmin(void)
00097     {
00098     Halfedge * curr ;
00099 
00100     curr = PQhash[PQmin].PQnext ;
00101     PQhash[PQmin].PQnext = curr->PQnext ;
00102     PQcount-- ;
00103     return (curr) ;
00104     }
00105 
00106 void
00107 PQinitialize(void)
00108     {
00109     int i ;
00110 
00111     PQcount = PQmin = 0 ;
00112     PQhashsize = 4 * sqrt_nsites ;
00113     PQhash = (Halfedge *)myalloc(PQhashsize * sizeof *PQhash) ;
00114     for (i = 0 ; i < PQhashsize; i++)
00115         {
00116         PQhash[i].PQnext = (Halfedge *)NULL ;
00117         }
00118     }