/*
 * Module ID: chains.h
 * Titre    : Declaration des classe de chaines.
 * Utilite  : Structure de donnee pour la location de point
 *            comme decrit dans 'Computational Geometry' de
 *            Franco P. Preparata & Michael Ian Shamos (P. 48)
 *
 * Note     : Les chaines monotones utilisees sur un diagramme de Voronoi
 *            permettent de trouver le plus proche voisin d'un point x en
 *            O(nlogn) comparativement a O(n^2) avec une methode brutale.
 *
 * Auteur   : Olivier Langlois (olivier@olivierlanglois.net)
 * Date     : 24 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.
 */

#ifndef   _CHAINS_H_
#define   _CHAINS_H_

#include "collect/bintree.h"
#include "collect/rbtree.h"
#include "collect/pq.h"
#include "geo/dcel.h"

class ChainMesh : public Collectable
{
  DECLARE_COLLECTABLE(ChainMesh)

  public:
  ChainMesh() : edgeIdx(ULONG_MAX), edgesPtr(NULL) {}
  ChainMesh( CollectableULong *idx, DCEL *ptr )
  : edgeIdx(*idx), edgesPtr(ptr) {}
  ~ChainMesh() {}

  CollectableULong *getEdgeIdx() { return &edgeIdx; }

/******************************************************************************
 *
 * Nom       : isInMesh
 *
 * Utilite   : Verifie si le point est a la meme hauteur (ycoord) que le
 *             maillon.
 *
 * Parametres:
 *     p
 *
 * Valeur de retour: (int) -1 le point est plus bas
 *                          0 le point est entre les 2 vertices
 *                          1 le point est plus haut
 *
 ****************************************************************************/
  int isInMesh( const point &p );

#ifdef __GNUG__
  virtual void                  saveGuts( FILE * );
  virtual void                  restoreGuts( FILE * );
#else
  virtual void                  saveGuts( ofstream & );
  virtual void                  restoreGuts( ifstream & );
#endif
  int operator==(const ChainMesh &b) const;
  int operator<(const ChainMesh &b) const;
  int operator>(const ChainMesh &b) const;

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

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

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

  DCEL *edgesPtr;

  private:
  CollectableULong edgeIdx;
};

class Chain : public RedBlackTree<ChainMesh>
{
  DECLARE_COLLECTABLE(Chain)

  public:
  Chain()
  : RedBlackTree<ChainMesh>(&Chain::saveChainMesh,&Chain::restoreChainMesh),
     chainNum(ULONG_MAX) {}
  Chain( unsigned long chainID )
  : RedBlackTree<ChainMesh>(&Chain::saveChainMesh,&Chain::restoreChainMesh),
    chainNum(chainID) {}
  ~Chain() {}

/******************************************************************************
 *
 * Nom       : findMesh
 *
 * Utilite   : Trouve le maillon qui est a la meme hauteur que p.
 *
 * Parametres:
 *     p
 *
 * Valeur de retour: (CollectableULong *) Index de l'arete du maillon
 *
 ****************************************************************************/
  CollectableULong *findMesh( const point &p );

  unsigned long getChainNum() { return chainNum; }
#ifdef __GNUG__
  virtual void                  saveGuts( FILE * );
  virtual void                  restoreGuts( FILE * );
#else
  virtual void                  saveGuts( ofstream & );
  virtual void                  restoreGuts( ifstream & );
#endif
  int operator==(const Chain &b) const
  {
     return chainNum == b.chainNum;
  }

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

  int operator<(const Chain &b) const
  {
     return chainNum < b.chainNum;
  }

  int operator>(const Chain &b) const
  {
     return chainNum > b.chainNum;
  }

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

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

  static DCEL *edgesPtr;

  private:
  static void saveChainMesh( const ChainMesh &item, void *param );
  static void restoreChainMesh( const ChainMesh &item, void *param );
  unsigned long chainNum;
};

class ChainsSet : public BinaryTree<Chain>
{
  DECLARE_COLLECTABLE(ChainsSet)

  public:
  ChainsSet();
  ChainsSet( DCEL *list );
  ~ChainsSet() { delete edgesPtr; }

/******************************************************************************
 *
 * Nom       : insert
 *
 * Utilite   : Insere une maille.
 *
 * Parametres:
 *     m       (ChainMesh *) maille a inseree.
 *     min,max (unsigned long) interval de chaines valides.
 *
 * Valeur de retour: Aucune
 *
 ****************************************************************************/
  void insert( ChainMesh *, unsigned long, unsigned long );

/******************************************************************************
 *
 * Nom       : location
 *
 * Utilite   : Trouve la location de p.
 *
 * Parametres:
 *     p
 *
 * Valeur de retour: (face *) Face dans lequel le point se trouve.
 *                            Si le graph est un diagramme de Voronoi alors
 *                            le point le plus proche est trouve par la meme
 *                            occasion.
 *
 ****************************************************************************/
  face *location( const point &p );
#ifdef __GNUG__
  virtual void                  saveGuts( FILE * );
  virtual void                  restoreGuts( FILE * );
#else
  virtual void                  saveGuts( ofstream & );
  virtual void                  restoreGuts( ifstream & );
#endif
  private:
     /*
      * Nom     : init
      * Utilite :
      * procedure WEIGHT-BALANCING IN REGULAR PSLG (Planar Straight-Line Graph)
          * 'Computational Geometry' de
      * Franco P. Preparata & Michael Ian Shamos (P. 51)
      */
     void init();
     static void saveChain( const Chain &item, void *param );
     static void restoreChain( const Chain &item, void *param );

     DCEL *edgesPtr;
};

/*
 * N'ayant pu verifier la validite de l'etat des pointeurs P1 et P2 des
 * instances de la classe edge, une methode alternative a du etre employe pour
 * traverser les aretes connectees a un vertex. La classe edgeInfo est utilisee
 * dans cette methode alternative utilise dans ChainsSet::init().
 */
class edgeInfo
{
  public:
  edgeInfo() : e(NULL) {}
  ~edgeInfo() {}

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

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

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

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

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

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

  edge *e;
  double Key;
};

#endif /* _CHAINS_H_ */