itkPreOrderTreeIterator.h

Go to the documentation of this file.

/*=========================================================================

  Program:   Insight Segmentation & Registration Toolkit
  Module:    $RCSfile: itkPreOrderTreeIterator.h,v $
  Language:  C++
  Date:      $Date: 2009-03-03 15:08:00 $
  Version:   $Revision: 1.5 $

  Copyright (c) Insight Software Consortium. All rights reserved.
  See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even 
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
     PURPOSE.  See the above copyright notices for more information.

=========================================================================*/
#ifndef __itkPreOrderTreeIterator_h
#define __itkPreOrderTreeIterator_h

#include <itkTreeIteratorBase.h>

namespace itk {

template <class TTreeType>
class PreOrderTreeIterator : public TreeIteratorBase<TTreeType> 
{
public:

  typedef typename TTreeType::ValueType     ValueType;
  typedef TreeIteratorBase<TTreeType>       Superclass;
  typedef typename Superclass::TreeNodeType TreeNodeType;

  PreOrderTreeIterator( const TTreeType* tree,const TreeNodeType* start = NULL );

  int GetType() const;

  TreeIteratorBase<TTreeType>* Clone();

protected:
  const ValueType& Next();

  bool HasNext() const;

private:  

  const TreeNodeType* FindNextNode() const;

};


template <class TTreeType>
PreOrderTreeIterator<TTreeType>::PreOrderTreeIterator( const TTreeType* tree, const TreeNodeType* start )
  :TreeIteratorBase<TTreeType>(tree,start) 
{

}

template <class TTreeType>
int 
PreOrderTreeIterator<TTreeType>::GetType() const 
{
  return TreeIteratorBase<TTreeType>::PREORDER; 
}

template <class TTreeType>
bool 
PreOrderTreeIterator<TTreeType>::HasNext() const
{
  if ( const_cast<TreeNodeType* >(FindNextNode()) != NULL )
    {
    return true;
    }
  return false;
}

template <class TTreeType>
const typename PreOrderTreeIterator<TTreeType>::ValueType&
PreOrderTreeIterator<TTreeType>::Next() 
{
  this->m_Position = const_cast<TreeNodeType* >(FindNextNode());
  return this->m_Position->Get();
}

template <class TTreeType>
const typename PreOrderTreeIterator<TTreeType>::TreeNodeType* 
PreOrderTreeIterator<TTreeType>::FindNextNode() const
{ 
  if ( this->m_Position == NULL )
    {
    return NULL;
    }
  if ( this->m_Position->HasChildren() )
    {
    return dynamic_cast<const TreeNodeType*>(this->m_Position->GetChild(0));
    }

  if ( !this->m_Position->HasParent() )
    {
    return NULL;
    }

  TreeNodeType* child = this->m_Position;
  TreeNodeType* parent = dynamic_cast<TreeNodeType*>(this->m_Position->GetParent());

  // Are we a subtree? Then we are done.
  if( parent && parent->ChildPosition( this->m_Root ) >= 0 )
    {
    return NULL;
    }

  int childPosition = parent->ChildPosition( child ); 
  int lastChildPosition = parent->CountChildren() - 1;

  while ( childPosition < lastChildPosition ) 
    {
    TreeNodeType* help = dynamic_cast<TreeNodeType*>(parent->GetChild( childPosition + 1 ));

    if ( help != NULL )
      {
      return help;
      }
    childPosition++;
    }
  
  while ( parent->HasParent() ) 
    {
    child = parent;
    parent = dynamic_cast<TreeNodeType*>(parent->GetParent());

    // Subtree
    if( parent->ChildPosition( this->m_Root ) >= 0 )
      {
      return NULL;
      }

    childPosition = parent->ChildPosition(child);
    lastChildPosition = parent->CountChildren() - 1;

    while ( childPosition < lastChildPosition ) 
      {
      TreeNodeType* help = dynamic_cast<TreeNodeType*>(parent->GetChild( childPosition + 1 ));

      if ( help != NULL )
        {
        return help;
        }
      }
    }
  return NULL;
}

template <class TTreeType>
TreeIteratorBase<TTreeType>* PreOrderTreeIterator<TTreeType>::Clone() 
{
  PreOrderTreeIterator<TTreeType>* clone = new PreOrderTreeIterator<TTreeType>( this->m_Tree, this->m_Position );
  *clone = *this;
  return clone;
}

} // end namespace itk

#endif