TapestryEngine

A 2D Platformer Game Engine
Log | Files | Refs

d861f35fa5f11db26454df3c408d133427104de5.svn-base (2653B)

      1 #include "BinaryTree.h"
      2 #include "Utils.h"
      3 
      4 bool Node::Insert(int i, void* data)
      5 {
      6 	return InsertNode(new Node(this, i, data));
      7 }
      8 
      9 Node* Node::Search(int i)
     10 {
     11 	if (mItem == i) { return this; }
     12 	else if (i < mItem && mLeft != NULL ) { return mLeft->Search(i);  }
     13 	else if (mItem < i && mRight != NULL) { return mRight->Search(i); }
     14 	else //Item Could not be found
     15 	{
     16 		return NULL;
     17 	}
     18 }
     19 
     20 int Node::Size(int i)
     21 {
     22 	i++;
     23 	if (mLeft  != NULL)  { i = mLeft->Size(i);  }
     24 	if (mRight != NULL)  { i = mRight->Size(i); }
     25 	return i;
     26 }
     27 
     28 Node** Node::Dump(int index, Node** contents)
     29 {
     30 	if (contents == 0)
     31 	{
     32 		//contents = (Node**)malloc(Size()); 
     33 		contents = new Node*[Size()];
     34 	}
     35 	contents[index] = this;
     36 	index++;
     37 
     38 
     39 	if (mLeft != NULL ) { mLeft->Dump(index, contents);  }
     40 	if (mRight != NULL) { mRight->Dump(index, contents); }
     41 
     42 	return contents;
     43 }
     44 
     45 bool Node::InsertNode(Node* n)
     46 {
     47 
     48 	if (n->mItem < mItem)
     49 	{
     50 		if (mLeft == NULL)
     51 		{
     52 			mLeft = n; 
     53 			n->mParent = this;
     54 			return true; 
     55 		}
     56 		else { return mLeft->InsertNode(n); }
     57 	} 
     58 
     59 	else if (mItem < n->mItem)
     60 	{
     61 		if (mRight == NULL) 
     62 		{ 
     63 			mRight = n; 			
     64 		n->mParent = this;
     65 		return true; 
     66 		}
     67 		else { return mRight->InsertNode(n); }
     68 	}
     69 	else// i==mItem this should never happen
     70 	{
     71 		//error
     72 		return false;
     73 	}
     74 }
     75 
     76 bool Node::InsertNodeAtRoot(Node* n)
     77 {
     78 	if (mParent != NULL)
     79 	{
     80 		return mParent->InsertNodeAtRoot(n);
     81 	}
     82 	else
     83 	{
     84 		bool r = InsertNode(n);
     85 		return r;
     86 	}
     87 }
     88 
     89 void Node::Delete()
     90 {
     91 	if (mParent == NULL) //If the node being deleted is the root.
     92 	{
     93 		mItem = 0;
     94 		mData = NULL;
     95 		return;
     96 	}
     97 	else if (mParent->mLeft == this ) { mParent->mLeft = NULL;  }
     98 	else if (mParent->mRight == this) { mParent->mRight = NULL; }
     99 	else 
    100 	{
    101 		assert(false);
    102 		return; //node listed as parent is does not have this node as a child. Tree broken.
    103 	}
    104 		 if (mLeft != NULL) 
    105 		 {
    106 			 InsertNodeAtRoot(mLeft); 
    107 			 mLeft->Delete();
    108 		 }
    109 		 if (mRight != NULL)
    110 		 {
    111 			 InsertNodeAtRoot(mRight); 	
    112 			 mRight->Delete();
    113 		 }
    114 	delete this;
    115 }
    116 
    117 void Node::rotate_left()
    118 {
    119 	Node* parent_i = mParent;
    120 	Node* left_i  = mLeft;
    121 	Node* right_i = mRight;
    122 	
    123 		 if (mParent->mLeft == this) { mParent->AttachLeft(left_i); }
    124 	else if (mParent->mRight == this) { mParent->AttachRight(left_i); }
    125 
    126 	Node* orphan = left_i->mLeft;
    127 	left_i->AttachLeft(this);
    128 
    129 	mRight->AttachRight(orphan);
    130 }
    131 
    132 void Node::rotate_right()
    133 {
    134 	Node* parent_i = mParent;
    135 	Node* left_i = mLeft;
    136 	Node* right_i = mRight;
    137 
    138 		 if (mParent->mLeft == this) { mParent->AttachLeft(right_i); }
    139 	else if (mParent->mRight == this) { mParent->AttachRight(right_i); }
    140 
    141 	Node* orphan = right_i->mRight;
    142 	left_i->AttachRight(this);
    143 
    144 	mRight->AttachLeft(orphan);
    145 }