tree.cpp

机甲指挥官2源代码

			//
			Check_Object( node->greater );
			if (node == root)
			{
				//
				// Node is root
				// Set subtree to new root
				//
				root = node->greater;
				//
				// Set new root to have null parent
				//
				node->greater->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->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 (root == node)
			{
				//
				// Node was root
				//
				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;
			}
		}
	}
}

//
//###########################################################################
// SearchForValue
//###########################################################################
//
TreeNode*
	Tree::SearchForValue(
		const void *value
	)
{
	Check_Object(this);
	TreeNode *node;
	int ret;

	node = 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 (currentNode != NULL) 
	{
		Check_Object(currentNode);
	}
}

//
//###########################################################################
// First
//###########################################################################
//
void
	TreeIterator::First()
{
	TreeNode *node;

	node = Cast_Object(Tree*, socket)->root;
	if (node != NULL) 
	{
		Check_Object(node);
		while (node->less != NULL) 
		{
			node = node->less;
			Check_Object(node);
		}
	}	
	currentNode = node;
}

//
//###########################################################################
// Last
//###########################################################################
//
void
	TreeIterator::Last()
{
	Check_Object(this);
	//
	// Should never reach here
	//
	#ifdef __BCPLUSPLUS__
		#pragma warn -ccc
			Verify(False);
		#pragma warn +ccc
	#endif
}

//
//###########################################################################
// Next
//###########################################################################
//
void
	TreeIterator::Next()
{
	Check_Object(this);
	TreeNode *node;
	
	if ((node = currentNode) == NULL)
		return;
	
	Check_Object(node);
	if (node->greater != NULL) 
	{
		node = node->greater;
		Check_Object(node);
		while (node->less != NULL) 
		{
			node = node->less;
			Check_Object(node);
		}
		currentNode = node;
		return;
	}
	
	currentNode = NULL;
	while (node->parent != NULL)
	{
		Check_Object(node->parent);
		if (node == node->parent->less) 
		{
			currentNode = node->parent;
			return;
		}
		node = node->parent;
		Check_Object(node);
	}
}

//
//###########################################################################
// Previous
//###########################################################################
//
void
	TreeIterator::Previous()
{
	Check_Object(this);
	//
	// Should never reach here
	//
	#ifdef __BCPLUSPLUS__
		#pragma warn -ccc
			Verify(False);
		#pragma warn +ccc
	#endif
}

#if 0
//
//###########################################################################
// ReadAndNextImplementation
//###########################################################################
//
void
	*TreeIterator::ReadAndNextImplementation()
{
	Check_Object(this);
	void *plug;

	if ((plug = GetCurrentImplementation()) != NULL)
	{
		Next();
	}
	return plug;
}
#endif

#if 0
//
//###########################################################################
// ReadAndPreviousImplementation
//###########################################################################
//
void
	*TreeIterator::ReadAndPreviousImplementation()
{
	Check_Object(this);
	#ifdef __BCPLUSPLUS__
		#pragma warn -ccc
			Verify(False);
		#pragma warn +ccc
	#endif
	return(NULL);
}
#endif

//
//###########################################################################
// GetCurrentImplementation
//###########################################################################
//
void
	*TreeIterator::GetCurrentImplementation()
{
	Check_Object(this);
	if (currentNode != NULL)
	{
		Check_Object(currentNode);
		return currentNode->GetPlug();
	}
	return NULL;
}

//
//###########################################################################
// GetSize
//###########################################################################
//
CollectionSize
	TreeIterator::GetSize()
{
	Check_Object(this);
	TreeIterator	iterator(Cast_Object(Tree*, socket));
	CollectionSize i = 0;

	while (iterator.ReadAndNextImplementation() != NULL)
	{
		i++;
	}
	return(i);
}

#if 0
//
//###########################################################################
// GetNthImplementation
//###########################################################################
//
void
	*TreeIterator::GetNthImplementation(
		CollectionSize index
	)
{
	Check_Object(this);
	CollectionSize i = 0;
	void 				*plug;

	First();
	while ((plug = GetCurrentImplementation()) != NULL)
	{
		if (i == index)
			return plug;
		Next();
		i++;
	}
	return NULL;
}
#endif

//
//###########################################################################
// Remove
//###########################################################################
//
void
	TreeIterator::Remove()
{
	Check_Object(this);
	if (currentNode != NULL)
	{
		Unregister_Object(currentNode);
		delete currentNode;
	}
}

//
//###########################################################################
// FindImplementation
//###########################################################################
//
Plug*
	TreeIterator::FindImplementation(
		const void *value
	)
{
	Check_Object(this);
	TreeNode *node;
	
	if ((node = Cast_Object(Tree*, socket)->SearchForValue(value)) != NULL)
	{
		Check_Object(node);
		return (currentNode = node)->GetPlug();
	}
	return NULL;
}

//
//###########################################################################
// ReceiveMemo
//###########################################################################
//
void
	TreeIterator::ReceiveMemo(
		IteratorMemo memo,
		void *content
	)
{
	Check_Object(this);
	if (memo == PlugRemoved)
	{
		if (content == currentNode)
			Next();
	}
}