1 /*========================================================================= 2 * 3 * Copyright Insight Software Consortium 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0.txt 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 *=========================================================================*/ 18 #ifndef itkPostOrderTreeIterator_h 19 #define itkPostOrderTreeIterator_h 20 21 #include "itkTreeIteratorBase.h" 22 23 namespace itk 24 { 25 template< typename TTreeType > 26 class PostOrderTreeIterator:public TreeIteratorBase< TTreeType > 27 { 28 public: 29 30 /** Typedefs */ 31 using Self = PostOrderTreeIterator; 32 using Superclass = TreeIteratorBase< TTreeType >; 33 using TreeType = TTreeType; 34 using ValueType = typename TTreeType::ValueType; 35 using TreeNodeType = typename Superclass::TreeNodeType; 36 using NodeType = typename Superclass::NodeType; 37 38 /** Constructor */ 39 PostOrderTreeIterator(TreeType *tree); 40 41 /** Get the type of the iterator */ 42 NodeType GetType() const override; 43 44 /** Clone function */ 45 TreeIteratorBase< TTreeType > * Clone() override; 46 47 protected: 48 /** Return the next node */ 49 const ValueType & Next() override; 50 51 /** Return true if the next node exists */ 52 bool HasNext() const override; 53 54 protected: 55 56 const TreeNodeType * FindNextNode() const; 57 58 const TreeNodeType * FindMostRightLeaf(TreeNodeType *node) const; 59 60 const TreeNodeType * FindSister(TreeNodeType *node) const; 61 }; 62 63 /** Constructor */ 64 template< typename TTreeType > PostOrderTreeIterator(TTreeType * tree)65PostOrderTreeIterator< TTreeType >::PostOrderTreeIterator(TTreeType *tree): 66 TreeIteratorBase< TTreeType >(tree, nullptr) 67 { 68 if ( tree->GetRoot() == nullptr ) 69 { 70 this->m_Begin = nullptr; 71 } 72 else 73 { 74 const auto * root = dynamic_cast<const TreeNodeType *>(tree->GetRoot()); 75 if(root == nullptr) 76 { 77 itkGenericExceptionMacro(<< "Can't downcast root node to TreeNodeType *"); 78 } 79 this->m_Position = const_cast<TreeNodeType *>(root); 80 this->m_Position = const_cast< TreeNodeType * >( FindMostRightLeaf(this->m_Position) ); 81 this->m_Begin = this->m_Position; 82 } 83 } 84 85 /** Return the type of the iterator */ 86 template< typename TTreeType > 87 typename PostOrderTreeIterator< TTreeType >::NodeType GetType()88PostOrderTreeIterator< TTreeType >::GetType() const 89 { 90 return TreeIteratorBase< TTreeType >::POSTORDER; 91 } 92 93 /** Return true if the next node exists */ 94 template< typename TTreeType > 95 bool HasNext()96PostOrderTreeIterator< TTreeType >::HasNext() const 97 { 98 if ( const_cast< TreeNodeType * >( FindNextNode() ) != nullptr ) 99 { 100 return true; 101 } 102 return false; 103 } 104 105 /** Go to the next node */ 106 template< typename TTreeType > 107 const typename PostOrderTreeIterator< TTreeType >::ValueType & Next()108PostOrderTreeIterator< TTreeType >::Next() 109 { 110 this->m_Position = const_cast< TreeNodeType * >( FindNextNode() ); 111 return this->m_Position->Get(); 112 } 113 114 /** Find the next node */ 115 template< typename TTreeType > 116 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType * FindNextNode()117PostOrderTreeIterator< TTreeType >::FindNextNode() const 118 { 119 if ( this->m_Position == nullptr || this->m_Position == this->m_Root ) 120 { 121 return nullptr; 122 } 123 auto * sister = const_cast< TreeNodeType * >( FindSister(this->m_Position) ); 124 125 if ( sister != nullptr ) 126 { 127 return FindMostRightLeaf(sister); 128 } 129 if(this->m_Position->GetParent() == nullptr) 130 { 131 return nullptr; 132 } 133 auto * rval = dynamic_cast<TreeNodeType *>(this->m_Position->GetParent()); 134 if(rval == nullptr) 135 { 136 itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *"); 137 } 138 return rval; 139 } 140 141 /** Find the sister node */ 142 template< typename TTreeType > 143 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType * FindSister(TreeNodeType * node)144PostOrderTreeIterator< TTreeType >::FindSister(TreeNodeType *node) const 145 { 146 if ( !node->HasParent() ) 147 { 148 return nullptr; 149 } 150 151 auto * parent = dynamic_cast<TreeNodeType *>(node->GetParent()); 152 if(parent == nullptr) 153 { 154 itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *"); 155 } 156 157 int childPosition = parent->ChildPosition(node); 158 int lastChildPosition = parent->CountChildren() - 1; 159 160 while ( childPosition < lastChildPosition ) 161 { 162 if(parent->GetChild(childPosition + 1) == nullptr) 163 { 164 childPosition++; 165 } 166 else 167 { 168 auto * sister = dynamic_cast<TreeNodeType *>(parent->GetChild(childPosition + 1)); 169 if ( sister == nullptr) 170 { 171 itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *"); 172 } 173 return sister; 174 } 175 } 176 return nullptr; 177 } 178 179 /** Find the most right leaf */ 180 template< typename TTreeType > 181 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType * FindMostRightLeaf(TreeNodeType * node)182PostOrderTreeIterator< TTreeType >::FindMostRightLeaf(TreeNodeType *node) const 183 { 184 while ( node->HasChildren() ) 185 { 186 TreeNodeType *helpNode; 187 int childCount = node->CountChildren(); 188 int i = 0; 189 190 do 191 { 192 if(node->GetChild(i) == nullptr) 193 { 194 helpNode = nullptr; 195 } 196 else 197 { 198 helpNode = dynamic_cast<TreeNodeType *>(node->GetChild(i)); 199 if(helpNode == nullptr) 200 { 201 itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *"); 202 } 203 } 204 i++; 205 } 206 while ( helpNode == nullptr && i < childCount ); 207 208 if ( helpNode == nullptr ) 209 { 210 return node; 211 } 212 node = helpNode; 213 } 214 return node; 215 } 216 217 /** Clone function */ 218 template< typename TTreeType > Clone()219TreeIteratorBase< TTreeType > *PostOrderTreeIterator< TTreeType >::Clone() 220 { 221 auto * clone = new PostOrderTreeIterator< TTreeType >( const_cast< TTreeType * >( this->m_Tree ) ); 222 *clone = *this; 223 return clone; 224 } 225 } // end namespace itk 226 227 #endif 228