Quad tree search queue.cc

From Minor Miracle Software
Revision as of 20:41, 3 July 2016 by Maintenance script (talk)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
// Jesse B. Dooley
// 22 Oct 1996

// Queue.cc

// template Queue class

// The following overloaded operators are
// assumed for the Q data type.
// <  LESS THAN
// >  greater than
// == equals
// << OUTPUT STREAM
// >> input stream
// =  assignment

// v 1.1 16-MAR-2000
// minor changes to eliminate conflicts with stl queue

#ifndef QUEUE_CC
#define QUEUE_CC

#include <iostream.h>  // UNIX

template <class Q> class Queue;

template <class Q> istream& operator >> (istream&, Queue<Q>&);

template <class Q> ostream& operator << (ostream&, Queue<Q>& );

template<class Q> class Queue {

   struct Queuenode {
      Q QueueData;
      Queuenode *next;
   };

   Queuenode *first, *last;

   unsigned long m_ulPopulation;

	friend istream& operator >> (istream &IS , Queue<Q> &A);

	friend ostream& operator << (ostream &OS , Queue<Q> &A );

public:

	Queue()
	{
	   first = NULL;
	   last = NULL;
	   m_ulPopulation = 0;
	}

	~Queue()
	{
	   while (first)
	   {
	      Queuenode *ptr = first;
	      first = first ->next;
	      delete ptr;
	   }
	   first = NULL;
	   last = NULL;
	}

	Queue( const Queue<Q> &P)
	{
	     if( P.first )
	     {
	         erase();
	         first = new Queuenode;
	         first->QueueData = P.first->QueueData;
	         Queuenode *currL = NULL;
	         Queuenode *Pcurr = P.first->next;
	         first->next = currL;
	         while( Pcurr )
	         {
	                currL = new Queuenode;
	                currL->QueueData = Pcurr->QueueData;
	                Pcurr = Pcurr->next;
	                currL = currL->next;
	         }
	     }
	     else
	     {
	         first = last = NULL;
	     }
	     m_ulPopulation = P.m_ulPopulation;
	}

	Queue operator=(const Queue &P )
	{
	     if( P.first )
	     {
	         erase();
	         first = new Queuenode;
	         first->QueueData = P.first->QueueData;
	         Queuenode *currL = NULL;
	         Queuenode *Pcurr = P.first->next;
	         first->next = currL;
	         while( Pcurr )
	         {
	                currL = new Queuenode;
	                currL->QueueData = Pcurr->QueueData;
	                Pcurr = Pcurr->next;
	                currL = currL->next;
	         }
	     }
	     else
	     {
	         first = last = NULL;
	     }
	     m_ulPopulation = P.m_ulPopulation;
	     return *this;
	}

	unsigned long size()
	{
	    return m_ulPopulation;
	}


	Q front()
	{
		Q d; // return empty item
	    if( first == NULL )
	        return d;

	    return first->QueueData;
	} // front( Q &d )

	Q pop() // return item and delete
	{
		Q d;
	    if( first == NULL )
	        return 0;

	    Queuenode *p_qptr = NULL;
	    p_qptr = first;
	    d = first->QueueData;
	    first = first->next;
	    delete p_qptr;

	    if( last == p_qptr )
	        last = NULL;

	    m_ulPopulation--;

	    return d;
	} // pop( Q &d )


	bool push( Q d )
	{
	     Queuenode *newnode = new Queuenode;
	     if( newnode == NULL )
	         return false;

	     newnode->next = NULL;
	     newnode->QueueData = d;

	     if( !last ) // first node in Queue
	     {
	         first = newnode;
	         last = newnode;
	         last->next = newnode;
	         last = newnode;
	     }
	     else
	     {
	         last->next = newnode;
	         last = newnode;
	     }

	     m_ulPopulation++;

	     return true;
	} // enQueue( Q d )


	void erase()
	{
	   while (first)
	   {
	      Queuenode *ptr = first;
	      first = first->next;
	      delete ptr;
	   }
	   first = NULL;
	} // erase()


	bool empty()
	{
	    return (first == NULL);
	} // isempty()

	int resetlast()
	{
	    if( first == NULL )
	        return 1;

	    last = first;
	    while( last->next )
	    {
	           last = last->next;
	    }
	    return 1;
	}
};

template<class Q> istream& operator >> (istream &IS , Queue<Q> &A)
{
     if( IS )
     {
         Q D;
         IS >> D;
         A.enQueue( D );
     }
     return IS;
}

template<class Q> ostream& operator << (ostream &OS , Queue<Q>& A )
{
     if( A.first == NULL )
        return OS;

     A.last = A.first;
     while( A.last )
     {
            OS << A.LAST->QueueData;
            A.last = A.last->next;
     }
     A.resetlast();
     return OS;
}
#endif  // QUEUE_CC