GeneralsZeroHour/Generals/Code/Libraries/Source/WWVegas/WWLib/binheap.h

/*
**	Command & Conquer Generals(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 : Buccaneer Bay                                                *
 *                                                                                             *
 *                    File name : Binary_Heap.h                                                *
 *                                                                                             *
 *                   Programmer : Mike Lytle                                                   *
 *                                                                                             *
 *                   Start date : 6/25/99                                                      *
 *                                                                                             *
 *                  Last update : 6/25/99                                                      *
 *                                                                                             *
 *---------------------------------------------------------------------------------------------*
 * Functions:                                                                                  *
 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

#ifndef BINARY_HEAP_CLASS_H
#define BINARY_HEAP_CLASS_H

/*=============================================================================================*/
// Includes.
/*=============================================================================================*/
#include <assert.h>
#include "bittype.h"

/*=============================================================================================*/
// Defines.
/*=============================================================================================*/

/*=============================================================================================*/
// Class declarations.
/*=============================================================================================*/
// WARNING!
// Any class used as an element of a heap for BinaryHeapClass must inherit HeapNodeClass.
template <class Key_Type>
class HeapNodeClass
{
	public:

		virtual uint32		Get_Heap_Location (void) const = 0;
		virtual void		Set_Heap_Location (uint32 location) = 0;

		// This is pure virtual so that any type of key can be used as long as it uses the comparison operators.
		virtual Key_Type	Heap_Key (void) const = 0;
		
};

// WARNING!
// To reduce the number of compares, element [0] is a sentinel.  It's key value must be the smallest or NULL.
// Keeps track of pointers to objects.
template <class Key_Type>
class BinaryHeapClass
{
	public:

		// This constructor uses elements that have already been allocated.
		BinaryHeapClass(HeapNodeClass<Key_Type> **allocated_list, unsigned int max_number_of_elements)
		{
			assert(allocated_list);
			assert(max_number_of_elements > 0);

			Elements = allocated_list;
			Max_Number_Of_Elements = max_number_of_elements;
			Number_Of_Elements = 0;
			Own_Array = false;
		}

		// This constructor allocates its own array of nodes
		BinaryHeapClass(unsigned int max_number_of_elements)
			:	Max_Number_Of_Elements (max_number_of_elements),
				Number_Of_Elements (0),
				Elements (NULL),
				Own_Array (false)
		{
			Resize_Array (max_number_of_elements);
		}

		// The destructor simply ensures the array is freed (if needs be)
		~BinaryHeapClass ()
		{
			Release_Array ();
		}

		// Reset all entries in the array to NULL
		void Flush_Array (void)
		{
			::memset (Elements, NULL, sizeof (HeapNodeClass<Key_Type> *) * Max_Number_Of_Elements);
			Number_Of_Elements = 0;
		}
		
		// Reallocate an array large enough to hold the elements
		void Resize_Array (unsigned int new_size)
		{
			// Start fresh
			Release_Array ();
			
			// Reallocate
			Elements						= W3DNEWARRAY HeapNodeClass<Key_Type> *[new_size];
			Max_Number_Of_Elements	= new_size;
			Number_Of_Elements		= 0;
			Own_Array					= true;
			
			// Initialize to NULL
			::memset (Elements, NULL, sizeof (HeapNodeClass<Key_Type> *) * new_size);
			return ;
		}

		void Release_Array (void)
		{
			if (Own_Array) {
				delete [] Elements;
				Elements = NULL;
				Number_Of_Elements = 0;
				Max_Number_Of_Elements = 0;
			}

			Own_Array = false;
			return ;
		}

		// Return the current number of elements.
		unsigned int Get_Number_Of_Elements()
		{
			return (Number_Of_Elements);
		}

		// Return the maximum number of elements.
		unsigned int Get_Max_Number_Of_Elements (void)
		{
			return (Max_Number_Of_Elements);
		}

		// Return a pointer to a node in the tree
		HeapNodeClass<Key_Type> *Peek_Node (unsigned int location)
		{
			return Elements[location];
		}

		// Insert an element into the tree.
		void Insert(HeapNodeClass<Key_Type> *node)
		{

			// Increment the number of elements in the heap.
			unsigned int i = ++Number_Of_Elements;

			// Doesn't handle the case of adding more elements than there is memory for.
			assert(Number_Of_Elements < Max_Number_Of_Elements);

			// Find the elements's place in the tree.  Remember: the smallest element is the root.
			while (Greater_Than(Elements[i / 2], node))
			{
				Elements[i] = Elements[i / 2];
				Elements[i]->Set_Heap_Location(i);
				i /= 2;
			}

			Elements[i] = node;
			Elements[i]->Set_Heap_Location(i);
		}
		
		// Move the element up in the tree if necessary.  Use this if the key value becomes smaller when it is 
		// already in the heap.
		void Percolate_Up(unsigned int location)
		{
			assert(location < Max_Number_Of_Elements);

			unsigned int i = location;
			HeapNodeClass<Key_Type> *node = Elements[i];

			// Find the elements's place in the tree.  Remember: the smallest element is the root.
			while (Greater_Than(Elements[i / 2], node))
			{
				Elements[i] = Elements[i / 2];
				Elements[i]->Set_Heap_Location(i);
				i /= 2;
			}

			Elements[i] = node;
			Elements[i]->Set_Heap_Location(i);
		}

		// Take the smallest element out of the tree and reorder
		HeapNodeClass<Key_Type>* Remove_Min (void)
		{
			unsigned int	child;
			HeapNodeClass<Key_Type>*  	last_element;
			HeapNodeClass<Key_Type>* 	min_element;

			if (Number_Of_Elements == 0) {
				return NULL;
			}

			assert(Number_Of_Elements > 0);
			assert(Elements);

			// The smallest element is always at this position.
			min_element = Elements[1];
			if (min_element != NULL) {
				min_element->Set_Heap_Location (0);
			}

			last_element = Elements[Number_Of_Elements];

			// Decrement the number of elements in the tree.
			Number_Of_Elements--;

			for (unsigned int i = 1; (i * 2) <= Number_Of_Elements; i = child)
			{
				// Find a smaller child.
				child = i * 2;
				if ((child != Number_Of_Elements) && (Less_Than(Elements[child + 1], Elements[child])))
				{
					child++;
				}

				// Percolate down one level.
				if (Greater_Than(last_element, Elements[child]))
				{
					Elements[i] = Elements[child];
					Elements[i]->Set_Heap_Location(i);
				}
				else 
				{
					break;
				}
			}

			Elements[i] = last_element;
			Elements[i]->Set_Heap_Location(i);

			return (min_element);
		}

	private:

		bool	Less_Than(HeapNodeClass<Key_Type> *op1, HeapNodeClass<Key_Type> *op2)
		{
			if (op1 == 0)
			{
				return (true);
			}

			if (op2 == 0)
			{
				return (false);
			}

			return (op1->Heap_Key() < op2->Heap_Key());
		}

		bool	Less_Than_Equal(HeapNodeClass<Key_Type> *op1, HeapNodeClass<Key_Type> *op2)
		{
			if (op1 == 0)
			{
				return (true);
			}

			if (op2 == 0)
			{
				return (false);
			}

			return (op1->Heap_Key() <= op2->Heap_Key());
		}


		bool	Greater_Than(HeapNodeClass<Key_Type> *op1, HeapNodeClass<Key_Type> *op2)
		{
			if (op1 == 0)
			{
				return (false);
			}

			if (op2 == 0)
			{
				return (true);
			}

			return (op1->Heap_Key() > op2->Heap_Key());
		}

	private:

		// The list of elements.
		HeapNodeClass<Key_Type>	**Elements;

		// The number of allocated elements.
		unsigned int					Max_Number_Of_Elements;

		// Current number of elements in the tree.
		unsigned int					Number_Of_Elements;

		// Flag to indicate who owns the memory for the
		// binary tree.
		bool								Own_Array;
};


#endif //BINARY_HEAP_CLASS_H