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

  Copyright (c) Kitware, Inc.
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/VolViewCopyright.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 notice for more information.

=========================================================================*/
#ifndef __itkImageFunctionConditionalPathConstIterator_h
#define __itkImageFunctionConditionalPathConstIterator_h

#include <queue>
#include <vector>

#include "itkIndex.h"
#include "itkSize.h"
#include "itkConditionalConstIterator.h"
#include "itkShapedNeighborhoodIterator.h"
#include "itkConnectedComponentAlgorithm.h"
#include "itkImage.h"

namespace itk
{

/**
 * \class ImageFunctionConditionalPathConstIterator
 * \brief Iterates over a flood-filled spatial function. 
 *
 * Contributed as a paper to the Insight Journal:
 *  http://hdl.handle.net/1926/1320
 *
 * \ingroup ImageIterators
 *
 */
template<class TImage, class TFunction>
class ITK_EXPORT ImageFunctionConditionalPathConstIterator:
    public ConditionalConstIterator<TImage>
{
public:
  /** Standard class typedefs. */
  typedef ImageFunctionConditionalPathConstIterator Self;

  /** Type of function */
  typedef TFunction FunctionType;

  /** Type of vector used to store location info in the spatial function */
  typedef typename TFunction::InputType FunctionInputType;

  /** Index typedef support. */
  typedef typename TImage::IndexType IndexType;
  
  /** Offset typedef support. */
  typedef typename TImage::OffsetType OffsetType;

  /** Size typedef support. */
  typedef typename TImage::SizeType SizeType;

  /** Region typedef support */
  typedef typename TImage::RegionType RegionType;

  /** Image typedef support. */
  typedef TImage ImageType;

  /** Internal Pixel Type */
  typedef typename TImage::InternalPixelType InternalPixelType;

  /** External Pixel Type */
  typedef typename TImage::PixelType   PixelType;  

  typedef typename TImage::PointType PointType;
  typedef typename PointType::VectorType VectorType;

  typedef std::vector< PointType > PointContainerType;
  typedef typename PointContainerType::const_iterator PointsContainerConstIterator;
  typedef typename PointContainerType::iterator PointsContainerIterator;
  
  /** Internal Neighborhood Iterator Type */
  typedef typename itk::ShapedNeighborhoodIterator<ImageType> NeighborhoodIteratorType;

  /** Dimension of the image the iterator walks.  This constant is needed so
   * that functions that are templated over image iterator type (as opposed to
   * being templated over pixel type and dimension) can have compile time
   * access to the dimension of the image that the iterator walks. */
  itkStaticConstMacro(NDimensions, unsigned int, TImage::ImageDimension);

  /** Constructor establishes an iterator to walk a particular image and a
   * particular region of that image. This version of the constructor uses
   * an explicit seed pixel for the flood fill, the "startIndex" */
  ImageFunctionConditionalPathConstIterator(const ImageType *imagePtr,
      FunctionType *fnPtr, PointContainerType & targetPoints, double searchRadius);

  virtual bool IsPixelIncluded(const IndexType & index) const;

  /** Initializes the iterator, called from constructor */
  void InitializeIterator();

  /** Default Destructor. */
  virtual ~ImageFunctionConditionalPathConstIterator() {};

  /** operator= is provided to make sure the handle to the image is properly
   * reference counted. */
  Self &operator=(const Self& it)
    {
    this->m_Image = it.m_Image;     // copy the smart pointer
    this->m_Region = it.m_Region;
    return *this;
    } 
  
  /** Get the dimension (size) of the index. */
  static unsigned int GetIteratorDimension() 
    {return TImage::ImageDimension;}

  /** Get the index. This provides a read only reference to the index.
   * This causes the index to be calculated from pointer arithmetic and is
   * therefore an expensive operation.
   * \sa SetIndex */
  const IndexType GetIndex()
    { return m_IndexStack.front();}

  /** Get the pixel value */
  const PixelType & Get(void) const
    { return this->m_Image->GetPixel(m_IndexStack.front() ); }
 
  /** Is the iterator at the end of the region? */
  bool IsAtEnd()
    { return this->m_IsAtEnd; }

  /** Put more seeds on the list */
  void AddSeed ( const IndexType seed )
    {
    m_StartIndices.push_back ( seed );
    }

  /** Clear all the seeds */
  void ClearSeeds ()
    {
    m_StartIndices.clear();
    }
  
  /** Move an iterator to the beginning of the region. "Begin" is
   * defined as the first pixel in the region. */
  void GoToBegin();

  /** Walk forward one index */
  void operator++()
    { this->DoFloodStep(); }

  void DoFloodStep();
  
  virtual SmartPointer<FunctionType> GetFunction() const
    {
    return m_Function;
    }
    
  /** When m_FullyConnected is set to true, the neighborhood
   * iterator will inspect an 8 respectively 26 neighborhood.
   * When the value is set to false, the neighborhood will be
   * 4 in 2D and 6 in 3D. */
  void SetFullyConnected(const bool _arg);
  bool GetFullyConnected() const;
  itkBooleanMacro(FullyConnected);

  bool HasReachedTarget() { return m_HasReachedTarget; }
  unsigned long GetTargetId() { return m_TargetId; }
  IndexType GetTargetIndex() { return m_TargetIndex; }
  PointType GetTargetPoint() { return m_TargetPoint; }

  void SetSourcePoint( const PointType & p );

protected: 

  void Fill( const IndexType & );
  bool IsNotFilled( const IndexType & );
  void Remove( const IndexType & );
  bool IsWithinSearchRadius( const IndexType & index );
  bool IsAtTarget( const IndexType & index );
  void AllocateTempImage();

  /** Smart pointer to the function we're evaluating */
  SmartPointer<FunctionType> m_Function;

  /** A temporary image used for storing info about indices
   * 0 = pixel has not yet been processed
   * 1 = pixel is not inside the function
   * 2 = pixel is inside the function, neighbor check incomplete
   * 3 = pixel is inside the function, neighbor check complete */
  typedef Image<unsigned char, itkGetStaticConstMacro(NDimensions)> TTempImage;
  
  typename TTempImage::Pointer m_TempPtr;
  
  /** A list of locations to start the recursive fill */
  typedef std::vector<IndexType> IndexContainerType;
  typedef typename IndexContainerType::iterator IndexIteratorType;
  typedef typename IndexContainerType::const_iterator IndexConstIteratorType;
  typedef typename IndexType::IndexValueType IndexValueType;

  IndexContainerType m_StartIndices;
  IndexContainerType m_TargetIndices;

  typename ImageType::PointType m_ImageOrigin;
  typename ImageType::SpacingType m_ImageSpacing;

  /** The neighborhood iterator */
  NeighborhoodIteratorType m_NeighborhoodIterator;

  /** Region of the source image */
  RegionType   m_ImageRegion;

  /** Stack used to hold the path of the iterator through the image */
  std::queue<IndexType> m_IndexStack;

  PointContainerType m_TargetPoints;
  unsigned long      m_TargetId;
  IndexType          m_TempIndex, m_TargetIndex, m_SourceIndex;
  VectorType         m_TempVector;
  bool               m_HasReachedTarget;
  PointType          m_TargetPoint, m_TempPoint, m_SourcePoint;
  double             m_SearchRadius, m_SearchRadiusSquared;


  /** Defines the connectivity of the neighborhood iterator. 
   * In case of 2D the default connectivity is 4 (6 in 3D) and 
   * when m_FullyConnected is set to true the connectivity is 
   * 8 (26 in 3D).
   */
  bool m_FullyConnected;
};

} // end namespace itk

#ifndef ITK_MANUAL_INSTANTIATION
#include "itkImageFunctionConditionalPathConstIterator.txx"
#endif

#endif