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: 2009-03-03 15:07:57 $
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 __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 PostOrderTreeIterator               Self;
00031   typedef TreeIteratorBase<TTreeType>         Superclass;
00032   typedef TTreeType                           TreeType;
00033   typedef typename TTreeType::ValueType       ValueType;
00034   typedef typename Superclass::TreeNodeType   TreeNodeType;
00035 
00037   PostOrderTreeIterator(TreeType* tree);
00038 
00040   int GetType() const;
00041 
00043   TreeIteratorBase<TTreeType>* Clone();
00044 
00045 protected:
00047   const ValueType& Next();
00048 
00050   bool HasNext() const;
00051 
00052 protected:
00053 
00054   const TreeNodeType* FindNextNode() const;
00055   const TreeNodeType* FindMostRightLeaf(TreeNodeType* node) const;
00056   const TreeNodeType* FindSister(TreeNodeType* node) const;
00057 
00058 };
00059 
00061 template <class TTreeType>
00062 PostOrderTreeIterator<TTreeType>::PostOrderTreeIterator( TTreeType* tree)
00063     :TreeIteratorBase<TTreeType>(tree,NULL) 
00064 {
00065   this->m_Position = const_cast<TreeNode<ValueType>*>(tree->GetRoot());
00066 
00067   if ( this->m_Position == NULL )
00068     {
00069     this->m_Begin = NULL;
00070     }
00071   else
00072     {
00073     this->m_Position =const_cast<TreeNodeType* >(FindMostRightLeaf(this->m_Position));
00074     this->m_Begin = this->m_Position;
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       }
00175     while ( helpNode == NULL && i < childCount );
00176 
00177     if ( helpNode == NULL )
00178       {
00179       return node;
00180       }
00181     node = helpNode;
00182     }
00183   return node;
00184 }
00185 
00187 template <class TTreeType>
00188 TreeIteratorBase<TTreeType>* PostOrderTreeIterator<TTreeType>::Clone() 
00189 {
00190   PostOrderTreeIterator<TTreeType>* clone = new PostOrderTreeIterator<TTreeType>( const_cast<TTreeType*>(this->m_Tree) );
00191   *clone = *this;
00192   return clone;
00193 }
00195 
00196 } // end namespace itk
00197 
00198 #endif
00199 

Generated at Thu May 28 11:10:42 2009 for ITK by doxygen 1.5.5 written by Dimitri van Heesch, © 1997-2000