home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / rayce27s / queue.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-02  |  2.2 KB  |  104 lines
  1. /*
  2.  * queue.c -- the implements a simple depth queue, needed for CSG and
  3.  * clips. Up to now, I no one has ever explained me how to do prioqs, so
  4.  * I've put this together myself.
  5.  * 
  6.  * (c) Han-Wen Nienhuys 1993, <hanwen@stack.urc.tue.nl>
  7.  * 
  8.  * This program is free software; you can redistribute it and/or modify it
  9.  * under; the terms of the GNU General Public License as published by the
  10.  * Free Software Foundation;
  11.  * 
  12.  * This program is distributed in the hope that it will be useful, but
  13.  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15.  * General Public License for more details.
  16.  * 
  17.  * You should have received a copy of the GNU General Public License along
  18.  * with this program; if not, write to the Free Software Foundation, Inc.,
  19.  * 675 Mass Ave, Cambridge, MA 02139, USA.
  20.  */
  21.  
  22. #include "ray.h"
  23. #include "proto.h"
  24. #include "extern.h"
  25.  
  26. /*
  27.  * insert an intersection into the queue. This is kept sorted by insertion
  28.  * sort
  29.  */
  30.  
  31. PUBLIC void
  32. add_to_queue(dqueue * root, dqueue q)
  33. {
  34.     dqueue         *p,
  35.                    *new,
  36.                    *last;
  37.  
  38.  
  39.     assert(root != NULL);
  40.  
  41.  
  42.     for (p = root; p != NULL && q.t >= p->t; p = p->next)
  43.     last = p;
  44.  
  45.     if (p == NULL) {        /* we're at the tail of the queue */
  46.     p = last->next = get_new_queue();
  47.     *p = q;
  48.     p->next = NULL;
  49.     } else {            /* insert entry before p. */
  50.  
  51.     /*
  52.      * actually, we're moving the info of p to a new node, and copy
  53.      * intersection i into p->i
  54.      */
  55.     new = get_new_queue();
  56.     *new = *p;
  57.     new->next = p->next;
  58.     *p = q;
  59.     p->next = new;
  60.     }
  61. }
  62.  
  63. PUBLIC dqueue  *
  64. get_new_queue(void)
  65. {
  66.     dqueue         *p;
  67.  
  68.     p = ALLOC(dqueue);
  69.  
  70.     CHECK_MEM(p, "queue entry");
  71.  
  72.     p->obj = p->obj2 = NULL;
  73.     p->t = INFTY;
  74.     p->next = NULL;
  75.     p->entering = FALSE;
  76.  
  77.     return p;
  78. }
  79.  
  80. PUBLIC void
  81. free_queue(dqueue * root)
  82. {
  83.     dqueue         *p,
  84.                    *next;
  85.  
  86.     for (p = root; p != NULL; p = next) {
  87.     next = p->next;
  88.     free((void *) p);
  89.     }
  90. }
  91.  
  92. PUBLIC void
  93. print_queue(dqueue * root)
  94. {
  95. #ifdef DEBUG
  96.     printf("\nQUEUE\n");
  97.     for (; root != NULL; root = root->next) {
  98.     printf("param t %lf, entering %d\n", root->t, root->entering);
  99.     if (root->obj != NULL)
  100.         print_object(root->obj);
  101.     }
  102. #endif
  103. }
  104.