#ifndef __CPM__ALGORITHMS__QUADEDGE__MESHEULEROPERATORJOINVERTEXFUNCTION__HXX__
#define __CPM__ALGORITHMS__QUADEDGE__MESHEULEROPERATORJOINVERTEXFUNCTION__HXX__

#include <cpm/Algorithms/QuadEdge/MeshZipFunction.h>

// -------------------------------------------------------------------------
template< class M >
typename
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
TOutput
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
Evaluate( const TInput& e )
{
  TStack del_edges;
  this->m_EdgeStatus = this->CheckStatus( e, del_edges );

  TOutput out;
  switch( this->m_EdgeStatus )
  {
  case Self::STANDARD_CONFIG:   out = this->Process( e ); break;
  case Self::QUADEDGE_ISOLATED: out = this->ProcessQuadEdge( e ); break;
  case Self::FACE_ISOLATED:     out = this->ProcessFace( e, del_edges ); break;
  default:                      out = NULL; break;
    /* TODO:
       case Self::EDGE_NULL:
       // this->m_Mesh == 0
       case Self::MESH_NULL:
       // e->IsIsolated( ) && e_sym->IsIsolated( )
       case Self::EDGE_ISOLATED:
       // more than 2 common vertices in 0-ring of org and dest respectively
       case Self::TOO_MANY_COMMON_VERTICES:
       // Tetrahedron case
       case Self::TETRAHEDRON_CONFIG:
       // Samosa case
       case Self::SAMOSA_CONFIG:
       // Eye case
       case Self::EYE_CONFIG:
       return( NULL );
       case Self::EDGE_JOINING_DIFFERENT_BORDERS:
       return( NULL );
    */
  } // hctiws
  return( out );
}

// -------------------------------------------------------------------------
template< class M >
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
MeshEulerOperatorJoinVertexFunction( )
  : Superclass( ),
    m_OldPointID( 0 ),
    m_EdgeStatus( Self::STANDARD_CONFIG )
{
}

// -------------------------------------------------------------------------
template< class M >
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
~MeshEulerOperatorJoinVertexFunction( )
{
}

// -------------------------------------------------------------------------
template< class M >
typename
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
TPointId
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
CommonVertexNeighboor( TEdge* e )
{
  TEdge* qe = e;
  TEdge* e_it  = qe->GetOnext( );

  typedef std::list< TPointId > TPointIdList;
  TPointIdList dir_list;
  TPointIdList sym_list;
  TPointIdList intersection_list;

  TPointId id;
  do
  {
    id = e_it->GetDestination( );
    dir_list.push_back( id );
    e_it = e_it->GetOnext( );
  }
  while( e_it != qe );

  qe = qe->GetSym( );
  e_it = qe;

  do
  {
    id = e_it->GetDestination( );
    sym_list.push_back( id );
    e_it = e_it->GetOnext( );
  }
  while( e_it != qe );

  dir_list.sort( );
  sym_list.sort( );

  std::set_intersection(
    dir_list.begin( ), dir_list.end( ),
    sym_list.begin( ), sym_list.end( ),
    std::back_inserter( intersection_list )
    );

  return( static_cast< TPointId >( intersection_list.size( ) ) );
}

// -------------------------------------------------------------------------
template< class M >
bool
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
IsTetrahedron( TEdge* e )
{
  typedef typename M::CellIdentifier _TCellId;
  if( true /* TODO: e->GetOrder( ) == 3 */ )
  {
    TEdge* e_sym = e->GetSym( );
    if( true /* TODO e_sym->GetOrder( ) == 3 */ )
    {
      if( true /* TODO e->GetLprev( )->GetOrder( ) == 3 */ )
      {
        if( true /* TODO e_sym->GetLprev( )->GetOrder( ) == 3 */ )
        {
          bool left_triangle; // TODO: = e->IsLnextOfTriangle( );
          bool right_triangle; // TODO: = e_sym->IsLnextOfTriangle( );

          if( left_triangle && right_triangle )
          {
            _TCellId id_left_right_triangle;
            if( e->GetLprev( )->IsRightSet( ) )
              id_left_right_triangle = e->GetLprev( )->GetRight( );
            else
              return( false );

            _TCellId id_left_left_triangle;
            if( e->GetLnext( )->IsRightSet( ) )
              id_left_left_triangle = e->GetLnext( )->GetRight( );
            else
              return( false );

            _TCellId id_right_left_triangle;
            if( e_sym->GetLnext( )->IsRightSet( ) )
              id_right_left_triangle = e_sym->GetLnext( )->GetRight( );
            else
              return( false );

            _TCellId id_right_right_triangle;
            if( e_sym->GetLprev( )->IsRightSet( ) )
              id_right_right_triangle = e_sym->GetLprev( )->GetRight( );
            else
              return( false );

            return(
              ( id_left_right_triangle == id_right_left_triangle ) &&
              ( id_left_left_triangle == id_right_right_triangle )
              );

          } // fi

        } // fi

      } // fi

    } // fi

  } // fi
  return( false );
}

// -------------------------------------------------------------------------
template< class M >
bool
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
IsFaceIsolated( TEdge* e, bool iWasLeftFace, TStack& oToBeDeleted )
{
  bool border;
  TEdge* e_sym = e->GetSym( );

  // turn around the face( left or right one ) while edges are on the border
  // and push them into a stack( which will be used to delete properly all
  // elements )
  TEdge* temp =( iWasLeftFace == true )? e: e_sym;
  TEdge* e_it = temp;

  oToBeDeleted.push( e_it );
  e_it = e_it->GetLnext( );
  do
  {
    oToBeDeleted.push( e_it );
    border = e_it->IsAtBorder( );
    e_it = e_it->GetLnext( );
  }
  while( ( e_it != temp ) && border );

  return( border );
}

// -------------------------------------------------------------------------
template< class M >
bool
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
IsSamosa( TEdge* e )
{
  // TODO return( ( e->GetOrder( ) == 2 ) && ( e->GetSym( )->GetOrder( ) == 2 ) );
  return( false );
}

// -------------------------------------------------------------------------
template< class M >
bool
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
IsEye( TEdge* e )
{
  bool OriginOrderIsTwo; // TODO =( e->GetOrder( ) == 2 );
  bool DestinationOrderIsTwo; // TODO =( e->GetSym( )->GetOrder( ) == 2 );

  return(
    (  OriginOrderIsTwo && !DestinationOrderIsTwo ) ||
    ( !OriginOrderIsTwo &&  DestinationOrderIsTwo )
    );
}

// -------------------------------------------------------------------------
template< class M >
bool
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
IsEdgeLinkingTwoDifferentBorders( TEdge* e )
{
  TEdge* t = e;
  TEdge* e_it = t;
  bool org_border;

  do
  {
    org_border = e_it->IsAtBorder( );
    e_it = e_it->GetOnext( );
  }
  while( ( e_it != t ) &&( !org_border ) );
  if( org_border )
  {
    t = e->GetSym( );
    e_it = t;
    bool dest_border;
    do
    {
      dest_border = e_it->IsAtBorder( );
      e_it = e_it->GetOnext( );
    }
    while( ( e_it != t ) &&( !dest_border ) );

    return( dest_border );
  }
  else
    return( false );
}

// -------------------------------------------------------------------------
template< class M >
typename
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
TEdgeStatus
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
CheckStatus( TEdge* e, TStack& oToBeDeleted )
{
  TEdge* e_sym = e->GetSym( );

  bool IsEdgeIsolated = e->IsIsolated( );
  bool IsSymEdgeIsolated = e_sym->IsIsolated( );
  if( IsEdgeIsolated || IsSymEdgeIsolated )
  {
    if( IsEdgeIsolated && IsSymEdgeIsolated )
    {
      // We could shrink the edge to a point,
      // But we consider this case to be degenerated.
      itkDebugMacro( "Argument edge isolated." );
      return( Self::EDGE_ISOLATED );

    } // fi

    // One the endpoints( and only one ) of the incoming edge is isolated.
    // Instead of "shrinking" the edge it suffice to delete it. Note that
    // this also avoids trouble since the definition of leftZip or rightZip
    // would be improper in this case( in fact leftZip or rightZip would
    // in fact be e or e->GetSym( )...
    //
    // When e is adjacent to a face, we must retrieve the edge [ a, b ]
    // in order to rebuild the face after edge deletion. If the left face
    // of e is set then the right face is also set... since it is the same
    // face ! Here is the situation:
    //
    //        b----a----X
    //        |    |    |
    //        |    e    |
    //        |    |    |
    //        |         |
    //        X----X----X
    //
    // We are not yet sure of the orientation of e and which endpoint
    // of e is attached in a.
    return( Self::QUADEDGE_ISOLATED );
  }

  TPointId number_common_vertices = this->CommonVertexNeighboor( e );
  if( number_common_vertices > 2 )
  {
    itkDebugMacro(
      "The 2 vertices have more than 2 common neighboor vertices."
      );
    return( Self::TOO_MANY_COMMON_VERTICES );

  } // fi

  if( number_common_vertices == 2 )
  {
    if( this->IsTetrahedron( e ) )
    {
      itkDebugMacro( "It forms a tetrahedron." );
      return( Self::TETRAHEDRON_CONFIG );

    } // fi

  } // fi

  // General case
  bool wasLeftFace = e->IsLeftSet( );
  bool wasRightFace = e->IsRightSet( );

  if( wasLeftFace && wasRightFace )
  {
    if( this->IsSamosa( e ) )
    {
      itkDebugMacro( "Self::SAMOSA_CONFIG." );
      return( Self::SAMOSA_CONFIG );

    } // fi
    if( this->IsEye( e ) )
    {
      itkDebugMacro( "Self::EYE_CONFIG." );
      return( Self::EYE_CONFIG );

    } // fi
    if( this->IsEdgeLinkingTwoDifferentBorders( e ) )
    {
      itkDebugMacro( "Self::EDGE_JOINING_DIFFERENT_BORDERS." );
      return( Self::EDGE_JOINING_DIFFERENT_BORDERS );

    } // fi
  }
  else
  {
    if( wasLeftFace || wasRightFace )
    {
      if( this->IsFaceIsolated( e, wasLeftFace, oToBeDeleted ) )
      {
        itkDebugMacro( "Self::FACE_ISOLATED." );
        return( Self::FACE_ISOLATED );

      } // fi

    } // fi

  } // fi
  return( Self::STANDARD_CONFIG );
}

// -------------------------------------------------------------------------
template< class M >
typename
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
TEdge*
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
Process( TEdge* e )
{
  TEdge* e_sym = e->GetSym( );

  // General case
  bool wasLeftFace     = e->IsLeftSet( );
  bool wasRightFace     = e->IsRightSet( );
  bool wasLeftTriangle; // TODO = e->IsLnextOfTriangle( );
  bool wasRightTriangle; // TODO = e_sym->IsLnextOfTriangle( );

  TPointId NewDest = e->GetDestination( );
  TPointId NewOrg  = e->GetOrigin( );
  TEdge* leftZip = e->GetLnext( );
  TEdge* rightZip = e->GetOprev( );

  //
  //                    \   |   /                //
  //                     \  |  /                 //
  //                      \ | /                  //
  //     ------------------ b ------------- Y    //
  //                   ___/ |               |    //
  //      _<_leftZip__/     |               |    //
  //     /                  ^               |    //
  //    X      left         e     right     |    //
  //     \____________      |               |    //
  //                  \___  |               |    //
  //                      \ |               |    //
  //     ------------------ a -rightZip->-- Y    //
  //                      / | \                  //
  //                     /  |  \                 //
  //                    /   |   \                //
  //
  // TODO: this->m_Mesh->LightWeightDeleteEdge( e );
  // TODO: this->m_OldPointID = this->m_Mesh->Splice( leftZip, rightZip );

  //
  //                            |      /       __Y  //
  //                            |     /     __/  |  //
  //       __<_leftZip___       |    /   __/     |  //
  //      /              \      |   / __/        |  //
  //     /                \__   |  / /           |  //
  //    X      NOFACE      __ [a = b]    NOFACE  |  //
  //     \                /  / / | \ \__         |  //
  //      \______________/ _/ /  |  \   \__      |  //
  //                    __/  /   |   \ rightZip  |  //
  //                 __/    /    |    \       \__|  //
  //                /      /     |     \         Y  //
  //
  // When the Lnext and/or the Rnext ring of the argument edge was originally
  // the one[s] of a triangle, the above edge deletion created the odd
  // situation of having two different edges adjacent to the same two
  // vertices( which is quite a bad thing ). This is was is depicted on
  // the above ascii-graph, the original left face was a triangle and
  // the resulting situation has two different edges adjacent to the
  // two vertices X and a. In order to clean up things, we can call the
  // Zip( MeshFunction ) algorithm which handles this case.
  // Once things are back to normal, we recreate faces when they were
  // originally present.
  //

  typedef MeshZipFunction< M > _TZip;
  if( wasLeftTriangle )
  {
    typename _TZip::Pointer zip = _TZip::New( );
    zip->SetMesh( this->m_Mesh );
    if( TEdge::NoGeometry != zip->Evaluate( leftZip ) )
    {
      itkDebugMacro( "Zip must return NoPoint( left )." );
      return( NULL );

    } // fi
  }
  else
  {
    /* TODO
       if( wasLeftFace )
       this->m_Mesh->AddFace( leftZip );
    */
  } // fi

  // NewOrg = rightZip->GetOprev( )->GetDestination( );
  if( wasRightTriangle )
  {
    NewOrg = rightZip->GetDestination( );
    typename _TZip::Pointer zip = _TZip::New( );
    zip->SetMesh( this->m_Mesh );
    if( TEdge::NoGeometry != zip->Evaluate( rightZip ) )
    {
      itkDebugMacro( "Zip must return NoPoint( right )." );
      return( NULL );

    } // fi
  }
  else
  {
    NewOrg = rightZip->GetLprev( )->GetOrigin( );
    /* TODO
       if( wasRightFace )
       this->m_Mesh->AddFace( rightZip );
    */
  } // fi

  TOutput result = this->m_Mesh->FindEdge( NewOrg, NewDest );
  if( !result )
    result = this->m_Mesh->FindEdge( NewDest )->GetSym( );
  return( result );
}

// -------------------------------------------------------------------------
template< class M >
typename
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
TEdge*
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
ProcessQuadEdge( TEdge* e )
{
  TEdge* temp = ( e->IsIsolated( ) == true )? e->GetSym( ): e;
  TEdge* rebuildEdge = temp->GetOprev( );

  this->m_OldPointID = temp->GetSym( )->GetOrigin( );

  bool e_leftset = e->IsLeftSet( );
  // TODO: this->m_Mesh->LightWeightDeleteEdge( e );
  /* TODO:
     if( e_leftset )
     this->m_Mesh->AddFace( rebuildEdge );
  */

  // this case has no symetric case in SPlitVertex
  // i.e. it is impossible to reconstruct such a pathological
  // case using SplitVertex. Thus the return value is
  // of less interest.
  // We return an edge whose dest is a, whichever.
  return( rebuildEdge );
}

// -------------------------------------------------------------------------
template< class M >
typename
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
TEdge*
cpm::Algorithms::QuadEdge::MeshEulerOperatorJoinVertexFunction< M >::
ProcessFace( TEdge* e, TStack& EdgesToBeDeleted )
{
  TPointId org = e->GetOrigin( );
  TPointId dest = e->GetDestination( );

  // delete all elements
  while( !EdgesToBeDeleted.empty( ) )
  {
    // TODO: this->m_Mesh->LightWeightDeleteEdge( EdgesToBeDeleted.top( ) );
    EdgesToBeDeleted.pop( );
  }

  // it now retuns one edge from NewDest or NewOrg if there are any
  // else NULL
  TEdge* temp = this->m_Mesh->FindEdge( dest );
  if( temp != NULL )
    return( temp );
  else
    return( this->m_Mesh->FindEdge( org ) );
}

#endif
// __CPM__ALGORITHMS__QUADEDGE__MESHEULEROPERATORJOINVERTEXFUNCTION__HXX__

// eof - $RCSfile$