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

itkPreOrderTreeIterator.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkPreOrderTreeIterator.h,v $
00005   Language:  C++
00006   Date:      $Date: 2008-06-20 20:28:42 $
00007   Version:   $Revision: 1.4 $
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 

Generated at Tue Jul 29 21:48:06 2008 for ITK by doxygen 1.5.1 written by Dimitri van Heesch, © 1997-2000