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

itkPostOrderTreeIterator.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkPostOrderTreeIterator.h,v $
00005   Language:  C++
00006   Date:      $Date: 2004/12/11 20:29:19 $
00007   Version:   $Revision: 1.2 $
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 __itkPostOrderTreeIterator_h
00018 #define __itkPostOrderTreeIterator_h
00019 
00020 #include <itkTreeIteratorBase.h>
00021 
00022 namespace itk{
00023 
00024 template <class TTreeType>
00025 class PostOrderTreeIterator : public TreeIteratorBase<TTreeType> 
00026 {
00027 public:
00028    
00030   typedef TreeIteratorBase<TTreeType>  Superclass;
00031   typedef TTreeType TreeType;
00032   typedef typename TTreeType::ValueType ValueType;
00033   typedef typename Superclass::TreeNodeType TreeNodeType;
00034 
00036   PostOrderTreeIterator(TreeType* tree);
00037 
00039   int GetType() const;
00040 
00042   TreeIteratorBase<TTreeType>* Clone();
00043 
00044 protected:
00046   const ValueType& Next();
00047 
00049   bool HasNext() const;
00050 
00051 protected:
00052 
00053   const TreeNodeType* FindNextNode() const;
00054   const TreeNodeType* FindMostRightLeaf(TreeNodeType* node) const;
00055   const TreeNodeType* FindSister(TreeNodeType* node) const;
00056 
00057 };
00058 
00060 template <class TTreeType>
00061 PostOrderTreeIterator<TTreeType>::PostOrderTreeIterator( TTreeType* tree)
00062     :TreeIteratorBase<TTreeType>(tree,NULL) 
00063 {
00064   this->m_Position = const_cast<TreeNode<ValueType>*>(tree->GetRoot());
00065 
00066   if ( this->m_Position == NULL )
00067   {
00068     this->m_Begin = NULL;
00069   }
00070   else
00071   {
00072     this->m_Position =const_cast<TreeNodeType* >(FindMostRightLeaf(this->m_Position));
00073     this->m_Begin = this->m_Position;
00074   }  
00075 }
00076 
00077 
00079 template <class TTreeType>
00080 int 
00081 PostOrderTreeIterator<TTreeType>::GetType() const
00082 {
00083   return TreeIteratorBase<TTreeType>::POSTORDER;
00084 }
00085 
00086 
00088 template <class TTreeType>
00089 bool 
00090 PostOrderTreeIterator<TTreeType>::HasNext() const
00091 {
00092   if(const_cast<TreeNodeType* >(FindNextNode()) != NULL)
00093     {
00094     return true;
00095     }
00096   return false;
00097 }
00099 
00101 template <class TTreeType>
00102 const typename PostOrderTreeIterator<TTreeType>::ValueType&
00103 PostOrderTreeIterator<TTreeType>::Next()
00104 { 
00105   this->m_Position = const_cast<TreeNodeType*>(FindNextNode());
00106   return this->m_Position->Get();
00107 }
00109 
00111 template <class TTreeType>
00112 const typename PostOrderTreeIterator<TTreeType>::TreeNodeType* 
00113 PostOrderTreeIterator<TTreeType>::FindNextNode() const
00114 {
00115   if ( this->m_Position == NULL || this->m_Position == this->m_Root )
00116     {
00117     return NULL;
00118     }
00119   TreeNodeType* sister = const_cast<TreeNodeType*>(FindSister( this->m_Position ));
00121 
00122   if ( sister != NULL )
00123     {
00124     return FindMostRightLeaf( sister );
00125     }
00126 
00127   return this->m_Position->GetParent();
00128 }
00129 
00130 
00132 template <class TTreeType>
00133 const typename PostOrderTreeIterator<TTreeType>::TreeNodeType* 
00134 PostOrderTreeIterator<TTreeType>::FindSister( TreeNodeType* node ) const
00135 {
00136   if ( !node->HasParent() )
00137     {
00138     return NULL;
00139     }
00140 
00141   TreeNodeType* parent = node->GetParent();
00142   int childPosition = parent->ChildPosition( node );
00143   int lastChildPosition = parent->CountChildren() - 1;
00144 
00145   while ( childPosition < lastChildPosition ) 
00146     {
00147     TreeNodeType* sister = parent->GetChild( childPosition + 1);
00148 
00149     if ( sister != NULL )
00150       {
00151       return sister;
00152       }
00153     childPosition++;
00154     }
00155   return NULL;
00156 }
00157 
00159 template <class TTreeType>
00160 const typename PostOrderTreeIterator<TTreeType>::TreeNodeType* 
00161 PostOrderTreeIterator<TTreeType>::FindMostRightLeaf(TreeNodeType* node) const
00162 {
00163  while ( node->HasChildren() ) 
00164    {
00165    TreeNodeType* helpNode;
00166    int childCount = node->CountChildren();
00167    int i = 0;
00169 
00170    do 
00171      {
00172      helpNode = node->GetChild( i );
00173      i++;
00174      } while ( helpNode == NULL && i < childCount );
00175 
00176    if ( helpNode == NULL )
00177      {
00178      return node;
00179      }
00180    node = helpNode;
00181    }
00182   return node;
00183 }
00184 
00186 template <class TTreeType>
00187 TreeIteratorBase<TTreeType>* PostOrderTreeIterator<TTreeType>::Clone() 
00188 {
00189   PostOrderTreeIterator<TTreeType>* clone = new PostOrderTreeIterator<TTreeType>( const_cast<TTreeType*>(this->m_Tree) );
00190   *clone = *this;
00191   return clone;
00192 }
00194 
00195 } // end namespace itk
00196 
00197 #endif
00198 
00199 

Generated at Sun Sep 23 13:55:21 2007 for ITK by doxygen 1.5.1 written by Dimitri van Heesch, © 1997-2000