/*
 * Module ID: dcel.cpp
 * Titre    : Definition de la classe DCEL (doubly connected edge list).
 * Utilite  : Structure de donnee pour contenir les aretes d'un graphe
 *            planaire comme decrit dans 'Computational Geometry' de
 *            Franco P. Preparata & Michael Ian Shamos (P. 15)
 *
 * Auteur   : Olivier Langlois (olivier@olivierlanglois.net)
 * Date     : 08 Mars 1998
 *
 * Revision :
 *
 * 001        27-Mar-1998 - Olivier Langlois
 *            Les fstreams ne fonctionnent pas avec le compilateur GNU 2.7.2.1
 *            lorsque compile avec l'option -frtti.
 */

#ifdef __GNUG__
#include <std/typeinfo.h>
#include "umath.h"
#else
#include <math.h>           // Pour HUGE_VAL
#endif
#include "collect/idlist.h"
#include "../tools/collect/pq.cpp"
#include "geo/point.h"
#include "geo/segment.h"
#include "geo/ray.h"
#include "collect/colvar.h"
#include "geo/dcel.h"
#include <limits.h>

DEFINE_COLLECTABLE(VerticesDictionary  , __VERTICESDICT)
DEFINE_COLLECTABLE(vertex, __VERTEX)
DEFINE_COLLECTABLE(face  , __FACE)
DEFINE_COLLECTABLE(edge  , __EDGE)
DEFINE_COLLECTABLE(DCEL  , __DCEL)

/******************************************************************************
 *
 * Nom       : removeIdx
 *
 ****************************************************************************/
void graphObject::removeIdx( const CollectableULong *key )
{
  delete edgeIdxList.remove(&IDList::CollectableIsEqual,
                            (void *)(Collectable *)key );
}

/******************************************************************************
 *
 * Nom       : addIdx
 *
 ****************************************************************************/
void graphObject::addIdx   ( const CollectableULong *key )
{
  D( if( edgeIdxList.contains(&IDList::CollectableIsEqual, (void *)(Collectable *)key ) == BOOL_TRUE ) cerr << "graphObject::addIdx : Clef deja presente" << endl; )
  edgeIdxList.insert( dynamic_cast< IsvDlink * >(key->copy()) );
}

/******************************************************************************
 *
 * Nom       : restoreList
 *
 ****************************************************************************/
#ifdef __GNUG__
void graphObject::restoreList( FILE *is )
#else
void graphObject::restoreList( istream &is )
#endif
{
  edgeIdxList.restoreGuts(is);
  IDList *tmpPtr = &edgeIdxList;
  RESTORE_IDLIST_ITEM( tmpPtr, CollectableULong, is )
  setRefCount( edgeIdxList.entries() );
}

/******************************************************************************
 *
 * Nom       : clear
 *
 ****************************************************************************/
void VerticesDictionary::clear()
{
  xmin.value(ULONG_MAX);
  xmax.value(ULONG_MAX);
  ymin.value(ULONG_MAX);
  ymax.value(ULONG_MAX);
  Dictionary::clear();
}

/******************************************************************************
 *
 * Nom       : Insert
 *
 * Utilite   : Insere un vertex et sa clef dans le dictionaire.
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
void VerticesDictionary::Insert(const Collectable *kx, const Collectable *dx )
{
  D( cout << "Insert #" << ((const CollectableULong *)kx)->value(); )
  D( cout << " " << *(point *)dx << endl; )
  if( xmin.value() == ULONG_MAX )
     xmin.value(((const CollectableULong *)kx)->value());
  else
  {
     if( point::cmp_xy( *((const vertex *)dx),
                        *dynamic_cast< vertex * >(getValue(&xmin)) ) < 0 )
        xmin.value(((const CollectableULong *)kx)->value());
  }
  if( xmax.value() == ULONG_MAX )
     xmax.value(((const CollectableULong *)kx)->value());
  else
  {
     if( point::cmp_xy( *((const vertex *)dx),
                        *dynamic_cast< vertex * >(getValue(&xmax)) ) > 0 )
        xmax.value(((const CollectableULong *)kx)->value());
  }
  if( ymin.value() == ULONG_MAX )
     ymin.value(((const CollectableULong *)kx)->value());
  else
  {
     if( point::cmp_yx( *((const vertex *)dx),
                        *dynamic_cast< vertex * >(getValue(&ymin)) ) < 0 )
        ymin.value(((const CollectableULong *)kx)->value());
  }
  if( ymax.value() == ULONG_MAX )
     ymax.value(((const CollectableULong *)kx)->value());
  else
  {
     if( point::cmp_yx( *((const vertex *)dx),
                        *dynamic_cast< vertex * >(getValue(&ymax)) ) > 0 )
        ymax.value(((const CollectableULong *)kx)->value());
  }
  Dictionary::Insert( kx, dx );
}

/******************************************************************************
 *
 * Nom       : remove
 *
 * Utilite   : Enleve un vertex associee a la clef specifiee.
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
Collectable *VerticesDictionary::remove(const Collectable *kx)
{
  Collectable *result = Dictionary::remove(kx);
  D( cout << "remove #" << ((const CollectableULong *)kx)->value(); )
  if( result )
  {
     D( cout << " " << *(point *)result << endl; )

     if( isEmpty() == BOOL_TRUE )
     {
        xmin.value(ULONG_MAX);
        xmax.value(ULONG_MAX);
        ymin.value(ULONG_MAX);
        ymax.value(ULONG_MAX);
     }
     else
     {
        vertex      *tmp;
        DictIterator it(*this);

        if( xmin.value() == ((const CollectableULong *)kx)->value() )
        {
          ++it;
          tmp  = dynamic_cast< vertex * >(it.getValue());
          xmin.value(dynamic_cast< CollectableULong * >(it.getKey())->value());
          while( ++it == BOOL_TRUE )
          {
             if( point::cmp_xy( *dynamic_cast< vertex * >(it.getValue()),
                                *tmp ) < 0 )
             {
                tmp  = dynamic_cast< vertex * >(it.getValue());
                xmin.value(dynamic_cast< CollectableULong * >(it.getKey())->value());
             }
          }
        }
        if( xmax.value() == ((const CollectableULong *)kx)->value() )
        {
          it.reset();
          ++it;
          tmp  = dynamic_cast< vertex * >(it.getValue());
          xmax.value(dynamic_cast< CollectableULong * >(it.getKey())->value());
          while( ++it == BOOL_TRUE )
          {
             if( point::cmp_xy( *dynamic_cast< vertex * >(it.getValue()),
                                *tmp ) > 0 )
             {
                tmp  = dynamic_cast< vertex * >(it.getValue());
                xmax.value(dynamic_cast< CollectableULong * >(it.getKey())->value());
             }
          }
        }
        if( ymin.value() == ((const CollectableULong *)kx)->value() )
        {
          it.reset();
          ++it;
          tmp  = dynamic_cast< vertex * >(it.getValue());
          ymin.value(dynamic_cast< CollectableULong * >(it.getKey())->value());
          while( ++it == BOOL_TRUE )
          {
             if( point::cmp_yx( *dynamic_cast< vertex * >(it.getValue()),
                                *tmp ) < 0 )
             {
                tmp  = dynamic_cast< vertex * >(it.getValue());
                ymin.value(dynamic_cast< CollectableULong * >(it.getKey())->value());
             }
          }
        }
        if( ymax.value() == ((const CollectableULong *)kx)->value() )
        {
          it.reset();
          ++it;
          tmp  = dynamic_cast< vertex * >(it.getValue());
          ymax.value(dynamic_cast< CollectableULong * >(it.getKey())->value());
          while( ++it == BOOL_TRUE )
          {
             if( point::cmp_yx( *dynamic_cast< vertex * >(it.getValue()),
                                *tmp ) > 0 )
             {
                tmp  = dynamic_cast< vertex * >(it.getValue());
                ymax.value(dynamic_cast< CollectableULong * >(it.getKey())->value());
             }
          }
        }
     } // ELSE(isEmpty())
  }   // IF(result)
  return result;
}

vertex::vertex(const point &p) : graphObject(), point(p) {}

vertex::~vertex()
{
}

/******************************************************************************
 *
 * Nom       : isEqual
 *
 ****************************************************************************/
Boolean vertex::isEqual(const Collectable *v) const
{
  if( v->isA() != __VERTEX ) return BOOL_FALSE;
  return operator==(*((const vertex *)v));
}

/******************************************************************************
 *
 * Nom       : saveGuts
 *
 ****************************************************************************/
#ifdef __GNUG__
void vertex::saveGuts( FILE *os )
#else
void vertex::saveGuts( ostream &os )
#endif
{
#ifdef __GNUG__
  fwrite( &myAtom, sizeof(ClassID), 1, os );
#else
  os.write((char *)&myAtom, sizeof(ClassID));
#endif
  point::saveGuts(os);
  saveList(os);
#ifdef __GNUG__
  fwrite( &myAtom, sizeof(ClassID), 1, os );
#else
  os.write((char *)&myAtom, sizeof(ClassID));
#endif
}

/******************************************************************************
 *
 * Nom       : restoreGuts
 *
 ****************************************************************************/
#ifdef __GNUG__
void vertex::restoreGuts( FILE *is )
#else
void vertex::restoreGuts( istream &is )
#endif
{
  ClassID id;

  // Verifie la validite du fichier
#ifdef __GNUG__
  fread( &id, sizeof(ClassID), 1, is );
#else
  is.read( (char *)&id, sizeof(ClassID) );
#endif
  if( id != myAtom ) throw int(0);

  point::restoreGuts(is);
  restoreList(is);

  // Verifie de nouveau l'intregrite du fichier
#ifdef __GNUG__
  fread( &id, sizeof(ClassID), 1, is );
#else
  is.read( (char *)&id, sizeof(ClassID) );
#endif
  if( id != myAtom ) throw int(0);
}

/******************************************************************************
 *
 * Nom       : operator==
 *
 ****************************************************************************/
Boolean vertex::operator==(const vertex &v) const
{
  return point::operator==(v)?BOOL_TRUE:BOOL_FALSE;
}

/******************************************************************************
 *
 * Nom       : operator==
 *
 ****************************************************************************/
Boolean face::operator==(const face &f) const
{
  return (location == f.location)?BOOL_TRUE:BOOL_FALSE;
}

/******************************************************************************
 *
 * Nom       : isEqual
 *
 ****************************************************************************/
Boolean face::isEqual(const Collectable *f) const
{
  if( f->isA() != __FACE ) return BOOL_FALSE;
  return operator==(*((const face *)f));
}

/******************************************************************************
 *
 * Nom       : saveGuts
 *
 ****************************************************************************/
#ifdef __GNUG__
void face::saveGuts( FILE *os )
#else
void face::saveGuts( ostream &os )
#endif
{
#ifdef __GNUG__
  fwrite( &myAtom, sizeof(ClassID), 1, os );
#else
  os.write((char *)&myAtom, sizeof(ClassID));
#endif
  location.saveGuts(os);
  saveList(os);
#ifdef __GNUG__
  fwrite( &myAtom, sizeof(ClassID), 1, os );
#else
  os.write((char *)&myAtom, sizeof(ClassID));
#endif
}

/******************************************************************************
 *
 * Nom       : restoreGuts
 *
 ****************************************************************************/
#ifdef __GNUG__
void face::restoreGuts( FILE *is )
#else
void face::restoreGuts( istream &is )
#endif
{
  ClassID id;

  // Verifie la validite du fichier
#ifdef __GNUG__
  fread( &id, sizeof(ClassID), 1, is );
#else
  is.read( (char *)&id, sizeof(ClassID) );
#endif
  if( id != myAtom ) throw int(0);

  location.restoreGuts(is);
  restoreList(is);

  // Verifie de nouveau l'intregrite du fichier
#ifdef __GNUG__
  fread( &id, sizeof(ClassID), 1, is );
#else
  is.read( (char *)&id, sizeof(ClassID) );
#endif
  if( id != myAtom ) throw int(0);
}

edge::edge( DCEL *l, face *f1, face *f2, vertex *v1, vertex *v2 )
: associatedList(l), P1(ULONG_MAX), P2(ULONG_MAX), myKey(ULONG_MAX)
{
  // N'est pas un edge Sentinel
  if( f1 && f2 && v1 && v2 )
  {
     init(f1, f2, v1, v2 );
  }
  else
  {
     // Juste au cas...
     if( f1 && !f1->references() ) delete f1;
     if( f2 && !f2->references() ) delete f2;
     if( v1 && !v1->references() ) delete v1;
     if( v2 && !v2->references() ) delete v2;
     throw GeoEx(GX_INVPAR);
  }
}

edge::edge( DCEL *l, face *f1, face *f2, const segment &s )
: associatedList(l), P1(ULONG_MAX), P2(ULONG_MAX), myKey(ULONG_MAX)
{
  vertex *v1 = new vertex(s.source());
  vertex *v2 = new vertex(s.target());

  if( f1 && f2 && v1 && v2 )
  {
     init(f1, f2, v1, v2 );
  }
  else
  {
    // Juste au cas...
     if( f1 && !f1->references() ) delete f1;
     if( f2 && !f2->references() ) delete f2;
     delete v1;
     delete v2;
     throw GeoEx(GX_INVPAR);
  }
}

edge::edge( DCEL *l, face *f1, face *f2, const line &s )
: associatedList(l), P1(ULONG_MAX), P2(ULONG_MAX), myKey(ULONG_MAX)
{
  vertex *v1 = new vertex(s.point1());
  vertex *v2 = new vertex(s.point2());

  if( f1 && f2 && v1 && v2 )
  {
     init(f1, f2, v1, v2 );
  }
  else
  {
    // Juste au cas...
     if( f1 && !f1->references() ) delete f1;
     if( f2 && !f2->references() ) delete f2;
     delete v1;
     delete v2;
     throw GeoEx(GX_INVPAR);
  }
}

/******************************************************************************
 *
 * Nom       : init
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
void edge::init( face *f1, face *f2, vertex *v1, vertex *v2 )
{
  CollectableULong *key;

  if( key = (CollectableULong *)associatedList->Faces().getKey(f1) )
  {
     if( !f1->references() ) delete f1;
     F1.value(key->value());
     dynamic_cast< face * >
     (associatedList->Faces().getValue(key))->addReference();
  }
  else
  {
     F1.value(associatedList->getNextFaceKey());
     f1->addReference();
     associatedList->Faces().Insert( F1.copy(), f1 );
  }

  if( key = (CollectableULong *)associatedList->Faces().getKey(f2) )
  {
     if( !f2->references() ) delete f2;
     F2.value(key->value());
     dynamic_cast< face * >
     (associatedList->Faces().getValue(key))->addReference();
  }
  else
  {
     F2.value(associatedList->getNextFaceKey());
     f2->addReference();
     associatedList->Faces().Insert( F2.copy(), f2 );
  }

  if( key = (CollectableULong *)associatedList->Vertices().getKey(v1) )
  {
     if( !v1->references() )delete v1;
     V1.value(key->value());
     dynamic_cast< vertex * >
     (associatedList->Vertices().getValue(key))->addReference();
  }
  else
  {
     V1.value(associatedList->getNextVertexKey());
     v1->addReference();
     associatedList->Vertices().Insert( V1.copy(), v1 );
  }

  if( key = (CollectableULong *)associatedList->Vertices().getKey(v2) )
  {
     if( !v2->references() ) delete v2;
     V2.value(key->value());
     dynamic_cast< vertex * >(associatedList->Vertices().getValue(key))->addReference();
  }
  else
  {
     V2.value(associatedList->getNextVertexKey());
     v2->addReference();
     associatedList->Vertices().Insert( V2.copy(), v2 );
  }
}

edge::~edge()
{
  associatedList->removeP1(this);
  associatedList->removeP2(this);

  face *f = getF1();
  if( !f->removeReference() )
  {
     delete associatedList->Faces().remove(&F1);
  }
  else if( myKey.value() != ULONG_MAX )
  {
     f->removeIdx(&myKey);
  }
  f = getF2();
  if( !f->removeReference() )
  {
     delete associatedList->Faces().remove(&F2);
  }
  else if( myKey.value() != ULONG_MAX )
  {
     f->removeIdx(&myKey);
  }
  vertex *v = getV1();
  if( !v->removeReference() )
  {
     delete associatedList->Vertices().remove(&V1);
  }
  else if( myKey.value() != ULONG_MAX )
  {
     v->removeIdx(&myKey);
  }
  v = getV2();
  if( !v->removeReference() )
  {
     delete associatedList->Vertices().remove(&V2);
  }
  else if( myKey.value() != ULONG_MAX )
  {
     v->removeIdx(&myKey);
  }
}

/******************************************************************************
 *
 * Nom       : isEqual
 *
 ****************************************************************************/
Boolean edge::isEqual(const Collectable *c) const
{
  edge *e;
  if( c->isA() != __EDGE ) return BOOL_FALSE;
  else e = (edge *)c;
  if( F1.value() == e->F1.value() &&
      F2.value() == e->F2.value() &&
      V1.value() == e->V1.value() &&
      V2.value() == e->V2.value() )
     return BOOL_TRUE;
  else return BOOL_FALSE;
}

/******************************************************************************
 *
 * Nom       : saveGuts
 *
 ****************************************************************************/
#ifdef __GNUG__
void edge::saveGuts( FILE *os )
#else
void edge::saveGuts( ostream &os )
#endif
{
#ifdef __GNUG__
  fwrite( &myAtom, sizeof(ClassID), 1, os );
#else
  os.write((char *)&myAtom, sizeof(ClassID));
#endif
  V1.saveGuts(os);
  V2.saveGuts(os);
  F1.saveGuts(os);
  F2.saveGuts(os);
  P1.saveGuts(os);
  P2.saveGuts(os);
  myKey.saveGuts(os);
#ifdef __GNUG__
  fwrite( &myAtom, sizeof(ClassID), 1, os );
#else
  os.write((char *)&myAtom, sizeof(ClassID));
#endif
}

/******************************************************************************
 *
 * Nom       : restoreGuts
 *
 ****************************************************************************/
#ifdef __GNUG__
void edge::restoreGuts( FILE *is )
#else
void edge::restoreGuts( istream &is )
#endif
{
  ClassID id;

  // Verifie la validite du fichier
#ifdef __GNUG__
  fread( &id, sizeof(ClassID), 1, is );
#else
  is.read( (char *)&id, sizeof(ClassID) );
#endif
  if( id != myAtom ) throw int(0);

  V1.restoreGuts(is);
  V2.restoreGuts(is);
  F1.restoreGuts(is);
  F2.restoreGuts(is);
  P1.restoreGuts(is);
  P2.restoreGuts(is);
  myKey.restoreGuts(is);

  // Verifie de nouveau l'intregrite du fichier
#ifdef __GNUG__
  fread( &id, sizeof(ClassID), 1, is );
#else
  is.read( (char *)&id, sizeof(ClassID) );
#endif
  if( id != myAtom ) throw int(0);
}

/******************************************************************************
 *
 * Nom       : setMyKey
 *
 ****************************************************************************/
void edge::setMyKey( unsigned long key )
{
  myKey.value(key);
  dynamic_cast< face * >(associatedList->Faces().getValue(&F1))->addIdx(&myKey);
  if( F2.value() != F1.value() )
     dynamic_cast< face * >
     (associatedList->Faces().getValue(&F2))->addIdx(&myKey);
  dynamic_cast< vertex * >(associatedList->Vertices().getValue(&V1))->addIdx(&myKey);
  if( V2.value() != V1.value() )
     dynamic_cast< vertex * >
     (associatedList->Vertices().getValue(&V2))->addIdx(&myKey);
}

/******************************************************************************
 *
 * Nom       : getF1
 *
 ****************************************************************************/
face  *edge::getF1() const
{
//  D( cout << "getF1 :" << F1.value() << endl; )
  return (face *)associatedList->Faces().getValue(&F1);
}

/******************************************************************************
 *
 * Nom       : getF2
 *
 ****************************************************************************/
face  *edge::getF2() const
{
//  D( cout << "getF2 :" << F2.value() << endl; )
  return (face *)associatedList->Faces().getValue(&F2);
}

/******************************************************************************
 *
 * Nom       : getV1
 *
 ****************************************************************************/
vertex *edge::getV1() const
{
//  D( cout << "getV1 :" << V1.value() << endl; )
  return (vertex *)associatedList->Vertices().getValue(&V1);
}

/******************************************************************************
 *
 * Nom       : getV2
 *
 ****************************************************************************/
vertex *edge::getV2() const
{
//  D( cout << "getV2 :" << V2.value() << endl; )
  return (vertex *)associatedList->Vertices().getValue(&V2);
}

/******************************************************************************
 *
 * Nom       : setF1
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
void edge::setF1( face *f )
{
  CollectableULong *key;

  // Recupere l'ancienne face
  face *f1 = dynamic_cast< face * >(associatedList->Faces().getValue(&F1));
  if( f1->isEqual(f) == BOOL_FALSE )
  {
     if( !f1->removeReference() )
     {
        delete associatedList->Faces().remove(&F1);
     }
     else if( myKey.value() != ULONG_MAX )
     {
        f1->removeIdx(&myKey);
     }

     if( key = (CollectableULong *)associatedList->Faces().getKey(f) )
     {
        if( !f->references() ) delete f;
        F1.value(key->value());
        f = dynamic_cast< face * >(associatedList->Faces().getValue(key));
        f->addReference();
        if( myKey.value() != ULONG_MAX ) f->addIdx(&myKey);
     }
     else
     {
        F1.value(associatedList->getNextFaceKey());
        f->addReference();
        if( myKey.value() != ULONG_MAX ) f->addIdx(&myKey);
        associatedList->Faces().Insert( F1.copy(), f );
     }
  }
}

/******************************************************************************
 *
 * Nom       : setF2
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
void edge::setF2( face *f )
{
  CollectableULong *key;

  // Recupere l'ancienne face
  face *f2 = dynamic_cast< face * >(associatedList->Faces().getValue(&F2));
  if( f2->isEqual(f) == BOOL_FALSE )
  {
     if( !f2->removeReference() )
     {
        delete associatedList->Faces().remove(&F2);
     }
     else if( myKey.value() != ULONG_MAX )
     {
        f2->removeIdx(&myKey);
     }

     if( key = (CollectableULong *)associatedList->Faces().getKey(f) )
     {
        if( !f->references() ) delete f;
        F2.value(key->value());
        f = dynamic_cast< face * >(associatedList->Faces().getValue(key));
        f->addReference();
        if( myKey.value() != ULONG_MAX ) f->addIdx(&myKey);
     }
     else
     {
        F1.value(associatedList->getNextFaceKey());
        f->addReference();
        if( myKey.value() != ULONG_MAX ) f->addIdx(&myKey);
        associatedList->Faces().Insert( F2.copy(), f );
     }
  }
}

/******************************************************************************
 *
 * Nom       : setV1
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
void edge::setV1( vertex *p )
{
  CollectableULong *key;
  // Recupere l'ancienne face
  vertex *v1 = dynamic_cast< vertex * >(associatedList->Vertices().getValue(&V1));
  if( v1->isEqual(p) == BOOL_FALSE )
  {
     associatedList->removeP1(this);

     if( !v1->removeReference() )
     {
        delete associatedList->Vertices().remove(&V1);
     }
     else if( myKey.value() != ULONG_MAX )
     {
        v1->removeIdx(&myKey);
     }

     if( key = (CollectableULong *)associatedList->Vertices().getKey(p) )
     {
        if( !p->references() ) delete p;
        V1.value(key->value());
        p = dynamic_cast< vertex * >(associatedList->Vertices().getValue(key));
        p->addReference();
     }
     else
     {
        V1.value(associatedList->getNextVertexKey());
        p->addReference();
        associatedList->Vertices().Insert( V1.copy(), p );
     }

     // Reajuste P1
     if( myKey.value() != ULONG_MAX )
     {
        associatedList->setP1( this, &myKey );
        p->addIdx(&myKey);
     }
  }
}

/******************************************************************************
 *
 * Nom       : setV2
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
void edge::setV2( vertex *p )
{
  CollectableULong *key;
  // Recupere l'ancienne face
  vertex *v2 = dynamic_cast< vertex * >(associatedList->Vertices().getValue(&V2));
  if( v2->isEqual(p) == BOOL_FALSE )
  {
     associatedList->removeP2(this);

     if( !v2->removeReference() )
     {
        delete associatedList->Vertices().remove(&V2);
     }
     else if( myKey.value() != ULONG_MAX )
     {
        v2->removeIdx(&myKey);
     }

     if( key = (CollectableULong *)associatedList->Vertices().getKey(p) )
     {
        if( !p->references() ) delete p;
        V2.value(key->value());
        p = dynamic_cast< vertex * >(associatedList->Vertices().getValue(key));
        p->addReference();
     }
     else
     {
        V2.value(associatedList->getNextVertexKey());
        p->addReference();
        associatedList->Vertices().Insert( V2.copy(), p );
     }

     // Reajuste P2
     if( myKey.value() != ULONG_MAX )
     {
        associatedList->setP2( this, &myKey );
        p->addIdx(&myKey);
     }
  }
}

/******************************************************************************
 *
 * Nom       : atRight
 *
 ****************************************************************************/
Boolean edge::atRight( const point &p ) const
{
  vertex *v1 = dynamic_cast< vertex * >(associatedList->Vertices().getValue(&V1));
  vertex *v2 = dynamic_cast< vertex * >(associatedList->Vertices().getValue(&V2));
  return right_turn( *v1, *v2, p );
}

/******************************************************************************
 *
 * Nom       : intersection
 *
 ****************************************************************************/
Boolean edge::intersection( edge &e, point &p )
{
  point  f1  = dynamic_cast< face * >(associatedList->Faces().getValue(&F1))->getLocation();
  point  f2  = dynamic_cast< face * >(associatedList->Faces().getValue(&F2))->getLocation();
  point  ef1 = e.getF1()->getLocation();
  point  ef2 = e.getF2()->getLocation();
  return p_bisector( f1, f2 ).intersection( p_bisector( ef1, ef2 ), p );
}

DCEL::DCEL()
{
  init();
}

/******************************************************************************
 *
 * Nom       : init
 *
 ****************************************************************************/
void DCEL::init( void )
{
  nextVertexKey   = 0;
  nextFaceKey     = 0;
  nextEdgeKey     = 0;
}

DCEL::~DCEL()
{
  clear();
}

/******************************************************************************
 *
 * Nom       : clear
 *
 ****************************************************************************/
void DCEL::clear()
{
  EdgesList.clear();
  VerticesList.clear();
  FacesList.clear();
  nextVertexKey = 0;
  nextFaceKey   = 0;
  nextEdgeKey   = 0;
}

/******************************************************************************
 *
 * Nom       : getNextVertexKey
 *
 ****************************************************************************/
unsigned long DCEL::getNextVertexKey()
{
  return nextVertexKey++;
}

/******************************************************************************
 *
 * Nom       : getNextFaceKey
 *
 ****************************************************************************/
unsigned long DCEL::getNextFaceKey()
{
  return nextFaceKey++;
}

/******************************************************************************
 *
 * Nom       : getNextEdgeKey
 *
 ****************************************************************************/
unsigned long DCEL::getNextEdgeKey()
{
  return nextEdgeKey++;
}

/******************************************************************************
 *
 * Nom       : getxminEdge
 *
 ****************************************************************************/
edge *DCEL::getxminEdge()
{
  edge *result;
  CollectableULong xminIdx = VerticesList.getxminIdx();
  vertex *xminV = (vertex *)VerticesList.getValue(&xminIdx);
  vertex *resultOtherVertex, *nextOtherVertex;
  if( xminV )
  {
     const IDList *listPtr = xminV->getEdgeIdxList();
     result = (edge *)EdgesList.getValue(listPtr->first());

     // Trouve l'autre vertex.
     if( result->V1.value() == xminIdx.value() )
        resultOtherVertex = (vertex *)VerticesList.getValue( &result->V2 );
     else
        resultOtherVertex = (vertex *)VerticesList.getValue( &result->V1 );

     IDListIterator it(*listPtr);
     CollectableULong *idx;
     edge *nextEdge;
     while( (idx = (CollectableULong *)++it) )
     {
        nextEdge = (edge *)EdgesList.getValue(idx);
        if( nextEdge->V1.value() == xminIdx.value() )
          nextOtherVertex = (vertex *)VerticesList.getValue( &nextEdge->V2 );
        else
          nextOtherVertex = (vertex *)VerticesList.getValue( &nextEdge->V1 );

        if( nextOtherVertex->xcoord() < resultOtherVertex->xcoord() )
        {
          result = nextEdge;
          resultOtherVertex = resultOtherVertex;
        }
     }
     return result;
  }
  else return NULL;
}

/******************************************************************************
 *
 * Nom       : getyminEdge
 *
 ****************************************************************************/
edge *DCEL::getyminEdge()
{
  edge *result;
  CollectableULong yminIdx = VerticesList.getyminIdx();
  vertex *yminV = (vertex *)VerticesList.getValue(&yminIdx);
  vertex *resultOtherVertex, *nextOtherVertex;
  if( yminV )
  {
     const IDList *listPtr = yminV->getEdgeIdxList();
     result = (edge *)EdgesList.getValue(listPtr->first());

     // Trouve l'autre vertex.
     if( result->V1.value() == yminIdx.value() )
        resultOtherVertex = (vertex *)VerticesList.getValue( &result->V2 );
     else
        resultOtherVertex = (vertex *)VerticesList.getValue( &result->V1 );

     IDListIterator it(*listPtr);
     CollectableULong *idx;
     edge *nextEdge;
     while( (idx = (CollectableULong *)++it) )
     {
        nextEdge = (edge *)EdgesList.getValue(idx);
        if( nextEdge->V1.value() == yminIdx.value() )
          nextOtherVertex = (vertex *)VerticesList.getValue( &nextEdge->V2 );
        else
          nextOtherVertex = (vertex *)VerticesList.getValue( &nextEdge->V1 );

        if( nextOtherVertex->ycoord() < resultOtherVertex->ycoord() )
        {
          result = nextEdge;
          resultOtherVertex = resultOtherVertex;
        }
     }
     return result;
  }
  else return NULL;
}

/******************************************************************************
 *
 * Nom       : getxmaxEdge
 *
 ****************************************************************************/
edge *DCEL::getxmaxEdge()
{
  edge *result;
  CollectableULong xmaxIdx = VerticesList.getxmaxIdx();
  vertex *xmaxV = (vertex *)VerticesList.getValue(&xmaxIdx);
  vertex *resultOtherVertex, *nextOtherVertex;
  if( xmaxV )
  {
     const IDList *listPtr = xmaxV->getEdgeIdxList();
     result = (edge *)EdgesList.getValue(listPtr->first());

     // Trouve l'autre vertex.
     if( result->V1.value() == xmaxIdx.value() )
        resultOtherVertex = (vertex *)VerticesList.getValue( &result->V2 );
     else
        resultOtherVertex = (vertex *)VerticesList.getValue( &result->V1 );

     IDListIterator it(*listPtr);
     CollectableULong *idx;
     edge *nextEdge;
     while( (idx = (CollectableULong *)++it) )
     {
        nextEdge = (edge *)EdgesList.getValue(idx);
        if( nextEdge->V1.value() == xmaxIdx.value() )
          nextOtherVertex = (vertex *)VerticesList.getValue( &nextEdge->V2 );
        else
          nextOtherVertex = (vertex *)VerticesList.getValue( &nextEdge->V1 );

        if( nextOtherVertex->xcoord() > resultOtherVertex->xcoord() )
        {
          result = nextEdge;
          resultOtherVertex = resultOtherVertex;
        }
     }
     return result;
  }
  else return NULL;
}

/******************************************************************************
 *
 * Nom       : getymaxEdge
 *
 ****************************************************************************/
edge *DCEL::getymaxEdge()
{
  edge *result;
  CollectableULong ymaxIdx = VerticesList.getymaxIdx();
  vertex *ymaxV = (vertex *)VerticesList.getValue(&ymaxIdx);
  vertex *resultOtherVertex, *nextOtherVertex;
  if( ymaxV )
  {
     const IDList *listPtr = ymaxV->getEdgeIdxList();
     result = (edge *)EdgesList.getValue(listPtr->first());

     // Trouve l'autre vertex.
     if( result->V1.value() == ymaxIdx.value() )
        resultOtherVertex = (vertex *)VerticesList.getValue( &result->V2 );
     else
        resultOtherVertex = (vertex *)VerticesList.getValue( &result->V1 );

     IDListIterator it(*listPtr);
     CollectableULong *idx;
     edge *nextEdge;
     while( (idx = (CollectableULong *)++it) )
     {
        nextEdge = (edge *)EdgesList.getValue(idx);
        if( nextEdge->V1.value() == ymaxIdx.value() )
          nextOtherVertex = (vertex *)VerticesList.getValue( &nextEdge->V2 );
        else
          nextOtherVertex = (vertex *)VerticesList.getValue( &nextEdge->V1 );

        if( nextOtherVertex->ycoord() > resultOtherVertex->ycoord() )
        {
          result = nextEdge;
          resultOtherVertex = resultOtherVertex;
        }
     }
     return result;
  }
  else return NULL;
}

/******************************************************************************
 *
 * Nom       : setP1
 *
 ****************************************************************************/
void DCEL::setP1( edge *e, CollectableULong *key )
{
  edge             *lastEdge, *curEdge;
  segment           lastSegment, curSegment;
  const IDList     *edgeIdxListPtr;
  size_t            numEdge;

  edgeIdxListPtr = dynamic_cast< vertex * >
                         (VerticesList.getValue(&e->V1))->getEdgeIdxList();
  if( (numEdge = edgeIdxListPtr->entries()) > 0 )
  {
     curEdge = (edge *)EdgesList.getValue( edgeIdxListPtr->first() );
     if( numEdge > 1 )
     {
        for( size_t i = 0; i < numEdge; i++ )
        {
          lastEdge  = curEdge;

          D( cout << "lastEdge P1, P2:" << lastEdge->P1.value() << " " << lastEdge->P2.value() << endl; )
          curEdge = (edge *)
          EdgesList.getValue((e->V1.value()==lastEdge->V1.value())?&lastEdge->P1:&lastEdge->P2);

          if( e->V1.value() == curEdge->V1.value() )
             curSegment = segment(*curEdge->getV1(),*curEdge->getV2());
          else
             curSegment = segment(*curEdge->getV2(), *curEdge->getV1() );

          if( e->V1.value() == lastEdge->V1.value() )
             lastSegment = segment(*lastEdge->getV1(),*lastEdge->getV2());
          else
             lastSegment = segment(*lastEdge->getV2(),*lastEdge->getV1());

          if( segment( *e->getV1(), *e->getV2()).angle( curSegment ) >
                lastSegment.angle( curSegment ) )
             break;

          D( if( e->getSegment().angle( curSegment ) >= lastEdge->getSegment().angle( curSegment ) ) cout << e->getSegment() << endl << curSegment << endl << lastEdge->getSegment() << endl; )
          D( if( e->getSegment().angle( curSegment ) >= lastEdge->getSegment().angle( curSegment ) ) cout << e->getSegment().angle( curSegment ) << " " << lastEdge->getSegment().angle( curSegment ) << endl; )
        }
        // Verifie les cas limites lorsque le # d'aretes connectees est 2.
        if( numEdge == 2 &&
            segment( *e->getV1(), *e->getV2()).angle( curSegment ) >
            lastSegment.angle( curSegment ) &&
            left_turn(curSegment.target(),*e->getV1(),*e->getV2()) == BOOL_TRUE)
        {
          edge *tmp = curEdge;
          curEdge   = lastEdge;
          lastEdge  = tmp;
        }
     }
     else lastEdge = curEdge;

     e->P1.value(curEdge->myKey.value());
     if( lastEdge->V1.value() == e->V1.value() )
        lastEdge->P1.value(key->value());
     else lastEdge->P2.value(key->value());
  }
}

/******************************************************************************
 *
 * Nom       : setP2
 *
 ****************************************************************************/
void DCEL::setP2( edge *e, CollectableULong *key )
{
  edge             *lastEdge, *curEdge;
  segment           lastSegment, curSegment;
  const IDList     *edgeIdxListPtr;
  size_t            numEdge;

  edgeIdxListPtr = dynamic_cast< vertex * >
                         (VerticesList.getValue(&e->V2))->getEdgeIdxList();
  if( (numEdge = edgeIdxListPtr->entries()) > 0 )
  {
     curEdge = (edge *)EdgesList.getValue( edgeIdxListPtr->first() );
     if( numEdge > 1 )
     {
        for( size_t i = 0; i < numEdge; i++ )
        {
          lastEdge  = curEdge;

          D( cout << "lastEdge P1, P2:" << lastEdge->P1.value() << " " << lastEdge->P2.value() << endl; )
          curEdge = (edge *)
          EdgesList.getValue((e->V2.value()==lastEdge->V1.value())?&lastEdge->P1:&lastEdge->P2);

          if( e->V1.value() == curEdge->V1.value() )
             curSegment  = segment(*curEdge->getV1(),*curEdge->getV2());
          else
             curSegment = segment(*curEdge->getV2(), *curEdge->getV1() );

          if( e->V1.value() == lastEdge->V1.value() )
             lastSegment = segment(*lastEdge->getV1(),*lastEdge->getV2());
          else
             lastSegment = segment(*lastEdge->getV2(),*lastEdge->getV1());

          if( segment( *e->getV2(), *e->getV1()).angle( curSegment ) >
                lastSegment.angle( curSegment ) )
             break;

          D( if( e->getSegment().angle( curSegment ) >= lastEdge->getSegment().angle( curSegment ) ) cout << e->getSegment() << endl << curSegment << endl << lastEdge->getSegment() << endl; )
          D( if( e->getSegment().angle( curSegment ) >= lastEdge->getSegment().angle( curSegment ) ) cout << e->getSegment().angle( curSegment ) << " " << lastEdge->getSegment().angle( curSegment ) << endl; )
        }
        // Verifie les cas limites lorsque le # d'aretes connectees est 2.
        if( numEdge == 2 &&
            segment( *e->getV2(), *e->getV1()).angle( curSegment ) >
            lastSegment.angle( curSegment ) &&
            left_turn(curSegment.target(),*e->getV2(),*e->getV1()) == BOOL_TRUE)
        {
          edge *tmp = curEdge;
          curEdge   = lastEdge;
          lastEdge  = tmp;
        }
     }
     else lastEdge = curEdge;

     e->P2.value(curEdge->myKey.value());
     if( lastEdge->V1.value() == e->V2.value() )
        lastEdge->P1.value(key->value());
     else lastEdge->P2.value(key->value());
  }
}

/******************************************************************************
 *
 * Nom       : removeP1
 *
 ****************************************************************************/
void DCEL::removeP1( edge *e )
{
  if( e->P1.value() != ULONG_MAX )
  {
     edge *nextEdge = (edge *)EdgesList.getValue(&e->P1);
     vertex *v1 = e->getV1();
     if( v1->getEdgeIdxList()->entries() > 2 )
     {
        unsigned long p1 = e->P1.value();
        do
        {
          if( nextEdge->V1.value() == e->V1.value() )
             nextEdge = (edge *)EdgesList.getValue(&nextEdge->P1);
          else
             nextEdge = (edge *)EdgesList.getValue(&nextEdge->P2);
        }
        while( nextEdge->P1.value() != e->myKey.value() &&
                 nextEdge->P2.value() != e->myKey.value() );
        if( nextEdge->V1.value() == e->V1.value() )
          nextEdge->P1.value(p1);
        else
          nextEdge->P2.value(p1);
     }
     else
     {
        if( e->V1.value() == nextEdge->V1.value() )
          nextEdge->P1.value(ULONG_MAX);
        else
          nextEdge->P2.value(ULONG_MAX);
     }
     e->P1.value(ULONG_MAX);
  }
}

/******************************************************************************
 *
 * Nom       : removeP2
 *
 ****************************************************************************/
void DCEL::removeP2( edge *e )
{
  if( e->P2.value() != ULONG_MAX )
  {
     edge *nextEdge = (edge *)EdgesList.getValue(&e->P2);
     vertex *v2 = e->getV2();
     if( v2->getEdgeIdxList()->entries() > 2 )
     {
        unsigned long p2 = e->P2.value();
        do
        {
          if( nextEdge->V2.value() == e->V2.value() )
             nextEdge = (edge *)EdgesList.getValue(&nextEdge->P2);
          else
             nextEdge = (edge *)EdgesList.getValue(&nextEdge->P1);
        }
        while( nextEdge->P1.value() != e->myKey.value() &&
                 nextEdge->P2.value() != e->myKey.value() );
        if( nextEdge->V1.value() == e->V2.value() )
          nextEdge->P1.value(p2);
        else
          nextEdge->P2.value(p2);
     }
     else
     {
        if( e->V2.value() == nextEdge->V1.value() )
          nextEdge->P1.value(ULONG_MAX);
        else
          nextEdge->P2.value(ULONG_MAX);
     }
     e->P2.value(ULONG_MAX);
  }
}

/******************************************************************************
 *
 * Nom       : insertEdge
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
int DCEL::insertEdge( edge *e )
{
  const IDList     *edgeIdxListPtr;

  D( if( point::cmp_xy(*e->getV1(),*e->getV2()) > 0 ) cout << "DCEL::insertEdge : V1 > V2" << endl; )
  D( cout << "insert :" << e->getSegment() << endl; )

  // Pour etre valide, une arete doit avoir 2 vertices distincts.
  if( e->V1.value() == e->V2.value() )
  {
     delete e;
     return -1;
  }

  CollectableULong *key = new CollectableULong(getNextEdgeKey());

  // Branche V1
  edgeIdxListPtr = dynamic_cast< vertex * >
                         (VerticesList.getValue(&e->V1))->getEdgeIdxList();
  if( edgeIdxListPtr->entries() > 0 )
  {
     // Verifie si on essaie d'inserer plus d'une fois la meme arete.
     DictIterator it(EdgesList);
     while( ++it == BOOL_TRUE )
     {
        if( e->isEqual(it.getValue()) == BOOL_TRUE )
        {
          delete e;
          delete key;
          return -1;
        }
     }
  }
  setP1(e, key);

  // Branche V2
  setP2(e, key);

  D( cout << "New edge:" << key->value() << endl; )
  e->setMyKey( key->value() );
  EdgesList.Insert( key, e );
  return 0;
}

/******************************************************************************
 *
 * Nom       : setBox
 *
 * Utilite   : Ferme le graph a l'interieur d'une boite.
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
void DCEL::setBox( polygon &poly )
{
  face *outside = new face(point(-1000,-1000));
  BoxInfo     *curInfo;
  segment     *segPtr;
  PQ<BoxInfo> *curPQ;
  const IDList &segmentsList = poly.segments();
  IDList  PQList;
  Boolean found;

  BoxInfo Sentinel;
  Sentinel.Key = -HUGE_VAL;
#ifndef __GNUG__
  PQ<BoxInfo>::setSentinel(&Sentinel);
  for( size_t i = segmentsList.entries()+1; --i; )
  {
     PQList.insert( new CollectableDlink( new PQ<BoxInfo> ) );
  }
#else
  for( int i = 0; i < segmentsList.entries(); i++ )
  {
     curPQ = new PQ<BoxInfo>;
     curPQ->setSentinel(&Sentinel);
    PQList.insert( new CollectableDlink( curPQ ) );
  }
#endif

  IDListIterator segIT(segmentsList);
  IDListIterator pqIT(PQList);

/*
  vertex *lbV = new vertex(*lb);
  vertex *rbV = new vertex(point(ub->xcoord(),lb->ycoord()));
  vertex *luV = new vertex(point(lb->xcoord(),ub->ycoord()));
  vertex *ruV = new vertex(*ub);

  segment d(*lbV,*rbV);
  segment l(*lbV,*luV);
  segment u(*luV,*ruV);
  segment r(*rbV,*ruV);
*/

  edge *edgePtr;
  vertex *newVertex, *oldVertex;
  IDList  edgeToRemove;
  segment curSeg;
  point interLocation;

  {
     D( cout << "Trouve les intersections" << endl; )

     DictIterator it(Edges());
     // Trouve les intersections.
    // Pas optimal, possibilite d'optimisation ?
     while( ++it == BOOL_TRUE )
     {
        edgePtr = (edge *)it.getValue();
        curSeg = edgePtr->getSegment();
        found = BOOL_FALSE;

        while( found == BOOL_FALSE &&
                (segPtr = (segment *)++segIT)   &&
                (curPQ  = (PQ<BoxInfo> *)((CollectableDlink *)++pqIT)->item ))
        {
          if( segPtr->intersection(curSeg, interLocation) == BOOL_TRUE )
          {
             newVertex = new vertex(interLocation);
             if( segPtr->contains( *edgePtr->getV1() ) == BOOL_FALSE   &&
                  segPtr->contains( *edgePtr->getV2() ) == BOOL_FALSE   )
             {
                // Si un des vertices est deja contenu dans le segment,
                // il n'est pas necessaire d'ajuster les vertices.
                if(right_turn( segPtr->source(),
                                    segPtr->target(), *edgePtr->getV1() ) == BOOL_TRUE)
                {
                  edgePtr->setV1(newVertex);
                  if( poly.outside(*edgePtr->getV2()) == BOOL_FALSE )
                     found = BOOL_TRUE;
                }
                else
                {
                  edgePtr->setV2(newVertex);
                  if( poly.outside(*edgePtr->getV1()) == BOOL_FALSE )
                     found = BOOL_TRUE;
                }
             }
             curInfo            = new BoxInfo;
             curInfo->Vertex    = newVertex;
             curInfo->leftFace  = edgePtr->getF1();
             curInfo->rightFace = edgePtr->getF2();
             if( right_turn( curInfo->leftFace->getLocation(),
                             curInfo->rightFace->getLocation(),
                             *newVertex) == BOOL_FALSE )
             {
                face *tmpFace      = curInfo->leftFace;
                curInfo->leftFace  = curInfo->rightFace;
                curInfo->rightFace = tmpFace;
             }
             curInfo->Key       = segPtr->source().distance(*newVertex);
             curPQ->insert(curInfo);

          // L'arete a change
             curSeg = edgePtr->getSegment();
          }
        } //WHILE(segment)

        if( poly.outside(curSeg.source()) == BOOL_TRUE ||
            poly.outside(curSeg.target()) == BOOL_TRUE )
        {
          edgeToRemove.insert( (IsvDlink *)edgePtr->myKey.copy() );
        }
        segIT.reset();
        pqIT.reset();
     } // WHILE(edge)
  }
  CollectableULong *idx;
  while( (idx = (CollectableULong *)edgeToRemove.get()) )
  {
     delete EdgesList.remove(idx);
     delete idx;
  }

  D( cout << "Connecte les aretes qui n'ont qu'une seule connection au diagramme" << endl; )

  {
     // Connecte les aretes qui n'ont qu'une seule connection au diagramme
     // Une copie du dictionnaire de Vertices est utilise car on ne peut
     // utiliser un iterateur et modifier le dictionnaire qui lui est associe.
     Dictionary tmpDict(VerticesList);
     DictIterator VerticesIt(tmpDict);

     while( ++VerticesIt == BOOL_TRUE )
     {
        Boolean V1isSource;
        oldVertex = (vertex *)VerticesIt.getValue();
        if( oldVertex->getEdgeIdxList()->entries() == 1 &&
            // S'assure que ce n'est pas un vertex cree par l'etape precedente
            poly.contains(*oldVertex) == BOOL_FALSE       )
        {
          vertex  *sourceVertex;
          edgePtr = getEdge((CollectableULong *)
                                  oldVertex->getEdgeIdxList()->first());
          sourceVertex = edgePtr->getV1();
          if( oldVertex->isEqual(sourceVertex) == BOOL_TRUE )
          {
             sourceVertex = edgePtr->getV2();
             V1isSource = BOOL_FALSE;
          }
          else
          {
             V1isSource = BOOL_TRUE;
          }
          D( if( sourceVertex->getEdgeIdxList()->entries() == 1 ) cout << "DCEL::clean() n'a pas fait sa job" << endl; )

          ray curRay(*sourceVertex,*oldVertex);
          found = BOOL_FALSE;
          while( found == BOOL_FALSE &&
                  (segPtr = (segment *)++segIT)   &&
                  (curPQ  = (PQ<BoxInfo> *)((CollectableDlink *)++pqIT)->item ))
          {
             if( curRay.intersection(*segPtr,interLocation) == BOOL_TRUE &&
                 interLocation != *sourceVertex )
             {
                newVertex = new vertex(interLocation);
                if(V1isSource == BOOL_TRUE)
                {
                  edgePtr->setV2(newVertex);
                }
                else
                {
                  edgePtr->setV1(newVertex);
                }
                curInfo            = new BoxInfo;
                curInfo->Vertex    = newVertex;
                curInfo->leftFace  = edgePtr->getF1();
                curInfo->rightFace = edgePtr->getF2();
                if( right_turn( curInfo->leftFace->getLocation(),
                                curInfo->rightFace->getLocation(),
                                *newVertex) == BOOL_FALSE )
                {
                  face *tmpFace      = curInfo->leftFace;
                  curInfo->leftFace  = curInfo->rightFace;
                  curInfo->rightFace = tmpFace;
                }
                curInfo->Key       = segPtr->source().distance(*newVertex);
                curPQ->insert(curInfo);
                found = BOOL_TRUE;
             }
          }
          segIT.reset();
          pqIT.reset();
        } // IF(vertex.entries() == 1)
     }   // WHILE(vertex)
  }
  face  *f1, *f2;
  double minDist;
  BoxInfo *lastInfo;

  while( (segPtr = (segment *)++segIT)   &&
            (curPQ  = (PQ<BoxInfo> *)((CollectableDlink *)++pqIT)->item) )
  {
     if( curPQ->isEmpty() == BOOL_TRUE )
     {
        {
          DictIterator FaceIt(FacesList);

          if( ++FaceIt == BOOL_TRUE )
          {
             f1      = (face *)FaceIt.getValue();
             minDist = segPtr->distance(f1->getLocation());

             while( ++FaceIt == BOOL_TRUE )
             {
                f2 = (face *)FaceIt.getValue();
                if( segPtr->distance(f2->getLocation()) < minDist )
                {
                  f1      = f2;
                  minDist = segPtr->distance(f1->getLocation());
                }
             }
          }
        }
        edgePtr = new edge( this, outside, f1, new vertex(segPtr->source()),
                            new vertex(segPtr->target()) );

        insertEdge(edgePtr);
     }
     else
     {
        lastInfo = curPQ->removeFirst();
        edgePtr  = new edge( this, outside, lastInfo->leftFace,
                             new vertex(segPtr->source()),
                             lastInfo->Vertex );
        insertEdge(edgePtr);
        while( (curInfo = curPQ->removeFirst()) != &Sentinel )
        {
          if( lastInfo->rightFace != curInfo->leftFace )
          {
             D( cout << "lastInfo leftFace " << lastInfo->leftFace->getLocation() << " rightFace " << lastInfo->rightFace->getLocation() << endl; )
             D( cout << "curInfo leftFace " << curInfo->leftFace->getLocation() << " rightFace " << curInfo->rightFace->getLocation() << endl; )
             D( cout << "lastInfo Vertex " << *lastInfo->Vertex << " curInfo Vertex " << *curInfo->Vertex << endl; )
             throw GeoEx(GX_CORFAC);
          }
          edgePtr = new edge( this, outside, lastInfo->rightFace, lastInfo->Vertex,
                              curInfo->Vertex );
          insertEdge(edgePtr);
          delete lastInfo;
          lastInfo = curInfo;
        }
        edgePtr = new edge( this, outside, lastInfo->rightFace,
                            lastInfo->Vertex, new vertex(segPtr->target()) );
        delete lastInfo;
        insertEdge(edgePtr);
     }
  } // WHILE(segment)
}

/******************************************************************************
 *
 * Nom       : clean
 *
 * Utilite   : Elimine toutes les aretes non connectees.
 *
 * Reference : dcel.h
 *
 ****************************************************************************/
void DCEL::clean()
{
  // Une liste est necessaire car on ne peut modifier un dictionnaire en
  // utilisant un iterateur sur ce dictionnaire en meme temps.
  IDList edgeToRemove;
  vertex *curVertex;
  Collectable *idx;

  D( cout << "Entering DCEL::clean()" << endl; )
  {
     DictIterator it(Vertices());
     while( ++it == BOOL_TRUE )
     {
        curVertex = (vertex *)it.getValue();
        const IDList *listPtr = curVertex->getEdgeIdxList();
        if( listPtr->entries() == 1 )
        {
          idx = (CollectableULong *)listPtr->first();
          edge *curEdge = (edge *)EdgesList.getValue(idx);
          if( ((CollectableULong *)it.getKey())->value() == curEdge->V1.value() )
          {
             curVertex = curEdge->getV2();
          }
          else
          {
             curVertex = curEdge->getV1();
          }
          if( curVertex->getEdgeIdxList()->entries() == 1 &&
              edgeToRemove.contains(&IDList::CollectableIsEqual,
                                    (void *)(Collectable *)idx ) == BOOL_FALSE )
             edgeToRemove.insert((IsvDlink *)idx->copy());
        }
     }
  }

  while( (idx = (CollectableULong *)edgeToRemove.get()) )
  {
     delete EdgesList.remove(idx);
     delete idx;
  }
  D( cout << "Exiting DCEL::clean()" << endl; )
}

/******************************************************************************
 *
 * Nom       : saveGuts
 *
 ****************************************************************************/
#ifdef __GNUG__
void DCEL::saveGuts( FILE *os )
#else
void DCEL::saveGuts( ostream &os )
#endif
{
#ifdef __GNUG__
  fwrite( &myAtom, sizeof(ClassID), 1, os );
  fwrite( &nextVertexKey, sizeof(unsigned long), 1, os );
  fwrite( &nextFaceKey, sizeof(unsigned long), 1, os );
  fwrite( &nextEdgeKey, sizeof(unsigned long), 1, os );
#else
  os.write((char *)&myAtom, sizeof(ClassID));
  os.write((char *)&nextVertexKey, sizeof(unsigned long));
  os.write((char *)&nextFaceKey, sizeof(unsigned long));
  os.write((char *)&nextEdgeKey, sizeof(unsigned long));
#endif
  EdgesList.saveGuts(os);
  FacesList.saveGuts(os);
  VerticesList.saveGuts(os);
#ifdef __GNUG__
  fwrite( &myAtom, sizeof(ClassID), 1, os );
#else
  os.write((char *)&myAtom, sizeof(ClassID));
#endif
}

/******************************************************************************
 *
 * Nom       : restoreGuts
 *
 ****************************************************************************/
#ifdef __GNUG__
void DCEL::restoreGuts( FILE *is )
#else
void DCEL::restoreGuts( istream &is )
#endif
{
  ClassID id;

  // Verifie la validite du fichier
#ifdef __GNUG__
  fread( &id, sizeof(ClassID), 1, is );
#else
  is.read( (char *)&id, sizeof(ClassID) );
#endif
  if( id != myAtom ) throw int(0);
  clear();
#ifdef __GNUG__
  fread( &nextVertexKey, sizeof(unsigned long), 1, is );
  fread( &nextFaceKey, sizeof(unsigned long), 1, is );
  fread( &nextEdgeKey, sizeof(unsigned long), 1, is );
#else
  is.read((char *)&nextVertexKey, sizeof(unsigned long));
  is.read((char *)&nextFaceKey, sizeof(unsigned long));
  is.read((char *)&nextEdgeKey, sizeof(unsigned long));
#endif
  Dictionary *tmpPtr;
  EdgesList.restoreGuts(is);
  tmpPtr = &EdgesList;
  RESTORE_DICT_ITEM( tmpPtr, CollectableULong, edge, is )
  D( cout << EdgesList.entries() << " edges restaures" << endl; )

  DictIterator it(EdgesList);
  edge *e;
  while( ++it == BOOL_TRUE )
  {
     e = (edge *)it.getValue();
     e->associatedList = this;
  }

  FacesList.restoreGuts(is);
  tmpPtr = &FacesList;
  RESTORE_DICT_ITEM( tmpPtr, CollectableULong, face, is )
  VerticesList.restoreGuts(is);
  tmpPtr = &VerticesList;
  RESTORE_DICT_ITEM( tmpPtr, CollectableULong, vertex, is )

  // Verifie de nouveau l'intregrite du fichier
#ifdef __GNUG__
  fread( &id, sizeof(ClassID), 1, is );
#else
  is.read( (char *)&id, sizeof(ClassID) );
#endif
  if( id != myAtom ) throw int(0);
}

#ifdef __GNUG__
template class PQ<BoxInfo>;
#endif