TapestryEngine

A 2D Platformer Game Engine
Log | Files | Refs

ab369f16f87b16ebd1c3128c1a368a1a90f992f2.svn-base (2342B)

      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) { mLeft = n; return true; }
     51 		else { return mLeft->InsertNode(n); }
     52 	} 
     53 
     54 	else if (mItem < n->mItem)
     55 	{
     56 		if (mRight == NULL) { mRight = n; return true; }
     57 		else { return mRight->InsertNode(n); }
     58 	}
     59 	else// i==mItem this should never happen
     60 	{
     61 		//error
     62 		return false;
     63 	}
     64 }
     65 
     66 bool Node::InsertNodeAtRoot(Node* n)
     67 {
     68 	if (mParent != NULL)
     69 	{
     70 		return mParent->InsertNodeAtRoot(n);
     71 	}
     72 	else
     73 	{
     74 		bool r = InsertNode(n);
     75 		return r;
     76 	}
     77 }
     78 
     79 void Node::Delete()
     80 {
     81 	   	 if (mParent->mLeft == this ) { mParent->mLeft = NULL;  }
     82 	else if (mParent->mRight == this) { mParent->mRight = NULL; }
     83 	else 
     84 	{
     85 		return; //If the node being deleted is the root.
     86 	}
     87 	InsertNodeAtRoot(mLeft);
     88 	InsertNodeAtRoot(mRight);
     89 	mLeft->Delete(); 
     90 	mRight->Delete();
     91 	delete this;
     92 }
     93 
     94 void Node::rotate_left()
     95 {
     96 	Node* parent_i = mParent;
     97 	Node* left_i  = mLeft;
     98 	Node* right_i = mRight;
     99 	
    100 		 if (mParent->mLeft == this) { mParent->AttachLeft(left_i); }
    101 	else if (mParent->mRight == this) { mParent->AttachRight(left_i); }
    102 
    103 	Node* orphan = left_i->mLeft;
    104 	left_i->AttachLeft(this);
    105 
    106 	mRight->AttachRight(orphan);
    107 }
    108 
    109 void Node::rotate_right()
    110 {
    111 	Node* parent_i = mParent;
    112 	Node* left_i = mLeft;
    113 	Node* right_i = mRight;
    114 
    115 		 if (mParent->mLeft == this) { mParent->AttachLeft(right_i); }
    116 	else if (mParent->mRight == this) { mParent->AttachRight(right_i); }
    117 
    118 	Node* orphan = right_i->mRight;
    119 	left_i->AttachRight(this);
    120 
    121 	mRight->AttachLeft(orphan);
    122 }