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-01-29 15:27:42 $
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 __itkLevelOrderTreeIterator_h
00018 #define __itkLevelOrderTreeIterator_h
00019 
00020 #include <queue>
00021 #include <itkTreeIteratorBase.h>
00022 
00023 namespace itk{
00024 
00025 template <class TTreeType>
00026 class LevelOrderTreeIterator : public TreeIteratorBase<TTreeType> 
00027 {
00028 public:
00029 
00031   typedef LevelOrderTreeIterator                Self;
00032   typedef TreeIteratorBase<TTreeType>           Superclass; 
00033   typedef TTreeType                             TreeType;
00034   typedef typename TTreeType::ValueType         ValueType;
00035   typedef typename Superclass::TreeNodeType     TreeNodeType;
00036 
00038   LevelOrderTreeIterator( TreeType* tree, int endLevel = INT_MAX, const TreeNodeType* start = NULL);
00039   LevelOrderTreeIterator( TreeType* tree, int startLevel, int endLevel, const TreeNodeType* start = NULL);
00041 
00042   virtual ~LevelOrderTreeIterator() {};
00043 
00045   int GetType() const ;
00046 
00048   int GetStartLevel() const;
00049 
00051   int GetEndLevel() const;
00052 
00054   int GetLevel() const;
00055 
00057   TreeIteratorBase<TTreeType>* Clone();
00058 
00060   const Self & operator=(const Self & iterator) 
00061     {
00062     this->Superclass::operator=(iterator);
00063     m_StartLevel = iterator.m_StartLevel;
00064     m_EndLevel = iterator.m_EndLevel;
00065     m_Queue = iterator.m_Queue;
00066     return *this;
00067     }
00069 
00070 
00071 protected:
00072 
00074   const ValueType& Next();
00075 
00077   bool HasNext() const;
00078 
00079 private:
00080 
00081   const TreeNodeType* FindNextNode() const;
00082   const TreeNodeType* FindNextNodeHelp() const ;
00083   int GetLevel( const TreeNodeType* node ) const;
00084   int m_StartLevel;
00085   int m_EndLevel;
00086   mutable std::queue<const TreeNodeType*> m_Queue;
00087 
00088 };
00089 
00090 
00092 template <class TTreeType>
00093 LevelOrderTreeIterator<TTreeType>
00094 ::LevelOrderTreeIterator( TTreeType* tree, int endLevel, const TreeNodeType* start)
00095  :TreeIteratorBase<TTreeType>(tree,start)
00096 {
00097   m_StartLevel =  -1;
00098   m_EndLevel = endLevel;
00099   if ( start != NULL )
00100     {
00101     m_Queue.push( start );
00102     this->m_Position = const_cast<TreeNodeType*>(start);
00103     }
00104   else
00105     {
00106     if(tree->GetRoot())
00107       {
00108       m_Queue.push( dynamic_cast<const TreeNodeType*>(tree->GetRoot()) );
00109       this->m_Position = const_cast<TreeNodeType*>(dynamic_cast<const TreeNodeType*>(tree->GetRoot()));
00110       }
00111     }
00112   this->m_Begin = this->m_Position;
00113 }
00115 
00117 template <class TTreeType>
00118 LevelOrderTreeIterator<TTreeType>
00119 ::LevelOrderTreeIterator( TTreeType* tree, int startLevel, int endLevel, const TreeNodeType* start)
00120  :TreeIteratorBase<TTreeType>(tree,start)
00121 {
00122   m_StartLevel = startLevel;
00123   m_EndLevel = endLevel;
00124   if ( start != NULL )
00125     {
00126     m_Queue.push( start );
00127     this->m_Position = const_cast<TreeNodeType*>(start);
00128     }
00129   else
00130     {
00131     if(tree->GetRoot())
00132       {
00133       m_Queue.push( dynamic_cast<const TreeNodeType*>(tree->GetRoot()) );
00134       this->m_Position = const_cast<TreeNodeType*>(dynamic_cast<const TreeNodeType*>(tree->GetRoot()));
00135       }
00136     }
00137   this->m_Begin = this->m_Position;
00138 }
00140 
00142 template <class TTreeType>
00143 int 
00144 LevelOrderTreeIterator<TTreeType>::GetType() const 
00145 {
00146   return TreeIteratorBase<TTreeType>::LEVELORDER;
00147 }
00148 
00150 template <class TTreeType>
00151 bool 
00152 LevelOrderTreeIterator<TTreeType>::HasNext() const
00153 {
00154  if(const_cast<TreeNodeType*>(FindNextNode()))
00155    {
00156    return true;
00157    }
00158   return false;
00159 }
00161 
00163 template <class TTreeType>
00164 const typename LevelOrderTreeIterator<TTreeType>::ValueType&
00165 LevelOrderTreeIterator<TTreeType>::Next() 
00166 {
00167   this->m_Position = const_cast<TreeNodeType* >(FindNextNode());
00168   return this->m_Position->Get();
00169 }
00171 
00173 template <class TTreeType>
00174 int LevelOrderTreeIterator<TTreeType>::GetStartLevel() const
00175 {
00176   return m_StartLevel;
00177 }
00178 
00180 template <class TTreeType>
00181 int 
00182 LevelOrderTreeIterator<TTreeType>::GetEndLevel() const
00183 {
00184   return m_EndLevel;
00185 }
00186 
00188 template <class TTreeType>
00189 const typename LevelOrderTreeIterator<TTreeType>::TreeNodeType*
00190 LevelOrderTreeIterator<TTreeType>::FindNextNode() const
00191 {
00192   int level;
00193   const TreeNodeType* node;
00194 
00195   do{
00196     node = FindNextNodeHelp();
00197     if ( node == NULL )
00198       {
00199       return NULL;
00200       }
00201     level = GetLevel( node );
00202     if ( level > m_EndLevel )
00203       {
00204       return NULL;
00205       }
00206   } while ( level < m_StartLevel );
00207 
00208   return node;
00209 }
00210 
00212 template <class TTreeType>
00213 int 
00214 LevelOrderTreeIterator<TTreeType>::GetLevel() const
00215 {
00216   if( this->m_Position == NULL )
00217     {
00218     return -1;
00219     }
00220 
00221   int level = 0;
00222   TreeNodeType* node = this->m_Position;
00223   while( node->HasParent() && node != this->m_Root ) 
00224     {
00225     node = dynamic_cast<TreeNodeType*>(node->GetParent());
00226     level++;
00227     }
00228   return level;
00229 }
00230 
00232 template <class TTreeType>
00233 int 
00234 LevelOrderTreeIterator<TTreeType>::GetLevel( const TreeNodeType* node ) const
00235 {
00236   if( node == NULL )
00237     {
00238     return -1;
00239     }
00240   int level = 0;
00242 
00243   while( node->HasParent() && node != this->m_Root )
00244     {
00245     node = dynamic_cast<const TreeNodeType*>(node->GetParent());
00246     level++;
00247     }
00248   return level;
00249 }
00250 
00252 template <class TTreeType>
00253 const typename LevelOrderTreeIterator<TTreeType>::TreeNodeType* 
00254 LevelOrderTreeIterator<TTreeType>::FindNextNodeHelp() const
00255 {
00256   if( m_Queue.empty() )
00257     {
00258     return NULL;
00259     }
00260 
00261   const TreeNodeType *currentNode = m_Queue.front();
00262   m_Queue.pop();
00263 
00264   if ( currentNode == NULL)
00265     {
00266     return NULL;
00267     }
00268 
00269   int size = currentNode->CountChildren();
00270 
00271   for ( int i=0; i < size; i++ ) 
00272     {
00273     TreeNodeType *child = dynamic_cast<TreeNodeType*>(currentNode->GetChild( i ));
00274     if ( child != NULL )
00275       {
00276       m_Queue.push(child);
00277       }
00278     }
00279 
00280   // If the current node is the root we try again
00281   if(currentNode == this->m_Root)
00282     {
00283     currentNode = const_cast<TreeNodeType*>(FindNextNodeHelp());
00284     }
00285   return currentNode;
00286 }
00287 
00289 template <class TTreeType>
00290 TreeIteratorBase<TTreeType>* LevelOrderTreeIterator<TTreeType>::Clone() 
00291 {
00292   LevelOrderTreeIterator<TTreeType>* clone = new LevelOrderTreeIterator<TTreeType>( const_cast<TTreeType*>(this->m_Tree), m_StartLevel, m_EndLevel );
00293   *clone = *this;
00294   return clone;
00295 }
00297 
00298 
00299 
00300 } // end namespace itk
00301 
00302 #endif
00303 

Generated at Mon Apr 14 13:22:43 2008 for ITK by doxygen 1.5.1 written by Dimitri van Heesch, © 1997-2000