tree.cpp

机甲指挥官2源代码

//===========================================================================//
// File:	tree.cc                                                          //
// Contents: Implementation details of Tree class                            //
//---------------------------------------------------------------------------//
// Copyright (C) Microsoft Corporation. All rights reserved.                 //
//===========================================================================//

#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*, 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 plug references
	//------------------------------------------
	//
	ReleaseFromPlug();

	//
	//-------------------------------------------------------------
	// Tell the node to release this link.  Note that this link
	// is not referenced by the plug or the chain at this point in
	// time.
	//-------------------------------------------------------------
	//
	if (tree->GetReleaseNode() != NULL)
	{
		Check_Object(tree->GetReleaseNode());
		tree->GetReleaseNode()->ReleaseLinkHandler(tree, plug);
	}
}

//
//###########################################################################
// 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
//###########################################################################
//
Tree::Tree(
	Node *node,
	bool has_unique_entries
):
	SortedSocket(node, has_unique_entries)
{
	root = NULL;
}

//
//###########################################################################
// ~Tree
//###########################################################################
//
Tree::~Tree()
{
	Check_Object(this);
	SetReleaseNode(NULL);
	while (root != NULL)
	{
		Unregister_Object(root);
		delete root;
	}
}

//
//###########################################################################
// TestInstance
//###########################################################################
//
void
	Tree::TestInstance()
{
	SortedSocket::TestInstance();

	//
	// Check root if not null
	//
	if (root != NULL)
	{
		Check_Object(root);
	}
}

//
//###########################################################################
// AddImplementation
//###########################################################################
//
void
	Tree::AddImplementation(
		Plug *plug
	)
{
	Check_Object(this);
	AddValueImplementation(plug, NULL);	
}

//
//###########################################################################
// AddValueImplementation
//###########################################################################
//
void
	Tree::AddValueImplementation(
		Plug *plug,
		const void *value
	)
{
	Check_Object(this);
	Check_Object(plug);

	/*
	 * Verify that value has not been added
	 */
	Verify(HasUniqueEntries() ? SearchForValue(value) == NULL : true);

	/*
	 * Make new tree node
	 */
	TreeNode *node;

	node = MakeTreeNode(plug, value);
	Register_Object(node);

	/*
	 * Add to the tree and send iterators memo to
	 * update pointers
	 */
	AddTreeNode(node);
	SendIteratorMemo(PlugAdded, node);
}

//
//###########################################################################
// FindImplementation
//###########################################################################
//
Plug*
	Tree::FindImplementation(
		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 (root == NULL);
}

//
//###########################################################################
// MakeTreeNode
//###########################################################################
//
TreeNode*
	Tree::MakeTreeNode(
      Plug*,
      const void*
   )
{
	Check_Object(this);
	STOP(("Tree::MakeTreeNode - Should never reach here"));
	return NULL;
}

//
//###########################################################################
// CompareTreeNodes
//###########################################################################
//
int
   Tree::CompareTreeNodes(
      TreeNode*,
      TreeNode*
   )
{
	Check_Object(this);
	STOP(("Tree::CompareTreeNodes - Should never reach here"));
   return 0;
}

//
//###########################################################################
// CompareValueToTreeNode
//###########################################################################
//
int
   Tree::CompareValueToTreeNode(
      const void*,
      TreeNode*
   )
{
	Check_Object(this);
	STOP(("Tree::CompareValueToTreeNode - Should never reach here"));
   return 0;
}

//
//###########################################################################
// AddTreeNode
//###########################################################################
//
void
	Tree::AddTreeNode(
		TreeNode *newNode
	)
{
	Check_Object(this);
	Check_Object(newNode);

	/*
	 * If root is NULL this is the first item
	 */
	if (root == NULL)
	{
		newNode->SetupTreeLinks(NULL, NULL, NULL);
		root = newNode;
		return;
	}

	/*
	 * Search for insertion point
	 */
	TreeNode *node;

	node = 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
//###########################################################################
//
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 == root)
			{
				//
				// Tree is now empty, set root to null
				//
				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 == root)
			{
				//
				// Node is root... Set subtree to new root
				//
				root = node->less;
				node->less->parent = NULL;
			}
			else
			{
				//
				// Node is not 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
			//--------------------------------------------------------------------