319 lines
9.1 KiB
C++
319 lines
9.1 KiB
C++
/*
|
|
** 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 : 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 = new 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
|