home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 2 / LSD and 17bit Compendium Deluxe - Volume II.iso / a / prog / cprog / voronoi.lha / heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-19  |  1.7 KB  |  92 lines
  1. #
  2. #include "defs.h"
  3.  
  4.  
  5. PQinsert(he, v, offset)
  6. struct Halfedge *he;
  7. struct Site *v;
  8. float     offset;
  9. {
  10. struct Halfedge *last, *next;
  11.  
  12. he -> vertex = v;
  13. ref(v);
  14. he -> ystar = v -> coord.y + offset;
  15. last = &PQhash[PQbucket(he)];
  16. while ((next = last -> PQnext) != (struct Halfedge *) NULL &&
  17.       (he -> ystar  > next -> ystar  ||
  18.       (he -> ystar == next -> ystar && v -> coord.x > next->vertex->coord.x)))
  19.     {    last = next;};
  20. he -> PQnext = last -> PQnext; 
  21. last -> PQnext = he;
  22. PQcount += 1;
  23. }
  24.  
  25. PQdelete(he)
  26. struct Halfedge *he;
  27. {
  28. struct Halfedge *last;
  29.  
  30. if(he ->  vertex != (struct Site *) NULL)
  31. {    last = &PQhash[PQbucket(he)];
  32.     while (last -> PQnext != he) last = last -> PQnext;
  33.     last -> PQnext = he -> PQnext;
  34.     PQcount -= 1;
  35.     deref(he -> vertex);
  36.     he -> vertex = (struct Site *) NULL;
  37. };
  38. }
  39.  
  40. int PQbucket(he)
  41. struct Halfedge *he;
  42. {
  43. int bucket;
  44.  
  45. bucket = (he->ystar - ymin)/deltay * PQhashsize;
  46. if (bucket<0) bucket = 0;
  47. if (bucket>=PQhashsize) bucket = PQhashsize-1 ;
  48. if (bucket < PQmin) PQmin = bucket;
  49. return(bucket);
  50. }
  51.  
  52.  
  53.  
  54. int PQempty()
  55. {
  56.     return(PQcount==0);
  57. }
  58.  
  59.  
  60. struct Point PQ_min()
  61. {
  62. struct Point answer;
  63.  
  64.     while(PQhash[PQmin].PQnext == (struct Halfedge *)NULL) {PQmin += 1;};
  65.     answer.x = PQhash[PQmin].PQnext -> vertex -> coord.x;
  66.     answer.y = PQhash[PQmin].PQnext -> ystar;
  67.     return (answer);
  68. }
  69.  
  70. struct Halfedge *PQextractmin()
  71. {
  72. struct Halfedge *curr;
  73.  
  74.     curr = PQhash[PQmin].PQnext;
  75.     PQhash[PQmin].PQnext = curr -> PQnext;
  76.     PQcount -= 1;
  77.     return(curr);
  78. }
  79.  
  80.  
  81. PQinitialize()
  82. {
  83. int i; struct Point *s;
  84.  
  85.     PQcount = 0;
  86.     PQmin = 0;
  87.     PQhashsize = 4 * sqrt_nsites;
  88.     PQhash = (struct Halfedge *) myalloc(PQhashsize * sizeof *PQhash);
  89.     for(i=0; i<PQhashsize; i+=1) PQhash[i].PQnext = (struct Halfedge *)NULL;
  90. }
  91.  
  92.