1 #include <stdlib.h> 2 #include <grass/gis.h> 3 #include "sw_defs.h" 4 5 PQinsert(struct Halfedge * he,struct Site * v,double offset)6int PQinsert(struct Halfedge *he, struct Site *v, double offset) 7 { 8 struct Halfedge *last, *next; 9 10 he->vertex = v; 11 ref(v); 12 he->ystar = v->coord.y + offset; 13 last = &PQhash[PQbucket(he)]; 14 while ((next = last->PQnext) != (struct Halfedge *)NULL && 15 (he->ystar > next->ystar || 16 (he->ystar == next->ystar && v->coord.x > next->vertex->coord.x))) 17 { 18 last = next; 19 } 20 he->PQnext = last->PQnext; 21 last->PQnext = he; 22 PQcount++; 23 return 0; 24 } 25 PQdelete(struct Halfedge * he)26int PQdelete(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) 33 last = last->PQnext; 34 last->PQnext = he->PQnext; 35 PQcount--; 36 deref(he->vertex); 37 he->vertex = (struct Site *)NULL; 38 } 39 return 0; 40 } 41 PQbucket(struct Halfedge * he)42int PQbucket(struct Halfedge *he) 43 { 44 int bucket; 45 46 bucket = (he->ystar - ymin) / deltay * PQhashsize; 47 if (bucket < 0) 48 bucket = 0; 49 if (bucket >= PQhashsize) 50 bucket = PQhashsize - 1; 51 if (bucket < PQmin) 52 PQmin = bucket; 53 return (bucket); 54 } 55 56 57 PQempty(void)58int PQempty(void) 59 { 60 return (PQcount == 0); 61 } 62 63 PQ_min(void)64struct Point PQ_min(void) 65 { 66 struct Point answer; 67 68 while (PQhash[PQmin].PQnext == (struct Halfedge *)NULL) { 69 PQmin++; 70 } 71 answer.x = PQhash[PQmin].PQnext->vertex->coord.x; 72 answer.y = PQhash[PQmin].PQnext->ystar; 73 answer.z = PQhash[PQmin].PQnext->vertex->coord.z; 74 return (answer); 75 } 76 PQextractmin(void)77struct Halfedge *PQextractmin(void) 78 { 79 struct Halfedge *curr; 80 81 curr = PQhash[PQmin].PQnext; 82 PQhash[PQmin].PQnext = curr->PQnext; 83 PQcount--; 84 return (curr); 85 } 86 87 PQinitialize(void)88int PQinitialize(void) 89 { 90 int i; 91 92 PQcount = 0; 93 PQmin = 0; 94 PQhashsize = 4 * sqrt_nsites; 95 PQhash = (struct Halfedge *)G_malloc(PQhashsize * sizeof(struct Halfedge)); 96 for (i = 0; i < PQhashsize; i++) 97 PQhash[i].PQnext = (struct Halfedge *)NULL; 98 99 return 0; 100 } 101