00001 /*========================================================================= 00002 00003 Program: Insight Segmentation & Registration Toolkit 00004 Module: $RCSfile: itkPreOrderTreeIterator.h,v $ 00005 Language: C++ 00006 Date: $Date: 2009-03-03 15:08:00 $ 00007 Version: $Revision: 1.5 $ 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 __itkPreOrderTreeIterator_h 00018 #define __itkPreOrderTreeIterator_h 00019 00020 #include <itkTreeIteratorBase.h> 00021 00022 namespace itk { 00023 00024 template <class TTreeType> 00025 class PreOrderTreeIterator : public TreeIteratorBase<TTreeType> 00026 { 00027 public: 00028 00030 typedef typename TTreeType::ValueType ValueType; 00031 typedef TreeIteratorBase<TTreeType> Superclass; 00032 typedef typename Superclass::TreeNodeType TreeNodeType; 00033 00035 PreOrderTreeIterator( const TTreeType* tree,const TreeNodeType* start = NULL ); 00036 00038 int GetType() const; 00039 00041 TreeIteratorBase<TTreeType>* Clone(); 00042 00043 protected: 00045 const ValueType& Next(); 00046 00048 bool HasNext() const; 00049 00050 private: 00051 00053 const TreeNodeType* FindNextNode() const; 00054 00055 }; 00056 00057 00059 template <class TTreeType> 00060 PreOrderTreeIterator<TTreeType>::PreOrderTreeIterator( const TTreeType* tree, const TreeNodeType* start ) 00061 :TreeIteratorBase<TTreeType>(tree,start) 00062 { 00063 00064 } 00065 00067 template <class TTreeType> 00068 int 00069 PreOrderTreeIterator<TTreeType>::GetType() const 00070 { 00071 return TreeIteratorBase<TTreeType>::PREORDER; 00072 } 00073 00075 template <class TTreeType> 00076 bool 00077 PreOrderTreeIterator<TTreeType>::HasNext() const 00078 { 00079 if ( const_cast<TreeNodeType* >(FindNextNode()) != NULL ) 00080 { 00081 return true; 00082 } 00083 return false; 00084 } 00086 00088 template <class TTreeType> 00089 const typename PreOrderTreeIterator<TTreeType>::ValueType& 00090 PreOrderTreeIterator<TTreeType>::Next() 00091 { 00092 this->m_Position = const_cast<TreeNodeType* >(FindNextNode()); 00093 return this->m_Position->Get(); 00094 } 00096 00098 template <class TTreeType> 00099 const typename PreOrderTreeIterator<TTreeType>::TreeNodeType* 00100 PreOrderTreeIterator<TTreeType>::FindNextNode() const 00101 { 00102 if ( this->m_Position == NULL ) 00103 { 00104 return NULL; 00105 } 00106 if ( this->m_Position->HasChildren() ) 00107 { 00108 return dynamic_cast<const TreeNodeType*>(this->m_Position->GetChild(0)); 00109 } 00111 00112 if ( !this->m_Position->HasParent() ) 00113 { 00114 return NULL; 00115 } 00116 00117 TreeNodeType* child = this->m_Position; 00118 TreeNodeType* parent = dynamic_cast<TreeNodeType*>(this->m_Position->GetParent()); 00119 00120 // Are we a subtree? Then we are done. 00121 if( parent && parent->ChildPosition( this->m_Root ) >= 0 ) 00122 { 00123 return NULL; 00124 } 00125 00126 int childPosition = parent->ChildPosition( child ); 00127 int lastChildPosition = parent->CountChildren() - 1; 00128 00129 while ( childPosition < lastChildPosition ) 00130 { 00131 TreeNodeType* help = dynamic_cast<TreeNodeType*>(parent->GetChild( childPosition + 1 )); 00132 00133 if ( help != NULL ) 00134 { 00135 return help; 00136 } 00137 childPosition++; 00138 } 00139 00140 while ( parent->HasParent() ) 00141 { 00142 child = parent; 00143 parent = dynamic_cast<TreeNodeType*>(parent->GetParent()); 00144 00145 // Subtree 00146 if( parent->ChildPosition( this->m_Root ) >= 0 ) 00147 { 00148 return NULL; 00149 } 00150 00151 childPosition = parent->ChildPosition(child); 00152 lastChildPosition = parent->CountChildren() - 1; 00153 00154 while ( childPosition < lastChildPosition ) 00155 { 00156 TreeNodeType* help = dynamic_cast<TreeNodeType*>(parent->GetChild( childPosition + 1 )); 00157 00158 if ( help != NULL ) 00159 { 00160 return help; 00161 } 00162 } 00163 } 00164 return NULL; 00165 } 00166 00168 template <class TTreeType> 00169 TreeIteratorBase<TTreeType>* PreOrderTreeIterator<TTreeType>::Clone() 00170 { 00171 PreOrderTreeIterator<TTreeType>* clone = new PreOrderTreeIterator<TTreeType>( this->m_Tree, this->m_Position ); 00172 *clone = *this; 00173 return clone; 00174 } 00176 00177 } // end namespace itk 00178 00179 #endif 00180