/*
 * Module ID: lab4.cpp
 * Titre    : Fonctions utilisees par le lab4.
 *
 * Auteur   : Olivier Langlois (olivier@olivierlanglois.net)
 * Date     : 5 Mars 1998
 */

#include <stdlib.h> // Pour rand()
#include <time.h>
#include "debug.h"
#include "collect/idlist.h"
#include "geo/point.h"
#include "geo/segment.h"
#include "geo/line.h"
#include "geo/polygon.h"
#include "lab4.h"
#include "geo/clqtree.h"
#include "../tools/collect/cirqueue.cpp"
#include "../tools/math/mathvec.cpp"

/******************************************************************************
 *
 * Nom       : getClusters
 *
 * Utilite   : Trouve les centroids d'un ensemble de points.
 *
 * Note      : La recursivite a ete eliminee en utilisant une queue.
 *
 * Reference : lab4.h
 *
 ****************************************************************************/
IDList *getClusters( ClusteringQuadTree *tree, size_t numIter )
{
  srand((unsigned int) (time(NULL) % 10000));
  short dx, dy;
  size_t numLoop;
  ClusteringQuadTree *lTree, *rTree, *currentTree = tree;
  cirQueue<ClusteringQuadTree *> treeQueue(2<<numIter);
  IDList *result = new IDList;
  point *moy;

  // La premiere iteration se fait a l'exterieur du loop principal
  // afin de ne pas effacer l'arbre passe par parametre (tree).
  moy = currentTree->getMoy();
  if(moy)
  {
     D( cout << "Moy:" << *moy << endl; )
     do
     {
        dx = rand()%3 - 1;
        dy = rand()%3 - 1;
     }
     while( !dx && !dy );

     line bissect = p_bisector( *moy, *moy + geoVector(dx,dy) );
     currentTree->splitTree( bissect, &lTree, &rTree );
     treeQueue.Push(lTree);
     treeQueue.Push(rTree);

     if( numIter > 1 )
     {
        for( int i = 1; i < numIter; i++ )
        {
          numLoop = treeQueue.entries();

          for( int j = 0; j < numLoop; j++ )
          {
             currentTree = treeQueue.Pop();
             moy = currentTree->getMoy();
             if( moy )
             {
                do
                {
                  dx = rand()%3 - 1;
                  dy = rand()%3 - 1;
                }
                while( !dx && !dy );

                bissect = p_bisector( *moy, *moy + geoVector(dx,dy) );
                currentTree->splitTree( bissect, &lTree, &rTree );
                treeQueue.Push(lTree);
                treeQueue.Push(rTree);
             }
             delete currentTree;
          } // FOR(j)
        }   // FOR(i)
     }     // IF( numIter > 1 )
     numLoop = treeQueue.entries();
     for( int i = 0; i < numLoop; i++ )
     {
        currentTree = treeQueue.Pop();
        moy = currentTree->getMoy();
        if( moy )
        {
          result->insert(new point(*moy));
        }
        delete currentTree;
     }
  }       // IF(moy)

  D( cout << "num points: " << result->entries() << endl; )
  D( IDListIterator it(*result);                          )
  D( while( moy = (point *)++it ) cout << *moy;           )
  D( cout << endl;                                        )

  return result;
}

#ifdef __GNUG__
template class Queue<ClusteringQuadTree *>;
template class cirQueue<ClusteringQuadTree *>;
typedef ClusteringQuadTree* clqTreePtr;
template void saveNodeToFile( const clqTreePtr &, void * );
#endif