/***************************************************************************
  This is part of the evolver toolkit for exploring genetic progamming.
  Copyright (C) 1996 Benjamin Bennett and Yeasah G. Pell

  This library is free software; you can redistribute it and/or modify
  it under the terms of the GNU Library General Public License as
  published by the Free Software Foundation; either version 2 of the
  License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Library General Public License for more details.

  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

  Contact information: Benjamin Bennett<fiji@limey.net> and Yeasah
    G. Pell<yeasah@wpi.edu>
  *************************************************************************/

#ifndef __QUEUE_H
#define __QUEUE_H

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#include "object.H"

template<class T> class GQueue;

/// Template queue node class to handle pointers to objects
/*@Doc: This class implements a node in a fifo (first in first out)
  queue that handles pointers to objects.  {\bf Note:} This class does
  not free up the stored object when its destructor is called.  It is
  necessary to call {\tt DeleteQueueNode()} in order to clean the
  stored data. */
template<class T>
class GQueueNode : public GObject
{
	/// A pointer to the data stored in the class
	T *data;
	/// A pointer to the next node in the chain
	GQueueNode<T> *next;
public:
	/// Constructor that takes a pointer to the data being stored in the node
	GQueueNode(T *d)
	{
		data = d;
		next = NULL;
	}

	/// Destructor that just frees up the chain of nodes
	~GQueueNode()
	{
		delete next;		// free the next in the chain
	}

	/// Set the next pointer
	void SetNext(GQueueNode<T> *n)
	{
		next = n;
	}

	/// Return the data held by the node
	T *GetData()
	{
		return data;
	}

	/// Get the next node in the chain
	GQueueNode<T> *GetNext()
	{
		return next;
	}

	/// Calls delete on all of the data stored in the queue
	void DeleteQueueNode()
	{
		delete data;
		data = NULL;			// prevent a segfault from a second deletion
		if (next != NULL)
			next->DeleteQueueNode();
	}
	
	/// This allows the copy operator to ``look'' inside the class
	friend class GQueue<T>;		// for operator=
};

/// A generic queue class to handle pointers to objects
/*@Doc: This class implements a fifo (first in first out) queue that
  handles pointers to objects.  {\bf Note:} This class does not free
  up the stored objects when its destructor is called.  It is
  necessary to call {\tt DeleteQueue()} in order to clean the
  queue out. */
template<class T>
class GQueue : public GObject
{
	/// The number of nodes in the queue
	int size;
	/// The head of the queue
	GQueueNode<T> *head;
	/// The tail of the queue
	GQueueNode<T> *tail;

public:
	/// 
	GQueue();
	/// Remeber this does not free the stored data, only the queue storage
	~GQueue();

	/// Assignment operator to allow queues to be copied
	GQueue &operator=(GQueue &x);

	/// Adds a node to the end of the queue
	void Add(T *data);

	/// Pops the node from the head of the queue
	T *Pop();	

	/// Returns the current queue size
	int GetSize();

	/// Calls delete on all of the data nodes in the queue
	void DeleteQueue();
};

/*===================== TEMPLATE CODE DEFINITONS =========================*/
/**************THIS CAN NOT BE IN A .C FILE, IT MUST BE HERE***************/

// constructor
template<class T>
GQueue<T>::GQueue()
{
	// start with nothing
	size = 0;

	head = NULL;
	tail = head;
}

// destructor
template<class T>
GQueue<T>::~GQueue()
{
	delete head;
}

// assignment operator
template<class T>
GQueue<T> &GQueue<T>::operator=(GQueue<T> &x)
{
	GQueueNode<T> *ptr = x.head;
	T *temp;

	delete head;
	size = 0;
	
	while(ptr != NULL)
	{
		temp = new T(*(ptr->data));
		Add(temp);
		ptr = ptr->next;
	}

	return *this;
}	

// adds a node to the end of the queue
template<class T>
void GQueue<T>::Add(T *data)
{
	GQueueNode<T> *tmp = new GQueueNode<T>(data);
	if (head != NULL && tail != NULL)
		tail->SetNext(tmp);
	else
		head = tmp;
	
	tail = tmp;
	size += 1;
}

// pops the node from the head of the queue
template<class T>
T *GQueue<T>::Pop()
{
	GQueueNode<T> *tmp;
	T *retval;

	if (head != NULL)
	{
		retval = head->GetData();
		tmp = head;
		
		head = head->GetNext();
		tmp->SetNext(NULL);
		delete tmp;
		size -= 1;

		return retval;
	}

	return NULL;		
}

template<class T>
int GQueue<T>::GetSize()
{
	return size;
}

template<class T>
void GQueue<T>::DeleteQueue()
{
	if (head != NULL)
		head->DeleteQueueNode();
	delete head;
	head = NULL;
	size = 0;
}

#endif __QUEUE_H