00001 /*========================================================================= 00002 00003 Program: Insight Segmentation & Registration Toolkit 00004 Module: $RCSfile: itkInOrderTreeIterator.h,v $ 00005 Language: C++ 00006 Date: $Date: 2009-02-05 19:04:57 $ 00007 Version: $Revision: 1.6 $ 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 InOrderTreeIterator Self; 00031 typedef TreeIteratorBase<TTreeType> Superclass; 00032 typedef TTreeType TreeType; 00033 typedef typename TTreeType::ValueType ValueType; 00034 typedef typename Superclass::TreeNodeType TreeNodeType; 00035 00037 InOrderTreeIterator( TreeType& start ); 00038 InOrderTreeIterator( TreeType* tree, TreeNodeType* start=NULL); 00040 00042 int GetType() const; 00043 00045 TreeIteratorBase<TTreeType>* Clone(); 00046 00047 protected: 00048 00050 const ValueType& Next(); 00051 00053 bool HasNext() const; 00054 00055 private: 00056 00058 const TreeNodeType* FindNextNode() const; 00059 00060 }; 00061 00062 00064 template <class TTreeType> 00065 InOrderTreeIterator<TTreeType>::InOrderTreeIterator( TTreeType& start ) 00066 :TreeIteratorBase<TTreeType>(start) 00067 { 00068 } 00069 00070 00072 template <class TTreeType> 00073 InOrderTreeIterator<TTreeType>::InOrderTreeIterator( TTreeType* tree, TreeNodeType* start) 00074 :TreeIteratorBase<TTreeType>(tree,start) 00075 { 00076 } 00077 00079 template <class TTreeType> 00080 int 00081 InOrderTreeIterator<TTreeType>::GetType() const 00082 { 00083 return TreeIteratorBase<TTreeType>::INORDER; 00084 } 00085 00086 00088 template <class TTreeType> 00089 bool InOrderTreeIterator<TTreeType>::HasNext() const 00090 { 00091 if ( const_cast<TreeNodeType*>(FindNextNode()) != NULL ) 00092 { 00093 return true; 00094 } 00095 return false; 00096 } 00098 00099 00101 template <class TTreeType> 00102 const typename InOrderTreeIterator<TTreeType>::ValueType& 00103 InOrderTreeIterator<TTreeType>::Next() 00104 { 00105 this->m_Position = const_cast<TreeNodeType* >(FindNextNode()); 00106 return this->m_Position->Get(); 00107 } 00109 00110 00112 template <class TTreeType> 00113 const typename InOrderTreeIterator<TTreeType>::TreeNodeType* 00114 InOrderTreeIterator<TTreeType>::FindNextNode() const 00115 { 00116 if ( this->m_Position == NULL ) 00117 { 00118 return NULL; 00119 } 00120 00121 if ( this->m_Position->HasChildren() ) 00122 { 00123 return this->m_Position->GetChild(0); 00124 } 00125 00126 if ( !this->m_Position->HasParent() ) 00127 { 00128 return NULL; 00129 } 00130 00131 TreeNodeType* child = this->m_Position; 00132 TreeNodeType* parent = this->m_Position->GetParent(); 00133 00134 int childPosition = parent->ChildPosition( child ); 00135 int lastChildPosition = parent->CountChildren() - 1; 00136 00137 while ( childPosition < lastChildPosition ) 00138 { 00139 TreeNodeType* help = parent->GetChild( childPosition + 1 ); 00140 if ( help != NULL ) 00141 { 00142 return help; 00143 } 00144 childPosition++; 00145 } 00146 00147 while ( parent->HasParent() ) 00148 { 00149 child = parent; 00150 parent = parent->GetParent(); 00151 00152 // Subtree 00153 if( parent->ChildPosition( this->m_Root ) >= 0 ) 00154 { 00155 return NULL; 00156 } 00157 childPosition = parent->ChildPosition(child); 00158 lastChildPosition = parent->CountChildren() - 1; 00159 00160 while ( childPosition < lastChildPosition ) 00161 { 00162 TreeNodeType* help = parent->GetChild( childPosition + 1 ); 00163 if ( help != NULL ) 00164 { 00165 return help; 00166 } 00167 } 00168 } 00169 return NULL; 00170 } 00171 00173 template <class TTreeType> 00174 TreeIteratorBase<TTreeType>* InOrderTreeIterator<TTreeType>::Clone() 00175 { 00176 InOrderTreeIterator* clone = new InOrderTreeIterator( const_cast<TTreeType*>(this->m_Tree) ); 00177 *clone = *this; 00178 return clone; 00179 } 00181 00182 } // end namespace itk 00183 00184 #endif 00185