Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef __itkLevelOrderTreeIterator_h
00018 #define __itkLevelOrderTreeIterator_h
00019
00020 #include <queue>
00021 #include <climits>
00022 #include <itkTreeIteratorBase.h>
00023
00024 namespace itk {
00025
00026 template <class TTreeType>
00027 class LevelOrderTreeIterator : public TreeIteratorBase<TTreeType>
00028 {
00029 public:
00030
00032 typedef LevelOrderTreeIterator Self;
00033 typedef TreeIteratorBase<TTreeType> Superclass;
00034 typedef TTreeType TreeType;
00035 typedef typename TTreeType::ValueType ValueType;
00036 typedef typename Superclass::TreeNodeType TreeNodeType;
00037
00039 LevelOrderTreeIterator( TreeType* tree, int endLevel = INT_MAX, const TreeNodeType* start = NULL);
00040 LevelOrderTreeIterator( TreeType* tree, int startLevel, int endLevel, const TreeNodeType* start = NULL);
00042
00043 virtual ~LevelOrderTreeIterator() {};
00044
00046 int GetType() const;
00047
00049 int GetStartLevel() const;
00050
00052 int GetEndLevel() const;
00053
00055 int GetLevel() const;
00056
00058 TreeIteratorBase<TTreeType>* Clone();
00059
00061 const Self & operator=(const Self & iterator)
00062 {
00063 this->Superclass::operator=(iterator);
00064 m_StartLevel = iterator.m_StartLevel;
00065 m_EndLevel = iterator.m_EndLevel;
00066 m_Queue = iterator.m_Queue;
00067 return *this;
00068 }
00070
00071
00072 protected:
00073
00075 const ValueType& Next();
00076
00078 bool HasNext() const;
00079
00080 private:
00081
00082 const TreeNodeType* FindNextNode() const;
00083 const TreeNodeType* FindNextNodeHelp() const;
00084 int GetLevel( const TreeNodeType* node ) const;
00085 int m_StartLevel;
00086 int m_EndLevel;
00087 mutable std::queue<const TreeNodeType*> m_Queue;
00088
00089 };
00090
00091
00093 template <class TTreeType>
00094 LevelOrderTreeIterator<TTreeType>
00095 ::LevelOrderTreeIterator( TTreeType* tree, int endLevel, const TreeNodeType* start)
00096 :TreeIteratorBase<TTreeType>(tree,start)
00097 {
00098 m_StartLevel = -1;
00099 m_EndLevel = endLevel;
00100 if ( start != NULL )
00101 {
00102 m_Queue.push( start );
00103 this->m_Position = const_cast<TreeNodeType*>(start);
00104 }
00105 else
00106 {
00107 if(tree->GetRoot())
00108 {
00109 m_Queue.push( dynamic_cast<const TreeNodeType*>(tree->GetRoot()) );
00110 this->m_Position = const_cast<TreeNodeType*>(dynamic_cast<const TreeNodeType*>(tree->GetRoot()));
00111 }
00112 }
00113 this->m_Begin = this->m_Position;
00114 }
00116
00118 template <class TTreeType>
00119 LevelOrderTreeIterator<TTreeType>
00120 ::LevelOrderTreeIterator( TTreeType* tree, int startLevel, int endLevel, const TreeNodeType* start)
00121 :TreeIteratorBase<TTreeType>(tree,start)
00122 {
00123 m_StartLevel = startLevel;
00124 m_EndLevel = endLevel;
00125 if ( start != NULL )
00126 {
00127 m_Queue.push( start );
00128 this->m_Position = const_cast<TreeNodeType*>(start);
00129 }
00130 else
00131 {
00132 if(tree->GetRoot())
00133 {
00134 m_Queue.push( dynamic_cast<const TreeNodeType*>(tree->GetRoot()) );
00135 this->m_Position = const_cast<TreeNodeType*>(dynamic_cast<const TreeNodeType*>(tree->GetRoot()));
00136 }
00137 }
00138 this->m_Begin = this->m_Position;
00139 }
00141
00143 template <class TTreeType>
00144 int
00145 LevelOrderTreeIterator<TTreeType>::GetType() const
00146 {
00147 return TreeIteratorBase<TTreeType>::LEVELORDER;
00148 }
00149
00151 template <class TTreeType>
00152 bool
00153 LevelOrderTreeIterator<TTreeType>::HasNext() const
00154 {
00155 if(const_cast<TreeNodeType*>(FindNextNode()))
00156 {
00157 return true;
00158 }
00159 return false;
00160 }
00162
00164 template <class TTreeType>
00165 const typename LevelOrderTreeIterator<TTreeType>::ValueType&
00166 LevelOrderTreeIterator<TTreeType>::Next()
00167 {
00168 this->m_Position = const_cast<TreeNodeType* >(FindNextNode());
00169 return this->m_Position->Get();
00170 }
00172
00174 template <class TTreeType>
00175 int LevelOrderTreeIterator<TTreeType>::GetStartLevel() const
00176 {
00177 return m_StartLevel;
00178 }
00179
00181 template <class TTreeType>
00182 int
00183 LevelOrderTreeIterator<TTreeType>::GetEndLevel() const
00184 {
00185 return m_EndLevel;
00186 }
00187
00189 template <class TTreeType>
00190 const typename LevelOrderTreeIterator<TTreeType>::TreeNodeType*
00191 LevelOrderTreeIterator<TTreeType>::FindNextNode() const
00192 {
00193 int level;
00194 const TreeNodeType* node;
00195
00196 do
00197 {
00198 node = FindNextNodeHelp();
00199 if ( node == NULL )
00200 {
00201 return NULL;
00202 }
00203 level = GetLevel( node );
00204 if ( level > m_EndLevel )
00205 {
00206 return NULL;
00207 }
00208 }
00209 while ( level < m_StartLevel );
00210
00211 return node;
00212 }
00213
00215 template <class TTreeType>
00216 int
00217 LevelOrderTreeIterator<TTreeType>::GetLevel() const
00218 {
00219 if( this->m_Position == NULL )
00220 {
00221 return -1;
00222 }
00223
00224 int level = 0;
00225 TreeNodeType* node = this->m_Position;
00226 while( node->HasParent() && node != this->m_Root )
00227 {
00228 node = dynamic_cast<TreeNodeType*>(node->GetParent());
00229 level++;
00230 }
00231 return level;
00232 }
00233
00235 template <class TTreeType>
00236 int
00237 LevelOrderTreeIterator<TTreeType>::GetLevel( const TreeNodeType* node ) const
00238 {
00239 if( node == NULL )
00240 {
00241 return -1;
00242 }
00243 int level = 0;
00245
00246 while( node->HasParent() && node != this->m_Root )
00247 {
00248 node = dynamic_cast<const TreeNodeType*>(node->GetParent());
00249 level++;
00250 }
00251 return level;
00252 }
00253
00255 template <class TTreeType>
00256 const typename LevelOrderTreeIterator<TTreeType>::TreeNodeType*
00257 LevelOrderTreeIterator<TTreeType>::FindNextNodeHelp() const
00258 {
00259 if( m_Queue.empty() )
00260 {
00261 return NULL;
00262 }
00263
00264 const TreeNodeType *currentNode = m_Queue.front();
00265 m_Queue.pop();
00266
00267 if ( currentNode == NULL)
00268 {
00269 return NULL;
00270 }
00271
00272 int size = currentNode->CountChildren();
00273
00274 for ( int i=0; i < size; i++ )
00275 {
00276 TreeNodeType *child = dynamic_cast<TreeNodeType*>(currentNode->GetChild( i ));
00277 if ( child != NULL )
00278 {
00279 m_Queue.push(child);
00280 }
00281 }
00282
00283
00284 if(currentNode == this->m_Root)
00285 {
00286 currentNode = const_cast<TreeNodeType*>(FindNextNodeHelp());
00287 }
00288 return currentNode;
00289 }
00290
00292 template <class TTreeType>
00293 TreeIteratorBase<TTreeType>* LevelOrderTreeIterator<TTreeType>::Clone()
00294 {
00295 LevelOrderTreeIterator<TTreeType>* clone = new LevelOrderTreeIterator<TTreeType>( const_cast<TTreeType*>(this->m_Tree), m_StartLevel, m_EndLevel );
00296 *clone = *this;
00297 return clone;
00298 }
00300
00301 }
00302
00303 #endif
00304