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 itkInOrderTreeIterator_h 19 #define itkInOrderTreeIterator_h 20 21 #include "itkTreeIteratorBase.h" 22 23 namespace itk 24 { 25 template< typename TTreeType > 26 class InOrderTreeIterator:public TreeIteratorBase< TTreeType > 27 { 28 public: 29 30 /** Typedefs */ 31 using Self = InOrderTreeIterator; 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 /** Constructors */ 39 InOrderTreeIterator(TreeType & start); 40 InOrderTreeIterator(TreeType *tree, TreeNodeType *start = nullptr); 41 42 /** Get the type of iterator */ 43 NodeType GetType() const override; 44 45 /** Clone function */ 46 TreeIteratorBase< TTreeType > * Clone() override; 47 48 protected: 49 50 /** Return the next node */ 51 const ValueType & Next() override; 52 53 /** Return true if the next node exists */ 54 bool HasNext() const override; 55 56 private: 57 58 /** Find the next node */ 59 const TreeNodeType * FindNextNode() const; 60 }; 61 62 /** Constructor */ 63 template< typename TTreeType > InOrderTreeIterator(TTreeType & start)64InOrderTreeIterator< TTreeType >::InOrderTreeIterator(TTreeType & start): 65 TreeIteratorBase< TTreeType >(start) 66 {} 67 68 /** Constructor */ 69 template< typename TTreeType > InOrderTreeIterator(TTreeType * tree,TreeNodeType * start)70InOrderTreeIterator< TTreeType >::InOrderTreeIterator(TTreeType *tree, TreeNodeType *start): 71 TreeIteratorBase< TTreeType >(tree, start) 72 {} 73 74 /** Get the type of the iterator */ 75 template< typename TTreeType > 76 typename InOrderTreeIterator< TTreeType >::NodeType GetType()77InOrderTreeIterator< TTreeType >::GetType() const 78 { 79 return TreeIteratorBase< TTreeType >::INORDER; 80 } 81 82 /** Return true if the next node exists */ 83 template< typename TTreeType > HasNext()84bool InOrderTreeIterator< TTreeType >::HasNext() const 85 { 86 if ( const_cast< TreeNodeType * >( FindNextNode() ) != nullptr ) 87 { 88 return true; 89 } 90 return false; 91 } 92 93 /** Return the next node */ 94 template< typename TTreeType > 95 const typename InOrderTreeIterator< TTreeType >::ValueType & Next()96InOrderTreeIterator< TTreeType >::Next() 97 { 98 this->m_Position = const_cast< TreeNodeType * >( FindNextNode() ); 99 return this->m_Position->Get(); 100 } 101 102 /** Find the next node */ 103 template< typename TTreeType > 104 const typename InOrderTreeIterator< TTreeType >::TreeNodeType * FindNextNode()105InOrderTreeIterator< TTreeType >::FindNextNode() const 106 { 107 if ( this->m_Position == nullptr ) 108 { 109 return nullptr; 110 } 111 112 if ( this->m_Position->HasChildren() ) 113 { 114 return this->m_Position->GetChild(0); 115 } 116 117 if ( !this->m_Position->HasParent() ) 118 { 119 return nullptr; 120 } 121 122 TreeNodeType *child = this->m_Position; 123 TreeNodeType *parent = this->m_Position->GetParent(); 124 125 int childPosition = parent->ChildPosition(child); 126 int lastChildPosition = parent->CountChildren() - 1; 127 128 while ( childPosition < lastChildPosition ) 129 { 130 TreeNodeType *help = parent->GetChild(childPosition + 1); 131 if ( help != nullptr ) 132 { 133 return help; 134 } 135 childPosition++; 136 } 137 138 while ( parent->HasParent() ) 139 { 140 child = parent; 141 parent = parent->GetParent(); 142 143 // Subtree 144 if ( parent->ChildPosition(this->m_Root) >= 0 ) 145 { 146 return nullptr; 147 } 148 childPosition = parent->ChildPosition(child); 149 lastChildPosition = parent->CountChildren() - 1; 150 151 while ( childPosition < lastChildPosition ) 152 { 153 TreeNodeType *help = parent->GetChild(childPosition + 1); 154 if ( help != nullptr ) 155 { 156 return help; 157 } 158 } 159 } 160 return nullptr; 161 } 162 163 /** Clone function */ 164 template< typename TTreeType > Clone()165TreeIteratorBase< TTreeType > *InOrderTreeIterator< TTreeType >::Clone() 166 { 167 auto * clone = new InOrderTreeIterator( const_cast< TTreeType * >( this->m_Tree ) ); 168 169 *clone = *this; 170 return clone; 171 } 172 } // end namespace itk 173 174 #endif 175