home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume10 / cbw / part01 / pqueue.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-06-16  |  1.6 KB  |  76 lines
  1. /*
  2.  * Priority queue.
  3.  *
  4.  * Bob Baldwin, February, 1985.
  5.  */
  6.  
  7. #include    <stdio.h>
  8. #include    "pqueue.h"
  9.  
  10.  
  11.  
  12. /* Initialize a pqueue header with the given parameters.
  13.  */
  14. pque_init(pque_hdr, max_score, pque_tab, pque_size)
  15. pqueue_hdr    *pque_hdr;
  16. float        max_score;
  17. pqueue_ent    *pque_tab;
  18. int            pque_size;
  19. {
  20.     pque_hdr->next_index = 0;
  21.     pque_hdr->pque_size = pque_size;
  22.     pque_hdr->max_score = max_score;
  23.     pque_hdr->pque_tab = pque_tab;
  24. }
  25.  
  26.  
  27. /* Return TRUE if the pqueue cannot hold another entry.
  28.  */
  29. int    pque_full(pque_hdr)
  30. pqueue_hdr    *pque_hdr;
  31. {
  32.     return (pque_hdr->next_index >= pque_hdr->pque_size);
  33. }
  34.  
  35.  
  36. /* Add an entry to the priority queue.  Sorted lowest score first.
  37.  * The queue header indicates the next free slot, the maximum
  38.  * score (all scores in queue < max), and the size of the table.
  39.  * If the pqueue is full the lowest scoring entry will be
  40.  * thrown out.
  41.  *
  42.  * Implementation:  Find the first slot before sizelast+1 that
  43.  * has a size less than the size arg.  Shuffle down the list
  44.  * to create a hole and insert the new entry.
  45.  */
  46. pque_add(pque_hdr, score, value1, value2)
  47. pqueue_hdr    *pque_hdr;
  48. float        score;
  49. int            value1;
  50. int            value2;
  51. {
  52.     int            k;        /* Slot where new entry will go. */
  53.     int            i;
  54.     pqueue_ent    *pque;
  55.     pqueue_ent    new_ent;
  56.  
  57.     if (score >= pque_hdr->max_score)  return;
  58.  
  59.     new_ent.score = score;
  60.     new_ent.value1 = value1;
  61.     new_ent.value2 = value2;
  62.     pque = pque_hdr->pque_tab;
  63.  
  64.     for (k = 0 ; k < pque_hdr->next_index ; k++)  {
  65.         if (pque[k].score > score)  break;
  66.         }
  67.  
  68.     for (i = pque_hdr->next_index ; i > k ; i--)  {
  69.         pque[i] = pque[i-1];
  70.         }
  71.     if (pque_hdr->next_index < pque_hdr->pque_size)
  72.         pque_hdr->next_index++;
  73.  
  74.     pque[k] = new_ent;
  75. }
  76.