redblack.cs

game implemented java

///<summary>
///A red-black tree must satisfy these properties:
///
///1. The root is black. 
///2. All leaves are black. 
///3. Red nodes can only have black children. 
///4. All paths from a node to its leaves contain the same number of black nodes.
///
///File adapted by an implementation by "RoyClem" available at The Code Project
///http://www.thecodeproject.com/csharp/RedBlackCS.asp
///(Comments his)
///</summary>

using System;
using System.Collections;
using System.Text;
using System.Reflection;
using WindowsApplication2;
using System.Windows.Forms;

namespace RedBlackCS
{
	public class RedBlack : object
	{
		// the number of nodes contained in the tree
		private int             intCount;
		// a simple randomized hash code. The hash code could be used as a key
		// if it is "unique" enough. Note: The IComparable interface would need to 
		// be replaced with int.
		private int             intHashCode;
		// identifies the owner of the tree
		private readonly string	objName;
		private string          strIdentifier;
		// the tree
		private RedBlackNode	rbTree;
		//  sentinelNode is convenient way of indicating a leaf node.
		public static RedBlackNode sentinelNode;          
		// the node that was last found; used to optimize searches
		private RedBlackNode	lastNodeFound;			
		private Random          rand	= new Random();
		private double[] speedArray;

		public RedBlack(int elements, string name) 
		{
			strIdentifier       = base.ToString() + rand.Next();
			intHashCode         = rand.Next();
			objName				= name;

			// set up the sentinel node. the sentinel node is the key to a successfull
			// implementation and for understanding the red-black tree properties.
			AStarNode sentData = new AStarNode();
			sentData.id		= -1;
			sentData.FofN	= double.MaxValue;

			sentinelNode        = new RedBlackNode();
			sentinelNode.Left   = null;
			sentinelNode.Right  = null;
			sentinelNode.Parent = null;
			sentinelNode.Data	= sentData;
			sentinelNode.Color  = RedBlackNode.BLACK;
			sentinelNode.Left_Min = double.MaxValue;
			sentinelNode.Right_Min = double.MaxValue;
			rbTree              = sentinelNode;
			lastNodeFound       = sentinelNode;
			speedArray = new double[elements];
			for (int i=0; i<speedArray.Length;i++)
				speedArray[i] = double.MaxValue;
		}
		public RedBlack(string strIdentifier) 
		{
			intHashCode         = rand.Next();
			this.strIdentifier  = strIdentifier;
		}		
		///<summary>
		/// Add
		/// args: ByVal key As IComparable, ByVal data As Object
		/// key is object that implements IComparable interface
		/// performance tip: change to use use int type (such as the hashcode)
		///</summary>
		public void Add(AStarNode toAdd)
		{
			//if (objName == "CLOSED")
				//MessageBox.Show("ADD: "+objName + " "+toAdd.id+ " "+toAdd.dist+ " " +this.Size());
			// traverse tree - find where node belongs

			// create new node
			RedBlackNode node	=	new RedBlackNode();
			RedBlackNode temp	=	rbTree;				// grab the rbTree node of the tree

			while(!isSentinelNode(temp))
			{	// find Parent
				node.Parent	= temp;
				if(toAdd.id == temp.Data.id)
					throw(new RedBlackException("A Node with the same key already exists"));
				if(toAdd.id > temp.Data.id)
					temp = temp.Right;
				else
					temp = temp.Left;
				if (temp == null)
					throw(new RedBlackException("HMMM "+objName+" "+intCount+" "+node.Parent.Data.id));
			}
			
			// setup node
			node.Data			=	toAdd;
			node.Left           =   sentinelNode;
			node.Right          =   sentinelNode;
			node.Left_Min		=	double.MaxValue;
			node.Right_Min		=	double.MaxValue;

			// insert node into tree starting at parent's location
			if(node.Parent != null)	
			{
				if(node.Data.id > node.Parent.Data.id)
					node.Parent.Right = node;
				else
					node.Parent.Left = node;
			}
			else
				rbTree = node;					// first node added

			setMinTags(node);

			RestoreAfterInsert(node);           // restore red-black properities

			lastNodeFound = node;
			
			setMinTags(rbTree);

			intCount = intCount + 1;
			speedArray[toAdd.id] = toAdd.dist;
		}
		///<summary>
		/// RestoreAfterInsert
		/// Additions to red-black trees usually destroy the red-black 
		/// properties. Examine the tree and restore. Rotations are normally 
		/// required to restore it
		///</summary>
		private void RestoreAfterInsert(RedBlackNode x)
		{   
			// x and y are used as variable names for brevity, in a more formal
			// implementation, you should probably change the names

			RedBlackNode y;

			// maintain red-black tree properties after adding x
			while(x.Data.id != rbTree.Data.id && x.Parent.Color == RedBlackNode.RED)
			{
				// Parent node is .Colored red; 
				if(x.Parent.Data.id == x.Parent.Parent.Left.Data.id)	// determine traversal path			
				{										// is it on the Left or Right subtree?
					y = x.Parent.Parent.Right;			// get uncle
					if(y!= null && y.Color == RedBlackNode.RED)
					{	// uncle is red; change x's Parent and uncle to black
						x.Parent.Color			= RedBlackNode.BLACK;
						y.Color					= RedBlackNode.BLACK;
						// grandparent must be red. Why? Every red node that is not 
						// a leaf has only black children 
						x.Parent.Parent.Color	= RedBlackNode.RED;	
						setMinTags(x);
						setMinTags(x.Parent);
						x						= x.Parent.Parent;	// continue loop with grandparent
					}	
					else
					{
						// uncle is black; determine if x is greater than Parent
						if(x.Data.id == x.Parent.Right.Data.id) 
						{	// yes, x is greater than Parent; rotate Left
							// make x a Left child
							setMinTags(x);
							x = x.Parent;
							RotateLeft(x);
						}
						// no, x is less than Parent
						x.Parent.Color			= RedBlackNode.BLACK;	// make Parent black
						x.Parent.Parent.Color	= RedBlackNode.RED;		// make grandparent black
						setMinTags(x);
						setMinTags(x.Parent);
						RotateRight(x.Parent.Parent);					// rotate right
					}
				}
				else
				{	// x's Parent is on the Right subtree
					// this code is the same as above with "Left" and "Right" swapped
					y = x.Parent.Parent.Left;
					if(y!= null && y.Color == RedBlackNode.RED)
					{
						x.Parent.Color			= RedBlackNode.BLACK;
						y.Color					= RedBlackNode.BLACK;
						x.Parent.Parent.Color	= RedBlackNode.RED;
						setMinTags(x);
						setMinTags(x.Parent);
						x						= x.Parent.Parent;
					}
					else
					{
						if(x.Data.id == x.Parent.Left.Data.id)
						{
							setMinTags(x);
							x = x.Parent;
							RotateRight(x);
						}
						x.Parent.Color			= RedBlackNode.BLACK;
						x.Parent.Parent.Color	= RedBlackNode.RED;
						setMinTags(x);
						setMinTags(x.Parent);
						RotateLeft(x.Parent.Parent);
					}
				}																									
			}
			rbTree.Color = RedBlackNode.BLACK;		// rbTree should always be black
		}
		
		///<summary>
		/// RotateLeft
		/// Rebalance the tree by rotating the nodes to the left
		///</summary>
		public void RotateLeft(RedBlackNode x)
		{
			// pushing node x down and to the Left to balance the tree. x's Right child (y)
			// replaces x (since y > x), and y's Left child becomes x's Right child 
			// (since it's < y but > x).
            
			RedBlackNode y = x.Right;			// get x's Right node, this becomes y

			// set x's Right link
			x.Right = y.Left;					// y's Left child's becomes x's Right child

			// modify parents
			if(!isSentinelNode(y.Left)) 
				y.Left.Parent = x;				// sets y's Left Parent to x

			if(!isSentinelNode(y))
				y.Parent = x.Parent;			// set y's Parent to x's Parent

			if(x.Parent != null)		
			{	// determine which side of it's Parent x was on
				if(x.Data.id == x.Parent.Left.Data.id)			
					x.Parent.Left = y;			// set Left Parent to y
				else
					x.Parent.Right = y;			// set Right Parent to y
			} 
			else 
				rbTree = y;						// at rbTree, set it to y

			// link x and y 
			y.Left = x;							// put x on y's Left 
			if(!isSentinelNode(x))						// set y as x's Parent
				x.Parent = y;		
			setMinTags(x);
			setMinTags(y);
		}
		///<summary>
		/// RotateRight
		/// Rebalance the tree by rotating the nodes to the right
		///</summary>
		public void RotateRight(RedBlackNode x)
		{
			// pushing node x down and to the Right to balance the tree. x's Left child (y)
			// replaces x (since x < y), and y's Right child becomes x's Left child 
			// (since it's < x but > y).
            
			RedBlackNode y = x.Left;			// get x's Left node, this becomes y

			// set x's Right link
			x.Left = y.Right;					// y's Right child becomes x's Left child

			// modify parents
			if(!isSentinelNode(y.Right)) 
				y.Right.Parent = x;				// sets y's Right Parent to x

			if(!isSentinelNode(y))
				y.Parent = x.Parent;			// set y's Parent to x's Parent

			if(x.Data.id != rbTree.Data.id)		// null=rbTree, could also have used rbTree
			{	// determine which side of it's Parent x was on
				if(x.Data.id == x.Parent.Right.Data.id)			
					x.Parent.Right = y;			// set Right Parent to y
				else
					x.Parent.Left = y;			// set Left Parent to y
			} 
			else 
				rbTree = y;						// at rbTree, set it to y

			// link x and y 
			y.Right = x;						// put x on y's Right
			if(!isSentinelNode(x))				// set y as x's Parent
				x.Parent = y;		
			setMinTags(x);
			setMinTags(y);
		}		
		///<summary>
		/// IsEmpty
		/// Is the tree empty?
		///<summary>
		public bool IsEmpty()
		{
			return (rbTree == null);
		}
		///<summary>
		/// Remove
		/// removes the key and data object (delete)
		///<summary>
		public void Remove(int key)
		{