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

  Program:   Insight Segmentation & Registration Toolkit
  Module:    itkQuadEdgeMeshEdgeMergeDecimationFilter.h
  Language:  C++
  Date:      $Date$
  Version:   $Revision$

  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 __itkQuadEdgeMeshEdgeMergeDecimationFilter_h
#define __itkQuadEdgeMeshEdgeMergeDecimationFilter_h

#include <list>
#include <map>
#include <algorithm>

#include <itkQuadEdgeMeshEulerOperatorJoinVertexFunction.h>
#include <itkQuadEdgeMeshPolygonCell.h>

#include "itkQuadEdgeMeshDecimationFilter.h"
#include "itkPriorityQueueContainer.h"
#include "itkTriangleHelper.h"

namespace itk
{
/**
 * \class QuadEdgeMeshEdgeMergeDecimationFilter
 * \brief
 */
template< class TInput, class TOutput, class TCriterion >
class QuadEdgeMeshEdgeMergeDecimationFilter :
      public QuadEdgeMeshDecimationFilter< TInput, TOutput, TCriterion >
{
public:
  typedef QuadEdgeMeshEdgeMergeDecimationFilter             Self;
  typedef SmartPointer< Self >                              Pointer;
  typedef SmartPointer< const Self >                        ConstPointer;
  typedef QuadEdgeMeshDecimationFilter< 
    TInput, TOutput, TCriterion >                           Superclass;

  /** Run-time type information (and related methods).   */
  itkTypeMacro( QuadEdgeMeshEdgeMergeDecimationFilter, QuadEdgeMeshDecimationFilter );

  typedef TInput                                            InputMeshType;
  typedef typename InputMeshType::Pointer                   InputMeshPointer;

  typedef TOutput                                           OutputMeshType;
  typedef typename OutputMeshType::Pointer                  OutputMeshPointer;
  typedef typename OutputMeshType::PointIdentifier          OutputPointIdentifier;
  typedef typename OutputMeshType::PointType                OutputPointType;
  typedef typename OutputPointType::VectorType              OutputVectorType;
  typedef typename OutputMeshType::QEType                   OutputQEType;
  typedef typename OutputMeshType::EdgeCellType             OutputEdgeCellType;
  typedef typename OutputMeshType::CellType                 OutputCellType;
  typedef typename OutputMeshType::CellIdentifier           OutputCellIdentifier;
  typedef typename OutputMeshType::CellsContainerPointer    OutputCellsContainerPointer;
  typedef typename OutputMeshType::CellsContainerIterator   OutputCellsContainerIterator;

  typedef QuadEdgeMeshPolygonCell< OutputCellType >         OutputPolygonType;

  typedef TCriterion                                        CriterionType;
  typedef typename CriterionType::Pointer                   CriterionPointer;
  typedef typename CriterionType::MeasureType               MeasureType;
  typedef typename CriterionType::PriorityType              PriorityType;
  typedef typename CriterionType::PriorityQueueWrapperType  PriorityQueueItemType;
    
  typedef PriorityQueueContainer< PriorityQueueItemType*,
    ElementWrapperPointerInterface< PriorityQueueItemType* >,
    PriorityType >                                          PriorityQueueType;
  typedef typename PriorityQueueType::Pointer               PriorityQueuePointer;

  typedef std::map< OutputQEType*, PriorityQueueItemType* > QueueMapType;
  typedef typename QueueMapType::iterator                   QueueMapIterator;

  typedef QuadEdgeMeshEulerOperatorJoinVertexFunction< 
    OutputMeshType, OutputQEType >                          OperatorType;
  typedef typename OperatorType::Pointer                    OperatorPointer;

protected:

  QuadEdgeMeshEdgeMergeDecimationFilter();
  virtual ~QuadEdgeMeshEdgeMergeDecimationFilter();

  bool m_Relocate;
  bool m_CheckOrientation;

  PriorityQueuePointer    m_PriorityQueue;
  QueueMapType            m_QueueMapper;
  OutputQEType*           m_Element;
  PriorityType            m_Priority;
  OperatorPointer         m_JoinVertexFunction;

  /**
  * \brief Compute the measure value for iEdge
  * \param[in] iEdge
  * \return measure value
  */
  virtual MeasureType MeasureEdge( OutputQEType* iEdge ) = 0;

  /**
  * \brief Fill the priority queue
  */
  void FillPriorityQueue();

  /**
  * \brief Push one edge in the priority queue
  * \param[in] iEdge
  */
  void PushElement( OutputQEType* iEdge );

  /**
  * \brief Check if iEdge is valid and then can be processed
  * \param[in] iEdge
  * \return 
  */
  bool IsEdgeOKToBeProcessed( OutputQEType* iEdge );

  /**
  * \brief Extract the edge to be processed
  */
  void Extract();

  /**
  * \brief Delete a given edge in the priority queue
  * \param[in] iEdge
  */
  void DeleteElement( OutputQEType* iEdge );
  
  virtual void DeletePoint( const OutputPointIdentifier& iIdToBeDeleted,
                            const OutputPointIdentifier& iRemaing );

  /**
  * \brief Push iEdge in the priority queue if it is not already, else
  * its corresponding priority value is updated.
  * \param[in] iEdge
  */
  virtual void PushOrUpdateElement( OutputQEType* iEdge );

  /**
  * \brief
  */
  virtual void JoinVertexFailed( );

  /**
  * \brief
  */
  virtual bool ProcessWithoutAnyTopologicalGuarantee();

  /**
  * \brief
  * \return 
  */
  virtual unsigned int CheckQEProcessingStatus( );

  /**
  * \brief
  * \return
  */
  virtual bool ProcessWithTopologicalGuarantee();

  /**
  * \brief
  */
  size_t NumberOfCommonVerticesIn0Ring( );

  /**
  * \brief
  */
  void RemoveSamosa();

  /**
  * \brief
  * \param[in] iEdge
  */
  void TagElementOut( OutputQEType* iEdge );

  /**
  * \brief
  */
  void RemoveEye();

  /**
  * \brief
  * \param[in] iEdge (the one which will be merged)
  * \return the new location of merged points
  */
  virtual OutputPointType Relocate( OutputQEType* iEdge ) = 0;

  /**
  * \brief
  * \todo Finish to implement this method! 
  */
  bool CheckOrientation( OutputQEType* iEdge,
    const OutputPointIdentifier& iId,
    const OutputPointType& iPt )
    {
    OutputMeshPointer output = this->GetOutput();
    OutputCellsContainerPointer cells = output->GetCells();

    std::list< OutputCellIdentifier > r1, r2, elements_to_be_tested;
    OutputQEType* qe = iEdge;
    OutputQEType* qe_it = qe->GetOnext();

    do
      {
      r1.push_back( qe_it->GetLeft() );
      qe_it = qe_it->GetOnext();
      }while( qe_it != qe );

    qe = iEdge->GetSym();
    qe_it = qe->GetOnext();

    do
      {
      r2.push_back( qe_it->GetLeft() );
      qe_it = qe_it->GetOnext();
      }while( qe_it != qe );

    r1.sort();
    r2.sort();

    std::set_symmetric_difference( r1.begin(), r1.end(),
      r2.begin(), r2.end(),
      std::back_inserter( elements_to_be_tested ) );

    typename std::list< OutputCellIdentifier >::iterator
      it = elements_to_be_tested.begin();

    typedef TriangleHelper< OutputPointType > TriangleType;

    bool orientation_ok( true );
    OutputCellIdentifier c_id( 0 );
    OutputPolygonType* poly;
    OutputPointIdentifier p_id;

    int k( 0 ), replace_k( 0 );
    OutputPointType pt[3];

    OutputVectorType n_bef, n_aft;

    while( ( it != elements_to_be_tested.end() ) && orientation_ok )
      {
      c_id = *it;
      poly = dynamic_cast< OutputPolygonType* >( cells->GetElement( c_id ) );

      qe = poly->GetEdgeRingEntry( );
      qe_it = qe;
      k = 0;
          
      do
        {
        p_id = qe_it->GetOrigin( );
        if( p_id == iId )
          replace_k = k;
        pt[k++] = output->GetPoint( p_id );
        qe_it = qe_it->GetLnext( );
        }while( qe_it != qe );

      n_bef = TriangleType::ComputeNormal( pt[0], pt[1], pt[2] );
      switch( replace_k )
        {
        default:
        case 0:
          n_aft = TriangleType::ComputeNormal( iPt, pt[1], pt[2] );
          break;
        case 1:
          n_aft = TriangleType::ComputeNormal( pt[0], iPt, pt[2] );
          break;
        case 2:
          n_aft = TriangleType::ComputeNormal( pt[0], pt[1], iPt );
          break;
        }

      orientation_ok = ( n_bef * n_aft ) < 0.;
      ++it;
      }

    return orientation_ok;
    }

  /**
   * \brief
   * \return
   */
  bool IsCriterionSatisfied();

private:
  QuadEdgeMeshEdgeMergeDecimationFilter( const Self& );
  void operator = ( const Self& );
};
}

#include "itkQuadEdgeMeshEdgeMergeDecimationFilter.txx"
#endif