Subversion Repositories wimsdev

Rev

Blame | Last modification | View Log | RSS feed

  1.  
  2. /*** HEAP.C ***/
  3.  
  4.  
  5. #include "vdefs.h"
  6.  
  7. int PQmin, PQcount, PQhashsize ;
  8. Halfedge * PQhash ;
  9.  
  10. void
  11. PQinsert(Halfedge * he, Site * v, float offset)
  12.     {
  13.     Halfedge * last, * next ;
  14.  
  15.     he->vertex = v ;
  16.     ref(v) ;
  17.     he->ystar = v->coord.y + offset ;
  18.     last = &PQhash[ PQbucket(he)] ;
  19.     while ((next = last->PQnext) != (Halfedge *)NULL &&
  20.       (he->ystar  > next->ystar  ||
  21.       (he->ystar == next->ystar &&
  22.       v->coord.x > next->vertex->coord.x)))
  23.         {
  24.         last = next ;
  25.         }
  26.     he->PQnext = last->PQnext ;
  27.     last->PQnext = he ;
  28.     PQcount++ ;
  29.     }
  30.  
  31. void
  32. PQdelete(Halfedge * he)
  33.     {
  34.     Halfedge * last;
  35.  
  36.     if(he ->  vertex != (Site *) NULL)
  37.         {
  38.         last = &PQhash[PQbucket(he)] ;
  39.         while (last -> PQnext != he)
  40.             {
  41.             last = last->PQnext ;
  42.             }
  43.         last->PQnext = he->PQnext;
  44.         PQcount-- ;
  45.         deref(he->vertex) ;
  46.         he->vertex = (Site *)NULL ;
  47.         }
  48.     }
  49.  
  50. int
  51. PQbucket(Halfedge * he)
  52.     {
  53.     int bucket ;
  54.  
  55.  
  56.     if      (he->ystar < ymin)  bucket = 0;
  57.     else if (he->ystar >= ymax) bucket = PQhashsize-1;
  58.     else                        bucket = (he->ystar - ymin)/deltay * PQhashsize;
  59.     if (bucket < 0)
  60.         {
  61.         bucket = 0 ;
  62.         }
  63.     if (bucket >= PQhashsize)
  64.         {
  65.         bucket = PQhashsize-1 ;
  66.         }
  67.     if (bucket < PQmin)
  68.         {
  69.         PQmin = bucket ;
  70.         }
  71.     return (bucket);
  72.     }
  73.  
  74. int
  75. PQempty(void)
  76.     {
  77.     return (PQcount == 0) ;
  78.     }
  79.  
  80.  
  81. Point
  82. PQ_min(void)
  83.     {
  84.     Point answer ;
  85.  
  86.     while (PQhash[PQmin].PQnext == (Halfedge *)NULL)
  87.         {
  88.         ++PQmin ;
  89.         }
  90.     answer.x = PQhash[PQmin].PQnext->vertex->coord.x ;
  91.     answer.y = PQhash[PQmin].PQnext->ystar ;
  92.     return (answer) ;
  93.     }
  94.  
  95. Halfedge *
  96. PQextractmin(void)
  97.     {
  98.     Halfedge * curr ;
  99.  
  100.     curr = PQhash[PQmin].PQnext ;
  101.     PQhash[PQmin].PQnext = curr->PQnext ;
  102.     PQcount-- ;
  103.     return (curr) ;
  104.     }
  105.  
  106. void
  107. PQinitialize(void)
  108.     {
  109.     int i ;
  110.  
  111.     PQcount = PQmin = 0 ;
  112.     PQhashsize = 4 * sqrt_nsites ;
  113.     PQhash = (Halfedge *)myalloc(PQhashsize * sizeof *PQhash) ;
  114.     for (i = 0 ; i < PQhashsize; i++)
  115.         {
  116.         PQhash[i].PQnext = (Halfedge *)NULL ;
  117.         }
  118.     }
  119.