queue.c

source code to compute the visibility polygon of a point in a polygon.

// list.cc 
//     	Routines to manage a singly linked list of "things".
//	Lists are implemented as templates so that we can store
//	anything on the list in a type-safe manner.
//
// 	A "ListElement" is allocated for each item to be put on the
//	list; it is de-allocated when the item is removed. This means
//      we don't need to keep a "next" pointer in every object we
//      want to put on a list.
// 
//     	NOTE: Mutual exclusion must be provided by the caller.
//  	If you want a synchronized list, you must use the routines 
//	in synchlist.cc.
//
// Copyright (c) 1992-1996 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "queue.h"
#include "input.h"
#include <stdio.h>

//----------------------------------------------------------------------
// QueueElement<T>::QueueElement
// 	Initialize a list element, so it can be added somewhere on a list.
//
//	"itm" is the thing to be put on the list.
//----------------------------------------------------------------------

QueueElement::QueueElement(PGNode * itm)
{
     item = itm;
     next = NULL;	// always initialize to something!
}


//----------------------------------------------------------------------
// Queue<T>::Queue
//	Initialize a list, empty to start with.
//	Elements can now be added to the list.
//----------------------------------------------------------------------

Queue::Queue()
{ 
    first = last = NULL; 
    numInList = 0;
}

//----------------------------------------------------------------------
// Queue::~Queue
//	Prepare a list for deallocation.  
//----------------------------------------------------------------------

Queue::~Queue()
{ 
}

//----------------------------------------------------------------------
// Queue<T>::Append
//      Append an "item" to the end of the list.
//      
//	Allocate a ListElement to keep track of the item.
//      If the list is empty, then this will be the only element.
//	Otherwise, put it at the end.
//
//	"item" is the thing to put on the list.
//----------------------------------------------------------------------

void
Queue::Append(PGNode * item)
{
    QueueElement *element = new QueueElement(item);

    if (IsEmpty()) {		// list is empty
	first = element;
	last = element;
    } else {			// else put it after last
	last->next = element;
	last = element;
    }
    numInList++;
}

//----------------------------------------------------------------------
// Queue<T>::Prepend
//	Same as Append, only put "item" on the front.
//----------------------------------------------------------------------

void
Queue::Prepend(PGNode * item)
{
    QueueElement *element = new QueueElement(item);

    if (IsEmpty()) {		// list is empty
	first = element;
	last = element;
    } else {			// else put it before first
	element->next = first;
	first = element;
    }
    numInList++;
}

//----------------------------------------------------------------------
// List<T>::RemoveFront
//      Remove the first "item" from the front of the list.
//	List must not be empty.
// 
// Returns:
//	The removed item.
//----------------------------------------------------------------------

PGNode * Queue::RemoveFront()
{
    QueueElement *element = first;
    PGNode * thing;


    thing = first->item;
    if (first == last) {	// list had one item, now has none 
        first = NULL;
	last = NULL;
    } else {
        first = element->next;
    }
    numInList--;
    delete element;
    return thing;
}

//----------------------------------------------------------------------
// Queue<T>::Remove
//      Remove a specific item from the list.  Must be in the list!
//----------------------------------------------------------------------

void
Queue::Remove(PGNode * item)
{
    QueueElement *prev, *ptr;
    PGNode * removed;


    // if first item on list is match, then remove from front
    if( first == NULL ) return;
    if (item == first->item) {	
        removed = RemoveFront();
    } else {
	prev = first;
        for (ptr = first->next; ptr != NULL; prev = ptr, ptr = ptr->next) {
            if (item == ptr->item) {
		prev->next = ptr->next;
		if (prev->next == NULL) {
		    last = prev;
		}
		delete ptr;
		numInList--;
		break;
	    }
        }
    }
}

//----------------------------------------------------------------------
// Queue<T>::IsInQueue
//      Return TRUE if the item is in the list.
//----------------------------------------------------------------------

bool
Queue::IsInQueue(PGNode * item) const
{ 
    QueueElement *ptr;

    for (ptr = first; ptr != NULL; ptr = ptr->next) {
        if (item == ptr->item) {
            return TRUE;
        }
    }
    return FALSE;
}


//----------------------------------------------------------------------
// Queue::Apply
//      Apply function to every item on a list.
//
//	"func" -- the function to apply
//----------------------------------------------------------------------

void
Queue::Apply(void (*func)(PGNode *)) const
{ 
    QueueElement *ptr;

    for (ptr = first; ptr != NULL; ptr = ptr->next) {
        (*func)(ptr->item);
    }
}

//----------------------------------------------------------------------
// SortedList::Insert
//      Insert an "item" into a list, so that the list elements are
//	sorted in increasing order.
//      
//	Allocate a ListElement to keep track of the item.
//      If the list is empty, then this will be the only element.
//	Otherwise, walk through the list, one element at a time,
//	to find where the new item should be placed.
//
//	"item" is the thing to put on the list. 
//----------------------------------------------------------------------

void
SortedList::Insert(PGNode * item)
{
    QueueElement *element = new QueueElement(item);
    QueueElement *ptr;		// keep track

    if (IsEmpty()) {			// if list is empty, put at front
        first = element;
        last = element;
    } else if (compare(item, first->item) < 0) {  // item goes at front 
	element->next = first;
	first = element;
    } else {		// look for first elt in list bigger than item
        for (ptr = first; ptr->next != NULL; ptr = ptr->next) {
            if (compare(item, ptr->next->item) < 0) {
		element->next = ptr->next;
	        ptr->next = element;
		numInList++;
		return;
	    }
	}
	last->next = element;		// item goes at end of list
	last = element;
    }
    numInList++;
}

//----------------------------------------------------------------------
// Queue::SanityCheck
//      Test whether this is still a legal list.
//
//	Tests: do I get to last starting from first?
//	       does the list have the right # of elements?
//----------------------------------------------------------------------

void 
Queue::SanityCheck() const
{
    QueueElement *ptr;
    int numFound;

    if (first == NULL) {
    } else if (first == last) {
    } else {
        for (numFound = 1, ptr = first; ptr != last; ptr = ptr->next) {
	    numFound++;
        }
    }
}

//----------------------------------------------------------------------
// SortedList::SanityCheck
//      Test whether this is still a legal sorted list.
//
//	Test: is the list sorted?
//----------------------------------------------------------------------

void 
SortedList::SanityCheck() const
{
    QueueElement *prev, *ptr;

    Queue::SanityCheck();
    if (first != last) {
        for (prev = first, ptr = first->next; ptr != NULL; 
						prev = ptr, ptr = ptr->next) {
        }
    }
}