//-----------------------------------------------------------------------------
//
//  $Logfile:: /game/queue.h                                                  $
// $Revision:: 2                                                              $
//   $Author:: Burgermac                                                      $
//     $Date:: 12/27/00 6:42 PM                                               $
//
// Copyright (C) 1997 by Ritual Entertainment, Inc.
// All rights reserved.
//
// This source is may not be distributed and/or modified without
// expressly written permission by Ritual Entertainment, Inc.
//
// DESCRIPTION:
// Generic Queue object
//

#ifndef __QUEUE_H__
#define __QUEUE_H__

#include "class.h"

class QueueNode
{
public:
	void*       data;
	QueueNode* next;

	QueueNode();
};

inline QueueNode::QueueNode()
{
	data = NULL;
	next = NULL;
}

class Queue
{
private:
	QueueNode* head;
	QueueNode* tail;

public:
	Queue();
	~Queue();
	void        Clear( void );
	qboolean Empty( void );
	void        Enqueue( void* data );
	void*       Dequeue( void );
	void     Remove( void* data );
	qboolean Inqueue( void* data );
};

inline Queue::Queue()
{
	head = NULL;
	tail = NULL;
}

inline Queue::~Queue()
{
	Clear();
}

inline void Queue::Clear( void )
{
	while( !Empty() )
	{
		Dequeue();
	}
}

inline qboolean Queue::Empty( void )
{
	if( head == NULL )
	{
		assert( !tail );

		return true;
	}

	assert( tail );

	return false;
}

inline void Queue::Enqueue( void* data )
{
	QueueNode* tmp;

	tmp = new QueueNode;
	if( !tmp )
	{
		assert( 0 );

		gi.error( "Queue::Enqueue : Out of memory" );
	}

	tmp->data = data;

	assert( !tmp->next );

	if( !head )
	{
		assert( !tail );
		head = tmp;
	}
	else
	{
		assert( tail );
		tail->next = tmp;
	}
	tail = tmp;
}

inline void* Queue::Dequeue( void )
{
	void* ptr;
	QueueNode* node;

	if( !head )
	{
		assert( !tail );
		return NULL;
	}

	node = head;
	ptr = node->data;

	head = node->next;
	if( head == NULL )
	{
		assert( tail == node );
		tail = NULL;
	}

	delete node;

	return ptr;
}

inline void Queue::Remove( void* data )
{
	QueueNode* node;
	QueueNode* prev;

	if( !head )
	{
		assert( !tail );

		gi.dprintf( "Queue::Remove : Data not found in queue\n" );
		return;
	}

	for( prev = NULL, node = head; node != NULL; prev = node, node = node->next )
	{
		if( node->data == data )
		{
			break;
		}
	}

	if( !node )
	{
		gi.dprintf( "Queue::Remove : Data not found in queue\n" );
	}
	else
	{
		if( !prev )
		{
			// at head
			assert( node == head );
			head = node->next;
			if( head == NULL )
			{
				assert( tail == node );
				tail = NULL;
			}
		}
		else
		{
			prev->next = node->next;
			if( prev->next == NULL )
			{
				// at tail
				assert( tail == node );
				tail = prev;
			}
		}

		delete node;
	}
}

inline qboolean Queue::Inqueue( void* data )
{
	QueueNode* node;

	for( node = head; node != NULL; node = node->next )
	{
		if( node->data == data )
		{
			return true;
		}
	}

	return false;
}

#endif /* queue.h */
