00001 /*! \file 00002 * X-Forge Util <br> 00003 * Copyright 2000-2003 Fathammer Ltd 00004 * 00005 * \brief N-tree template 00006 * 00007 * $Id: XFuNTree.h,v 1.8 2003/03/20 13:19:59 jetro Exp $ 00008 * $Date: 2003/03/20 13:19:59 $ 00009 * $Revision: 1.8 $ 00010 */ 00011 00012 #ifndef XFUNTREE_H_INCLUDED 00013 #define XFUNTREE_H_INCLUDED 00014 00015 #include <xfutil/XFuNTreeNode.h> 00016 #include <xfutil/XFuNTreeAbstractIterator.h> 00017 #include <xfutil/XFuNTreeRandomAccessIterator.h> 00018 #include <xfutil/XFuNTreePreOrderIterator.h> 00019 #include <xfutil/XFuNTreePostOrderIterator.h> 00020 00021 00022 //! Generic N-tree template. 00023 template<class T> class XFuNTree 00024 { 00025 public: 00026 00027 typedef XFuNTreeAbstractIterator<T> iterator; 00028 typedef XFuNTreeRandomAccessIterator<T> randomAccessIterator; 00029 typedef XFuNTreePreOrderIterator<T> preOrderIterator; 00030 typedef XFuNTreePostOrderIterator<T> postOrderIterator; 00031 00032 //! Returns a random iterator pointing to the root of the tree. 00033 /*! \return Random iterator pointing to the root of the tree 00034 */ 00035 randomAccessIterator beginRandomAccess() const; 00036 00037 //! Returns a pre-order iterator pointing to the first node in iteration. 00038 preOrderIterator beginPreOrder() const; 00039 00040 //! Returns a post-order iterator pointing to the first node in iteration. 00041 /*! \return PostOrder iterator pointing to the first node in iteration 00042 */ 00043 postOrderIterator beginPostOrder() const; 00044 00045 //! Returns an iterator pointing to an empty node. 00046 iterator end() const; 00047 00048 //! Returns the amount of nodes in the tree. 00049 /*! \return Amount of nodes in the tree. 00050 */ 00051 UINT32 size() const; 00052 00053 //! Adds a new child node to a certain node. 00054 /*! 00055 * If the tree is empty, the node will be added as the root. 00056 * If all child nodes are already reserved, the operation fails. 00057 * \param aIterator Iterator pointing to the node where the new node should be added as a child. 00058 * \param aNewData Internal data of the node. 00059 * \return A valid iterator if the addition succeeds, or an invalid iterator if an error occured. 00060 */ 00061 iterator add(iterator aIterator, T aNewData); 00062 00063 //! Adds a new child node to a certain node as the Nth child node. 00064 /*! 00065 * If the tree is empty, the node will be added as the root. 00066 * If the Nth node is already reserved, the operation fails. 00067 * \param aIterator Iterator pointing to the node where the new node should be added as a child. 00068 * \param aIndex Index to which child node should the new node be created as. 00069 * \param aNewData Internal data of the node. 00070 * \return A valid iterator if the addition succeeds, or an invalid iterator if an error occured. 00071 */ 00072 iterator add(iterator aIterator, const UINT32 aIndex, T aNewData); 00073 00074 //! Inserts new internal data to the Nth child node in a certain node. 00075 /*! 00076 * \param aIterator Iterator pointing to the parent node. 00077 * \param aIndex Index to which child node should the new internal data be inserted to. 00078 * \param aNewData Internal data of the node. 00079 * \return 1 if the insertion succeeds, 0 if an error occured. 00080 */ 00081 INT insert(iterator aIterator, const UINT32 aIndex, T aNewData); 00082 00083 //! Removes a node with the given internal data from the list. 00084 /*! 00085 * \param aData Internal data of the node which is to be removed. 00086 * \return 1 if the removal succeeds, 0 otherwise. 00087 */ 00088 INT remove(const T aData); 00089 00090 //! Removes a node pointed to by an iterator. 00091 /*! 00092 * \param aData Iterator pointing to a node. 00093 * \return 1 if the removal succeeds, 0 otherwise. 00094 */ 00095 INT remove(iterator &aIterator); 00096 00097 //! Creates an empty N-tree. 00098 /*! 00099 * \param aChildNodes amount of child nodes per each node. 00100 */ 00101 XFuNTree(const UINT32 aChildNodes); 00102 //! Destructor. 00103 ~XFuNTree(); 00104 00105 protected: 00106 00107 //! Number of nodes in tree. 00108 UINT32 mNodes; 00109 00110 //! Number of child nodes in each node. 00111 UINT32 mChildNodes; 00112 00113 //! Pointer to root node in tree. 00114 XFuNTreeNode<T> *mRoot; 00115 00116 //! Removes a node from the tree. 00117 /*! \param aNode Pointer to the node 00118 */ 00119 void removeNode(XFuNTreeNode<T> *aNode); 00120 }; 00121 00122 00123 template<class T> void XFuNTree<T>::removeNode(XFuNTreeNode<T> *aNode) 00124 { 00125 if (aNode != NULL) 00126 { 00127 UINT32 i; 00128 00129 for (i = 0; i < mChildNodes; ++i) 00130 { 00131 if (aNode->mChildren[i] != NULL) 00132 removeNode(aNode->mChildren[i]); 00133 } 00134 00135 if (aNode->mParent != NULL) 00136 aNode->mParent->mChildren[aNode->mIndexInParent] = NULL; 00137 00138 mNodes--; 00139 00140 delete aNode; 00141 } 00142 } 00143 00144 00145 template<class T> 00146 XFuNTree<T>::randomAccessIterator XFuNTree<T>::beginRandomAccess() const 00147 { 00148 return randomAccessIterator(mRoot, mChildNodes); 00149 } 00150 00151 00152 template<class T> 00153 XFuNTree<T>::preOrderIterator XFuNTree<T>::beginPreOrder() const 00154 { 00155 return preOrderIterator(mRoot, mNodes, mChildNodes); 00156 } 00157 00158 00159 template<class T> 00160 XFuNTree<T>::postOrderIterator XFuNTree<T>::beginPostOrder() const 00161 { 00162 return postOrderIterator(mRoot, mNodes, mChildNodes); 00163 } 00164 00165 00166 template<class T> UINT32 XFuNTree<T>::size() const 00167 { 00168 return mNodes; 00169 } 00170 00171 00172 template<class T> XFuNTree<T>::iterator XFuNTree<T>::add(iterator aIterator, 00173 const T aNewData) 00174 { 00175 XFuNTreeNode<T> *node = aIterator.mNode; 00176 XFuNTreeNode<T> *temp = NULL; 00177 00178 if ((!mNodes) && (node == NULL)) 00179 { 00180 temp = new XFuNTreeNode<T>(mChildNodes, aNewData); 00181 00182 mRoot = temp; 00183 mNodes++; 00184 00185 return iterator(temp, mChildNodes); 00186 } 00187 else if (aIterator.isValid()) 00188 { 00189 temp = new XFuNTreeNode<T>(mChildNodes, aNewData); 00190 00191 UINT32 i; 00192 00193 while (i < node->mChildNodes) 00194 { 00195 if (node->mChildren[i] == NULL) 00196 { 00197 temp->mParent = node; 00198 temp->mIndexInParent = i; 00199 node->mChildren[i] = temp; 00200 node->mAllocatedChildNodes++; 00201 00202 mNodes++; 00203 break; 00204 } 00205 00206 i++; 00207 } 00208 00209 return iterator(temp, mChildNodes); 00210 } 00211 00212 return iterator(NULL, 0); 00213 } 00214 00215 00216 template<class T> XFuNTree<T>::iterator XFuNTree<T>::add(iterator aIterator, 00217 const UINT32 aIndex, 00218 const T aNewData) 00219 { 00220 if (aIterator.isValid()) 00221 { 00222 XFuNTreeNode<T> *node = aIterator.mNode; 00223 XFuNTreeNode<T> *temp = NULL; 00224 00225 if (node->mChildren[aIndex] == NULL) 00226 { 00227 temp = new XFuNTreeNode<T>(mChildNodes, aNewData); 00228 00229 temp->mParent = node; 00230 temp->mIndexInParent = aIndex; 00231 node->mChildren[aIndex] = temp; 00232 node->mAllocatedChildNodes++; 00233 00234 mNodes++; 00235 } 00236 00237 return iterator(temp, mChildNodes); 00238 } 00239 00240 return iterator(NULL, 0); 00241 } 00242 00243 00244 template<class T> INT XFuNTree<T>::insert(iterator aIterator, 00245 const UINT32 aIndex, 00246 const T aNewData) 00247 { 00248 if (aIterator.isValid()) 00249 { 00250 XFuNTreeNode<T> *node = aIterator.mNode; 00251 00252 if (node != NULL) 00253 { 00254 if (node->mChildren[aIndex] != NULL) 00255 { 00256 node->mChildren[aIndex]->mData = aNewData; 00257 00258 return 1; 00259 } 00260 } 00261 } 00262 00263 return 0; 00264 } 00265 00266 00267 template<class T> INT XFuNTree<T>::remove(const T aData) 00268 { 00269 /* 00270 XFuLinkedListNode<T> *ptr = mHead; 00271 00272 UINT32 i; 00273 for (i = 0; i < mNodes; ++i) 00274 { 00275 if (ptr != NULL) 00276 { 00277 if (ptr->mData == aData) 00278 { 00279 removeNode(ptr); 00280 return 1; 00281 } 00282 } 00283 00284 ptr = ptr->mNext; 00285 } 00286 */ 00287 return 0; 00288 } 00289 00290 00291 template<class T> INT XFuNTree<T>::remove(iterator &aIterator) 00292 { 00293 if (aIterator.mNode != NULL) 00294 { 00295 XFuNTreeNode<T> *temp = aIterator.mNode; 00296 aIterator.backup(); 00297 00298 removeNode(temp); 00299 00300 return 1; 00301 } 00302 else 00303 return 0; 00304 } 00305 00306 00307 template<class T> XFuNTree<T>::XFuNTree(const UINT32 aChildNodes) 00308 { 00309 mNodes = 0; 00310 mRoot = NULL; 00311 mChildNodes = aChildNodes; 00312 } 00313 00314 00315 template<class T> XFuNTree<T>::~XFuNTree() 00316 { 00317 if (mRoot != NULL) 00318 removeNode(mRoot); 00319 } 00320 00321 00322 #endif // !XFUNTREE_H_INCLUDED
![]() | ||||
![]() |
Confidential Copyright © 2002-2003 Fathammer | with doxygen by Dimitri van Heesch |