/****************************************************************************\

  Copyright 1995 The University of North Carolina at Chapel Hill.
  All Rights Reserved.

  Permission to use, copy, modify and distribute this software and its
  documentation for educational, research and non-profit purposes,
  without fee, and without a written agreement is hereby granted,
  provided that the above copyright notice and the following three
  paragraphs appear in all copies.

  IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE
  LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR
  CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE
  USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY
  OF NORTH CAROLINA HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
  DAMAGES.


  Permission to use, copy, modify and distribute this software and its
  documentation for educational, research and non-profit purposes,
  without fee, and without a written agreement is hereby granted,
  provided that the above copyright notice and the following three
  paragraphs appear in all copies.

  THE UNIVERSITY OF NORTH CAROLINA SPECIFICALLY DISCLAIM ANY
  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE
  PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
  NORTH CAROLINA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT,
  UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

  The authors may be contacted via:

  US Mail:  Jonathan Cohen                      Amitabh Varshney
            Department of Computer Science      Department of Computer Science 
            Sitterson Hall, CB #3175            State University of New York
            University of N. Carolina           Stony Brook, NY 11794-4400, USA 
            Chapel Hill, NC 27599-3175
	    
  Phone:    (919)962-1749                       Phone: (516)632-8446 
	    
  EMail:    cohenj@cs.unc.edu                   varshney@cs.sunysb.edu

\****************************************************************************/
/*****************************************************************************\
  removal_queue.c
  --
  Description : Functions for managaing the vertex removal queue, which
                contains the id's of vertices which still need to be
		processed.

  ----------------------------------------------------------------------------
  $Source: /cvs/RenderPark/SE/Simplify/removal_queue.c,v $
  $Revision: 1.1.1.1 $
  $Date: 2000/04/06 15:35:32 $
  $Author: philippe $
  $Locker:  $
\*****************************************************************************/


/*----------------------------- Local Includes -----------------------------*/

#include <removal_queue.h>
#include <simplify.h>
#include <stdio.h>
#include <stdlib.h>

/*----------------------------- Local Constants -----------------------------*/


/*------------------------------ Local Macros -------------------------------*/


/*------------------------------- Local Types -------------------------------*/


/*------------------------ Local Function Prototypes ------------------------*/


/*------------------------------ Local Globals ------------------------------*/


/*---------------------------------Functions-------------------------------- */


/*****************************************************************************\
 @ removal_queue_init()
 -----------------------------------------------------------------------------
 description : Create a removal queue for a list of <size> elements.
 input       : size is the number of elements to create the queue for.
 output      : The queue is created, empty.
 notes       :
\*****************************************************************************/
void removal_queue_init(RemovalQueue *queue, int size)
{
    int i;
    
    ALLOCN(queue->queue, int, size);
    ALLOCN(queue->in_queue, char, size);
    queue->max_size = size;
    
    for (i=0; i<size; i++)
    {
	queue->in_queue[i] = FALSE;
	queue->queue[i] = -1;
    }
    queue->first = 0;
    queue->last = queue->max_size - 1;
    queue->size = 0;
    return;
} /** End of removal_queue_init() **/

/*****************************************************************************\
 @ removal_queue_destroy()
 -----------------------------------------------------------------------------
 description : Deallocate a removal queue.
 input       : Queue to deallocate
 output      : Queue has been deallocated.
 notes       :
\*****************************************************************************/
void removal_queue_destroy(RemovalQueue *queue)
{
    FREE(queue->in_queue);
    FREE(queue->queue);
    queue->first = queue->last = queue->size = queue->max_size = 0;
    return;
} /** End of removal_queue_destroy() **/

/*****************************************************************************\
 @ removal_queue_extract()
 -----------------------------------------------------------------------------
 description : Pick the first element off the queue.
 input       : Queue to extract element from.
 output      : The id of the first element on the queue, which has now been
               removed from the queue.
 notes       :
\*****************************************************************************/
int removal_queue_extract(RemovalQueue *queue)
{
    int retval;
    
    if (queue->size <= 0)
	return -1;

    retval = queue->queue[queue->first];
    queue->first = (queue->first + 1) % queue->max_size;
    queue->size--;
    queue->in_queue[retval] = FALSE;
    return retval;
} /** End of removal_queue_extract() **/

/*****************************************************************************\
 @ removal_queue_touch()
 -----------------------------------------------------------------------------
 description : Touching a queue element makes sure the element is in the
               queue. If the element was not active in the queue, it is
	       inserted.  Otherwise, nothing happens.
 input       : Removal queue, id of element to touch
 output      : The element is now in the queue.
 notes       :
\*****************************************************************************/
void removal_queue_touch(RemovalQueue *queue, int id)
{
    if ((id < 0) || (id >= queue->max_size))
	return;
    if (queue->in_queue[id] == TRUE)
	return;

    queue->last = (queue->last + 1) % queue->max_size;
    queue->queue[queue->last] = id;
    queue->in_queue[id] = TRUE;
    queue->size++;
} /** End of removal_queue_touch() **/

/*****************************************************************************\
  $Log: removal_queue.c,v $
  Revision 1.1.1.1  2000/04/06 15:35:32  philippe
  Initial CVS release

  Revision 1.4  1997/04/10 20:10:46  cohenj
  Added Amitabh's name to credits

  Revision 1.3  1996/04/08 19:02:01  cohenj
  added procedure comments and copyright

 * Revision 1.2  95/10/16  16:29:41  cohenj
 * fixed bug in initialization of queue->last
 * 
 * Revision 1.1  95/09/29  19:16:01  cohenj
 * Initial revision
 * 
\*****************************************************************************/