00001 /*========================================================================= 00002 00003 Program: Insight Segmentation & Registration Toolkit 00004 Module: $RCSfile: itkInOrderTreeIterator.h,v $ 00005 Language: C++ 00006 Date: $Date: 2004/12/11 20:29:18 $ 00007 Version: $Revision: 1.2 $ 00008 00009 Copyright (c) Insight Software Consortium. All rights reserved. 00010 See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details. 00011 00012 This software is distributed WITHOUT ANY WARRANTY; without even 00013 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 00014 PURPOSE. See the above copyright notices for more information. 00015 00016 =========================================================================*/ 00017 #ifndef __itkInOrderTreeIterator_h 00018 #define __itkInOrderTreeIterator_h 00019 00020 #include <itkTreeIteratorBase.h> 00021 00022 namespace itk{ 00023 00024 template <class TTreeType> 00025 class InOrderTreeIterator : public TreeIteratorBase<TTreeType> 00026 { 00027 public: 00028 00030 typedef TreeIteratorBase<TTreeType> Superclass; 00031 typedef TTreeType TreeType; 00032 typedef typename TTreeType::ValueType ValueType; 00033 typedef typename Superclass::TreeNodeType TreeNodeType; 00034 00036 InOrderTreeIterator( TreeType& start ); 00037 InOrderTreeIterator( TreeType* tree, TreeNodeType* start=NULL); 00039 00041 int GetType() const; 00042 00044 TreeIteratorBase<TTreeType>* Clone(); 00045 00046 protected: 00047 00049 const ValueType& Next(); 00050 00052 bool HasNext() const; 00053 00054 private: 00055 00057 const TreeNodeType* FindNextNode() const; 00058 00059 }; 00060 00061 00063 template <class TTreeType> 00064 InOrderTreeIterator<TTreeType>::InOrderTreeIterator( TTreeType& start ) 00065 :TreeIteratorBase<TTreeType>(start) 00066 { 00067 } 00068 00069 00071 template <class TTreeType> 00072 InOrderTreeIterator<TTreeType>::InOrderTreeIterator( TTreeType* tree, TreeNodeType* start) 00073 :TreeIteratorBase<TTreeType>(tree,start) 00074 { 00075 } 00076 00078 template <class TTreeType> 00079 int 00080 InOrderTreeIterator<TTreeType>::GetType() const 00081 { 00082 return TreeIteratorBase<TTreeType>::INORDER; 00083 } 00084 00085 00087 template <class TTreeType> 00088 bool InOrderTreeIterator<TTreeType>::HasNext() const 00089 { 00090 if ( const_cast<TreeNodeType*>(FindNextNode()) != NULL ) 00091 { 00092 return true; 00093 } 00094 return false; 00095 } 00097 00098 00100 template <class TTreeType> 00101 const typename InOrderTreeIterator<TTreeType>::ValueType& 00102 InOrderTreeIterator<TTreeType>::Next() 00103 { 00104 this->m_Position = const_cast<TreeNodeType* >(FindNextNode()); 00105 return this->m_Position->Get(); 00106 } 00108 00109 00111 template <class TTreeType> 00112 const typename InOrderTreeIterator<TTreeType>::TreeNodeType* 00113 InOrderTreeIterator<TTreeType>::FindNextNode() const 00114 { 00115 if ( this->m_Position == NULL ) 00116 { 00117 return NULL; 00118 } 00119 00120 if ( this->m_Position->HasChildren() ) 00121 { 00122 return this->m_Position->GetChild(0); 00123 } 00124 00125 if ( !this->m_Position->HasParent() ) 00126 { 00127 return NULL; 00128 } 00129 00130 TreeNodeType* child = this->m_Position; 00131 TreeNodeType* parent = this->m_Position->GetParent(); 00132 00133 int ChildPosition = parent->ChildPosition( child ); 00134 int lastChildPosition = parent->CountChildren() - 1; 00135 00136 while ( ChildPosition < lastChildPosition ) 00137 { 00138 TreeNodeType* help = parent->GetChild( ChildPosition + 1 ); 00139 if ( help != NULL ) 00140 { 00141 return help; 00142 } 00143 ChildPosition++; 00144 } 00145 00146 while ( parent->HasParent() ) 00147 { 00148 child = parent; 00149 parent = parent->GetParent(); 00150 00151 // Subtree 00152 if( parent->ChildPosition( this->m_Root ) >= 0 ) 00153 { 00154 return NULL; 00155 } 00156 ChildPosition = parent->ChildPosition(child); 00157 lastChildPosition = parent->CountChildren() - 1; 00158 00159 while ( ChildPosition < lastChildPosition ) 00160 { 00161 TreeNodeType* help = parent->GetChild( ChildPosition + 1 ); 00162 if ( help != NULL ) 00163 { 00164 return help; 00165 } 00166 } 00167 } 00168 return NULL; 00169 } 00170 00172 template <class TTreeType> 00173 TreeIteratorBase<TTreeType>* InOrderTreeIterator<TTreeType>::Clone() 00174 { 00175 InOrderTreeIterator* clone = new InOrderTreeIterator( const_cast<TTreeType*>(this->m_Tree) ); 00176 *clone = *this; 00177 return clone; 00178 } 00180 00181 } // end namespace itk 00182 00183 #endif 00184