/*
 * Module ID: clqtree.cpp
 * Titre    : Definition 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        03-Sep-1998 - Olivier Langlois
 *            Modifications pour s'adapter a la nouvelle classe geoVector.
 */

#include "collect/idlist.h"
#include "geo/point.h"
#include "geo/segment.h"
#include "geo/line.h"
#include "geo/polygon.h"
#include "geo/clqtree.h"
#include "debug.h"
#include "../math/mathvec.cpp"

DEFINE_COLLECTABLE(ClusteringQuadTree, __CQUADTREE)

ClusteringQuadTree::ClusteringQuadTree( IDList &pl, size_t numLvls )
: numEntries(0), levels(numLvls)
{
  if( levels == 1 )
     root = new CQTBucketNode( pl );
  else
     root = new CQTNode( pl, levels );
}

void ClusteringQuadTree::clear( void )
{
  if(root)
  {
     IDList &pl = const_cast<IDList &>(root->vertices());
     root->removeReference();
     numEntries = 0;
     if( levels == 1 )
        root = new CQTBucketNode( pl );
     else
        root = new CQTNode( pl, levels );
  }
}

ClusteringQuadTree::~ClusteringQuadTree()
{
  if( root && !root->removeReference())
     delete root;
}

/******************************************************************************
 *
 * 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.
 *
 * Reference : cqtree.h
 *
 ****************************************************************************/
void ClusteringQuadTree::splitTree( const line &l,
                    ClusteringQuadTree **lTree,
                    ClusteringQuadTree **rTree
                    )
{
  *lTree = new ClusteringQuadTree;
  *rTree = new ClusteringQuadTree;

  root->split( l, &(*lTree)->root, &(*rTree)->root );
}

/******************************************************************************
 *
 * Nom       : insertPoint
 *
 * Reference : cqtree.h
 *
 ****************************************************************************/
void ClusteringQuadTree::insertPoint( point *p )
{
  if( root )
  {
     if( root->insertPoint( p ) == BOOL_FALSE )
     {
        D( cout << "Polygon: " << *root;  )
        D( cout << "Point  : " << *p;     )
        throw CQTreeEx(QTX_INSERT);
     }
    else numEntries++;
  }
}

CQTNode::CQTNode( IDList &pl, size_t numLvls ) : polygon(pl), moy(NULL)
{
  if( pl.entries() == 4 )
  {
    addReference();
     point *p1 = (point *)pl.get();
     point *p2 = (point *)pl.get();
     point *p3 = (point *)pl.get();
     point *p4 = (point *)pl.get();

     *p2 = midpoint(*p1, *p2 );
     *p4 = midpoint(*p1, *p4 );

     mathVector<double> v1 = *p2 - *p1;
     mathVector<double> v2 = *p4 - *p1;

     if( segment(*p1,*p2).is_horizontal() == BOOL_TRUE )
        *p3 = point( p2->xcoord(), p4->ycoord() );
     else
        *p3 = point( p4->xcoord(), p2->ycoord() );

     pl.insert(p1);
     pl.insert(p2);
     pl.insert(p3);
     pl.insert(p4);
     IDListIterator it(pl);

     point *pTmp;
     // Une copie de la liste de points est passee au constructeur des
     // enfants car eux aussi modifient la liste.
     if( numLvls > 1 )
     {
        IDList node1PL(pl);
        node1 = new CQTNode(node1PL, numLvls-1 );
     }
     else
        node1 = new CQTBucketNode(pl);
     while( pTmp = (point *)++it )
        *pTmp = pTmp->translate(v1);
     if( numLvls > 1 )
     {
        IDList node2PL(pl);
        node2 = new CQTNode(node2PL, numLvls-1 );
     }
     else
        node2 = new CQTBucketNode(pl);
     it.reset();
     while( pTmp = (point *)++it )
        *pTmp = pTmp->translate(v2);
     if( numLvls > 1 )
     {
        IDList node3PL(pl);
        node3 = new CQTNode(node3PL, numLvls-1 );
     }
     else
        node3 = new CQTBucketNode(pl);
     it.reset();
     while( pTmp = (point *)++it )
        *pTmp = pTmp->translate(-v1);
     if( numLvls > 1 )
        // La liste courante peut etre directement passee au constructeur
        // du dernier enfant car apres, la liste n'est plus utilisee.
        node4 = new CQTNode(pl, numLvls-1 );
     else
        node4 = new CQTBucketNode(pl);
  }
  else throw CQTreeEx(QTX_LIST_SIZE);
}

CQTNode::~CQTNode()
{
  if(node1 && !node1->removeReference()) delete node1;
  if(node2 && !node2->removeReference()) delete node2;
  if(node3 && !node3->removeReference()) delete node3;
  if(node4 && !node4->removeReference()) delete node4;

  delete moy;
}

Boolean CQTNode::insertPoint( point *p )
{
  if( inside(*p) == BOOL_TRUE || contains(*p) == BOOL_TRUE )
  {
     if( !moy )
        moy = new point(*p);
     else
        *moy = midpoint(*moy, *p);

     // Le point ne peut etre insere que dans un seul bucket
     if( node1->insertPoint(p) == BOOL_FALSE )
        if( node2->insertPoint(p) == BOOL_FALSE )
          if( node3->insertPoint(p) == BOOL_FALSE )
             if( node4->insertPoint(p) == BOOL_FALSE )
             {
                D( cout << "Polygon: " << *this;  )
                D( cout << "node1  : " << *node1; )
                D( cout << "node2  : " << *node2; )
                D( cout << "node3  : " << *node3; )
                D( cout << "node4  : " << *node4; )
                D( cout << "Point  : " << *p;     )
                throw CQTreeEx(QTX_INSERT);
             }

     return BOOL_TRUE;
  }
  else return BOOL_FALSE;
}

void CQTNode::calculateMoy()
{
  if( node1->moy )
  {
     if( moy )
        *moy = midpoint( *moy, *node1->moy );
     else
        moy = new point(*node1->moy );
  }
  if( node2->moy )
  {
     if( moy )
        *moy = midpoint( *moy, *node2->moy );
     else
        moy = new point(*node2->moy );
  }
  if( node3->moy )
  {
     if( moy )
        *moy = midpoint( *moy, *node3->moy );
     else
        moy = new point(*node3->moy );
  }
  if( node4->moy )
  {
     if( moy )
        *moy = midpoint( *moy, *node4->moy );
     else
        moy = new point(*node4->moy );
  }
}

void CQTNode::split( const line &l, CQTNode **lNode, CQTNode **rNode )
{
  const IDList &pl = vertices();

  if( moy && (intersection(l).isEmpty() == BOOL_FALSE) )
  {
     // On doit 'splitter' encore plus
     *lNode = new CQTNode(IDList(pl));
     *rNode = new CQTNode(const_cast< IDList & >(pl));
     node1->split( l, &(*lNode)->node1, &(*rNode)->node1 );
     node2->split( l, &(*lNode)->node2, &(*rNode)->node2 );
     node3->split( l, &(*lNode)->node3, &(*rNode)->node3 );
     node4->split( l, &(*lNode)->node4, &(*rNode)->node4 );

     (*lNode)->calculateMoy();
     (*rNode)->calculateMoy();
  }
  // Sinon le noeud se trouve soit a gauche ou a droite de la ligne.
  else
  {
     addReference();
     if( left_turn(l.point1(),
               l.point2(),
               *(point *)pl.first()) == BOOL_TRUE )
     {
        *lNode = this;
        *rNode = new CQTBucketNode(pl);
     }
     else
     {
        *lNode = new CQTBucketNode(pl);
        *rNode = this;
     }
  }
}

Boolean CQTBucketNode::insertPoint( point *p )
{
  if( inside(*p) == BOOL_TRUE || contains(*p) == BOOL_TRUE )
  {
     if( !moy )
        moy = new point(*p);
     else
        *moy = midpoint(*moy, *p);

     pointList.insert(p);

     return BOOL_TRUE;
  }
  else return BOOL_FALSE;
}

void CQTBucketNode::split( const line &l, CQTNode **lNode, CQTNode **rNode )
{
  const IDList &pl = vertices();

  if( moy && (intersection(l).isEmpty() == BOOL_FALSE) )
  {
     // On doit 'splitter' encore plus
     *lNode = new CQTBucketNode(IDList(pl));
     *rNode = new CQTBucketNode(pl);

     IDListIterator it(pointList);
     point *p;

     while( p = (point *)++it )
     {
        if( left_turn( l.point1(),
                   l.point2(),
                   *p ) == BOOL_TRUE )
        {
          (*lNode)->insertPoint( new point(*p) );
        }
        else
        {
          (*rNode)->insertPoint( new point(*p) );
        }
     }
  }
  // Sinon le noeud se trouve soit a gauche ou a droite de la ligne.
  else
  {
     addReference();
     if( left_turn(l.point1(),
               l.point2(),
               *(point *)pl.first()) == BOOL_TRUE )
     {
        *lNode = this;
        *rNode = new CQTBucketNode(pl);
     }
     else
     {
        *lNode = new CQTBucketNode(pl);
        *rNode = this;
     }
  }
}