/*!
 * \file fgngFib.h
 *
 * \brief FGngFib class definition
 *
 * \author Carlos Augusto Teixeira Mendes
 * \date september, 2011
 */

#ifndef _FGNGFIB_H_
#define _FGNGFIB_H_

#define FGNG_DIMENSION 2 //!< Sample dimension. Defines the dimension of each node in the FGNG graph.

// Uncomment the next define to include consistency tests in the algorithm.
// This tests are done at each execution step and can be quite slow.
// #define FGNG_CHECK

#include <QList>

struct FGngRTreeNode;

//! Auxiliar structure used to collect all FGNG parameters
struct FGngParameters
{
  int    nodes;    //!< Number of nodes that will be generated by the algorithm
  int    lambda;   //!< Steps between each node generation
  double epsilonB; //!< Adaptation factor for the winning node
  double epsilonN; //!< Adaptation factor for neighbors of the winning node
  int    ageMax;   //!< Maximum age for an edge
  double alpha;    //!< Decrement facctor applied to errors after a node insertion
  double beta;     //!< Aging factor applied to nodes
  int    rtreeMaxChilds; //!< Maximum number of childs for each RTree node
  int    rtreeMinChilds; //!< Minimum number of childs for each RTree node
  int    rtreeNNAlg;     //!< Algorithm used in the search for the nearest neighbor (NN)

  //! Constructor. Creates an uninitialized set of parameters
  FGngParameters() {}

  //! Constructor.  Initializes the structure with the received parameters
  FGngParameters(int n, int l, double eb, double en, int am, double a, double b, int maxC=8, int minC=4, int alg=0)
    : nodes(n), lambda(l), epsilonB(eb), epsilonN(en), ageMax(am), alpha(a), beta(b),
      rtreeMaxChilds(maxC), rtreeMinChilds(minC), rtreeNNAlg(alg) {}
};

class FGngFib;

/*! \brief Class used to represent a node in the graph created by the FGNG
           Fib algorithm

Despite beeing different than the FGngNode class used by the FGng algorithm, this 
class keeps the name FGngNode (instead of FGngFibNode) to allow for reuse of the
FGngRTree without changes.
*/
class FGngNode
{
public:
  //! Returns the n-dimensional vector containing the node position
  const double* pos() const { return _pos; }

  //! Returns the index of the node in the graph
  int index() const { return _index; }

  //! Returns the list of neighbor nodes for this node
  const QList<FGngNode*>& neighbours() const { return _neighbours; }

private:
  // Nodes methods and attributes are private to the user, and not to the 
  // GNG algorithm.  The user iteration with the node should be restricted 
  // to knowing the nodes position and its neighborhood.
  friend class FGngFib;
  friend class FGngRTree;

  FGngNode();

  //! Returns a pointer to the node in the RTree that indexes this node
  FGngRTreeNode* rtreeNode() const { return _rtreeNode; }

  //! Updates the connection between the node and the RTree
  void setRTreeNode(FGngRTreeNode* node) { _rtreeNode = node; }

  void updatePos(double epsilon, const double* newpos);

  double squaredDistanceTo(const double* pos) const;

  void incAges();
  void connectTo(FGngNode* node);
  void disconnectFrom(int nodeIndex);

  void   updateError(int iter, double beta);
  double error(int iter, double beta);

  int              _index;               //!< Index of this node in the graphs node vector
  double           _pos[FGNG_DIMENSION]; //!< Position of the node in the n-dimensional space
  QList<FGngNode*> _neighbours;          //!< Neighbors of this node
  QList<int>       _ages;                //!< Age for each edge in _neighbours. The information is duplicated in each ending of the edge :(
  double           _error;               //!< Accumulated error until the iteration defined by _lastErrorUpdate
  int              _lastErrorUpdate;     //!< Iteration number of the last update to _error
  FGngRTreeNode*   _rtreeNode;           //!< Location of the node in the RTree

  // Parameters for controlling the node inside the Fibonacci heap

  int       _fibDegree;  //!< Number of childs of the node inside the heap
  bool      _fibMarked;  //!< Is the node marked on the heap?
  FGngNode* _fibFather;  //!< Node father on the heap
  FGngNode* _fibChild;   //!< Pointer for one (any) of the childs of the node in the heap
  FGngNode* _fibNext;    //!< Pointer for the next brother on the circular list
  FGngNode* _fibPrev;    //!< Pointer for the previous brother on the circular list
};

/*! \brief Callback type for the sampler function. It receives a context supplied by 
           the user and is expected to fill samplePos with the next sample position
*/
typedef void (*FGngSampleSrc)(void* context, double* samplePos);

//! Class used for the implementation of the FGNG algorithm with Fibonacci heap
class FGngFib
{
public:
  FGngFib(const FGngParameters& pars, FGngSampleSrc sampler, void* samplerContext);
  ~FGngFib();

  void execute();

  //! Returns the list of nodes generated by the algorithm
  FGngNode** nodeList(int* size) const { *size = _nodesSize; return _nodes; }

  //! Returns a reference to the parameter set used in the execution
  const FGngParameters& parameters() const { return _par; }

private:
  void initGraph();
  void getNearestNodes(const double* samplePos, FGngNode** na, FGngNode** nb);
  void updateNodePositions (FGngNode* node, const double* samplePos);
  int  removeOldConnections(int iter, FGngNode* node);
  void removeIsolatedNode  (int iter, FGngNode* node);
  void addNewNode(int iter);

  FGngNode* getNode(int index);
  void      recycleNode(FGngNode* node);

  FGngNode* findNodeWithBiggestError(int iter, QList<FGngNode*>& list, int* index) const;

  void      fibheapInsert(int iter, FGngNode* node);
  FGngNode* fibheapRemoveMax(int iter);
  void      fibheapRemove(int iter, FGngNode* node);
  void      fibheapIncVal(int iter, FGngNode* node);
  void      fibheapDecVal(int iter, FGngNode* node);

  inline int  fibD() const;
  inline void fibAddToList     (FGngNode* listNode, FGngNode* x);
  inline void fibRemoveFromList(const FGngNode* x);
  inline void fibMergeLists    (FGngNode* firstListNode, FGngNode* secondListNode);

  inline void fibConsolidate(int iter);
  inline void fibCut        (FGngNode* x, FGngNode* y);

#ifdef FGNG_CHECK
  void runInternalCheck(int iter) const;
  void fibCheck(int iter) const;
  int  fibCheckTree(int iter, FGngNode* node, FGngNode* father) const;
#endif

  FGngParameters   _par;            //!< FGNG parameters
  FGngNode**       _nodes;          //!< List of nodes in the graph
  int              _nodesSize;      //!< Number of nodes actually in _nodes
  FGngNode*        _nodeBuffer;     //!< Pre-allocated node vector
  int              _firstFreeNode;  //!< Index of the first "unused" node in the vector
  QList<FGngNode*> _freeNodeList;   //!< List storing nodes that should be reused
  FGngRTree*       _rtree;          //!< Spatial index for the nodes
  FGngSampleSrc    _sampler;        //!< Function responsible for feeding the algorithm with input samples  
  void*            _samplerContext; //!< User contex passed as a parameter to every call to _sampler
                                         
  int       _fibN;    //!< Number of entries in the Fibonacci heap
  FGngNode* _fibMax;  //!< Node with biggest value on the Fibonacci heap
};  


#endif