/*
** 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 .
*/
/***********************************************************************************************
*** 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 NTreeLeafClass;
template class SortedNTreeLeafClass;
//////////////////////////////////////////////////////////////////////////
//
// NTreeClass
//
//////////////////////////////////////////////////////////////////////////
template
class NTreeClass
{
public:
//////////////////////////////////////////////////////////////
// Public constructors/destructors
//////////////////////////////////////////////////////////////
NTreeClass (void)
: m_Root (NULL) { }
virtual ~NTreeClass (void) { Reset (); }
//////////////////////////////////////////////////////////////
// Public methods
//////////////////////////////////////////////////////////////
virtual NTreeLeafClass * Add (const T &value);
NTreeLeafClass * Peek_Root (void) { return m_Root; }
virtual void Reset (void);
protected:
//////////////////////////////////////////////////////////////
// Protected methods
//////////////////////////////////////////////////////////////
virtual NTreeLeafClass * Allocate_Leaf (void) { return new NTreeLeafClass; }
//////////////////////////////////////////////////////////////
// Protected member data
//////////////////////////////////////////////////////////////
NTreeLeafClass * m_Root;
};
/////////////////////////////////////////////////////////
// Add
/////////////////////////////////////////////////////////
template
NTreeLeafClass *NTreeClass::Add (const T &value)
{
NTreeLeafClass *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
void NTreeClass::Reset (void)
{
if (m_Root != NULL) {
//
// Find the last leaf in the root
//
NTreeLeafClass *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 *leaf = end_leaf; leaf != NULL; ) {
NTreeLeafClass *curr_leaf = leaf;
leaf = leaf->Peek_Prev ();
//
// Remove this leaf
//
curr_leaf->Remove ();
}
REF_PTR_RELEASE (m_Root);
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// SortedNTreeClass
//
//////////////////////////////////////////////////////////////////////////
template
class SortedNTreeClass : public NTreeClass
{
public:
//////////////////////////////////////////////////////////////
// Public constructors/destructors
//////////////////////////////////////////////////////////////
SortedNTreeClass (void) { }
virtual ~SortedNTreeClass (void) { }
//////////////////////////////////////////////////////////////
// Public methods
//////////////////////////////////////////////////////////////
SortedNTreeLeafClass * Add_Sorted (const T &value, const char *name);
protected:
//////////////////////////////////////////////////////////////
// Protected methods
//////////////////////////////////////////////////////////////
NTreeLeafClass * Allocate_Leaf (void) { return new SortedNTreeLeafClass; }
};
/////////////////////////////////////////////////////////
// Add_Sorted
/////////////////////////////////////////////////////////
template
SortedNTreeLeafClass *SortedNTreeClass::Add_Sorted (const T &value, const char *name)
{
SortedNTreeLeafClass *retval = NULL;
if (m_Root == NULL) {
//
// Allocate a new root node
//
m_Root = Allocate_Leaf ();
retval = (SortedNTreeLeafClass *)m_Root;
retval->Set_Value (value);
retval->Set_Name (name);
} else {
//
// Simply add this value to list
//
retval = ((SortedNTreeLeafClass *)m_Root)->Add_Sorted (value, name);
//
// Make sure our 'root' pointer is the first one in the list
//
NTreeLeafClass *prev = m_Root->Peek_Prev ();
if (prev != NULL) {
REF_PTR_SET (m_Root, prev);
}
}
return retval;
}
//////////////////////////////////////////////////////////////////////////
//
// NTreeLeafClass
//
//////////////////////////////////////////////////////////////////////////
template
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 * Add_Child (const T &value);
virtual NTreeLeafClass * 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 * Peek_Parent (void) { return m_Parent; }
NTreeLeafClass * Peek_Child (void) { return m_Child; }
NTreeLeafClass * Peek_Next (void) { return m_NextSibling; }
NTreeLeafClass * Peek_Prev (void) { return m_PrevSibling; }
protected:
//////////////////////////////////////////////////////////////
// Protected member data
//////////////////////////////////////////////////////////////
void Set_Parent (NTreeLeafClass *parent) { REF_PTR_SET (m_Parent, parent); }
void Set_Child (NTreeLeafClass *child) { REF_PTR_SET (m_Child, child); }
void Set_Prev (NTreeLeafClass *prev) { REF_PTR_SET (m_PrevSibling, prev); }
void Set_Next (NTreeLeafClass *next) { REF_PTR_SET (m_NextSibling, next); }
//////////////////////////////////////////////////////////////
// Protected member data
//////////////////////////////////////////////////////////////
NTreeLeafClass * m_Parent;
NTreeLeafClass * m_Child;
NTreeLeafClass * m_NextSibling;
NTreeLeafClass * m_PrevSibling;
T m_Data;
};
/////////////////////////////////////////////////////////
// ~NTreeLeafClass
/////////////////////////////////////////////////////////
template
NTreeLeafClass::~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
NTreeLeafClass *NTreeLeafClass::Add_Child (const T &value)
{
//
// Allocate a new leaf object
//
NTreeLeafClass *new_child = new NTreeLeafClass;
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
NTreeLeafClass *NTreeLeafClass::Add (const T &value)
{
//
// Allocate a new leaf object
//
NTreeLeafClass *new_leaf = new NTreeLeafClass;
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
void NTreeLeafClass::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 SortedNTreeLeafClass : public NTreeLeafClass
{
public:
//////////////////////////////////////////////////////////////
// Public constructors/destructors
//////////////////////////////////////////////////////////////
SortedNTreeLeafClass (void) { }
~SortedNTreeLeafClass (void) { }
//////////////////////////////////////////////////////////////
// Public methods
//////////////////////////////////////////////////////////////
SortedNTreeLeafClass * Add_Sorted (const T &value, const char *name);
SortedNTreeLeafClass * 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 *start, SortedNTreeLeafClass *new_sibling);
//////////////////////////////////////////////////////////////
// Protected member data
//////////////////////////////////////////////////////////////
StringClass m_Name;
};
/////////////////////////////////////////////////////////
// Add_Sorted
/////////////////////////////////////////////////////////
template
SortedNTreeLeafClass *SortedNTreeLeafClass::Add_Sorted (const T &value, const char *name)
{
//
// Allocate a new leaf object
//
SortedNTreeLeafClass *new_sibling = new SortedNTreeLeafClass;
new_sibling->Set_Value (value);
new_sibling->Set_Name (name);
//
// Find the first-most sibling
//
SortedNTreeLeafClass *start = this;
while (start->Peek_Prev () != NULL) {
start = (SortedNTreeLeafClass *)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
SortedNTreeLeafClass *SortedNTreeLeafClass::Add_Child_Sorted (const T &value, const char *name)
{
//
// Allocate a new leaf object
//
SortedNTreeLeafClass *new_child = new SortedNTreeLeafClass;
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 *)m_Child, new_child);
//
// Make sure our 'child' pointer is the first one in the list
//
NTreeLeafClass *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
void SortedNTreeLeafClass::Insertion_Sort (SortedNTreeLeafClass *start, SortedNTreeLeafClass *new_sibling)
{
const char *name = new_sibling->Get_Name ();
//
// Determine where to insert the new sibling
//
bool inserted = false;
for ( SortedNTreeLeafClass *leaf = start;
leaf != NULL && !inserted;
leaf = (SortedNTreeLeafClass *)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 *prev = (SortedNTreeLeafClass *)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