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 }