TapestryEngine

A 2D Platformer Game Engine
Log | Files | Refs

234b2330b40c5322a99503b351822263be2b7d35.svn-base (2662B)

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