ITK
4.1.0
Insight Segmentation and Registration Toolkit
|
00001 /*========================================================================= 00002 * 00003 * Copyright Insight Software Consortium 00004 * 00005 * Licensed under the Apache License, Version 2.0 (the "License"); 00006 * you may not use this file except in compliance with the License. 00007 * You may obtain a copy of the License at 00008 * 00009 * http://www.apache.org/licenses/LICENSE-2.0.txt 00010 * 00011 * Unless required by applicable law or agreed to in writing, software 00012 * distributed under the License is distributed on an "AS IS" BASIS, 00013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00014 * See the License for the specific language governing permissions and 00015 * limitations under the License. 00016 * 00017 *=========================================================================*/ 00018 #ifndef __itkPostOrderTreeIterator_h 00019 #define __itkPostOrderTreeIterator_h 00020 00021 #include "itkTreeIteratorBase.h" 00022 00023 namespace itk 00024 { 00025 template< class TTreeType > 00026 class PostOrderTreeIterator:public TreeIteratorBase< TTreeType > 00027 { 00028 public: 00029 00031 typedef PostOrderTreeIterator Self; 00032 typedef TreeIteratorBase< TTreeType > Superclass; 00033 typedef TTreeType TreeType; 00034 typedef typename TTreeType::ValueType ValueType; 00035 typedef typename Superclass::TreeNodeType TreeNodeType; 00036 typedef typename Superclass::NodeType NodeType; 00037 00039 PostOrderTreeIterator(TreeType *tree); 00040 00042 NodeType GetType() const; 00043 00045 TreeIteratorBase< TTreeType > * Clone(); 00046 00047 protected: 00049 const ValueType & Next(); 00050 00052 bool HasNext() const; 00053 00054 protected: 00055 00056 const TreeNodeType * FindNextNode() const; 00057 00058 const TreeNodeType * FindMostRightLeaf(TreeNodeType *node) const; 00059 00060 const TreeNodeType * FindSister(TreeNodeType *node) const; 00061 }; 00062 00064 template< class TTreeType > 00065 PostOrderTreeIterator< TTreeType >::PostOrderTreeIterator(TTreeType *tree): 00066 TreeIteratorBase< TTreeType >(tree, NULL) 00067 { 00068 if ( tree->GetRoot() == 0 ) 00069 { 00070 this->m_Begin = 0; 00071 } 00072 else 00073 { 00074 const TreeNodeType *root = dynamic_cast<const TreeNodeType *>(tree->GetRoot()); 00075 if(root == 0) 00076 { 00077 itkGenericExceptionMacro(<< "Can't downcast root node to TreeNodeType *"); 00078 } 00079 this->m_Position = const_cast<TreeNodeType *>(root); 00080 this->m_Position = const_cast< TreeNodeType * >( FindMostRightLeaf(this->m_Position) ); 00081 this->m_Begin = this->m_Position; 00082 } 00083 } 00085 00087 template< class TTreeType > 00088 typename PostOrderTreeIterator< TTreeType >::NodeType 00089 PostOrderTreeIterator< TTreeType >::GetType() const 00090 { 00091 return TreeIteratorBase< TTreeType >::POSTORDER; 00092 } 00093 00095 template< class TTreeType > 00096 bool 00097 PostOrderTreeIterator< TTreeType >::HasNext() const 00098 { 00099 if ( const_cast< TreeNodeType * >( FindNextNode() ) != NULL ) 00100 { 00101 return true; 00102 } 00103 return false; 00104 } 00106 00108 template< class TTreeType > 00109 const typename PostOrderTreeIterator< TTreeType >::ValueType & 00110 PostOrderTreeIterator< TTreeType >::Next() 00111 { 00112 this->m_Position = const_cast< TreeNodeType * >( FindNextNode() ); 00113 return this->m_Position->Get(); 00114 } 00116 00118 template< class TTreeType > 00119 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType * 00120 PostOrderTreeIterator< TTreeType >::FindNextNode() const 00121 { 00122 if ( this->m_Position == NULL || this->m_Position == this->m_Root ) 00123 { 00124 return NULL; 00125 } 00126 TreeNodeType *sister = const_cast< TreeNodeType * >( FindSister(this->m_Position) ); 00128 00129 if ( sister != NULL ) 00130 { 00131 return FindMostRightLeaf(sister); 00132 } 00133 if(this->m_Position->GetParent() == 0) 00134 { 00135 return 0; 00136 } 00137 TreeNodeType *rval = dynamic_cast<TreeNodeType *>(this->m_Position->GetParent()); 00138 if(rval == 0) 00139 { 00140 itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *"); 00141 } 00142 return rval; 00143 } 00144 00146 template< class TTreeType > 00147 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType * 00148 PostOrderTreeIterator< TTreeType >::FindSister(TreeNodeType *node) const 00149 { 00150 if ( !node->HasParent() ) 00151 { 00152 return NULL; 00153 } 00154 00155 TreeNodeType *parent = dynamic_cast<TreeNodeType *>(node->GetParent()); 00156 if(parent == 0) 00157 { 00158 itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *"); 00159 } 00160 00161 int childPosition = parent->ChildPosition(node); 00162 int lastChildPosition = parent->CountChildren() - 1; 00163 00164 while ( childPosition < lastChildPosition ) 00165 { 00166 if(parent->GetChild(childPosition + 1) == 0) 00167 { 00168 childPosition++; 00169 } 00170 else 00171 { 00172 TreeNodeType *sister = dynamic_cast<TreeNodeType *>(parent->GetChild(childPosition + 1)); 00173 if ( sister == 0) 00174 { 00175 itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *"); 00176 } 00177 return sister; 00178 } 00179 } 00180 return NULL; 00181 } 00182 00184 template< class TTreeType > 00185 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType * 00186 PostOrderTreeIterator< TTreeType >::FindMostRightLeaf(TreeNodeType *node) const 00187 { 00188 while ( node->HasChildren() ) 00189 { 00190 TreeNodeType *helpNode; 00191 int childCount = node->CountChildren(); 00192 int i = 0; 00194 00195 do 00196 { 00197 if(node->GetChild(i) == 0) 00198 { 00199 helpNode = 0; 00200 } 00201 else 00202 { 00203 helpNode = dynamic_cast<TreeNodeType *>(node->GetChild(i)); 00204 if(helpNode == 0) 00205 { 00206 itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *"); 00207 } 00208 } 00209 i++; 00210 } 00211 while ( helpNode == NULL && i < childCount ); 00212 00213 if ( helpNode == NULL ) 00214 { 00215 return node; 00216 } 00217 node = helpNode; 00218 } 00219 return node; 00220 } 00221 00223 template< class TTreeType > 00224 TreeIteratorBase< TTreeType > *PostOrderTreeIterator< TTreeType >::Clone() 00225 { 00226 PostOrderTreeIterator< TTreeType > *clone = 00227 new PostOrderTreeIterator< TTreeType >( const_cast< TTreeType * >( this->m_Tree ) ); 00228 *clone = *this; 00229 return clone; 00230 } 00231 } // end namespace itk 00233 00234 #endif 00235