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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
/*************************************************************************
* Copyright (c) 2011 AT&T Intellectual Property
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/legal/epl-v10.html
*
* Contributors: Details at https://graphviz.org
*************************************************************************/
#include <stdio.h>
#include <util/alloc.h>
/* Priority queue:
* To work, the following have to be defined before this file is
* included:
* - PQTYPE : type of object stored in the queue
* - PQVTYPE : type of priority value
* - N_VAL(pq,n) : macro for (negative) priority value of object n in pq
* - N_IDX(pq,n) : macro for integer index > 0 of n in pq
* - guard, type PQTYPE, with N_VAL(guard) == 0
*
* Priorities are stored as negative numbers, with the item with the least
* negative priority at the head (just after the guard).
*/
#ifdef PQ_TYPES
typedef struct {
PQTYPE* pq;
int PQcnt;
int PQsize;
} PQ;
#endif
#ifdef PQ_CODE
static void
PQgen(PQ* pq, int sz, PQTYPE guard)
{
pq->pq = gv_calloc(sz + 1, sizeof(PQTYPE));
pq->pq[0] = guard;
pq->PQsize = sz;
pq->PQcnt = 0;
}
static void
PQfree(PQ* pq, int freeAll)
{
free (pq->pq);
if (freeAll) free (pq);
}
static void
PQinit(PQ* pq)
{
pq->PQcnt = 0;
}
#ifdef PQCHECK
static int
PQcheck (PQ* pq)
{
int i;
for (i = 1; i <= pq->PQcnt; i++) {
if (N_IDX(pq,pq->pq[i]) != i) {
return 1;
}
}
return 0;
}
#endif
static void
PQupheap(PQ* ppq, int k)
{
PQTYPE* pq = ppq->pq;
PQTYPE x = pq[k];
PQVTYPE v = N_VAL(ppq,x);
int next = k/2;
PQTYPE n;
while (N_VAL(ppq,n = pq[next]) < v) {
pq[k] = n;
N_IDX(ppq,n) = k;
k = next;
next /= 2;
}
pq[k] = x;
N_IDX(ppq,x) = k;
}
static int
PQinsert(PQ* pq, PQTYPE np)
{
if (pq->PQcnt == pq->PQsize) {
agerrorf("Heap overflow\n");
return (1);
}
pq->PQcnt++;
pq->pq[pq->PQcnt] = np;
PQupheap (pq, pq->PQcnt);
#ifdef PQCHECK
PQcheck(pq);
#endif
return 0;
}
static void
PQdownheap (PQ* ppq, int k)
{
PQTYPE* pq = ppq->pq;
PQTYPE x = pq[k];
PQVTYPE v = N_VAL(ppq,x);
int lim = ppq->PQcnt/2;
PQTYPE n;
int j;
while (k <= lim) {
j = k+k;
n = pq[j];
if (j < ppq->PQcnt) {
if (N_VAL(ppq,n) < N_VAL(ppq,pq[j+1])) {
j++;
n = pq[j];
}
}
if (v >= N_VAL(ppq,n)) break;
pq[k] = n;
N_IDX(ppq,n) = k;
k = j;
}
pq[k] = x;
N_IDX(ppq,x) = k;
}
static PQTYPE
PQremove (PQ* pq)
{
PQTYPE n;
if (pq->PQcnt) {
n = pq->pq[1];
pq->pq[1] = pq->pq[pq->PQcnt];
pq->PQcnt--;
if (pq->PQcnt) PQdownheap (pq, 1);
#ifdef PQCHECK
PQcheck(pq);
#endif
return n;
}
else return pq->pq[0];
}
static void
PQupdate (PQ* pq, PQTYPE n, PQVTYPE d)
{
N_VAL(pq,n) = d;
PQupheap (pq, N_IDX(pq,n));
#ifdef PQCHECK
PQcheck(pq);
#endif
}
#if defined(DEBUG) && DEBUG > 1
static void
PQprint (PQ* pq)
{
int i;
PQTYPE n;
fprintf (stderr, "Q: ");
for (i = 1; i <= pq->PQcnt; i++) {
n = pq->pq[i];
fprintf (stderr, "(%d:%f) ", N_IDX(pq,n), N_VAL(pq,n));
}
fprintf (stderr, "\n");
}
#endif
#endif
|
