vwemirror/firestorm
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
firestorm/Gameleap/code/mw4/Libraries/stuff/Tree.cpp
T
Cyd 2b8ca921cb Initial full mirror of c:\VWE (source + assets + toolchain + outputs) via Git LFS 
Complete disaster-recovery snapshot: engine/game source, game data assets,
VC6 toolchain + DX SDKs, build outputs, deployed game, and _UNUSED archive.
Large binaries in Git LFS; text preserved byte-for-byte (core.autocrlf=false,
no eol attributes). See RECOVERY.md for the one-clone rebuild procedure.
2026-06-24 21:28:16 -05:00

840 lines
18 KiB
C++
Raw Permalink Blame History

//===========================================================================//
// File: tree.cc //
// Project: MUNGA Brick: Connection Library //
// Contents: Implementation details of Tree class //
//---------------------------------------------------------------------------//
// Date Who Modification //
// -------- --- ---------------------------------------------------------- //
// 10/01/94 ECH Initial coding. //
// 11/02/94 JMA Made compatible with SGI CC, merged with iterator //
// 11/03/94 ECH Made compatible with BC4.0 //
// 11/03/94 ECH Removed SGI warning //
// 11/05/94 JMA Made compatible with GNU C++ //
// 12/12/94 ECH Changed release handling //
//---------------------------------------------------------------------------//
// Copyright (C) 1994-1995, Virtual World Entertainment, Inc. //
// PROPRIETARY AND CONFIDENTIAL //
//===========================================================================//
#include "StuffHeaders.hpp"
//~~~~~~~~~~~~~~~~~~~~~~~~~~~ TreeNode ~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
//###########################################################################
// TreeNode
//###########################################################################
//
TreeNode::TreeNode(
Tree *tree,
Plug *plug
):
Link(tree, plug)
{
less = NULL;
greater = NULL;
parent = NULL;
}
//
//###########################################################################
// ~TreeNode
//###########################################################################
//
TreeNode::~TreeNode()
{
Check_Object(this);
Tree *tree = Cast_Object(Tree*, m_socket);
Check_Object(tree);
//
//-------------------------------------------
// Notify iterators that deletion is occuring
//-------------------------------------------
//
tree->SendIteratorMemo(PlugRemoved, this);
//
//-----------------------------------
// Tell the tree to release this node
//-----------------------------------
//
tree->SeverFromTreeNode(this);
//
//------------------------------------------
// Remove this link from any m_plug references
//------------------------------------------
//
ReleaseFromPlug();
}
//
//###########################################################################
// TestInstance
//###########################################################################
//
void
TreeNode::TestInstance()
{
Link::TestInstance();
if (less != NULL)
{
Check_Signature(less);
}
if (greater != NULL)
{
Check_Signature(greater);
}
if (parent != NULL)
{
Check_Signature(parent);
}
}
//
//###########################################################################
// SetupTreeLinks
//###########################################################################
//
void
TreeNode::SetupTreeLinks(
TreeNode *less,
TreeNode *greater,
TreeNode *parent
)
{
Check_Object(this);
this->less = less;
this->greater = greater;
this->parent = parent;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~ Tree ~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
//###########################################################################
// ~Tree
//###########################################################################
//
#if defined(NDEBUG)
#pragma optimize("a",off)
#endif
Tree::~Tree()
{
Check_Object(this);
while (m_root != NULL)
{
Check_Object(m_root);
delete m_root;
}
}
#if defined(NDEBUG)
#pragma optimize("a",on)
#endif
//
//###########################################################################
// TestInstance
//###########################################################################
//
void
Tree::TestInstance()
{
SortedSocket::TestInstance();
//
// Check m_root if not null
//
if (m_root != NULL)
{
Check_Object(m_root);
}
}
//
//###########################################################################
// DeletePlugs
//###########################################################################
//
#if defined(NDEBUG)
#pragma optimize("a",off)
#endif
void
Tree::DeletePlugs()
{
Check_Object(this);
while (m_root != NULL)
{
Check_Object(m_root);
Check_Object(m_root->m_plug);
delete m_root->m_plug;
}
}
#if defined(NDEBUG)
#pragma optimize("a",on)
#endif
//
//###########################################################################
// GetSize
//###########################################################################
//
unsigned
Tree::GetSize()
{
Check_Object(this);
TreeIterator iterator(this);
unsigned i = 0;
while (iterator.ReadAndNextItem() != NULL)
i++;
return(i);
}
//
//###########################################################################
// GetNthImplementation
//###########################################################################
//
void
*Tree::GetNthItem(unsigned index)
{
STOP(("Not implemented"));
return NULL;
}
//
//###########################################################################
// AddValueImplementation
//###########################################################################
//
void
Tree::AddValuePlug(
Plug *m_plug,
const void *value
)
{
Check_Object(this);
Check_Object(m_plug);
/*
* Verify that value has not been added
*/
Verify(HasUniqueEntries() ? SearchForValue(value) == NULL : true);
/*
* Make new tree node
*/
TreeNode *node;
node = MakeTreeNode(m_plug, value);
Check_Object(node);
/*
* Add to the tree and send iterators memo to
* update pointers
*/
AddTreeNode(node);
SendIteratorMemo(PlugAdded, node);
}
//
//###########################################################################
// FindImplementation
//###########################################################################
//
Plug*
Tree::FindPlug(const void *value)
{
Check_Object(this);
TreeNode *node;
if ((node = SearchForValue(value)) != NULL)
{
Check_Object(node);
return node->GetPlug();
}
return NULL;
}
//
//#############################################################################
// IsEmpty
//#############################################################################
//
bool
Tree::IsEmpty()
{
Check_Object(this);
return (m_root == NULL);
}
//
//###########################################################################
// AddTreeNode
//###########################################################################
//
void
Tree::AddTreeNode(
TreeNode *newNode
)
{
Check_Object(this);
Check_Object(newNode);
/*
* If m_root is NULL this is the first item
*/
if (m_root == NULL)
{
newNode->SetupTreeLinks(NULL, NULL, NULL);
m_root = newNode;
return;
}
/*
* Search for insertion point
*/
TreeNode *node;
node = m_root;
while (node != NULL)
{
Check_Object(node);
if (CompareTreeNodes(newNode, node) < 0)
{
if (node->less == NULL)
{
newNode->SetupTreeLinks(NULL, NULL, node);
node->less = newNode;
break;
}
else
node = node->less;
}
else
{
if (node->greater == NULL)
{
newNode->SetupTreeLinks(NULL, NULL, node);
node->greater = newNode;
break;
}
else
node = node->greater;
}
}
}
//
//###########################################################################
// SeverFromTreeNode
//###########################################################################
//
#if defined(NDEBUG)
#pragma optimize("a",off)
#endif
void
Tree::SeverFromTreeNode(
TreeNode *node
)
{
Check_Object(this);
Check_Object(node);
if (node->greater == NULL)
{
if (node->less == NULL)
{
//
//--------------------------------------------------------------------
// The node has no subtrees
//--------------------------------------------------------------------
//
if (node == m_root)
{
//
// Tree is now empty, set m_root to null
//
m_root = NULL;
}
else
{
//
// Set appropiate branch to NULL
//
Check_Object(node->parent);
if (node->parent->less == node)
node->parent->less = NULL;
else
node->parent->greater = NULL;
}
}
else
{
//
//--------------------------------------------------------------------
// The node has a less subtree
//--------------------------------------------------------------------
//
Check_Object(node->less);
if (node == m_root)
{
//
// Node is m_root... Set subtree to new m_root
//
m_root = node->less;
node->less->parent = NULL;
}
else
{
//
// Node is not m_root
// Set parents pointer to subtree
//
Check_Object( node->parent );
if (node->parent->less == node)
{
node->parent->less = node->less;
}
else
{
node->parent->greater = node->less;
}
//
// Set subtree parent to node parent
//
node->less->parent = node->parent;
}
}
}
else {
if (node->less == NULL)
{
//
//--------------------------------------------------------------------
// The node has a greater subtree
//--------------------------------------------------------------------
//
Check_Object( node->greater );
if (node == m_root)
{
//
// Node is m_root
// Set subtree to new m_root
//
m_root = node->greater;
//
// Set new m_root to have null parent
//
node->greater->parent = NULL;
}
else
{
//
// Node is not m_root
// Set parents pointer to subtree
//
Check_Object( node->parent );
if (node->parent->less == node)
node->parent->less = node->greater;
else
node->parent->greater = node->greater;
//
// Set subtree parent to node parent
//
node->greater->parent = node->parent;
}
}
else
{
//
//--------------------------------------------------------------------
// The node has lesser and greater sub-trees
//--------------------------------------------------------------------
//
TreeNode *successor;
Check_Object(node->less);
Check_Object(node->greater);
successor = node->greater;
while (successor->less != NULL)
{
successor = successor->less;
Check_Object(successor);
}
//
// Set successor's parent to subtree
//
Check_Object(successor->parent);
if (successor->parent->less == successor)
successor->parent->less = successor->greater;
else
successor->parent->greater = successor->greater;
//
// Set successor's subtree to parent
//
if (successor->greater != NULL)
{
Check_Object(successor->greater);
successor->greater->parent = successor->parent;
}
//
// Place at node
//
successor->parent = node->parent;
successor->less = node->less;
successor->greater = node->greater;
if (m_root == node)
{
//
// Node was m_root
//
m_root = successor;
}
else
{
//
// Set nodes parent to successor
//
Check_Object(successor->parent);
if (successor->parent->less == node)
successor->parent->less = successor;
else
successor->parent->greater = successor;
}
//
// Set subtrees parent to successor
//
if (successor->greater != NULL)
{
Check_Object(successor->greater);
successor->greater->parent = successor;
}
if (successor->less != NULL)
{
Check_Object(successor->less);
successor->less->parent = successor;
}
}
}
}
#if defined(NDEBUG)
#pragma optimize("a",on)
#endif
//
//###########################################################################
// SearchForValue
//###########################################################################
//
TreeNode*
Tree::SearchForValue(
const void *value
)
{
Check_Object(this);
TreeNode *node;
int ret;
node = m_root;
while (node != NULL)
{
Check_Object(node);
if ((ret = CompareValueToTreeNode(value, node)) == 0)
break;
node = (ret < 0) ? node->less : node->greater;
}
return node;
}
//
//###########################################################################
// TreeIterator
//###########################################################################
//
TreeIterator::TreeIterator(Tree *tree):
SortedIterator(tree)
{
First();
}
Iterator*
TreeIterator::MakeClone()
{
Check_Object(this);
return new TreeIterator(*this);
}
//
//###########################################################################
//###########################################################################
//
TreeIterator::~TreeIterator()
{
Check_Object(this);
}
//
//###########################################################################
// TestInstance
//###########################################################################
//
void
TreeIterator::TestInstance()
{
SortedIterator::TestInstance();
if (m_currentNode != NULL)
{
Check_Object(m_currentNode);
}
}
//
//###########################################################################
// First
//###########################################################################
//
Iterator&
TreeIterator::First()
{
TreeNode *node;
node = Cast_Object(Tree*, m_socket)->m_root;
if (node != NULL)
{
Check_Object(node);
while (node->less != NULL)
{
node = node->less;
Check_Object(node);
}
}
m_currentNode = node;
return *this;
}
//
//###########################################################################
// Last
//###########################################################################
//
Iterator&
TreeIterator::Last()
{
Check_Object(this);
//
// Should never reach here
//
STOP(("Shouldn't get here"));
return *this;
}
//
//###########################################################################
// Next
//###########################################################################
//
Iterator&
TreeIterator::Next()
{
Check_Object(this);
TreeNode *node;
if ((node = m_currentNode) == NULL)
return *this;
Check_Object(node);
if (node->greater != NULL)
{
node = node->greater;
Check_Object(node);
while (node->less != NULL)
{
node = node->less;
Check_Object(node);
}
m_currentNode = node;
return *this;
}
m_currentNode = NULL;
while (node->parent != NULL)
{
Check_Object(node->parent);
if (node == node->parent->less)
{
m_currentNode = node->parent;
return *this;
}
node = node->parent;
Check_Object(node);
}
return *this;
}
//
//###########################################################################
// Previous
//###########################################################################
//
Iterator&
TreeIterator::Previous()
{
Check_Object(this);
//
// Should never reach here
//
STOP(("Shouldn't get here"));
return *this;
}
//
//###########################################################################
// ReadAndNextItem
//###########################################################################
//
void
*TreeIterator::ReadAndNextItem()
{
Check_Object(this);
void *m_plug;
if ((m_plug = GetCurrentItem()) != NULL)
Next();
return m_plug;
}
//
//###########################################################################
// ReadAndPreviousItem
//###########################################################################
//
void
*TreeIterator::ReadAndPreviousItem()
{
Check_Object(this);
#ifdef __BCPLUSPLUS__
#pragma warn -ccc
Verify(False);
#pragma warn +ccc
#endif
return(NULL);
}
//
//###########################################################################
// GetCurrentItem
//###########################################################################
//
void
*TreeIterator::GetCurrentItem()
{
Check_Object(this);
if (m_currentNode != NULL)
{
Check_Object(m_currentNode);
return m_currentNode->GetPlug();
}
return NULL;
}
//
//###########################################################################
// GetNthImplementation
//###########################################################################
//
void
*TreeIterator::GetNthItem(unsigned index)
{
Check_Object(this);
unsigned i = 0;
void *plug;
TreeIterator::First();
while ((plug = TreeIterator::GetCurrentItem()) != NULL)
{
if (i == index)
return plug;
TreeIterator::Next();
i++;
}
return NULL;
}
//
//###########################################################################
// Remove
//###########################################################################
//
void
TreeIterator::Remove()
{
Check_Object(this);
if (m_currentNode != NULL)
{
Check_Object(m_currentNode);
delete m_currentNode;
}
}
//
//###########################################################################
// FindImplementation
//###########################################################################
//
Plug*
TreeIterator::FindPlug(const void *value)
{
Check_Object(this);
TreeNode *node;
if ((node = Cast_Object(Tree*, m_socket)->SearchForValue(value)) != NULL)
{
Check_Object(node);
return (m_currentNode = node)->GetPlug();
}
return NULL;
}
//
//###########################################################################
// FindImplementation
//###########################################################################
//
void*
TreeIterator::GetPlugValue()
{
STOP(("Not implemented"));
return NULL;
}
//
//###########################################################################
// ReceiveMemo
//###########################################################################
//
void
TreeIterator::ReceiveMemo(
IteratorMemo memo,
void *content
)
{
Check_Object(this);
if (memo == PlugRemoved)
{
if (content == m_currentNode)
Next();
}
}
Reference in New Issue View Git Blame Copy Permalink