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: 2008-01-29 15:27: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 __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 
00078 
00080 template <class TTreeType>
00081 int 
00082 PostOrderTreeIterator<TTreeType>::GetType() const
00083 {
00084   return TreeIteratorBase<TTreeType>::POSTORDER;
00085 }
00086 
00087 
00089 template <class TTreeType>
00090 bool 
00091 PostOrderTreeIterator<TTreeType>::HasNext() const
00092 {
00093   if(const_cast<TreeNodeType* >(FindNextNode()) != NULL)
00094     {
00095     return true;
00096     }
00097   return false;
00098 }
00100 
00102 template <class TTreeType>
00103 const typename PostOrderTreeIterator<TTreeType>::ValueType&
00104 PostOrderTreeIterator<TTreeType>::Next()
00105 { 
00106   this->m_Position = const_cast<TreeNodeType*>(FindNextNode());
00107   return this->m_Position->Get();
00108 }
00110 
00112 template <class TTreeType>
00113 const typename PostOrderTreeIterator<TTreeType>::TreeNodeType* 
00114 PostOrderTreeIterator<TTreeType>::FindNextNode() const
00115 {
00116   if ( this->m_Position == NULL || this->m_Position == this->m_Root )
00117     {
00118     return NULL;
00119     }
00120   TreeNodeType* sister = const_cast<TreeNodeType*>(FindSister( this->m_Position ));
00122 
00123   if ( sister != NULL )
00124     {
00125     return FindMostRightLeaf( sister );
00126     }
00127 
00128   return this->m_Position->GetParent();
00129 }
00130 
00131 
00133 template <class TTreeType>
00134 const typename PostOrderTreeIterator<TTreeType>::TreeNodeType* 
00135 PostOrderTreeIterator<TTreeType>::FindSister( TreeNodeType* node ) const
00136 {
00137   if ( !node->HasParent() )
00138     {
00139     return NULL;
00140     }
00141 
00142   TreeNodeType* parent = node->GetParent();
00143   int childPosition = parent->ChildPosition( node );
00144   int lastChildPosition = parent->CountChildren() - 1;
00145 
00146   while ( childPosition < lastChildPosition ) 
00147     {
00148     TreeNodeType* sister = parent->GetChild( childPosition + 1);
00149 
00150     if ( sister != NULL )
00151       {
00152       return sister;
00153       }
00154     childPosition++;
00155     }
00156   return NULL;
00157 }
00158 
00160 template <class TTreeType>
00161 const typename PostOrderTreeIterator<TTreeType>::TreeNodeType* 
00162 PostOrderTreeIterator<TTreeType>::FindMostRightLeaf(TreeNodeType* node) const
00163 {
00164  while ( node->HasChildren() ) 
00165    {
00166    TreeNodeType* helpNode;
00167    int childCount = node->CountChildren();
00168    int i = 0;
00170 
00171    do 
00172      {
00173      helpNode = node->GetChild( i );
00174      i++;
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 
00200 

Generated at Sat Feb 28 13:17:33 2009 for ITK by doxygen 1.5.6 written by Dimitri van Heesch, © 1997-2000