/*
 * Module ID: clqtree.h
 * Titre    : Declaration de la classe ClusteringQuadTree.
 * Utilite  : Structure de donnees inventee par moi-meme pour
 *            resoudre efficacement les problemes de clustering.
 *            Le raisonnement qui a guide le design de cette structure,
 *            c'est qu'il est plus efficace de manipuler une collection
 *            d'objets (dans ce cas ci, ce sont des points) que tous les
 *            objets individuellement.
 *            Les performances sont encore a analyser.
 *
 * Auteur   : Olivier Langlois (olivier@olivierlanglois.net)
 * Date     : 1 Mars 1998
 *
 * Revision :
 *
 * 001        09-Sep-1998 - Olivier Langlois
 *            Modifications pour s'adapter a la nouvelle classe oliCollection.
 */

#ifndef   _CLQTREE_H_
#define   _CLQTREE_H_

#include "geo/polygon.h"
#include "collect/idlist.h"
#include "uref.h"
#include "geo/cqtreex.h"

class CQTNode : public polygon, public Reference
{
  friend class ClusteringQuadTree;

  private:
  // La raison qui justifie l'usage de 4 pointeurs distincts plutot
  // qu'un array, c'est qu'avec un array, il est impossible de faire
  // references a des objets d'une classe derivee.
  CQTNode *node1;
  CQTNode *node2;
  CQTNode *node3;
  CQTNode *node4;

  void calculateMoy();

  protected:
  point *moy;
  // Constructeur qui peut etre utilise par les classes derivees
  CQTNode( const IDList &pl )
  : polygon(pl), node1(NULL), node2(NULL), node3(NULL), node4(NULL), moy(NULL)
  { addReference(); }

  public:
  CQTNode( IDList &, size_t );
  virtual ~CQTNode();
  virtual Boolean insertPoint( point * );
  virtual void split( const line &, CQTNode **, CQTNode ** );
};

class CQTBucketNode : public CQTNode
{
  private:
  IDList pointList;

  public:
  CQTBucketNode( const IDList &pl ) : CQTNode(pl) {}
  virtual Boolean insertPoint( point * );
  virtual void split( const line &, CQTNode **, CQTNode ** );
};

class ClusteringQuadTree : public oliCollection
{
  DECLARE_COLLECTABLE(ClusteringQuadTree)

  private:
  CQTNode *root;
  size_t   numEntries;
  size_t   levels;

  public:
  ClusteringQuadTree() : root(NULL), numEntries(0), levels(1) {}

/******************************************************************************
 *
 * Nom       : ClusteringQuadTree
 *
 * Utilite   : Constructeur.
 *
 * Parametres:
 *     pl      (IDList &) Liste de points representant les vertices de la region
 *                        geree par l'arbre
 *
 *     numLvls (size_t)   Nombre de niveaux desires dans l'arbre.
 *
 * Valeur de retour: Aucune
 *
 ****************************************************************************/
  ClusteringQuadTree( IDList &pl, size_t numLvls = 4 );
  ~ClusteringQuadTree();

/******************************************************************************
 *
 * Nom       : splitTree
 *
 * Utilite   : Construit 2 sous-QuadTree, l'un contenant tous les noeuds
 *             a gauche de la ligne, l'autre tous les noeud a droite.
 *
 * Parametres:
 *     l       (line &) ligne separatrice
 *     lTree   (ClusteringQuadTree **) Arbre gauche
 *     rTree   (ClusteringQuadTree **) Arbre droit
 *
 * Note      : L'usager est responsable de liberer les ressources utilisees
 *             par lTree & rTree.
 *
 * Valeur de retour: Aucune
 *
 ****************************************************************************/
  void splitTree( const line &, ClusteringQuadTree **, ClusteringQuadTree ** );

/******************************************************************************
 *
 * Nom       : insertPoint
 *
 * Utilite   : Insere un point dans l'arbre
 *
 * Parametres:
 *     p       (point *) Le point a insere
 *
 * Note      : L'usage de cette fonction apres l'appel de splitTree peut
 *             affecter de facon indesirable les arbres retournes par
 *             splitTree.
 *
 * Valeur de retour: Aucune
 *
 ****************************************************************************/
  void insertPoint( point * );

  virtual void                  clear( void );
  virtual size_t                entries( void ) const { return numEntries; }
  virtual Boolean               isEmpty( void ) const
  { return (!numEntries)?BOOL_TRUE:BOOL_FALSE; }

  // Fonctions getters
  point *getMoy( void ) { return root->moy; }
};

#endif /* _CLQTREE_H_ */