00001 /*! \file 00002 * X-Forge Util <br> 00003 * Copyright 2000-2003 Fathammer Ltd 00004 * 00005 * \brief N-Tree post-order iterator template 00006 * 00007 * $Id: XFuNTreePostOrderIterator.h,v 1.6 2003/03/20 13:19:59 jetro Exp $ 00008 * $Date: 2003/03/20 13:19:59 $ 00009 * $Revision: 1.6 $ 00010 */ 00011 00012 #ifndef XFUNTREEPOSTORDERITERATOR_H_INCLUDED 00013 #define XFUNTREEPOSTORDERITERATOR_H_INCLUDED 00014 00015 #include <xfutil/XFuNTreeAbstractIterator.h> 00016 #include <xfutil/XFuDynamicArray.h> 00017 00018 template<class T> class XFuNTree; 00019 template<class T> class XFuNTreeNode; 00020 00021 00022 template<class T> class XFuNTreePostOrderIterator : public XFuNTreeAbstractIterator<T> 00023 { 00024 public: 00025 00026 //! Assignment operator overload. 00027 void operator=(const XFuNTreePostOrderIterator &aClone); 00028 00029 //! Advances to the next node, pre-operation. 00030 /*! 00031 * \return Reference to next node. 00032 */ 00033 XFuNTreePostOrderIterator<T> & operator++(); 00034 00035 //! Advances to the next node, post-operation. 00036 /*! 00037 * \return Next node. 00038 */ 00039 XFuNTreePostOrderIterator<T> operator++(int); 00040 00041 //! Creates an empty iterator. 00042 XFuNTreePostOrderIterator(); 00043 //! Creates an iterator pointing to a node. 00044 XFuNTreePostOrderIterator(XFuNTreeNode<T> *aNode, const UINT32 aNodes, 00045 const UINT32 aChildNodes); 00046 //! Clones an iterator. 00047 XFuNTreePostOrderIterator(const XFuNTreePostOrderIterator<T> &aClone); 00048 00049 //! Destructor. 00050 ~XFuNTreePostOrderIterator(); 00051 00052 protected: 00053 00054 //! Number of nodes in tree. 00055 UINT32 mNodes; 00056 00057 //! Stack used for saving pointers to nodes. 00058 XFuDynamicArray<XFuNTreeNode<T> *> *mNodeStack; 00059 //! Stack used for saving information on visitation of node. 00060 XFuDynamicArray<INT> *mBoolStack; 00061 }; 00062 00063 00064 template<class T> 00065 void XFuNTreePostOrderIterator<T>::operator=( 00066 const XFuNTreePostOrderIterator &aClone) 00067 { 00068 mNode = aClone.mNode; 00069 mNodes = aClone.mNodes; 00070 mChildNodes = aClone.mChildNodes; 00071 00072 if ((aClone.mNodeStack != NULL) && (aClone.mBoolStack != NULL)) 00073 { 00074 if (mNodeStack == NULL) 00075 mNodeStack = XFuDynamicArray<XFuNTreeNode<T> *>::create( 00076 aClone.mNodeStack->maxSize()); 00077 00078 if (mBoolStack == NULL) 00079 mBoolStack = XFuDynamicArray<INT>::create( 00080 aClone.mBoolStack->maxSize()); 00081 00082 if ((mNodeStack == NULL) || (mBoolStack == NULL)) 00083 { 00084 mNode = NULL; 00085 mNodes = 0; 00086 mChildNodes = 0; 00087 return; 00088 } 00089 00090 UINT32 i, lastElement; 00091 XFuNTreeNode<T> *temp = NULL; 00092 INT boolTemp; 00093 00094 lastElement = aClone.mNodeStack->size(); 00095 for (i = 0; i < lastElement; ++i) 00096 { 00097 temp = aClone.mNodeStack->get(i); 00098 mNodeStack->put(i, temp); 00099 } 00100 00101 lastElement = aClone.mBoolStack->size(); 00102 for (i = 0; i < lastElement; ++i) 00103 { 00104 boolTemp = aClone.mBoolStack->get(i); 00105 mBoolStack->put(i, boolTemp); 00106 } 00107 } 00108 else 00109 { 00110 if (mNodeStack != NULL) 00111 { 00112 delete mNodeStack; 00113 mNodeStack = NULL; 00114 } 00115 00116 if (mBoolStack != NULL) 00117 { 00118 delete mBoolStack; 00119 mBoolStack = NULL; 00120 } 00121 } 00122 } 00123 00124 00125 template<class T> 00126 XFuNTreePostOrderIterator<T> & XFuNTreePostOrderIterator<T>::operator++() 00127 { 00128 if (!mNodeStack->isEmpty()) 00129 { 00130 mNode = mNodeStack->remove(); 00131 INT temp = mBoolStack->remove(); 00132 00133 if (!temp) 00134 { 00135 UINT32 i, j; 00136 00137 while (!mNode->isLeaf()) 00138 { 00139 mNodeStack->put(mNode); 00140 mBoolStack->put(1); 00141 00142 for (j = 0; j < mChildNodes; ++j) 00143 { 00144 if (mNode->isValid(j)) 00145 { 00146 for (i = (mChildNodes - 1); i > j; --i) 00147 { 00148 if (mNode->isValid(i)) 00149 { 00150 mNodeStack->put(mNode->getChild(i)); 00151 mBoolStack->put(0); 00152 } 00153 } 00154 00155 mNode = mNode->getChild(j); 00156 break; 00157 } 00158 } 00159 } 00160 } 00161 } 00162 else 00163 { 00164 mNode = NULL; 00165 } 00166 00167 return *this; 00168 } 00169 00170 00171 template<class T> 00172 XFuNTreePostOrderIterator<T> XFuNTreePostOrderIterator<T>::operator++(int) 00173 { 00174 XFuNTreePostOrderIterator<T> newIt = XFuNTreePostOrderIterator<T>(*this); 00175 00176 /* 00177 if (mNode != NULL) mNode = mNode->mNext; 00178 00179 return newIt; 00180 */ 00181 } 00182 00183 00184 template<class T> XFuNTreePostOrderIterator<T>::XFuNTreePostOrderIterator() 00185 { 00186 mNode = NULL; 00187 mNodes = 0; 00188 mChildNodes = 0; 00189 mNodeStack = NULL; 00190 mBoolStack = NULL; 00191 } 00192 00193 00194 template<class T> 00195 XFuNTreePostOrderIterator<T>::XFuNTreePostOrderIterator(XFuNTreeNode<T> *aNode, 00196 const UINT32 aNodes, 00197 const UINT32 aChildNodes) 00198 { 00199 if (aNode != NULL) 00200 { 00201 mNode = aNode; 00202 mNodes = aNodes; 00203 mChildNodes = aChildNodes; 00204 00205 mNodeStack = XFuDynamicArray<XFuNTreeNode<T> *>::create(aNodes); 00206 mBoolStack = XFuDynamicArray<INT>::create(aNodes); 00207 00208 if ((mNodeStack == NULL) || (mBoolStack == NULL)) 00209 { 00210 mNode = NULL; 00211 mNodes = 0; 00212 mChildNodes = 0; 00213 } 00214 else 00215 { 00216 UINT32 i, j; 00217 00218 while (!mNode->isLeaf()) 00219 { 00220 mNodeStack->put(mNode); 00221 mBoolStack->put(1); 00222 00223 for (j = 0; j < mChildNodes; ++j) 00224 { 00225 if (mNode->isValid(j)) 00226 { 00227 for (i = (mChildNodes - 1); i > j; --i) 00228 { 00229 if (mNode->isValid(i)) 00230 { 00231 mNodeStack->put(mNode->getChild(i)); 00232 mBoolStack->put(0); 00233 } 00234 } 00235 00236 mNode = mNode->getChild(j); 00237 break; 00238 } 00239 } 00240 } 00241 } 00242 } 00243 } 00244 00245 00246 template<class T> 00247 XFuNTreePostOrderIterator<T>::XFuNTreePostOrderIterator( 00248 const XFuNTreePostOrderIterator<T> &aClone) 00249 { 00250 mNode = aClone.mNode; 00251 mNodes = aClone.mNodes; 00252 mChildNodes = aClone.mChildNodes; 00253 00254 if ((aClone.mNodeStack != NULL) && (aClone.mBoolStack != NULL)) 00255 { 00256 if (mNodeStack == NULL) 00257 mNodeStack = XFuDynamicArray<XFuNTreeNode<T> *>::create( 00258 aClone.mNodeStack->maxSize()); 00259 00260 if (mBoolStack == NULL) 00261 mBoolStack = XFuDynamicArray<INT>::create( 00262 aClone.mBoolStack->maxSize()); 00263 00264 if ((mNodeStack == NULL) || (mBoolStack == NULL)) 00265 { 00266 mNode = NULL; 00267 mNodes = 0; 00268 mChildNodes = 0; 00269 return; 00270 } 00271 00272 UINT32 i, lastElement; 00273 XFuNTreeNode<T> *temp = NULL; 00274 INT boolTemp = NULL; 00275 00276 lastElement = aClone.mNodeStack->size(); 00277 for (i = 0; i < lastElement; ++i) 00278 { 00279 temp = aClone.mNodeStack->get(i); 00280 mNodeStack->put(i, temp); 00281 } 00282 00283 lastElement = aClone.mBoolStack->size(); 00284 for (i = 0; i < lastElement; ++i) 00285 { 00286 boolTemp = aClone.mBoolStack->get(i); 00287 mBoolStack->put(i, boolTemp); 00288 } 00289 } 00290 else 00291 { 00292 delete mNodeStack; 00293 delete mBoolStack; 00294 mNodeStack = NULL; 00295 mBoolStack = NULL; 00296 } 00297 } 00298 00299 00300 template<class T> 00301 XFuNTreePostOrderIterator<T>::~XFuNTreePostOrderIterator() 00302 { 00303 delete mNodeStack; 00304 delete mBoolStack; 00305 } 00306 00307 00308 #endif // !XFUNTREEPOSTORDERITERATOR_H_INCLUDED
![]() | ||||
![]() |
Confidential Copyright © 2002-2003 Fathammer | with doxygen by Dimitri van Heesch |