Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

XFuNTree.h

Go to the documentation of this file.
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

   
X-Forge Documentation
Confidential
Copyright © 2002-2003 Fathammer
   
Documentation generated
with doxygen
by Dimitri van Heesch