RedAlert/CODE/QUEUE.H

/*
**	Command & Conquer Red Alert(tm)
**	Copyright 2025 Electronic Arts Inc.
**
**	This program is free software: you can redistribute it and/or modify
**	it under the terms of the GNU General Public License as published by
**	the Free Software Foundation, either version 3 of the License, or
**	(at your option) any later version.
**
**	This program 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 General Public License for more details.
**
**	You should have received a copy of the GNU General Public License
**	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

/* $Header: /CounterStrike/QUEUE.H 1     3/03/97 10:25a Joe_bostic $ */
/***********************************************************************************************
 ***              C O N F I D E N T I A L  ---  W E S T W O O D  S T U D I O S               ***
 ***********************************************************************************************
 *                                                                                             *
 *                 Project Name : Command & Conquer                                            *
 *                                                                                             *
 *                    File Name : QUEUE.H                                                      *
 *                                                                                             *
 *                   Programmer : Joe L. Bostic                                                *
 *                                                                                             *
 *                   Start Date : 12/08/94                                                     *
 *                                                                                             *
 *                  Last Update : December 9, 1994 [JLB]                                       *
 *                                                                                             *
 *---------------------------------------------------------------------------------------------*
 * Functions:                                                                                  *
 *   QueueClass<T,size>::Add -- Add object to queue.                                           *
 *   QueueClass<T,size>::First -- Fetches reference to first object in list.                   *
 *   QueueClass<T,size>::Init -- Initializes queue to empty state.                             *
 *   QueueClass<T,size>::Next -- Throws out the head of the line.                              *
 *   QueueClass<T,size>::operator[] -- Fetches reference to sub object in queue.               *
 *   QueueClass<T,size>::QueueClass -- Default constructor for QueueClass objects.             *
 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

#ifndef QUEUE_H
#define QUEUE_H

#include	"mission.h"
#include	"target.h"
#include	"defines.h"

#pragma warn -inl

/*
**	This class implements a classic FIFO queue (also known as - standing in line). Objects
**	are added to the end (tail) of the line. Objects are removed from the start (first) of
**	the line. A keyboard buffer is a good example of a common computer use of a queue. There
**	is no provision for "taking cuts" or leaving the line once an object has been added.
**
**	The implementation uses a circular list of objects. This allows adding and deleting of
**	elements without any maintenance moves of remaining objects that would otherwise be
**	necessary in a simple array storage method. A side effect of this means that accessing the
**	internal array directly is not allowed. Supporting functions are provided for this purpose.
**
**	WARNING WARNING WARNING WARNING!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
**	The size parameter MUST be an exact power of two (2, 4, 8, 16, etc.) otherwise the internal
**	indexing algorithm will fail.
*/
template<class T, int size>
class QueueClass
{
	public:
		/*
		**	This is the count of the number of objects in the queue. If this count is zero,
		**	then the operator[], First(), and Next() functions are undefined. Check this
		**	value BEFORE calling these functions.
		*/
		const int Count;

		//-------------- Functions --------------------
		QueueClass(void);						// Default constructor.

		/*
		**	The bracket subscript operator functions similarly to the way a normal subscript
		**	operator works except that entry [0] matches the first-in-line and entry
		**	[Count-1] matches the last-in-line. This is ensured regardless of the actual position
		**	of the object in the circular internal list.
		*/
		T & operator[](int);

		/*
		**	This function will return a reference to the "head of the line" object.
		*/
		T & First(void);

		/*
		**	This function clears the list of objects.
		*/
		void Init(void);

		/*
		**	This function discards the head-of-the-line object and advances all the remaining
		**	objects up by one. Mnemonic: Imagine a broadway audition and the director yells
		**	"NEXT!"
		*/
		int Next(void);

		/*
		**	This will add an object to the tail of the line. If there is no more room to add
		**	the object, then false will be returned.
		*/
		int Add(T const &);

		int Get_Head(void);
		int Get_Tail(void);
		T * Get_Array(void);

	private:
		int Head;								// Index of element in list the longest.
		int Tail;								// Index where next new addition will go.

		T Array[size];							// Raw array of objects.
};


/***********************************************************************************************
 * QueueClass<T,size>::QueueClass -- Default constructor for QueueClass objects.               *
 *                                                                                             *
 *    This default constructor for QueueClass objects initializes the queue to an empty        *
 *    state.                                                                                   *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  none                                                                               *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   12/09/1994 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T, int size>
inline QueueClass<T,size>::QueueClass(void) : Count(0)
{
	Init();
}


/***********************************************************************************************
 * QueueClass<T,size>::Init -- Initializes queue to empty state.                               *
 *                                                                                             *
 *    This function resets the queue to an empty state.                                        *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  none                                                                               *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   12/09/1994 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T, int size>
inline void QueueClass<T,size>::Init(void)
{
	((int &)Count) = 0;
	Head = 0;
	Tail = 0;
}


/***********************************************************************************************
 * QueueClass<T,size>::Add -- Add object to queue.                                             *
 *                                                                                             *
 *    This function is used to add an object to the tail of the line. If the queue cannot      *
 *    accept any more entries, then the object won't be added and false will be returned.      *
 *                                                                                             *
 * INPUT:   object   -- The object that is to be added to the queue.                           *
 *                                                                                             *
 * OUTPUT:  bool; Was the object added successfully?                                           *
 *                                                                                             *
 * WARNINGS:   If the queue is full, then the object won't be added. Be sure to check for this.*
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   12/09/1994 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T, int size>
inline int QueueClass<T,size>::Add(T const &q)
{
	if (Count < size) {
		Array[Tail] = q;
		Tail = (Tail + 1) & (size-1);
		((int &)Count) = Count + 1;
		return(true);
	}
	return (false);
}


/***********************************************************************************************
 * QueueClass<T,size>::Next -- Throws out the head of the line.                                *
 *                                                                                             *
 *    This routine is used to discard the object at the head of the line. All remaining        *
 *    objects "move up" one. No actual movement occurs, merely the index is adjusted, but      *
 *    the affect is that the next oldest object in the queue will now be returned with the     *
 *    next call to the First() function.                                                       *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  Returns the number of object remaining in the queue.                               *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   12/09/1994 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T, int size>
inline int QueueClass<T,size>::Next(void)
{
	if (Count) {
		Head = (Head + 1) & (size-1);
		((int &)Count) = Count - 1;
	}
	return (Count);
}


/***********************************************************************************************
 * QueueClass<T,size>::operator[] -- Fetches reference to sub object in queue.                 *
 *                                                                                             *
 *    Use this routine to examine individual objects within the queue. The oldest object in    *
 *    the queue is referenced by an index value of zero. The newest object in the queue is     *
 *    referenced by a value of Count-1. If there are no objects in the queue, then this        *
 *    operator is undefined. Although this operator allows examination of the queue, there is  *
 *    no corresponding ability to insert or delete objects from the middle of the queue.       *
 *                                                                                             *
 * INPUT:   index -- The index into the queue of objects. Valid values range from zero to      *
 *                   Count-1. All other values return an undefined reference!                  *
 *                                                                                             *
 * OUTPUT:  Returns with a reference to the object indicated by the index.                     *
 *                                                                                             *
 * WARNINGS:   Check to make sure that Count is not zero before using this operator. Failure   *
 *             to do so will return a reference to an undefined object.                        *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   12/09/1994 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T, int size>
inline T & QueueClass<T,size>::operator[](int index)
{
	return Array[(Head + index) & (size-1)];
}


/***********************************************************************************************
 * QueueClass<T,size>::First -- Fetches reference to first object in list.                     *
 *                                                                                             *
 *    This routine is used to fetch the first object in the list (head of the line). This      *
 *    object is the oldest in the list. Typical use of this function is to get and process     *
 *    the first object so that it may be discarded with the Next() function in order to bring  *
 *    subsequent objects to the first position.                                                *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  Returns with a reference to the oldest object in the queue.                        *
 *                                                                                             *
 * WARNINGS:   If there are no objects in the queue, then this function returns an undefined   *
 *             reference. Be sure to check Count against zero before calling this function.    *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   12/09/1994 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T, int size>
inline T & QueueClass<T,size>::First(void)
{
	return Array[Head];
}

template<class T, int size>
inline int QueueClass<T,size>::Get_Head(void)
{
	return Head;
}

template<class T, int size>
inline int QueueClass<T,size>::Get_Tail(void)
{
	return Tail;
}

template<class T, int size>
inline T * QueueClass<T,size>::Get_Array(void)
{
	return Array;
}

#endif