ITK  4.1.0
Insight Segmentation and Registration Toolkit
itkPostOrderTreeIterator.h
Go to the documentation of this file.
00001 /*=========================================================================
00002  *
00003  *  Copyright Insight Software Consortium
00004  *
00005  *  Licensed under the Apache License, Version 2.0 (the "License");
00006  *  you may not use this file except in compliance with the License.
00007  *  You may obtain a copy of the License at
00008  *
00009  *         http://www.apache.org/licenses/LICENSE-2.0.txt
00010  *
00011  *  Unless required by applicable law or agreed to in writing, software
00012  *  distributed under the License is distributed on an "AS IS" BASIS,
00013  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  *  See the License for the specific language governing permissions and
00015  *  limitations under the License.
00016  *
00017  *=========================================================================*/
00018 #ifndef __itkPostOrderTreeIterator_h
00019 #define __itkPostOrderTreeIterator_h
00020 
00021 #include "itkTreeIteratorBase.h"
00022 
00023 namespace itk
00024 {
00025 template< class TTreeType >
00026 class PostOrderTreeIterator:public TreeIteratorBase< TTreeType >
00027 {
00028 public:
00029 
00031   typedef PostOrderTreeIterator             Self;
00032   typedef TreeIteratorBase< TTreeType >     Superclass;
00033   typedef TTreeType                         TreeType;
00034   typedef typename TTreeType::ValueType     ValueType;
00035   typedef typename Superclass::TreeNodeType TreeNodeType;
00036   typedef typename Superclass::NodeType     NodeType;
00037 
00039   PostOrderTreeIterator(TreeType *tree);
00040 
00042   NodeType GetType() const;
00043 
00045   TreeIteratorBase< TTreeType > * Clone();
00046 
00047 protected:
00049   const ValueType & Next();
00050 
00052   bool HasNext() const;
00053 
00054 protected:
00055 
00056   const TreeNodeType * FindNextNode() const;
00057 
00058   const TreeNodeType * FindMostRightLeaf(TreeNodeType *node) const;
00059 
00060   const TreeNodeType * FindSister(TreeNodeType *node) const;
00061 };
00062 
00064 template< class TTreeType >
00065 PostOrderTreeIterator< TTreeType >::PostOrderTreeIterator(TTreeType *tree):
00066   TreeIteratorBase< TTreeType >(tree, NULL)
00067 {
00068   if ( tree->GetRoot() == 0 )
00069     {
00070     this->m_Begin = 0;
00071     }
00072   else
00073     {
00074     const TreeNodeType *root = dynamic_cast<const TreeNodeType *>(tree->GetRoot());
00075     if(root == 0)
00076       {
00077       itkGenericExceptionMacro(<< "Can't downcast root node to TreeNodeType *");
00078       }
00079     this->m_Position = const_cast<TreeNodeType *>(root);
00080     this->m_Position = const_cast< TreeNodeType * >( FindMostRightLeaf(this->m_Position) );
00081     this->m_Begin = this->m_Position;
00082     }
00083 }
00085 
00087 template< class TTreeType >
00088 typename PostOrderTreeIterator< TTreeType >::NodeType
00089 PostOrderTreeIterator< TTreeType >::GetType() const
00090 {
00091   return TreeIteratorBase< TTreeType >::POSTORDER;
00092 }
00093 
00095 template< class TTreeType >
00096 bool
00097 PostOrderTreeIterator< TTreeType >::HasNext() const
00098 {
00099   if ( const_cast< TreeNodeType * >( FindNextNode() ) != NULL )
00100     {
00101     return true;
00102     }
00103   return false;
00104 }
00106 
00108 template< class TTreeType >
00109 const typename PostOrderTreeIterator< TTreeType >::ValueType &
00110 PostOrderTreeIterator< TTreeType >::Next()
00111 {
00112   this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
00113   return this->m_Position->Get();
00114 }
00116 
00118 template< class TTreeType >
00119 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType *
00120 PostOrderTreeIterator< TTreeType >::FindNextNode() const
00121 {
00122   if ( this->m_Position == NULL || this->m_Position == this->m_Root )
00123     {
00124     return NULL;
00125     }
00126   TreeNodeType *sister = const_cast< TreeNodeType * >( FindSister(this->m_Position) );
00128 
00129   if ( sister != NULL )
00130     {
00131     return FindMostRightLeaf(sister);
00132     }
00133   if(this->m_Position->GetParent() == 0)
00134     {
00135     return 0;
00136     }
00137   TreeNodeType *rval = dynamic_cast<TreeNodeType *>(this->m_Position->GetParent());
00138   if(rval == 0)
00139     {
00140       itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
00141     }
00142   return rval;
00143 }
00144 
00146 template< class TTreeType >
00147 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType *
00148 PostOrderTreeIterator< TTreeType >::FindSister(TreeNodeType *node) const
00149 {
00150   if ( !node->HasParent() )
00151     {
00152     return NULL;
00153     }
00154 
00155   TreeNodeType *parent = dynamic_cast<TreeNodeType *>(node->GetParent());
00156   if(parent == 0)
00157     {
00158     itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
00159     }
00160 
00161   int           childPosition = parent->ChildPosition(node);
00162   int           lastChildPosition = parent->CountChildren() - 1;
00163 
00164   while ( childPosition < lastChildPosition )
00165     {
00166     if(parent->GetChild(childPosition + 1) == 0)
00167       {
00168       childPosition++;
00169       }
00170     else
00171       {
00172       TreeNodeType *sister = dynamic_cast<TreeNodeType *>(parent->GetChild(childPosition + 1));
00173       if ( sister == 0)
00174       {
00175       itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
00176       }
00177       return sister;
00178       }
00179     }
00180   return NULL;
00181 }
00182 
00184 template< class TTreeType >
00185 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType *
00186 PostOrderTreeIterator< TTreeType >::FindMostRightLeaf(TreeNodeType *node) const
00187 {
00188   while ( node->HasChildren() )
00189     {
00190     TreeNodeType *helpNode;
00191     int           childCount = node->CountChildren();
00192     int           i = 0;
00194 
00195     do
00196       {
00197       if(node->GetChild(i) == 0)
00198         {
00199         helpNode = 0;
00200         }
00201       else
00202         {
00203         helpNode = dynamic_cast<TreeNodeType *>(node->GetChild(i));
00204        if(helpNode == 0)
00205           {
00206           itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
00207           }
00208         }
00209       i++;
00210       }
00211     while ( helpNode == NULL && i < childCount );
00212 
00213     if ( helpNode == NULL )
00214       {
00215       return node;
00216       }
00217     node = helpNode;
00218     }
00219   return node;
00220 }
00221 
00223 template< class TTreeType >
00224 TreeIteratorBase< TTreeType > *PostOrderTreeIterator< TTreeType >::Clone()
00225 {
00226   PostOrderTreeIterator< TTreeType > *clone =
00227     new PostOrderTreeIterator< TTreeType >( const_cast< TTreeType * >( this->m_Tree ) );
00228   *clone = *this;
00229   return clone;
00230 }
00231 } // end namespace itk
00233 
00234 #endif
00235