src/prioq.c


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

#include "prioq.h"

#include "genalloc.h"

GEN_ALLOC_readyplus(prioq, struct prioq_elt, p, len, a, i, n, x, 100, prioq_readyplus);

int prioq_insert(prioq *pq, struct prioq_elt *pe)
{
  int i;
  int j;

  if (!prioq_readyplus(pq, 1)) return 0;
  j = pq->len++;
  while (j) {
    i = (j - 1) / 2;
    if (pq->p[i].dt <= pe->dt) break;
    pq->p[j] = pq->p[i];
    j = i;
  }
  pq->p[j] = *pe;
  return 1;
}

int prioq_min(prioq *pq, struct prioq_elt *pe)
{
  if (!pq->p) return 0;
  if (!pq->len) return 0;
  *pe = pq->p[0];
  return 1;
}

void prioq_delmin(prioq *pq)
{
  int i;
  int j;
  int n;

  if (!pq->p) return;
  n = pq->len;
  if (!n) return;
  i = 0;
  --n;

  for (;;) {
    j = i + i + 2;
    if (j > n) break;
    if (pq->p[j - 1].dt <= pq->p[j].dt) --j;
    if (pq->p[n].dt <= pq->p[j].dt) break;
    pq->p[i] = pq->p[j];
    i = j;
  }
  pq->p[i] = pq->p[n];
  pq->len = n;
}