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