Renegade/Code/wwlib/search.h

/*
**	Command & Conquer Renegade(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/>.
*/

/*********************************************************************************************** 
 ***              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                                            * 
 *                                                                                             * 
 *                     $Archive:: /Commando/Library/SEARCH.H                                  $* 
 *                                                                                             * 
 *                      $Author:: Greg_h                                                      $*
 *                                                                                             * 
 *                     $Modtime:: 7/22/97 11:37a                                              $*
 *                                                                                             * 
 *                    $Revision:: 1                                                           $*
 *                                                                                             *
 *---------------------------------------------------------------------------------------------* 
 * Functions:                                                                                  * 
 *   IndexClass<T>::Add_Index -- Add element to index tracking system.                         *
 *   IndexClass<T>::Clear -- Clear index handler to empty state.                               *
 *   IndexClass<T>::Count -- Fetch the number of index entries recorded.                       *
 *   IndexClass<T>::Fetch_Index -- Fetch data from specified index.                            *
 *   IndexClass<T>::Increase_Table_Size -- Increase the internal index table capacity.         *
 *   IndexClass<T>::IndexClass -- Constructor for index handler.                               *
 *   IndexClass<T>::Invalidate_Archive -- Invalidate the archive pointer.                      *
 *   IndexClass<T>::Is_Archive_Same -- Checks to see if archive pointer is same as index.      *
 *   IndexClass<T>::Is_Present -- Checks for presense of index entry.                          *
 *   IndexClass<T>::Remove_Index -- Find matching index and remove it from system.             *
 *   IndexClass<T>::Search_For_Node -- Perform a search for the specified node ID              *
 *   IndexClass<T>::Set_Archive -- Records the node pointer into the archive.                  *
 *   IndexClass<T>::Sort_Nodes -- Sorts nodes in preparation for a binary search.              *
 *   IndexClass<T>::~IndexClass -- Destructor for index handler object.                        *
 *   compfunc -- Support function for bsearch and bsort.                                       *
 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

#ifndef SEARCH_H
#define SEARCH_H

/*
**	The "bool" integral type was defined by the C++ comittee in
**	November of '94. Until the compiler supports this, use the following
**	definition.
*/
#include	"bool.h"


#if !defined(__BORLANDC__) || !defined(_USERENTRY)
#define	_USERENTRY
#endif

/*
**	This class is used to create and maintain an index. It does this by assigning a unique
**	identifier number to the type objects that it is indexing. The regular binary sort and search
**	function are used for speedy index retrieval. Typical use of this would be to index pointers to
**	normal data objects, but it can be used to hold the data objects themselves. Keep in mind that
**	the data object "T" is copied around by this routine in the internal tables so not only must
**	it have a valid copy constructor, it must also be efficient. The internal algorithm will
**	create an arbitrary number of default constructed objects of type "T". Make sure it has a
**	default constructor that is efficient and trivial. The constructor need not perform any actual
**	initialization since this class has prior knowledge about the legality of these temporary
**	objects and doesn't use them until after the copy constructor is used to initialize them.
**	This means that the default constructed object of type "T" can be technically in an unusable
**	state since it won't ever be used by this routine and won't ever be returned by any of
**	this template's methods.
**
**	This should properly be called a "map container class" since it is a container with a
**	mapping of an identifier with the element in the container.
*/

template<class T>
class IndexClass
{
	public:
		IndexClass(void);
		~IndexClass(void);

		/*
		**	Add element to index table.
		*/
		bool Add_Index(int id, T data);

		/*
		**	Removes an index entry from the index table.
		*/
		bool Remove_Index(int id);

		/*
		**	Check to see if index is present.
		*/
		bool Is_Present(int id) const;

		/*
		**	Fetch number of indexes in the table.
		*/
		int Count(void) const;

		/*
		**	Actually a fetch an index data element from the table.
		*/
		T Fetch_Index(int id) const;

		/*
		**	Clear out the index table to null (empty) state.
		*/
		void Clear(void);

	private:
		/*
		**	This node object is used to keep track of the connection between the data
		**	object and the index identifier number.
		*/
		struct NodeElement {
			int ID;			// ID number (must be first element in this structure).
			T Data;			// Data element assigned to this ID number.
		};

		/*
		**	This is the pointer to the allocated index table. It contains all valid nodes in
		**	a sorted order.
		*/
		NodeElement * IndexTable;

		/*
		**	This records the number of valid nodes within the index table.
		*/
		int IndexCount;

		/*
		**	The total size (in nodes) of the index table is recorded here. If adding a node
		**	would cause the index count to exceed this value, the index table must be resized
		**	to make room.
		*/
		int IndexSize;

		/*
		**	If the index table is sorted and ready for searching, this flag will be true. Sorting
		**	of the table only occurs when absolutely necessary.
		*/
		bool IsSorted;

		/*
		**	This records a pointer to the last element found by the Is_Present() function. Using
		**	this last recorded value can allow quick fetches of data whenever possible.
		*/
		NodeElement const * Archive;

		//-------------------------------------------------------------------------------------
		IndexClass(IndexClass const & rvalue);
		IndexClass * operator = (IndexClass const & rvalue);

		/*
		**	Increase size of internal index table by amount specified.
		*/
		bool Increase_Table_Size(int amount);

		/*
		**	Check if archive pointer is the same as that requested.
		*/
		bool Is_Archive_Same(int id) const;

		/*
		**	Invalidate the archive pointer.
		*/
		void Invalidate_Archive(void);

		/*
		**	Set archive to specified value.
		*/
		void Set_Archive(NodeElement const * node);

		/*
		**	Search for the node in the index table.
		*/
		NodeElement const * Search_For_Node(int id) const;

		static int _USERENTRY search_compfunc(void const * ptr, void const * ptr2);
};


/***********************************************************************************************
 * IndexClass<T>::IndexClass -- Constructor for index handler.                                 *
 *                                                                                             *
 *    This constructs an empty index handler.                                                  *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  none                                                                               *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
IndexClass<T>::IndexClass(void) :
	IndexTable(0),
	IndexCount(0),
	IndexSize(0),
	IsSorted(false),
	Archive(0)
{
	Invalidate_Archive();
}


/***********************************************************************************************
 * IndexClass<T>::~IndexClass -- Destructor for index handler object.                          *
 *                                                                                             *
 *    This will destruct and free any resources managed by this index handler.                 *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  none                                                                               *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
IndexClass<T>::~IndexClass(void)
{
	Clear();
}


/***********************************************************************************************
 * IndexClass<T>::Clear -- Clear index handler to empty state.                                 *
 *                                                                                             *
 *    This routine will free all internal resources and bring the index handler into a         *
 *    known empty state. After this routine, the index handler is free to be reused.           *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  none                                                                               *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
void IndexClass<T>::Clear(void)
{
	delete [] IndexTable;
	IndexTable = 0;
	IndexCount = 0;
	IndexSize = 0;
	IsSorted = false;
	Invalidate_Archive();
}


/***********************************************************************************************
 * IndexClass<T>::Increase_Table_Size -- Increase the internal index table capacity.           *
 *                                                                                             *
 *    This helper function will increase the capacity of the internal index table without      *
 *    performing any alterations to the index data. Use this routine prior to adding a new     *
 *    element if the existing capacity is insufficient.                                        *
 *                                                                                             *
 * INPUT:   amount   -- The number of index element spaces to add to its capacity.             *
 *                                                                                             *
 * OUTPUT:  bool; Was the internal capacity increased without error?                           *
 *                                                                                             *
 * WARNINGS:   If there is insufficient RAM, then this routine will fail.                      *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
bool IndexClass<T>::Increase_Table_Size(int amount)
{
	/*
	**	Check size increase parameter for legality.
	*/
	if (amount < 0) return(false);

	NodeElement * table = new NodeElement[IndexSize + amount];
	if (table != NULL) {

		/*
		**	Copy all valid nodes into the new table.
		*/
		for (int index = 0; index < IndexCount; index++) {
			table[index] = IndexTable[index];
		}

		/*
		**	Make the new table the current one (and delete the old one).
		*/
		delete [] IndexTable;
		IndexTable = table;
		IndexSize += amount;
		Invalidate_Archive();

		/*
		**	Return with success flag.
		*/
		return(true);
	}

	/*
	**	Failure to allocate the memory results in a failure to increase
	**	the size of the index table.
	*/
	return(false);
}


/***********************************************************************************************
 * IndexClass<T>::Count -- Fetch the number of index entries recorded.                         *
 *                                                                                             *
 *    This will return the quantity of index entries that have been recored by this index      *
 *    handler.                                                                                 *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  Returns with number of recored indecies present.                                   *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
int IndexClass<T>::Count(void) const
{
	return(IndexCount);
}


/***********************************************************************************************
 * IndexClass<T>::Is_Present -- Checks for presense of index entry.                            *
 *                                                                                             *
 *    This routine will scan for the specified index entry. If it was found, then 'true' is    *
 *    returned.                                                                                *
 *                                                                                             *
 * INPUT:   id -- The index ID to search for.                                                  *
 *                                                                                             *
 * OUTPUT:  bool; Was the index entry found in this index handler object?                      *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
bool IndexClass<T>::Is_Present(int id) const
{
	/*
	**	If there are no data elements in the index table, then it can
	**	never find the specified index. Check for and return failure
	**	in this case.
	*/
	if (IndexCount == 0) {
		return(false);
	}

	/*
	**	Check to see if this same index element was previously searched for. If
	**	so and it was previously found, then there is no need to search for it
	**	again -- just return true.
	*/
	if (Is_Archive_Same(id)) {
		return(true);
	}

	/*
	**	Perform a binary search on the index nodes in order to look for a
	**	matching index value.
	*/
	NodeElement const * nodeptr = Search_For_Node(id);

	/*
	**	If a matching index was found, then record it for future reference and return success.
	*/
	if (nodeptr != 0) {
		((IndexClass<T> *)this)->Set_Archive(nodeptr);
		return(true);
	}

	/*
	**	Could not find element so return failure condition.
	*/
	return(false);
}


/***********************************************************************************************
 * IndexClass<T>::Fetch_Index -- Fetch data from specified index.                              *
 *                                                                                             *
 *    This routine will find the specified index and return the data value associated with it. *
 *                                                                                             *
 * INPUT:   id -- The index ID to search for.                                                  *
 *                                                                                             *
 * OUTPUT:  Returns with the data value associated with the index value.                       *
 *                                                                                             *
 * WARNINGS:   This routine presumes that the index exists. If it doesn't exist, then the      *
 *             default constructed object "T" is returned instead. To avoid this problem,      *
 *             always verfiy the existance of the index by calling Is_Present() first.         *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
#ifdef __BORLANDC__
#pragma warn -def
#endif
template<class T>
T IndexClass<T>::Fetch_Index(int id) const
{
	if (Is_Present(id)) {

		/*
		**	Count on the fact that the archive pointer is always valid after a call to Is_Present
		**	that returns "true".
		*/
		return(Archive->Data);
	}
	static T x;
	return(x);
}
#ifdef __BORLANDC__
#pragma warn .def
#endif


/***********************************************************************************************
 * IndexClass<T>::Is_Archive_Same -- Checks to see if archive pointer is same as index.        *
 *                                                                                             *
 *    This routine compares the specified index ID with the previously recorded index archive  *
 *    pointer in order to determine if they match.                                             *
 *                                                                                             *
 * INPUT:   id -- The index ID to compare to the archive index object pointer.                 *
 *                                                                                             *
 * OUTPUT:  bool; Does the specified index match the archive pointer?                          *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
bool IndexClass<T>::Is_Archive_Same(int id) const
{
	if (Archive != 0 && Archive->ID == id) {
		return(true);
	}
	return(false);
}


/***********************************************************************************************
 * IndexClass<T>::Invalidate_Archive -- Invalidate the archive pointer.                        *
 *                                                                                             *
 *    This routine will set the archive pointer to an invalid state. This must be performed    *
 *    if ever the archive pointer would become illegal (such as when the element it refers to  *
 *    is deleted).                                                                             *
 *                                                                                             *
 * INPUT:   none                                                                               *
 *                                                                                             *
 * OUTPUT:  none                                                                               *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
void IndexClass<T>::Invalidate_Archive(void)
{
	Archive = 0;
}


/***********************************************************************************************
 * IndexClass<T>::Set_Archive -- Records the node pointer into the archive.                    *
 *                                                                                             *
 *    This routine records the specified node pointer. Use this routine when there is a        *
 *    good chance that the specified node will be requested in the immediate future.           *
 *                                                                                             *
 * INPUT:   node  -- Pointer to the node to assign to the archive.                             *
 *                                                                                             *
 * OUTPUT:  none                                                                               *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
void IndexClass<T>::Set_Archive(NodeElement const * node)
{
	Archive = node;
}


/***********************************************************************************************
 * IndexClass<T>::Add_Index -- Add element to index tracking system.                           *
 *                                                                                             *
 *    This routine will record the index information into this index manager object. It        *
 *    associates the index number with the data specified. The data is copied to an internal   *
 *    storage location.                                                                        *
 *                                                                                             *
 * INPUT:   id    -- The ID number to associate with the data.                                 *
 *                                                                                             *
 *          data  -- The data to store.                                                        *
 *                                                                                             *
 * OUTPUT:  bool; Was the element added without error? Failure indicates that RAM has been     *
 *                exhausted.                                                                   *
 *                                                                                             *
 * WARNINGS:   The data is COPIED to internal storage. This means that the data object must    *
 *             have a functional and efficient copy constructor and assignment operator.       *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
bool IndexClass<T>::Add_Index(int id, T data)
{
	/*
	**	Ensure that there is enough room to add this index. If not, then increase the
	**	capacity of the internal index table.
	*/
	if (IndexCount + 1 > IndexSize) {
		if (!Increase_Table_Size(IndexSize == 0 ? 10 : IndexSize)) {

			/*
			**	Failure to increase the size of the index table means failure to add
			**	the index element.
			*/
			return(false);
		}
	}

	/*
	**	Add the data to the end of the index data and then sort the index table.
	*/
	IndexTable[IndexCount].ID = id;
	IndexTable[IndexCount].Data = data;
	IndexCount++;
	IsSorted = false;

	return(true);
}


/***********************************************************************************************
 * IndexClass<T>::Remove_Index -- Find matching index and remove it from system.               *
 *                                                                                             *
 *    This will scan through the previously added index elements and if a match was found, it  *
 *    will be removed.                                                                         *
 *                                                                                             *
 * INPUT:   id -- The index ID to search for and remove.                                       *
 *                                                                                             *
 * OUTPUT:  bool; Was the index element found and removed?                                     *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
bool IndexClass<T>::Remove_Index(int id)
{
	/*
	**	Find the array index into the table that matches the specified id value.
	*/
	int found_index = -1;
	for (int index = 0; index < IndexCount; index++) {
		if (IndexTable[index].ID == id) {
			found_index = index;
			break;
		}
	}

	/*
	**	If the array index was found, then copy all higher index entries
	**	downward to fill the vacated location. We cannot use memcpy here because the type
	**	object may not support raw copies. C++ defines the assignment operator to deal
	**	with this, so that is what we use.
	*/
	if (found_index != -1) {

		for (int index = found_index+1; index < IndexCount; index++) {
			IndexTable[index-1] = IndexTable[index];
		}
		IndexCount--;

		NodeElement fake;
		fake.ID = 0;
		fake.Data = T();
		IndexTable[IndexCount] = fake;		// zap last (now unused) element

		Invalidate_Archive();
		return(true);
	}

	return(false);
}


/***********************************************************************************************
 * compfunc -- Support function for bsearch and bsort.                                         *
 *                                                                                             *
 *    This compare function presumes that its parameters are pointing to NodeElements and that *
 *    the first "int" in the node is the index ID number to be used for comparison.            *
 *                                                                                             *
 * INPUT:   ptr1  -- Pointer to first node.                                                    *
 *                                                                                             *
 *          ptr2  -- Pointer to second node.                                                   *
 *                                                                                             *
 * OUTPUT:  Returns with the comparision value between the two nodes.                          *
 *                                                                                             *
 * WARNINGS:   This is highly dependant upon the layout of the NodeElement structure.          *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
int _USERENTRY IndexClass<T>::search_compfunc(void const * ptr1, void const * ptr2)
{
	if (*(int const *)ptr1 == *(int const *)ptr2) {
		return(0);
	}
	if (*(int const *)ptr1 < *(int const *)ptr2) {
		return(-1);
	}
	return(1);
}


/***********************************************************************************************
 * IndexClass<T>::Search_For_Node -- Perform a search for the specified node ID                *
 *                                                                                             *
 *    This routine will perform a binary search on the previously recorded index values and    *
 *    if a match was found, it will return a pointer to the NodeElement.                       *
 *                                                                                             *
 * INPUT:   id -- The index ID to search for.                                                  *
 *                                                                                             *
 * OUTPUT:  Returns with a pointer to the NodeElement that matches the index ID specified. If  *
 *          no matching index could be found, then NULL is returned.                           *
 *                                                                                             *
 * WARNINGS:   none                                                                            *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   11/02/1996 JLB : Created.                                                                 *
 *=============================================================================================*/
template<class T>
#ifdef __BORLANDC__
NodeElement const * IndexClass<T>::Search_For_Node(int id) const
#else
IndexClass<T>::NodeElement const * IndexClass<T>::Search_For_Node(int id) const
#endif
{
	/*
	**	If there are no elements in the list, then it certainly can't find any matches.
	*/
	if (IndexCount == 0) {
		return(0);
	}

	/*
	**	If the list has not yet been sorted, then do so now. Binary searching requires
	**	the list to be sorted.
	*/
	if (!IsSorted) {
		qsort(&IndexTable[0], IndexCount, sizeof(IndexTable[0]), search_compfunc);
		((IndexClass<T> *)this)->Invalidate_Archive();
		((IndexClass<T> *)this)->IsSorted = true;
	}

	/*
	**	This list is sorted and ready to perform a binary search upon it.
	*/
	NodeElement node;
	node.ID = id;
	return((NodeElement const *)bsearch(&node, &IndexTable[0], IndexCount, sizeof(IndexTable[0]), search_compfunc));
}


#endif