/*
 * Module ID: dcel.h
 * Titre    : Declaration 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     : 07 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.
 *
 * 002        09-Sep-1998 - Olivier Langlois
 *            Modifications pour s'adapter a la nouvelle classe oliCollection.
 */

#ifndef   _DCEL_H_
#define   _DCEL_H_

#include "collect/dict.h"
#include "collect/colvar.h"
#include "geo/geox.h"
#include "geo/line.h"
#include "geo/polygon.h"
#include "uref.h"

/*
 * Declarations incompletes
 */
class edge;

class graphObject : public Reference
{
  public:
  virtual ~graphObject() {}
  void removeIdx( const CollectableULong *key );
  void addIdx   ( const CollectableULong *key );
  const IDList *getEdgeIdxList( void ) const { return &edgeIdxList; }

  protected:
  // Cette classe ne possede pas de fonctions pures virtuelles alors pour
  // la rendre abstraite, le default & le copy constructors sont definis
  // comme etant protected. Ainsi, il y a que les classes derivees qui
  // peuvent instantier une instance de cette classe.
  graphObject() {}
  graphObject(const graphObject &go)
  : edgeIdxList(go.edgeIdxList) {}

#ifdef __GNUG__
  void restoreList( FILE *is );
  void saveList( FILE *os )
#else
  void restoreList( istream &is );
  void saveList( ostream &os )
#endif
  { edgeIdxList.saveGuts(os); }

  private:
  IDList edgeIdxList; // Liste des edges qui ont une reference a cet objet.
};

class vertex : public graphObject, public point
{
  DECLARE_COLLECTABLE(vertex)

  public:
  vertex() {}
  vertex(const point &p);
  ~vertex();

  virtual Boolean               isEqual(const Collectable*) const;
#ifdef __GNUG__
  virtual void                  saveGuts( FILE * );
  virtual void                  restoreGuts( FILE * );
#else
  virtual void                  saveGuts( ostream & );
  virtual void                  restoreGuts( istream & );
#endif
  Boolean operator==(const vertex &) const;
};

class face : public graphObject, public Collectable
{
  DECLARE_COLLECTABLE(face)

  public:
  face() {}
  face( const point &p ) : location(p) {}

  virtual unsigned              hash( void ) const { return location.hash(); }
  virtual Boolean               isEqual(const Collectable*) const;
#ifdef __GNUG__
  virtual void                  saveGuts( FILE * );
  virtual void                  restoreGuts( FILE * );
#else
  virtual void                  saveGuts( ostream & );
  virtual void                  restoreGuts( istream & );
#endif
  Boolean operator==(const face &) const;
  const point &getLocation( void ) const { return location; }

  private:
  point location;
};

/*
 * VerticesDictionary : Conserve une reference sur
 *
 * 1 - Le vertex le plus a gauche dans le dictionaire
 * 2 - Le vertex le plus a droite dans le dictionaire
 * 3 - Le vertex le plus haut dans le dictionaire
 * 4 - Le vertex le plus bas  dans le dictionaire
 */
class VerticesDictionary : public Dictionary
{
  DECLARE_COLLECTABLE(VerticesDictionary)

  public:

     VerticesDictionary(size_t N = oliCollection::DEFAULT_CAPACITY,
                              float ff = 0.67)
     : Dictionary(N,ff), xmin(ULONG_MAX), xmax(ULONG_MAX),
       ymin(ULONG_MAX), ymax(ULONG_MAX) {}
     VerticesDictionary(const VerticesDictionary &dict)
     : Dictionary(dict), xmin(dict.xmin), xmax(dict.xmax),
        ymin(dict.ymin), ymax(dict.ymax) {}

  virtual void clear();

/******************************************************************************
 *
 * Nom       : Insert
 *
 * Utilite   : Insere un vertex et sa clef dans le dictionaire.
 *
 * Parametres:
 *     kx      (const Collectable *) Clef.
 *     dx      (const Collectable *) Donnee.
 *
 * Valeur de retour: Aucune
 *
 ****************************************************************************/
     virtual void Insert(const Collectable *kx, const Collectable *dx );

/******************************************************************************
 *
 * Nom       : remove
 *
 * Utilite   : Enleve un vertex associee a la clef specifiee.
 *
 * Parametres:
 *     kx      (const Collectable *) Clef.
 *
 * Note      : L'usager est responsable de la destruction de la valeur
 *             retournee.
 *
 * Valeur de retour: (Collectable *) La valeur demandee ou NULL si
 *                   non-existante.
 *
 ****************************************************************************/
     virtual Collectable *remove(const Collectable *kx);

     CollectableULong getxminIdx() { return xmin; }
     CollectableULong getxmaxIdx() { return xmax; }
     CollectableULong getyminIdx() { return ymin; }
     CollectableULong getymaxIdx() { return ymax; }

     vertex          *getxmin()
     { return (vertex *)getValue(&xmin); }
     vertex          *getxmax()
     { return (vertex *)getValue(&xmax); }
     vertex          *getymin()
     { return (vertex *)getValue(&ymin); }
     vertex          *getymax()
     { return (vertex *)getValue(&ymax); }

  private:
  CollectableULong ymin;
  CollectableULong xmin;
  CollectableULong ymax;
  CollectableULong xmax;
};

// Classe utilisee par DCEL::setBox
class BoxInfo
{
  public:
  BoxInfo(): Vertex(NULL),leftFace(NULL),rightFace(NULL) {}

  int operator==(const BoxInfo &b)
  {
     return Key == b.Key;
  }

  int operator!=(const BoxInfo &b)
  {
     return !operator==(b);
  }

  // La priorite est plus petite lorsque la clef est plus grande.
  int operator<(const BoxInfo &b)
  {
     return Key > b.Key;
  }

  // La priorite est plus grande lorsque la clef est plus petite.
  int operator>(const BoxInfo &b)
  {
     return Key < b.Key;
  }

  int operator<=(const BoxInfo &b)
  {
     return operator<(b)||operator==(b);
  }

  int operator>=(const BoxInfo &b)
  {
     return operator>(b)||operator==(b);
  }

  vertex *Vertex;
  face   *leftFace;
  face   *rightFace;
  double  Key;
};

class DCEL : public oliCollection
{
  DECLARE_COLLECTABLE(DCEL)
  friend class edge;

  public:
  DCEL();
  ~DCEL();

  unsigned long getNextVertexKey();
  unsigned long getNextFaceKey();
  unsigned long getNextEdgeKey();
  VerticesDictionary &Vertices() { return VerticesList; }
  Dictionary         &Faces()    { return FacesList;    }
  Dictionary         &Edges()    { return EdgesList;    }

/******************************************************************************
 *
 * Nom       : insertEdge
 *
 * Utilite   : Insere une arete dans la liste associatedList.
 *
 * Note      : Si le edge ne peut etre insere, il sera detruit.
 *
 * Parametres:
 *     e       (edge *) Edge a insere
 *
 * Valeur de retour: 0 si insere sinon -1
 *
 ****************************************************************************/
  int insertEdge( edge * );

/******************************************************************************
 *
 * Nom       : setBox
 *
 * Utilite   : Ferme le graph a l'interieur d'une boite.
 *
 *
 * Parametres:
 *     poly    (polygon &) Forme de la boite.
 *
 * Valeur de retour: Aucune
 *
 ****************************************************************************/
  void setBox( polygon & );

/******************************************************************************
 *
 * Nom       : clean
 *
 * Utilite   : Elimine toutes les aretes non connectees.
 *
 * Parametres:
 *     Aucun
 *
 * Valeur de retour: Aucune
 *
 ****************************************************************************/
  void clean();

  virtual void clear();
#ifdef __GNUG__
  virtual void                  saveGuts( FILE * );
  virtual void                  restoreGuts( FILE * );
#else
  virtual void saveGuts( ostream & );
  virtual void restoreGuts( istream & );
#endif
  vertex *getVertex( const CollectableULong *idx ) const
  {
     return (vertex *)VerticesList.getValue(idx);
  }

  face   *getFace  ( const CollectableULong *idx ) const
  {
     return (face *)FacesList.getValue(idx);
  }

  edge   *getEdge  ( const CollectableULong *idx ) const
  {
    return (edge *)EdgesList.getValue(idx);
  }

  edge *getxminEdge();
  edge *getyminEdge();
  edge *getxmaxEdge();
  edge *getymaxEdge();

  virtual size_t                entries( void ) const
  { return EdgesList.entries(); }
  virtual Boolean               isEmpty( void ) const
  { return EdgesList.isEmpty(); }

  private:
  void init(void);

  void setP1( edge *, CollectableULong * );
  void setP2( edge *, CollectableULong * );
  void removeP1( edge * );
  void removeP2( edge * );

  unsigned long    nextVertexKey;
  unsigned long    nextFaceKey;
  unsigned long    nextEdgeKey;

  /*
   * Des indexes sont preferes a des pointeurs. La raison est qu'ainsi,
   * il est plus facile d'implanter la persistence sur cette classe.
   */
  Dictionary         EdgesList;
  Dictionary         FacesList;
  VerticesDictionary VerticesList;
};

/*
 * class edge
 */
class edge : public Collectable, public Reference
{
  DECLARE_COLLECTABLE(edge)
  friend class DCEL;

  public:
  edge( DCEL *l, face *f1, face *f2, vertex *v1, vertex *v2 );
  edge( DCEL *l, face *f1, face *f2, const segment &s );
  edge( DCEL *l, face *f1, face *f2, const line    &s );

  ~edge();

  virtual Boolean               isEqual(const Collectable*) const;
#ifdef __GNUG__
  virtual void                  saveGuts( FILE * );
  virtual void                  restoreGuts( FILE * );
#else
  virtual void                  saveGuts( ostream & );
  virtual void                  restoreGuts( istream & );
#endif
  Boolean atRight( const point & ) const;
  Boolean intersection( edge &, point & );
  face  *getF1() const;
  face  *getF2() const;
  vertex *getV1() const;
  vertex *getV2() const;
  CollectableULong *getKey() { return &myKey; }

  unsigned long getF1Idx() {return F1.value();}
  unsigned long getF2Idx() {return F2.value();}
  unsigned long getV1Idx() {return V1.value();}
  unsigned long getV2Idx() {return V2.value();}

  segment getSegment()
  { return segment( *getV1(), *getV2() ); }

  void setF1( face * );
  void setF2( face * );
  void setV1( vertex * );
  void setV2( vertex * );

/******************************************************************************
 *
 * Nom       : insert
 *
 * Utilite   : Insere cette arete dans la liste associatedList.
 *
 * Note      : Cette fonction est surtout utile pour les algorithmes de
 *             construction de graphe planaire qui doivent executer certaines
 *             manipulations sur les edges avant de les inseres.
 *
 * Parametres:
 *     Aucun.
 *
 * Valeur de retour: Aucune.
 *
 ****************************************************************************/
  void insert( void ) { associatedList->insertEdge( this ); }

  protected:
  edge() {}
  void init( face *f1, face *f2, vertex *v1, vertex *v2 );

  // Fonction appellee exclusivement par le DCEL.
  void setMyKey( unsigned long key );

  /*
   * Des indexes sont preferes a des pointeurs. La raison est qu'ainsi,
   *  1 - il est plus facile d'implanter la persistence sur cette classe.
   */
  // Convention: V1 est toujours le point dont x est plus petit
  CollectableULong V1,  V2; // Index des vertices
  // Convention: F1 est toujours le point a droite de segment(V1,V2)
  CollectableULong F1,  F2; // Index des faces
  CollectableULong P1, P2;  // Indexes sur les aretes suivantes
  CollectableULong myKey;   // Index attribue par le DCEL pour l'arete courante.

  DCEL            *associatedList;

  private:
    edge( const edge &e ) {}
};

#endif /* _DCEL_H_ */