Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

itkLevelOrderTreeIterator.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkLevelOrderTreeIterator.h,v $
00005   Language:  C++
00006   Date:      $Date: 2009-02-05 19:05:00 $
00007   Version:   $Revision: 1.7 $
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 __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   // If the current node is the root we try again
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 } // end namespace itk
00302 
00303 #endif
00304 

Generated at Tue Sep 15 03:50:37 2009 for ITK by doxygen 1.5.8 written by Dimitri van Heesch, © 1997-2000