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

itkInOrderTreeIterator.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkInOrderTreeIterator.h,v $
00005   Language:  C++
00006   Date:      $Date: 2009-02-05 19:04:57 $
00007   Version:   $Revision: 1.6 $
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 __itkInOrderTreeIterator_h
00018 #define __itkInOrderTreeIterator_h
00019 
00020 #include <itkTreeIteratorBase.h>
00021 
00022 namespace itk {
00023 
00024 template <class TTreeType>
00025 class InOrderTreeIterator : public TreeIteratorBase<TTreeType> 
00026 {
00027 public:
00028 
00030   typedef InOrderTreeIterator                 Self;
00031   typedef TreeIteratorBase<TTreeType>         Superclass;
00032   typedef TTreeType                           TreeType;
00033   typedef typename TTreeType::ValueType       ValueType;
00034   typedef typename Superclass::TreeNodeType   TreeNodeType;
00035 
00037   InOrderTreeIterator( TreeType& start );
00038   InOrderTreeIterator( TreeType* tree, TreeNodeType* start=NULL);
00040 
00042   int GetType() const;
00043 
00045   TreeIteratorBase<TTreeType>* Clone();
00046 
00047 protected:
00048 
00050   const ValueType& Next();
00051 
00053   bool HasNext() const;
00054 
00055 private:
00056 
00058   const TreeNodeType* FindNextNode() const;
00059 
00060 };
00061 
00062 
00064 template <class TTreeType>
00065 InOrderTreeIterator<TTreeType>::InOrderTreeIterator( TTreeType& start )
00066     :TreeIteratorBase<TTreeType>(start) 
00067 {
00068 }
00069 
00070 
00072 template <class TTreeType>
00073 InOrderTreeIterator<TTreeType>::InOrderTreeIterator( TTreeType* tree, TreeNodeType* start)
00074     :TreeIteratorBase<TTreeType>(tree,start)
00075 {
00076 }
00077 
00079 template <class TTreeType>
00080 int 
00081 InOrderTreeIterator<TTreeType>::GetType() const 
00082 {
00083   return TreeIteratorBase<TTreeType>::INORDER;
00084 }
00085 
00086 
00088 template <class TTreeType>
00089 bool InOrderTreeIterator<TTreeType>::HasNext() const
00090 {
00091   if ( const_cast<TreeNodeType*>(FindNextNode()) != NULL )
00092     {
00093     return true;
00094     }
00095   return false;
00096 }
00098 
00099 
00101 template <class TTreeType>
00102 const typename InOrderTreeIterator<TTreeType>::ValueType&
00103 InOrderTreeIterator<TTreeType>::Next() 
00104 {
00105   this->m_Position =  const_cast<TreeNodeType* >(FindNextNode());
00106   return this->m_Position->Get();
00107 }
00109 
00110 
00112 template <class TTreeType>
00113 const typename InOrderTreeIterator<TTreeType>::TreeNodeType* 
00114 InOrderTreeIterator<TTreeType>::FindNextNode() const 
00115 {
00116   if ( this->m_Position == NULL )
00117     {
00118     return NULL;
00119     }
00120 
00121   if ( this->m_Position->HasChildren() )
00122     {
00123     return this->m_Position->GetChild(0);
00124     }
00125     
00126   if ( !this->m_Position->HasParent() )
00127     {
00128     return NULL;
00129     }
00130   
00131   TreeNodeType* child = this->m_Position;
00132   TreeNodeType* parent = this->m_Position->GetParent();
00133 
00134   int childPosition = parent->ChildPosition( child );
00135   int lastChildPosition = parent->CountChildren() - 1;
00136 
00137   while ( childPosition < lastChildPosition ) 
00138     {
00139     TreeNodeType* help = parent->GetChild( childPosition + 1 );
00140     if ( help != NULL )
00141       {
00142       return help;
00143       }
00144     childPosition++;
00145     }
00146 
00147   while ( parent->HasParent() )
00148     {
00149     child = parent;
00150     parent = parent->GetParent();
00151 
00152     // Subtree
00153     if( parent->ChildPosition( this->m_Root ) >= 0 )
00154       {
00155       return NULL;
00156       }
00157     childPosition = parent->ChildPosition(child);
00158     lastChildPosition = parent->CountChildren() - 1;
00159 
00160     while ( childPosition < lastChildPosition ) 
00161       {
00162       TreeNodeType* help = parent->GetChild( childPosition + 1 );
00163       if ( help != NULL )
00164         {
00165         return help;
00166         }
00167       }
00168     }
00169   return NULL;
00170 }
00171 
00173 template <class TTreeType>
00174 TreeIteratorBase<TTreeType>* InOrderTreeIterator<TTreeType>::Clone() 
00175 {
00176   InOrderTreeIterator* clone = new InOrderTreeIterator( const_cast<TTreeType*>(this->m_Tree) );
00177   *clone = *this;
00178   return clone;
00179 }
00181 
00182 } // end namespace itk
00183 
00184 #endif
00185 

Generated at Tue Sep 15 03:33:50 2009 for ITK by doxygen 1.5.8 written by Dimitri van Heesch, © 1997-2000