568 lines
15 KiB
C++
568 lines
15 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 : LevelEdit *
|
|
* *
|
|
* $Archive:: /Commando/Code/wwlib/ntree.h $*
|
|
* *
|
|
* Author:: Patrick Smith *
|
|
* *
|
|
* $Modtime:: 4/18/00 7:02p $*
|
|
* *
|
|
* $Revision:: 3 $*
|
|
* *
|
|
*---------------------------------------------------------------------------------------------*
|
|
* Functions: *
|
|
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
|
|
|
|
|
#if defined(_MSC_VER)
|
|
#pragma once
|
|
#endif
|
|
|
|
#ifndef __NTREE_H
|
|
#define __NTREE_H
|
|
|
|
|
|
#include "refcount.h"
|
|
#include "wwstring.h"
|
|
|
|
|
|
//////////////////////////////////////////////////////////////////////////
|
|
// Forward declarations
|
|
//////////////////////////////////////////////////////////////////////////
|
|
template<class T> class NTreeLeafClass;
|
|
template<class T> class SortedNTreeLeafClass;
|
|
|
|
|
|
//////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// NTreeClass
|
|
//
|
|
//////////////////////////////////////////////////////////////////////////
|
|
template<class T>
|
|
class NTreeClass
|
|
{
|
|
public:
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Public constructors/destructors
|
|
//////////////////////////////////////////////////////////////
|
|
NTreeClass (void)
|
|
: m_Root (NULL) { }
|
|
virtual ~NTreeClass (void) { Reset (); }
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Public methods
|
|
//////////////////////////////////////////////////////////////
|
|
virtual NTreeLeafClass<T> * Add (const T &value);
|
|
|
|
NTreeLeafClass<T> * Peek_Root (void) { return m_Root; }
|
|
virtual void Reset (void);
|
|
|
|
protected:
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Protected methods
|
|
//////////////////////////////////////////////////////////////
|
|
virtual NTreeLeafClass<T> * Allocate_Leaf (void) { return new NTreeLeafClass<T>; }
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Protected member data
|
|
//////////////////////////////////////////////////////////////
|
|
NTreeLeafClass<T> * m_Root;
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Add
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
NTreeLeafClass<T> *NTreeClass<T>::Add (const T &value)
|
|
{
|
|
NTreeLeafClass<T> *retval = NULL;
|
|
|
|
if (m_Root == NULL) {
|
|
|
|
//
|
|
// Allocate a new root node
|
|
//
|
|
m_Root = Allocate_Leaf ();
|
|
m_Root->Set_Value (value);
|
|
retval = m_Root;
|
|
|
|
} else {
|
|
|
|
//
|
|
// Simply add this value to list
|
|
//
|
|
retval = m_Root->Add (value);
|
|
}
|
|
|
|
return retval;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Reset
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
void NTreeClass<T>::Reset (void)
|
|
{
|
|
if (m_Root != NULL) {
|
|
|
|
//
|
|
// Find the last leaf in the root
|
|
//
|
|
NTreeLeafClass<T> *end_leaf = m_Root;
|
|
while (end_leaf->Peek_Next () != NULL) {
|
|
end_leaf = end_leaf->Peek_Next ();
|
|
}
|
|
|
|
//
|
|
// Remove all the top-level leaves from the tree.
|
|
// Note: We work backwards from last root-leaf so each
|
|
// leaf along the way is guarenteed to have at least 1
|
|
// reference count on it.
|
|
//
|
|
for (NTreeLeafClass<T> *leaf = end_leaf; leaf != NULL; ) {
|
|
NTreeLeafClass<T> *curr_leaf = leaf;
|
|
leaf = leaf->Peek_Prev ();
|
|
|
|
//
|
|
// Remove this leaf
|
|
//
|
|
curr_leaf->Remove ();
|
|
}
|
|
|
|
REF_PTR_RELEASE (m_Root);
|
|
}
|
|
return ;
|
|
}
|
|
|
|
|
|
|
|
//////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// SortedNTreeClass
|
|
//
|
|
//////////////////////////////////////////////////////////////////////////
|
|
template<class T>
|
|
class SortedNTreeClass : public NTreeClass<T>
|
|
{
|
|
public:
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Public constructors/destructors
|
|
//////////////////////////////////////////////////////////////
|
|
SortedNTreeClass (void) { }
|
|
virtual ~SortedNTreeClass (void) { }
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Public methods
|
|
//////////////////////////////////////////////////////////////
|
|
SortedNTreeLeafClass<T> * Add_Sorted (const T &value, const char *name);
|
|
|
|
protected:
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Protected methods
|
|
//////////////////////////////////////////////////////////////
|
|
NTreeLeafClass<T> * Allocate_Leaf (void) { return new SortedNTreeLeafClass<T>; }
|
|
};
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Add_Sorted
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
SortedNTreeLeafClass<T> *SortedNTreeClass<T>::Add_Sorted (const T &value, const char *name)
|
|
{
|
|
SortedNTreeLeafClass<T> *retval = NULL;
|
|
|
|
if (m_Root == NULL) {
|
|
|
|
//
|
|
// Allocate a new root node
|
|
//
|
|
m_Root = Allocate_Leaf ();
|
|
|
|
retval = (SortedNTreeLeafClass<T> *)m_Root;
|
|
retval->Set_Value (value);
|
|
retval->Set_Name (name);
|
|
|
|
} else {
|
|
|
|
//
|
|
// Simply add this value to list
|
|
//
|
|
retval = ((SortedNTreeLeafClass<T> *)m_Root)->Add_Sorted (value, name);
|
|
|
|
//
|
|
// Make sure our 'root' pointer is the first one in the list
|
|
//
|
|
NTreeLeafClass<T> *prev = m_Root->Peek_Prev ();
|
|
if (prev != NULL) {
|
|
REF_PTR_SET (m_Root, prev);
|
|
}
|
|
}
|
|
|
|
return retval;
|
|
}
|
|
|
|
|
|
//////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// NTreeLeafClass
|
|
//
|
|
//////////////////////////////////////////////////////////////////////////
|
|
template<class T>
|
|
class NTreeLeafClass : public RefCountClass
|
|
{
|
|
public:
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Public constructors/destructors
|
|
//////////////////////////////////////////////////////////////
|
|
NTreeLeafClass (void)
|
|
: m_Parent (NULL),
|
|
m_Child (NULL),
|
|
m_PrevSibling (NULL),
|
|
m_NextSibling (NULL) { }
|
|
|
|
virtual ~NTreeLeafClass (void);
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Public methods
|
|
//////////////////////////////////////////////////////////////
|
|
|
|
//
|
|
// Tree management
|
|
//
|
|
virtual NTreeLeafClass<T> * Add_Child (const T &value);
|
|
virtual NTreeLeafClass<T> * Add (const T &value);
|
|
virtual void Remove (void);
|
|
|
|
//
|
|
// Value accessors
|
|
//
|
|
virtual const T & Get_Value (void) const { return m_Data; }
|
|
virtual void Set_Value (const T &data) { m_Data = data; }
|
|
|
|
//
|
|
// Tree traversal methods
|
|
//
|
|
NTreeLeafClass<T> * Peek_Parent (void) { return m_Parent; }
|
|
NTreeLeafClass<T> * Peek_Child (void) { return m_Child; }
|
|
NTreeLeafClass<T> * Peek_Next (void) { return m_NextSibling; }
|
|
NTreeLeafClass<T> * Peek_Prev (void) { return m_PrevSibling; }
|
|
|
|
protected:
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Protected member data
|
|
//////////////////////////////////////////////////////////////
|
|
void Set_Parent (NTreeLeafClass<T> *parent) { REF_PTR_SET (m_Parent, parent); }
|
|
void Set_Child (NTreeLeafClass<T> *child) { REF_PTR_SET (m_Child, child); }
|
|
void Set_Prev (NTreeLeafClass<T> *prev) { REF_PTR_SET (m_PrevSibling, prev); }
|
|
void Set_Next (NTreeLeafClass<T> *next) { REF_PTR_SET (m_NextSibling, next); }
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Protected member data
|
|
//////////////////////////////////////////////////////////////
|
|
NTreeLeafClass<T> * m_Parent;
|
|
NTreeLeafClass<T> * m_Child;
|
|
NTreeLeafClass<T> * m_NextSibling;
|
|
NTreeLeafClass<T> * m_PrevSibling;
|
|
|
|
T m_Data;
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// ~NTreeLeafClass
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
NTreeLeafClass<T>::~NTreeLeafClass (void)
|
|
{
|
|
REF_PTR_RELEASE (m_Parent);
|
|
REF_PTR_RELEASE (m_Child);
|
|
REF_PTR_RELEASE (m_NextSibling);
|
|
REF_PTR_RELEASE (m_PrevSibling);
|
|
return;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Add_Child
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
NTreeLeafClass<T> *NTreeLeafClass<T>::Add_Child (const T &value)
|
|
{
|
|
//
|
|
// Allocate a new leaf object
|
|
//
|
|
NTreeLeafClass<T> *new_child = new NTreeLeafClass<T>;
|
|
new_child->Set_Value (value);
|
|
new_child->Set_Parent (this);
|
|
|
|
//
|
|
// Link this new leaf into the hierarchy
|
|
//
|
|
if (m_Child != NULL) {
|
|
m_Child->Set_Prev (new_child);
|
|
new_child->Set_Next (m_Child);
|
|
}
|
|
m_Child = new_child;
|
|
return m_Child;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Add
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
NTreeLeafClass<T> *NTreeLeafClass<T>::Add (const T &value)
|
|
{
|
|
//
|
|
// Allocate a new leaf object
|
|
//
|
|
NTreeLeafClass<T> *new_leaf = new NTreeLeafClass<T>;
|
|
new_leaf->Set_Value (value);
|
|
|
|
//
|
|
// Link this new leaf into the list
|
|
//
|
|
new_leaf->Set_Prev (this);
|
|
new_leaf->Set_Next (m_NextSibling);
|
|
Set_Next (new_leaf);
|
|
|
|
//
|
|
// Release our hold on the new leaf
|
|
//
|
|
new_leaf->Release_Ref ();
|
|
return new_leaf;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Remove
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
void NTreeLeafClass<T>::Remove (void)
|
|
{
|
|
Add_Ref ();
|
|
|
|
//
|
|
// Fixup the parent's child leaf object
|
|
//
|
|
if (m_Parent != NULL && m_Parent->Peek_Child () == this) {
|
|
m_Parent->Set_Child (m_NextSibling);
|
|
}
|
|
|
|
//
|
|
// Remove all our children
|
|
//
|
|
while (m_Child != NULL) {
|
|
m_Child->Remove ();
|
|
}
|
|
|
|
//
|
|
// Unlink ourselves from our siblings
|
|
//
|
|
if (m_NextSibling != NULL) {
|
|
m_NextSibling->Set_Prev (NULL);
|
|
}
|
|
|
|
if (m_PrevSibling != NULL) {
|
|
m_PrevSibling->Set_Next (NULL);
|
|
}
|
|
|
|
REF_PTR_RELEASE (m_Parent);
|
|
REF_PTR_RELEASE (m_Child);
|
|
REF_PTR_RELEASE (m_NextSibling);
|
|
REF_PTR_RELEASE (m_PrevSibling);
|
|
|
|
Release_Ref ();
|
|
return ;
|
|
}
|
|
|
|
|
|
//////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// SortedNTreeLeafClass
|
|
//
|
|
//////////////////////////////////////////////////////////////////////////
|
|
template<class T>
|
|
class SortedNTreeLeafClass : public NTreeLeafClass<T>
|
|
{
|
|
public:
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Public constructors/destructors
|
|
//////////////////////////////////////////////////////////////
|
|
SortedNTreeLeafClass (void) { }
|
|
~SortedNTreeLeafClass (void) { }
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Public methods
|
|
//////////////////////////////////////////////////////////////
|
|
SortedNTreeLeafClass<T> * Add_Sorted (const T &value, const char *name);
|
|
SortedNTreeLeafClass<T> * Add_Child_Sorted (const T &value, const char *name);
|
|
|
|
const StringClass & Get_Name (void) const { return m_Name; }
|
|
void Set_Name (const char *name) { m_Name = name; }
|
|
|
|
protected:
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Protected methods
|
|
//////////////////////////////////////////////////////////////
|
|
void Insertion_Sort (SortedNTreeLeafClass<T> *start, SortedNTreeLeafClass<T> *new_sibling);
|
|
|
|
//////////////////////////////////////////////////////////////
|
|
// Protected member data
|
|
//////////////////////////////////////////////////////////////
|
|
StringClass m_Name;
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Add_Sorted
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
SortedNTreeLeafClass<T> *SortedNTreeLeafClass<T>::Add_Sorted (const T &value, const char *name)
|
|
{
|
|
//
|
|
// Allocate a new leaf object
|
|
//
|
|
SortedNTreeLeafClass<T> *new_sibling = new SortedNTreeLeafClass<T>;
|
|
new_sibling->Set_Value (value);
|
|
new_sibling->Set_Name (name);
|
|
|
|
//
|
|
// Find the first-most sibling
|
|
//
|
|
SortedNTreeLeafClass<T> *start = this;
|
|
while (start->Peek_Prev () != NULL) {
|
|
start = (SortedNTreeLeafClass<T> *)start->Peek_Prev ();
|
|
}
|
|
|
|
//
|
|
// Insert the new leaf in its sorted position
|
|
//
|
|
Insertion_Sort (start, new_sibling);
|
|
|
|
//
|
|
// Release our hold on the object pointer
|
|
//
|
|
new_sibling->Release_Ref ();
|
|
return new_sibling;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Add_Child_Sorted
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
SortedNTreeLeafClass<T> *SortedNTreeLeafClass<T>::Add_Child_Sorted (const T &value, const char *name)
|
|
{
|
|
//
|
|
// Allocate a new leaf object
|
|
//
|
|
SortedNTreeLeafClass<T> *new_child = new SortedNTreeLeafClass<T>;
|
|
new_child->Set_Value (value);
|
|
new_child->Set_Name (name);
|
|
new_child->Set_Parent (this);
|
|
|
|
if (m_Child == NULL) {
|
|
m_Child = new_child;
|
|
} else {
|
|
|
|
//
|
|
// Insert the new leaf in its sorted position
|
|
//
|
|
Insertion_Sort ((SortedNTreeLeafClass<T> *)m_Child, new_child);
|
|
|
|
//
|
|
// Make sure our 'child' pointer is the first one in the list
|
|
//
|
|
NTreeLeafClass<T> *prev = m_Child->Peek_Prev ();
|
|
if (prev != NULL) {
|
|
REF_PTR_SET (m_Child, prev);
|
|
}
|
|
|
|
//
|
|
// Release our hold on the object pointer
|
|
//
|
|
new_child->Release_Ref ();
|
|
}
|
|
|
|
return new_child;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////
|
|
// Insertion_Sort
|
|
/////////////////////////////////////////////////////////
|
|
template<class T>
|
|
void SortedNTreeLeafClass<T>::Insertion_Sort (SortedNTreeLeafClass<T> *start, SortedNTreeLeafClass<T> *new_sibling)
|
|
{
|
|
const char *name = new_sibling->Get_Name ();
|
|
|
|
//
|
|
// Determine where to insert the new sibling
|
|
//
|
|
bool inserted = false;
|
|
for ( SortedNTreeLeafClass<T> *leaf = start;
|
|
leaf != NULL && !inserted;
|
|
leaf = (SortedNTreeLeafClass<T> *)leaf->Peek_Next ())
|
|
{
|
|
//
|
|
// Does the new sibling come before the current leaf?
|
|
//
|
|
if (::stricmp (name, leaf->Get_Name ()) < 0) {
|
|
|
|
//
|
|
// Insert this sibling before the leaf
|
|
//
|
|
SortedNTreeLeafClass<T> *prev = (SortedNTreeLeafClass<T> *)leaf->Peek_Prev ();
|
|
new_sibling->Set_Prev (prev);
|
|
new_sibling->Set_Next (leaf);
|
|
leaf->Set_Prev (new_sibling);
|
|
if (prev != NULL) {
|
|
prev->Set_Next (new_sibling);
|
|
}
|
|
|
|
inserted = true;
|
|
|
|
} else if (leaf->Peek_Next () == NULL) {
|
|
|
|
//
|
|
// Put the new sibling on the end of the list
|
|
//
|
|
new_sibling->Set_Prev (leaf);
|
|
leaf->Set_Next (new_sibling);
|
|
inserted = true;
|
|
}
|
|
}
|
|
|
|
return ;
|
|
}
|
|
|
|
#endif //__NTREE_H
|