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)6 int 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)26 int 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)42 int 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)58 int PQempty(void)
59 {
60     return (PQcount == 0);
61 }
62 
63 
PQ_min(void)64 struct 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)77 struct 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)88 int 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