home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / mac / developm / source / povsrc.sit / SOURCE / PRIOQ.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-03  |  3.9 KB  |  175 lines
  1. /****************************************************************************
  2. *                prioq.c
  3. *
  4. *  This module implements a priority queue using a heap.
  5. *
  6. *  from Persistence of Vision Raytracer 
  7. *  Copyright 1992 Persistence of Vision Team
  8. *---------------------------------------------------------------------------
  9. *  Copying, distribution and legal info is in the file povlegal.doc which
  10. *  should be distributed with this file. If povlegal.doc is not available
  11. *  or for more info please contact:
  12. *
  13. *       Drew Wells [POV-Team Leader] 
  14. *       CIS: 73767,1244  Internet: 73767.1244@compuserve.com
  15. *       Phone: (213) 254-4041
  16. * 
  17. * This program is based on the popular DKB raytracer version 2.12.
  18. * DKBTrace was originally written by David K. Buck.
  19. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  20. *
  21. *****************************************************************************/
  22.  
  23. #include "frame.h"
  24. #include "povproto.h"
  25.  
  26. #define NUMBER_OF_PRIOQS 32
  27. #define NUMBER_OF_INTERSECTIONS 128
  28.  
  29. PRIOQ *prioqs;
  30.  
  31. void pq_init ()
  32. {
  33.    register int i;
  34.    PRIOQ *new_pq;
  35.  
  36.    prioqs = NULL;
  37.  
  38.    for (i = 0 ; i < NUMBER_OF_PRIOQS; i++)
  39.    {
  40.       if ((new_pq = (PRIOQ *) malloc (sizeof (PRIOQ))) == NULL) {
  41.          fprintf (stderr, "\nOut of memory. Cannot allocate queues");
  42.          close_all();
  43.          exit(1);
  44.       }
  45.  
  46.       new_pq -> next_pq = prioqs;
  47.       prioqs = new_pq;
  48.  
  49.       if ((new_pq -> queue = (INTERSECTION *)
  50.          malloc (NUMBER_OF_INTERSECTIONS * sizeof (INTERSECTION))) == NULL) {
  51.          fprintf (stderr, "\nOut of memory. Cannot allocate queue entries");
  52.          close_all();
  53.          exit(1);
  54.       }
  55.    }
  56. }
  57.  
  58. PRIOQ *pq_alloc()
  59. {
  60.    PRIOQ *allocated_queue;
  61.  
  62.    if (prioqs == NULL) {
  63.       fprintf (stderr, "\nOut of prioqs");
  64.       close_all();
  65.       exit(1);
  66.    }
  67.  
  68.    allocated_queue = prioqs;
  69.    prioqs = allocated_queue -> next_pq;
  70.    return (allocated_queue);
  71. }
  72.  
  73. void pq_free (pq)
  74. PRIOQ *pq;
  75. {
  76.    pq -> next_pq = prioqs;
  77.    prioqs = pq;
  78. }
  79.  
  80. PRIOQ *pq_new (index_size)
  81. int index_size;
  82. {
  83.    PRIOQ *pq;
  84.  
  85.    if (index_size >= NUMBER_OF_INTERSECTIONS)    /* Charles Marslett */
  86.       index_size = NUMBER_OF_INTERSECTIONS - 1;    /* Most real scenes overflow! */
  87.  
  88.  
  89.    if ((pq = pq_alloc()) == NULL)
  90.       return (NULL);
  91.  
  92.    pq -> queue_size = index_size;
  93.    pq -> current_entry = 0;
  94.    return (pq);
  95. }
  96.  
  97. void pq_balance(q, entry_pos1)
  98. PRIOQ *q;
  99. unsigned int entry_pos1;
  100. {
  101.    register INTERSECTION *entry1, *entry2;
  102.    INTERSECTION temp_entry;
  103.    register unsigned int entry_pos2;
  104.  
  105.    entry1 = &q->queue[entry_pos1];
  106.  
  107.    if ((entry_pos1 * 2 < q->queue_size)
  108.       && (entry_pos1 * 2 <= q -> current_entry))
  109.    {
  110.       if ((entry_pos1*2+1 > q->current_entry) ||
  111.          (q->queue[entry_pos1*2].Depth < q->queue[entry_pos1*2+1].Depth))
  112.          entry_pos2 = entry_pos1*2;
  113.       else
  114.          entry_pos2 = entry_pos1*2+1;
  115.  
  116.       entry2 = &q->queue[entry_pos2];
  117.  
  118.       if (entry1->Depth > entry2->Depth) {
  119.          temp_entry = *entry1;
  120.          *entry1 = *entry2;
  121.          *entry2 = temp_entry;
  122.          pq_balance (q, entry_pos2);
  123.       }
  124.    }
  125.  
  126.    if (entry_pos1 / 2 >= 1 )
  127.    {
  128.       entry_pos2 = entry_pos1 / 2;
  129.       entry2 = &q->queue[entry_pos2];
  130.       if (entry1->Depth < entry2->Depth) {
  131.          temp_entry = *entry1;
  132.          *entry1 = *entry2;
  133.          *entry2 = temp_entry;
  134.          pq_balance (q, entry_pos2);
  135.       }
  136.    }
  137. }
  138.  
  139. void pq_add (q, queue_entry)
  140. PRIOQ *q;
  141. INTERSECTION *queue_entry;
  142. {
  143.    q -> current_entry++;
  144.    if (q -> current_entry >= q -> queue_size)
  145.       q -> current_entry--;
  146.  
  147.    q -> queue [q -> current_entry] = *queue_entry;
  148.    pq_balance (q, q -> current_entry);
  149. }
  150.  
  151. INTERSECTION *pq_get_highest(q)
  152. PRIOQ *q;
  153. {
  154.    if (q -> current_entry >= 1)
  155.       return (&(q -> queue[1]));
  156.    else
  157.       return (NULL);
  158. }
  159.  
  160. int pq_is_empty(q)
  161. PRIOQ *q;
  162. {
  163.    if (q -> current_entry < 1)
  164.       return (TRUE);
  165.    else
  166.       return (FALSE);
  167. }
  168.  
  169. void pq_delete_highest (q)
  170. PRIOQ *q;
  171. {
  172.    q -> queue[1] = q -> queue[q -> current_entry--];
  173.    pq_balance (q, 1);
  174. }
  175.