ITK  4.1.0
Insight Segmentation and Registration Toolkit
itkInOrderTreeIterator.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 __itkInOrderTreeIterator_h
00019 #define __itkInOrderTreeIterator_h
00020 
00021 #include "itkTreeIteratorBase.h"
00022 
00023 namespace itk
00024 {
00025 template< class TTreeType >
00026 class InOrderTreeIterator:public TreeIteratorBase< TTreeType >
00027 {
00028 public:
00029 
00031   typedef InOrderTreeIterator               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   InOrderTreeIterator(TreeType & start);
00040   InOrderTreeIterator(TreeType *tree, TreeNodeType *start = NULL);
00042 
00044   NodeType GetType() const;
00045 
00047   TreeIteratorBase< TTreeType > * Clone();
00048 
00049 protected:
00050 
00052   const ValueType & Next();
00053 
00055   bool HasNext() const;
00056 
00057 private:
00058 
00060   const TreeNodeType * FindNextNode() const;
00061 };
00062 
00064 template< class TTreeType >
00065 InOrderTreeIterator< TTreeType >::InOrderTreeIterator(TTreeType & start):
00066   TreeIteratorBase< TTreeType >(start)
00067 {}
00068 
00070 template< class TTreeType >
00071 InOrderTreeIterator< TTreeType >::InOrderTreeIterator(TTreeType *tree, TreeNodeType *start):
00072   TreeIteratorBase< TTreeType >(tree, start)
00073 {}
00074 
00076 template< class TTreeType >
00077 typename InOrderTreeIterator< TTreeType >::NodeType
00078 InOrderTreeIterator< TTreeType >::GetType() const
00079 {
00080   return TreeIteratorBase< TTreeType >::INORDER;
00081 }
00082 
00084 template< class TTreeType >
00085 bool InOrderTreeIterator< TTreeType >::HasNext() const
00086 {
00087   if ( const_cast< TreeNodeType * >( FindNextNode() ) != NULL )
00088     {
00089     return true;
00090     }
00091   return false;
00092 }
00094 
00096 template< class TTreeType >
00097 const typename InOrderTreeIterator< TTreeType >::ValueType &
00098 InOrderTreeIterator< TTreeType >::Next()
00099 {
00100   this->m_Position =  const_cast< TreeNodeType * >( FindNextNode() );
00101   return this->m_Position->Get();
00102 }
00104 
00106 template< class TTreeType >
00107 const typename InOrderTreeIterator< TTreeType >::TreeNodeType *
00108 InOrderTreeIterator< TTreeType >::FindNextNode() const
00109 {
00110   if ( this->m_Position == NULL )
00111     {
00112     return NULL;
00113     }
00114 
00115   if ( this->m_Position->HasChildren() )
00116     {
00117     return this->m_Position->GetChild(0);
00118     }
00119 
00120   if ( !this->m_Position->HasParent() )
00121     {
00122     return NULL;
00123     }
00124 
00125   TreeNodeType *child = this->m_Position;
00126   TreeNodeType *parent = this->m_Position->GetParent();
00127 
00128   int childPosition = parent->ChildPosition(child);
00129   int lastChildPosition = parent->CountChildren() - 1;
00130 
00131   while ( childPosition < lastChildPosition )
00132     {
00133     TreeNodeType *help = parent->GetChild(childPosition + 1);
00134     if ( help != NULL )
00135       {
00136       return help;
00137       }
00138     childPosition++;
00139     }
00140 
00141   while ( parent->HasParent() )
00142     {
00143     child = parent;
00144     parent = parent->GetParent();
00145 
00146     // Subtree
00147     if ( parent->ChildPosition(this->m_Root) >= 0 )
00148       {
00149       return NULL;
00150       }
00151     childPosition = parent->ChildPosition(child);
00152     lastChildPosition = parent->CountChildren() - 1;
00153 
00154     while ( childPosition < lastChildPosition )
00155       {
00156       TreeNodeType *help = parent->GetChild(childPosition + 1);
00157       if ( help != NULL )
00158         {
00159         return help;
00160         }
00161       }
00162     }
00163   return NULL;
00164 }
00165 
00167 template< class TTreeType >
00168 TreeIteratorBase< TTreeType > *InOrderTreeIterator< TTreeType >::Clone()
00169 {
00170   InOrderTreeIterator *clone = new InOrderTreeIterator( const_cast< TTreeType * >( this->m_Tree ) );
00171 
00172   *clone = *this;
00173   return clone;
00174 }
00175 } // end namespace itk
00176 
00177 #endif
00178