/*!
 * \file fgngRTree.h
 *
 * \brief Rtree Class definition FGngRTree
 *
 * \author Carlos Augusto Teixeira Mendes
 * \date september, 2011
 */

#ifndef _FGNG_RTREE_H_
#define _FGNG_RTREE_H_

// Uncomment the following define to check the consistency of the RTree at each alteration of the tree
// #define FGNG_RTREE_CHECK

// Uncomment the following define to enable the drawing of the tree structure.  Only for FGNG_DIMENSION == 2
// #define FGNG_RTREE_DRAW_2D

#ifdef FGNG_RTREE_DRAW_2D
class QPainter;
#endif


// Uncomment the following define to generate the statistics of visited nodes in the NN algorithm
// #define FGNG_RTREE_NN_STATS

class  FGngNode;
struct FGngRTreeNode;
class  FGngRTreeChildData;
class  FGngRTreeRect;

struct FGngRTreeRKVPPContext;

/*! \brief Class used to implement an RTree specialized to store points of FGNG_DIMENSION and to search nearest neighbors.
*/
class FGngRTree
{
public:
  FGngRTree(int maxChilds, int minChilds, int NNalg = 0);
  ~FGngRTree();

  void insertNode (FGngNode* node);
  void removeNode (FGngNode* node);
  void nodeUpdated(FGngNode* node);

  /*! \brief Returns the two nearest points to a given position. 

    Uses the algorithm defined in the builder 
    Tree must have at least two points
  */
  void nearestNeighbours(const double* position, FGngNode** n1, FGngNode** n2) const { (this->*_nnFunc)(position, n1, n2); }

#ifdef FGNG_RTREE_CHECK
  void check() const;
  void print() const;
  int nodeCount() const { return nodeCount(_root); }
  int nodeCount(FGngRTreeNode* node) const;
  int leafCount() const { return leafCount(_root); }
  int leafCount(FGngRTreeNode* node) const;
#endif

#ifdef FGNG_RTREE_DRAW_2D
  void draw(QPainter* painter) const;
#endif

#ifdef FGNG_RTREE_NN_STATS
  static int FGngRTreeVisitedNodes;
#endif

private:
  void           clear       (FGngRTreeNode* node);
  inline bool    isLeaf      (const FGngRTreeNode* node) const;
  void           insertNode  (FGngRTreeChildData& data, int level);
  FGngRTreeNode* chooseNode  (const FGngRTreeRect& rect, int level) const;
  FGngRTreeNode* addChildData(FGngRTreeNode* node, FGngRTreeChildData& data, bool isLeaf);
  FGngRTreeNode* adjustTree  (FGngRTreeNode* node, FGngNode* pointNode, FGngRTreeNode* splitNode);
  FGngRTreeNode* splitNode   (FGngRTreeNode* node, FGngRTreeChildData& data, bool isLeaf);
  void           pickSeeds   (FGngRTreeChildData* nodeSet, int setsize, FGngRTreeNode* n1, FGngRTreeNode* n2, bool isLeaf);
  void           pickNext    (FGngRTreeChildData* nodeSet, int setsize, FGngRTreeNode* n1, FGngRTreeNode* n2,
                              FGngRTreeRect* n1rect, FGngRTreeRect* n2rect, bool isLeaf);
  void           condenseTree(FGngRTreeNode* node);

  void nearestNeighboursHS      (const double* position, FGngNode** n1, FGngNode** n2) const;
  void nearestNeighboursHSModif (const double* position, FGngNode** n1, FGngNode** n2) const;
  void nearestNeighboursRKVPP   (const double* position, FGngNode** n1, FGngNode** n2) const;
  void nearestNeighboursRKVPPAux(FGngRTreeNode* node, const double* position, FGngRTreeRKVPPContext* context) const;

  FGngRTreeNode* alocNode() const;
  void           freeNode(FGngRTreeNode* node) const;

  FGngRTreeNode*      _root;        //!< Root node
  int                 _minChilds;   //!< Minimum number of children of a node 
  int                 _maxChilds;   //!< Maximum number of children of a node
  FGngRTreeChildData* _nodeSet;     //!< Auxiliary vector of size _maxChilds +1 used by splitNode
  int                 _numElements; //!< Number of elements inserted in the tree

  void (FGngRTree::*_nnFunc)(const double*, FGngNode**, FGngNode**) const; //!< NN search function 
};

#endif