Commit | Line | Data |
---|---|---|
2117e02e MW |
1 | #include "alloc.h" |
2 | #include "gen_allocdefs.h" | |
3 | #include "prioq.h" | |
4 | ||
5 | GEN_ALLOC_readyplus(prioq,struct prioq_elt,p,len,a,i,n,x,100,prioq_readyplus) | |
6 | ||
7 | int prioq_insert(pq,pe) | |
8 | prioq *pq; | |
9 | struct prioq_elt *pe; | |
10 | { | |
11 | int i; | |
12 | int j; | |
13 | if (!prioq_readyplus(pq,1)) return 0; | |
14 | j = pq->len++; | |
15 | while (j) | |
16 | { | |
17 | i = (j - 1)/2; | |
18 | if (pq->p[i].dt <= pe->dt) break; | |
19 | pq->p[j] = pq->p[i]; | |
20 | j = i; | |
21 | } | |
22 | pq->p[j] = *pe; | |
23 | return 1; | |
24 | } | |
25 | ||
26 | int prioq_min(pq,pe) | |
27 | prioq *pq; | |
28 | struct prioq_elt *pe; | |
29 | { | |
30 | if (!pq->p) return 0; | |
31 | if (!pq->len) return 0; | |
32 | *pe = pq->p[0]; | |
33 | return 1; | |
34 | } | |
35 | ||
36 | void prioq_delmin(pq) | |
37 | prioq *pq; | |
38 | { | |
39 | int i; | |
40 | int j; | |
41 | int n; | |
42 | if (!pq->p) return; | |
43 | n = pq->len; | |
44 | if (!n) return; | |
45 | i = 0; | |
46 | --n; | |
47 | for (;;) | |
48 | { | |
49 | j = i + i + 2; | |
50 | if (j > n) break; | |
51 | if (pq->p[j - 1].dt <= pq->p[j].dt) --j; | |
52 | if (pq->p[n].dt <= pq->p[j].dt) break; | |
53 | pq->p[i] = pq->p[j]; | |
54 | i = j; | |
55 | } | |
56 | pq->p[i] = pq->p[n]; | |
57 | pq->len = n; | |
58 | } |