TapestryEngine

A 2D Platformer Game Engine
Log | Files | Refs

8c5b67be4eeaa1f8561d26d9c7803eb48381abfb.svn-base (2984B)

      1 #ifndef BINARY_TREE_H
      2 #define BINARY_TREE_H
      3 
      4 #define NULL 0
      5 
      6 
      7 class Node
      8 {
      9 public:
     10 
     11 	Node() : mParent(NULL), mLeft(NULL), mRight(NULL), mColor(RED)
     12 	{}
     13 
     14 	Node(Node* parent, int item, void* data) : mItem(item), mData(data), mParent(parent), mLeft(NULL), mRight(NULL), mColor(RED)
     15 	{}
     16 
     17 	Node(int item, void* data) : mItem(item), mData(data), mParent(NULL), mLeft(NULL), mRight(NULL), mColor(BLACK) //Used to create debugging root node w/test data
     18 	{}
     19 
     20 //	~Node()
     21 //	{
     22 //		mParent = NULL;
     23 //		mRight = NULL;
     24 //		mLeft = NULL;
     25 //		mData = NULL;
     26 //	}
     27 
     28 	bool nInsert(int i, void* data);
     29 	
     30 	Node* nSearch(int i);
     31 
     32 	int nSize(int i = 0);
     33 
     34 	Node** nDump(int* index, Node** contents = 0); //Should always be called with no arguments, arguements only used for recursion.
     35 
     36 	bool nInsertNode(Node* n);
     37 
     38 	bool nInsertNodeAtRoot(Node* n);
     39 
     40 	void nDelete();
     41 
     42 	void rotate_left();
     43 	void rotate_right();
     44 
     45 	int GetItem()
     46 	{
     47 		return mItem;
     48 	}
     49 
     50 	void* GetData()
     51 	{
     52 		if (mData != NULL)
     53 		{
     54 			return mData;
     55 		}
     56 		else
     57 		{
     58 			return NULL;
     59 		}
     60 	}
     61 
     62 	void AttachLeft(Node* n)
     63 	{
     64 		n->mParent = this;
     65 		mLeft = n;
     66 	}
     67 
     68 	void AttachRight(Node* n)
     69 	{
     70 		n->mParent = this;
     71 		mRight = n;
     72 	}
     73 
     74 	void SwapColor()
     75 	{
     76 		if (mColor == RED) { mColor = BLACK; }
     77 		else               { mColor = RED; }
     78 	}
     79 
     80 	Node* mParent;
     81 	Node* mLeft;
     82 	Node* mRight;
     83 
     84 protected:
     85 
     86 	enum { RED, BLACK } mColor;
     87 
     88 	int mItem;
     89 
     90 	void* mData;
     91 };
     92 
     93 
     94 class BinaryTree
     95 {
     96 public:
     97 
     98 	BinaryTree() : mRoot(NULL)
     99 	{
    100 	}
    101 
    102 	BinaryTree(Node* Root) : mRoot(Root)
    103 	{
    104 	}
    105 
    106 	bool Insert(int i, void* data)
    107 	{
    108 		if (mRoot != NULL)
    109 		{
    110 			return mRoot->nInsert(i, data);
    111 		}
    112 		else //mRoot == NULL -> Tree is empty
    113 		{
    114 			mRoot = new Node(i, data);
    115 			return true;
    116 		}
    117 	}
    118 
    119 	bool InsertNode(Node* node)
    120 	{	
    121 		if (mRoot != NULL)
    122 		{
    123 			return mRoot->nInsertNode(node);
    124 		}
    125 		else //mRoot == NULL -> Tree is empty
    126 		{
    127 			node->mParent = NULL;
    128 			mRoot = node;
    129 			return true;
    130 		}
    131 	}
    132 
    133 	Node* Search(int i)
    134 	{
    135 		if (mRoot != NULL)
    136 		{
    137 			return mRoot->nSearch(i);
    138 		}
    139 		return NULL;
    140 	}
    141 
    142 	int Size(int i = 0)
    143 	{
    144 		if (mRoot != NULL)
    145 		{
    146 			return mRoot->nSize(i);
    147 		}
    148 		return -1;
    149 	}
    150 
    151 	Node** Dump(Node** contents = 0)
    152 	{
    153 		if (mRoot != NULL)
    154 		{
    155 			int index = 0;
    156 			return mRoot->nDump(&index, contents);
    157 		}
    158 		return NULL;
    159 	}
    160 
    161 	void DeleteNode(int node_item)
    162 	{
    163 		Node* target = Search(node_item);
    164 		if (target == mRoot) { mRoot = NULL; }
    165 		else if (target->mParent->mLeft == target) { target->mParent->mLeft = NULL; }
    166 		else if (target->mParent->mRight == target) { target->mParent->mRight = NULL; }
    167 		else
    168 		{
    169 			//assert(false);
    170 			return; //node listed as parent is does not have this node as a child. Tree broken.
    171 		}
    172 		if (target->mLeft != NULL)
    173 		{
    174 			InsertNode(target->mLeft);
    175 			//target->mLeft->nDelete(); //this stuff is all broken. fix it tommorrow
    176 		}
    177 		if (target->mRight != NULL)
    178 		{
    179 			InsertNode(target->mRight);
    180 			//target->mRight->nDelete();
    181 		}
    182 		delete target; 
    183 	}
    184 
    185 
    186 	void Delete()
    187 	{
    188 		mRoot->nDelete();
    189 	}
    190 
    191 
    192 protected:
    193 
    194 	Node* mRoot;
    195 };
    196 #endif