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

#ifndef _GNG_H_
#define _GNG_H_

#define GNG_DIMENSION 2 //!< Sample dimension. Defines the dimension of each node in the GNG 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 GNG_CHECK

#include <QList>

//! Auxiliar structure used to collect all GNG parameters
struct GngParameters
{
  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

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

  //! Constructor.  Initializes the structure with the received parameters
  GngParameters(int n, int l, double eb, double en, int am, double a, double b)
    : nodes(n), lambda(l), epsilonB(eb), epsilonN(en), ageMax(am), alpha(a), beta(b){}
};

class Gng;

//! Class used to represent a node in the graph created by the GNG
class GngNode
{
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<GngNode*>& 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 Gng; 

  GngNode();

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

  double squaredDistanceTo(const double* pos) const;

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

  int             _index;              //!< Index of this node in the graphs node vector
  double          _pos[GNG_DIMENSION]; //!< Position of the node in the n-dimensional space
  QList<GngNode*> _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
};

/*! \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 (*GngSampleSrc)(void* context, double* samplePos);

//! Class used for the implementation of the GNG algorithm
class Gng
{
public:
  Gng(const GngParameters& pars, GngSampleSrc sampler, void* samplerContext);
  ~Gng();

  void execute();

  //! Returns the list of nodes generated by the algorithm
  const QList<GngNode*>& nodeList() const { return _nodes; }

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

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

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

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

#ifdef GNG_CHECK
  void runInternalCheck() const;
#endif

  GngParameters   _par;            //!< FGNG parameters
  QList<GngNode*> _nodes;          //!< List of nodes in the graph
  GngNode*        _nodeBuffer;     //!< Pre-allocated node vector
  int             _firstFreeNode;  //!< Index of the first "unused" node in the vector
  QList<GngNode*> _freeNodeList;   //!< List storing nodes that should be reused
  GngSampleSrc    _sampler;        //!< Function responsible for feeding the algorithm with input samples  
  void*           _samplerContext; //!< User contex passed as a parameter to every call to _sampler
};  


#endif