00001 00002 00003 00004 00005 00006 00007 00008 00009 00010 #ifndef __DS_TREE_H 00011 #define __DS_TREE_H 00012 00013 #include "Export.h" 00014 #include "DS_List.h" 00015 #include "DS_Queue.h" 00016 #include "RakMemoryOverride.h" 00017 00020 namespace DataStructures 00021 { 00022 template <class TreeType> 00023 class RAK_DLL_EXPORT Tree 00024 { 00025 public: 00026 Tree(); 00027 Tree(TreeType &inputData); 00028 ~Tree(); 00029 void LevelOrderTraversal(DataStructures::List<Tree*> &output); 00030 void AddChild(TreeType &newData); 00031 void DeleteDecendants(void); 00032 00033 TreeType data; 00034 DataStructures::List<Tree *> children; 00035 }; 00036 00037 template <class TreeType> 00038 Tree<TreeType>::Tree() 00039 { 00040 00041 } 00042 00043 template <class TreeType> 00044 Tree<TreeType>::Tree(TreeType &inputData) 00045 { 00046 data=inputData; 00047 } 00048 00049 template <class TreeType> 00050 Tree<TreeType>::~Tree() 00051 { 00052 DeleteDecendants(); 00053 } 00054 00055 template <class TreeType> 00056 void Tree<TreeType>::LevelOrderTraversal(DataStructures::List<Tree*> &output) 00057 { 00058 unsigned i; 00059 Tree<TreeType> *node; 00060 DataStructures::Queue<Tree<TreeType>*> queue; 00061 00062 for (i=0; i < children.Size(); i++) 00063 queue.Push(children[i]); 00064 00065 while (queue.Size()) 00066 { 00067 node=queue.Pop(); 00068 output.Insert(node, __FILE__, __LINE__); 00069 for (i=0; i < node->children.Size(); i++) 00070 queue.Push(node->children[i]); 00071 } 00072 } 00073 00074 template <class TreeType> 00075 void Tree<TreeType>::AddChild(TreeType &newData) 00076 { 00077 children.Insert(RakNet::OP_NEW<Tree>(newData, __FILE__, __LINE__)); 00078 } 00079 00080 template <class TreeType> 00081 void Tree<TreeType>::DeleteDecendants(void) 00082 { 00083 /* 00084 DataStructures::List<Tree*> output; 00085 LevelOrderTraversal(output); 00086 unsigned i; 00087 for (i=0; i < output.Size(); i++) 00088 RakNet::OP_DELETE(output[i], __FILE__, __LINE__); 00089 */ 00090 00091 // Already recursive to do this 00092 unsigned int i; 00093 for (i=0; i < children.Size(); i++) 00094 RakNet::OP_DELETE(children[i], __FILE__, __LINE__); 00095 } 00096 } 00097 00098 #endif
1.7.1