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: 2008-05-26 02:36:52 $
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 __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     node = FindNextNodeHelp();
00198     if ( node == NULL )
00199       {
00200       return NULL;
00201       }
00202     level = GetLevel( node );
00203     if ( level > m_EndLevel )
00204       {
00205       return NULL;
00206       }
00207   } while ( level < m_StartLevel );
00208 
00209   return node;
00210 }
00211 
00213 template <class TTreeType>
00214 int 
00215 LevelOrderTreeIterator<TTreeType>::GetLevel() const
00216 {
00217   if( this->m_Position == NULL )
00218     {
00219     return -1;
00220     }
00221 
00222   int level = 0;
00223   TreeNodeType* node = this->m_Position;
00224   while( node->HasParent() && node != this->m_Root ) 
00225     {
00226     node = dynamic_cast<TreeNodeType*>(node->GetParent());
00227     level++;
00228     }
00229   return level;
00230 }
00231 
00233 template <class TTreeType>
00234 int 
00235 LevelOrderTreeIterator<TTreeType>::GetLevel( const TreeNodeType* node ) const
00236 {
00237   if( node == NULL )
00238     {
00239     return -1;
00240     }
00241   int level = 0;
00243 
00244   while( node->HasParent() && node != this->m_Root )
00245     {
00246     node = dynamic_cast<const TreeNodeType*>(node->GetParent());
00247     level++;
00248     }
00249   return level;
00250 }
00251 
00253 template <class TTreeType>
00254 const typename LevelOrderTreeIterator<TTreeType>::TreeNodeType* 
00255 LevelOrderTreeIterator<TTreeType>::FindNextNodeHelp() const
00256 {
00257   if( m_Queue.empty() )
00258     {
00259     return NULL;
00260     }
00261 
00262   const TreeNodeType *currentNode = m_Queue.front();
00263   m_Queue.pop();
00264 
00265   if ( currentNode == NULL)
00266     {
00267     return NULL;
00268     }
00269 
00270   int size = currentNode->CountChildren();
00271 
00272   for ( int i=0; i < size; i++ ) 
00273     {
00274     TreeNodeType *child = dynamic_cast<TreeNodeType*>(currentNode->GetChild( i ));
00275     if ( child != NULL )
00276       {
00277       m_Queue.push(child);
00278       }
00279     }
00280 
00281   // If the current node is the root we try again
00282   if(currentNode == this->m_Root)
00283     {
00284     currentNode = const_cast<TreeNodeType*>(FindNextNodeHelp());
00285     }
00286   return currentNode;
00287 }
00288 
00290 template <class TTreeType>
00291 TreeIteratorBase<TTreeType>* LevelOrderTreeIterator<TTreeType>::Clone() 
00292 {
00293   LevelOrderTreeIterator<TTreeType>* clone = new LevelOrderTreeIterator<TTreeType>( const_cast<TTreeType*>(this->m_Tree), m_StartLevel, m_EndLevel );
00294   *clone = *this;
00295   return clone;
00296 }
00298 
00299 
00300 
00301 } // end namespace itk
00302 
00303 #endif
00304 

Generated at Wed Nov 5 22:38:57 2008 for ITK by doxygen 1.5.1 written by Dimitri van Heesch, © 1997-2000