home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume18 / mtvraytrace / part01 / pqueue.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-26  |  1.8 KB  |  114 lines
  1. /***********************************************************************
  2.  * $Author: markv $
  3.  * $Revision: 1.1 $
  4.  * $Date: 88/09/11 11:00:42 $
  5.  * $Log:    pqueue.c,v $
  6.  * Revision 1.1  88/09/11  11:00:42  markv
  7.  * Initial revision
  8.  * 
  9.  ***********************************************************************/
  10.  
  11. #include <stdio.h>
  12. #include <math.h>
  13. #include "defs.h"
  14. #include "extern.h"
  15.  
  16. typedef struct t_qelem {
  17.     Flt    q_key ;
  18.     Object    * q_obj ;
  19. } Qelem ;
  20.  
  21. static int     Qsize ;
  22. static Qelem    Q[PQSIZE] ;
  23.  
  24. PriorityQueueNull()
  25. {
  26.     Qsize = 0 ;
  27.     totalQueueResets ++ ;
  28. #ifdef DEBUG    
  29.     printf("resetting\n") ;
  30. #endif /* DEBUG */
  31. }
  32.  
  33. PriorityQueueEmpty()
  34. {
  35.     return (Qsize == 0) ;
  36. }
  37.  
  38. PriorityQueueInsert(key, obj)
  39.  Flt key ;
  40.  Object * obj ;
  41. {
  42.     int i ; 
  43.     Qelem tmp ;
  44.  
  45.     totalQueues ++ ;
  46. #ifdef DEBUG
  47.     printf("inserting element, key = %g\n", key) ;
  48. #endif
  49.      Qsize ++ ;
  50.     if (Qsize > maxQueueSize)
  51.         maxQueueSize = Qsize ;
  52.     if (Qsize >= PQSIZE) {
  53.         fprintf(stderr, "%s: exhausted priority queue space\n", 
  54.             Progname) ;
  55.         exit(1) ;
  56.     }
  57.     Q[Qsize].q_key = key ;
  58.     Q[Qsize].q_obj = obj ;
  59.  
  60.     i = Qsize ;
  61.     while (i > 1 && Q[i].q_key < Q[i/2].q_key) {
  62.         tmp = Q[i] ;
  63.         Q[i] = Q[i/2] ;
  64.         Q[i/2] = tmp ;
  65.         i = i / 2 ;
  66.     }
  67. }
  68.  
  69. PriorityQueueDelete(key, obj)
  70.  Flt * key ;
  71.  Object ** obj ;
  72. {
  73.     Qelem tmp ;
  74.     int i, j ;
  75.  
  76.     if (Qsize == 0) {
  77.         fprintf(stderr, "%s: priority queue is empty\n",
  78.             Progname) ;
  79.         exit(1) ;
  80.     }
  81.  
  82.     *key = Q[1].q_key ;
  83.     *obj = Q[1].q_obj ;
  84.  
  85. #ifdef DEBUG
  86.     printf("deleting element, key = %g\n", *key) ;
  87. #endif
  88.  
  89.     Q[1] = Q[Qsize] ;
  90.     Qsize -- ;
  91.  
  92.     i = 1 ;
  93.  
  94.     while (2 * i <= Qsize) {
  95.  
  96.         if (2 * i == Qsize) {
  97.             j = 2 * i ;
  98.         } else if (Q[2*i].q_key < Q[2*i+1].q_key) {
  99.             j = 2 * i ;
  100.         } else {
  101.             j = 2 * i + 1 ;
  102.         }
  103.  
  104.         if (Q[i].q_key > Q[j].q_key) {
  105.             tmp = Q[i] ;
  106.             Q[i] = Q[j] ;
  107.             Q[j] = tmp ;
  108.             i = j ;
  109.         } else {
  110.             break ;
  111.         }
  112.     }
  113. }
  114.