#ifndef _ClusterEngine_h
#define _ClusterEngine_h

#include "ClusterList.h"
#include "GeomHash.h"

//__STL_TEMPLATE_NULL struct ...
namespace __gnu_cxx
{

template< class ClusterType>
struct hash< const ClusterType*>
{
  size_t operator()(const ClusterType* const t) const 
  { 
    return ((size_t)t/sizeof(ClusterType));
  }
};

} // namespace __gnu_cxx

template< class ElementType, class ClusterType>
/*
CLASS
  ClusterEngine

  Class template defines a framework for performing clustering operation. 
  The class is receives a list of data elements and clusters them using
  the algorithms in the ClusterList class template.

KEYWORDS
  cluster, find, iterator, container

AUTHORS
  Meir Fuchs (meirfux@math.tau.ac.il).

  Copyright: SAMBA group, Tel-Aviv Univ. Israel, 1997.

CHANGES LOG
<UL>
<LI> I have made the preClusterGrid into a pointer to prevent loss of memory
Thus by defualt the preClusterGrid points to nothing, unless the indicator to precluster is set to non zero. Then a grid is invoked using new.
Thus I added a destructor to the class. 13.9.99 Zipi Fligelman </LI>
</UL>

GOALS
  The ClusterEngine class template serves as a framework for clustering
  algorithms. It is based on the ClusterList class template. ClusterEngine's
  added value is its ability to efficiently generate potential neighbor
  pairs. The user may only add the data elements themselves without specifying
  which of them actually neighbor each other.

USAGE
  The ClusterEngine class template is in many ways similar to the ClusterList
  class template. It need only receive the type or class of elements being
  clusered (ClusterType) and the type of cluster that holds them ClusterType.

  Several methods must be defined if the Cluster type if it is to be used with 
  ClusterEngine. Most of these methods are described with the ClusterList
  class but are described here again:

  a. A dist method returning the distance between two Cluster instances.
  EXAMPLE
  float dist(const Cluster&);
  END
  b. A join method capable of joining two clusters. The join method receives
  a single argument of type Cluster and should join the given Cluster object
  with the parent object (this).
  EXAMPLE
  void join(const Cluster&);
  END
  c. The updates() method. Under normal circumstances the updates() method 
  should return the number of times the method join was called on the given
  class instance. The updates method is used as a signature for the Cluster
  instance wether it has been updated. If two Cluster instances have not been
  updated then the distance between them need not be recalculated. The 
  updates function may be used to minimize the calls to the dist method when
  calculating the distance between two Cluster objects is time consuming. For 
  example if the user has the updates() method return a constant 0, the 
  distances between the Cluster objects will never be calculated and the 
  distance between the Cluster elements will be used. (This is good for 
  nearest neighbor clustering).
  EXAMPLE
  unsigned int updates() const;
  END
  d. A constructor that constructs a single-element ClusterType from a given
  ElementType
  EXAMPLE
  ClusterType(const ElementType&);
  END
  e. An element() method returning an ElementType for a single-element 
  cluster. This function is used by ClusterEngine at the outset of the
  algorithm when all clusters are single-element clusters.
  EXAMPLE
    const ElementType& element() const;
  END

  ElementType must support a single method - operator[]. This method is used 
  in generating the neighbors lists. Data elements are thrown into a Grid (a 
  GeomHash object) and neighbors in the grid are added to the list of neighbor
  pairs in ClusterList. operator[] is used by the GeomHash insert method.
  EXAMPLE
    float operator[](const int dim);
  END

  The following is an example of a class named Transformation used to cluster
  3-dimensional rigid transformations using 3 rotational parameter and 3 
  translational parameters. The transformations are clustered (joined) using
  a weighted average. For brevity we use 
  ElementType = ClusterType = Transformation

  EXAMPLE
    class Transformation
    {
    public:
      Transformation(const ReferenceFrame& rt, const float transScore)
        : trans(rt), scr(transScore), joins(0)  {}

      float dist(const Transformation& t)  const  {
        return (trans.rotation().dist(t.trans.rotation()) +
                trans.translation().dist(t.trans.translation())/5);
      }
      void join(const Transformation& t)  {
        float sum = scr + t.scr;
        const Rotation3& rot = trans.rotation();
        const Rotation3& trot = t.trans.rotation();
        trans = ReferenceFrame(Rotation3(rot[0]*scr + trot[0]*t.scr,
                                         rot[1]*scr + trot[1]*t.scr,
                                         rot[2]*scr + trot[2]*t.scr,
                                         rot[3]*scr + trot[3]*t.scr),
                               (trans.translation()*scr + 
                                t.trans.translation()*t.scr) / sum);
        scr = sum;
        ++joins;
      }

      unsigned int updates() const          { return joins; }

      float operator[](const unsigned int dim) const {
        if (dim < 3)
          return trans.rotation()[dim+1];
        else
          return trans.translation()[dim-3];
      }

      const Transformation& element() const { return *this; }

    private:
      ReferenceFrame trans;
      float scr;
      int joins;
    };
  END

  To use the ClusterEngine class the user adds a list of single element 
  clusters and then calls cluster or fastCluster.  At any point the
  user may use ClusterEngine as an STL-like container to inspect what clusters
  are present.

  The clustering algorithms used by the ClusterList keep the neighbor pairs 
  sorted by their distance. When cluster or fastCluster are called, neighbor 
  pairs with shorter distances are accessed first. Each such pair is a
  ssociated with a Cluster. If the distance between the two Cluster objects 
  does not exceed a given threshold they are joined. In the fastCluster 
  version of the  algorithm neighbors are processed in the order in which they 
  are found. In the cluster version, neighbor pairs may be repositioned in the
  distance sorted list if the clusters are changed via previous join 
  operations. Both versions are quite efficient although putting an upper 
  bound on the complexity of cluster method seems difficult.

  A function that uses Transformation class to cluster 3-D rigid 
  transformations may look something like the following:
  EXAMPLE
    typedef ClusterEngine<Transformation, Transformation> TransCluster;
    TransCluster clusterList(maxDist*2, 6);
    for (int i=0; i<count; ++i)
      clusterList.addElement(transformation[i]);

    clusterList.cluster(maxDist);

    for (TransCluster::iterator it = clusterList.begin();
         it != clusterList.end();
         ++it) {
      cout << (*it);
  END
  This example assumes the existance of an array of Transformation objects.
  Also a maxDist parameter sets an upper-bound on the inter-cluster distance
  for clusters that may be joined. It is assumed that operator<< was defined.
*/
class ClusterEngine
  : public ClusterList< unsigned int, ClusterType>
{ 
public:
  //// Constructor. Receives three parameters. The first, maxDist, defines the
  // maximal distance between two neighboring single-element clusters. If two
  // single-element clusters are more distant then the given maxDist they will 
  // not be added to the neighbors lists. The second parameter, dim, specifies
  // the dimension of the grid into which the single element clusters are 
  // thrown. 
  // 
  // The third parameter, preClusterFactor specifies the level of 
  // pre-clustering desired. This parameter is set to 0 by default, meaning
  // no pre-clustering at all. When parameter is > 0 a finer grid with
  // cube size of maxDist/preClusterFactor is used to pre-cluster the elements.
  // Within the finer grid elments are clustered so that there is no more then
  // one cluster for each bucket/grid cube. The bigger the pre-clustering 
  // factor, the finer the grid, the closer the results are to the normal
  // clustering run. Pre-clustering may be used when elements are clumped
  // together into large groups causing a near n^2 complexity on the number of
  // neighbor pairs.
  ClusterEngine(const float maxDist, const unsigned int dim,
                const unsigned int preClusterFactor = 0);
  
  //// Since the preCluster grid is a pointer to such a grid 
  // invoked by new there is a necessity to write a destructor
  ~ClusterEngine();
  
  //// Add an element to be clustered. The elements are added as single-element
  // clusters.
  void addElement(const ElementType& data);

  //// Prepares neighbors lists and calls ClusterList's cluster() method with
  // the maxDist given in the constructor.
  void cluster();

  //// Prepares neighbors lists and calls ClusterList's cluster() method.
  void cluster(const float maxDist);

  //// Prepares neighbors lists and calls ClusterList's fastCluster() method 
  // with the maxDist given in the constructor.
  void fastCluster();

  //// Prepares neighbors lists and calls ClusterList's fastCluster() method.
  void fastCluster(const float maxDist);
  
private:
  struct ElementInfo 
  {
    ElementInfo(const unsigned int k, ClusterType* const clus);
    unsigned int key;
    ClusterType* cluster; 
  };

  void makeNeighborLists();

  typedef ClusterList< unsigned int, ClusterType> MyClusterListType;
  typedef GeomHash< ElementType, ElementInfo> NeighGrid;
  typedef GeomHash< ElementType, ClusterType*> PreClusterGrid;

  NeighGrid neighGrid;
  unsigned int preCluster;
  PreClusterGrid *preClusterGrid;
};

/*********************************
 **       Implementation        **
 *********************************/

template< class ElementType, class ClusterType>
ClusterEngine< ElementType, ClusterType>
::ElementInfo::ElementInfo(const unsigned int k, ClusterType* const clus)
  : key(k), cluster(clus)
{}

template< class ElementType, class ClusterType>
ClusterEngine< ElementType, ClusterType>::
ClusterEngine(const float maxDist, 
              const unsigned int dim,
              const unsigned preClusterFactor)
  : MyClusterListType(), neighGrid(dim, maxDist), preCluster(preClusterFactor),
    preClusterGrid(NULL)
{
  if (preCluster)
    preClusterGrid = new PreClusterGrid(dim, maxDist/(float)preClusterFactor);
}

template< class ElementType, class ClusterType>
ClusterEngine< ElementType, ClusterType>::~ClusterEngine()
{
    if (preClusterGrid)
        delete preClusterGrid;
}

template< class ElementType, class ClusterType>
void 
ClusterEngine< ElementType, ClusterType>::addElement(const ElementType& data)
{
  static unsigned int key = 0;

  if (preCluster) {
    typename PreClusterGrid::Bucket* buck = 
      const_cast< typename PreClusterGrid::Bucket*>((*preClusterGrid).bucket(data));
    if (buck != NULL) {
      cout << "Preclustering\n";
      (*(buck->begin()))->join(ClusterType(data));
      return;
    }
  }

  typename MyClusterListType::iterator cluster = addCluster(key, ClusterType(data));
  neighGrid.insert(data, ElementInfo(key++, &*cluster));

  if (preCluster)
    (*preClusterGrid).insert(data, &*cluster);
}

template< class ElementType, class ClusterType>
void ClusterEngine< ElementType, ClusterType>::cluster(const float maxDist)
{
  makeNeighborLists();
  MyClusterListType::cluster(maxDist);
}

template< class ElementType, class ClusterType>
void ClusterEngine<ElementType, ClusterType>::cluster()
{
  cluster(neighGrid.resolution()); 
}

template< class ElementType, class ClusterType>
void ClusterEngine< ElementType, ClusterType>::fastCluster(const float maxDist)
{
  makeNeighborLists();
  MyClusterListType::fastCluster(maxDist);
}

template< class ElementType, class ClusterType>
void ClusterEngine< ElementType, ClusterType>::fastCluster()
{
  fastCluster(neighGrid.resolution());
}
  
template< class ElementType, class ClusterType>
void ClusterEngine< ElementType, ClusterType>::makeNeighborLists()
{
  const float maxDist = neighGrid.resolution();
  float dist;

  typename NeighGrid::Result all;
  typename NeighGrid::Result neigh;

  neighGrid.query(all);   // All of the transformations.
  typename NeighGrid::Iterator buck = all.begin(); 
  while (buck != all.end()) {
    neigh.clear();
    neighGrid.query((*buck).cluster->element(), maxDist, neigh);
    for (typename NeighGrid::Iterator buckEnd = buck.nextBucket(); 
         buck != buckEnd; 
         ++buck)
      for (typename NeighGrid::Iterator it = neigh.begin(); it != neigh.end(); ++it)
        if ((*it).key < (*buck).key)
          if ((dist = (*buck).cluster->dist(*((*it).cluster))) < maxDist)
            addNeighbors((*buck).key, (*it).key, dist);
  }
  cout.flush();
}  
#endif