#ifndef __CPM__DATASTRUCTURES__QUADEDGE__HXX__
#define __CPM__DATASTRUCTURES__QUADEDGE__HXX__

#include <limits>

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
const typename cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
TPrimalGeometry cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
NoGeometry = std::numeric_limits< P >::max( );

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
void cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
CreateRings( )
{
  TPrimal* e = this;
  PtrDual r = TDual::New( );
  Pointer s = Self::New( );
  PtrDual i = TDual::New( );

  // Create Rot ring
  e->m_Rot = r;
  r->m_Rot = s;
  s->m_Rot = i;
  i->m_Rot = e;

  // Update Onext rings
  r->m_Onext = i;
  i->m_Onext = r;
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
void cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
SetLnextRingGeometry( const D& v )
{
  for( Iterator i = this->BeginLnext( ); i != this->EndLnext( ); ++i )
    ( *i )->SetLeft( v );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
void cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
UnsetLnextRingGeometry( )
{
  this->SetLnextRingGeometry( TDual::NoGeometry );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
bool cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
IsEdgeInOnextRing( const TPrimal* e ) const
{
  bool found = false;
  for(
    ConstIterator i = this->BeginOnext( );
    i != this->EndOnext( ) && !found;
    ++i
    )
    found |= ( *i == e );
  return( found );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
bool cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
IsEdgeInLnextRing( const TPrimal* e ) const
{
  bool found = false;
  for(
    ConstIterator i = this->BeginLnext( );
    i != this->EndLnext( ) && !found;
    ++i
    )
    found |= ( *i == e );
  return( found );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
unsigned int cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
GetOnextRingSize( ) const
{
  unsigned int count = 0;
  for(
    ConstIterator i = this->BeginOnext( );
    i != this->EndOnext( );
    ++i
    )
    count++;
  return( count );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
unsigned int cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
GetLnextRingSize( ) const
{
  unsigned int count = 0;
  for(
    ConstIterator i = this->BeginLnext( );
    i != this->EndLnext( );
    ++i
    )
    count++;
  return( count );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
bool cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
IsAtBorder( ) const
{
  return(
    (    this->IsLeftSet( )   && !( this->IsRightSet( ) ) ) ||
    ( !( this->IsLeftSet( ) ) &&    this->IsRightSet( )   )
    );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
bool cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
IsOriginInternal( ) const
{
  bool internal = true;
  for(
    ConstIterator i = this->BeginOnext( );
    i != this->EndOnext( ) && internal;
    ++i
    )
    internal &= ( *i )->IsInternal( );
  return( internal );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
typename cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
TPrimal* cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
GetNextBorderEdgeWithUnsetLeft( TPrimal* edge ) const
{
  // Be sure the Onext ring isn't already full
  if( this->IsOriginInternal( ) )
    return( NULL );

  // Update reference
  edge = ( edge == NULL )? const_cast< TPrimal* >( this ): edge;

  // On efficiency purposes
  if( edge->IsIsolated( ) )
    return( edge );

  // Ok, no more special cases
  const TPrimal* cedge = const_cast< const TPrimal* >( edge );
  ConstIterator it = cedge->BeginOnext( );
  TPrimal* found = NULL;
  for( ; it != cedge->EndOnext( ) && found == NULL; ++it )
    if( !( ( *it )->IsLeftSet( ) ) )
      found = const_cast< TPrimal* >( *it );
  return( found );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
bool cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
ReorderOnextRing( TPrimal* first, TPrimal* second )
{
  // Making sure point adjacency is correct:
  if( first->GetOrigin( ) != second->GetOrigin( ) )
    return( false );

  if( first->GetOnext( ) == second )
    return( true );

  if( first->IsLeftSet( ) )
    return( false );

  // Second is an internal edge.
  if( second->IsInternal( ) )
    return( false );

  // Disconnect the triangles containing second:
  TPrimal* bsplice;
  if( second->IsLeftSet( ) )
    bsplice = second->GetNextBorderEdgeWithUnsetLeft( );
  else
    bsplice = second;
  TPrimal::Splice( second->GetOprev( ), bsplice );

  // Reconnect second after first:
  TPrimal::Splice( first, bsplice );
  return( true );
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
void cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
Splice( TPrimal* a, TPrimal* b )
{
  // Don't waste time splicing the same edge (or non-existent)
  // remember: it is its own inverse!
  if( a != b || a == NULL || b == NULL )
  {
    TPrimal* aNext = a->m_Onext;
    TPrimal* bNext = b->m_Onext;
    TDual* al      = aNext->m_Rot;
    TDual* be      = bNext->m_Rot;
    TDual* alNext  = al->m_Onext;
    TDual* beNext  = be->m_Onext;

    a->SetOnext( bNext );
    b->SetOnext( aNext );
    al->SetOnext( beNext );
    be->SetOnext( alNext );

  } // fi
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
QuadEdge( )
  : m_Origin( Self::NoGeometry )
{
  this->m_Onext = this;
  this->m_Rot = NULL;
}

// -------------------------------------------------------------------------
template< typename P, typename D, bool IsPrimal >
cpm::DataStructures::QuadEdge< P, D, IsPrimal >::
~QuadEdge( )
{
}

#endif // __CPM__DATASTRUCTURES__QUADEDGE__HXX__

// eof - $RCSfile$