#ifndef _GeomHash_h
#define _GeomHash_h

#include "HashLink.h"

template< class KeyT, class DataT, class BucketT = vector< DataT> >
/*
CLASS
  GeomHash

  The template defines a geometric hash table class. The class is declared
  using a key type with which the data type instances are inserted and
  accessed. The geometric hash table may be instantiated using any dimension
  and grid-size.

KEYWORDS
  geometric, hash, iterator, query, container

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

CHANGES LOG
<UL>
  <LI>27/02/02 - Dina Duhovny & Oranit Shem-Tov:
  - GeomHashParams - We refer to the dimension attribute as the dimension
  of the overall geometric hash. Previously, this attribute was reffered
  to as the index of the last axis (i.e. dimension-1).
  Axis explanation by an example: 
  Assume a 2D geometric hash. It's axes are numbered as 0 (the x-axis) & 1 (the y-axis).
  - Defining cube size for each axis. Previously, there was only one value
  for all the axis. It is usefull for storing data and a key, composed of
  several components, each one of them has a different scale. For example,
  a 4D key, composed of a 3D coordinates and a type. 
  - Defining query ranges - for querying, within a different radius for each axis.
  </LI>
  <LI>8/8/99 - Ram Nathaniel:<BR>
  Add bucket iteration - method vector<Bucket *> *getBuckets() const;
  </LI>
  <LI> 7/11/99 - Zipi Fligelman
  Changed the method by Ram and added parameter at the whole table query
  In the full table query there is a flag that by default is set to false, that 
  means you collect only non empty buckets. But when it is set to true non-empty 
  buckets are also collected. The same is true for the method getBuckets.
  That returns a vector of <b> const Bucket * </b> with all the buckets
  The empty backets are returned only if the flag is set to true.
  </LI>
  <LI> 15/5/03 - M. Shatsky
  Copy constructor is added
  </LI>
</UL>
  Copyright: SAMBA group, Tel-Aviv Univ. Israel, 1997.

GOALS
  GeomHash defines a high performance geometric hash table with an intuitive
  interface. The class can be defined for any key type that supports the []
  operator for any data type. The hash table can be instantiated using any
  dimension and any cube or grid size. It is possible to specify different
  cube size for each axis. The query function also may be called with a set of
  radii, one for each axis. User may also decide how the data
  elements are collected in each bucket by determining the container used in
  each bucket.

  GeomHash actually is a wrap for the HashLink class which does most of
  the work of hash table traversal, insertion and querying. The user need
  not know anything about HashLink to use the hash table.

  Geometric hash table results are returned using an STL-like container class
  called HashResult. This class and its accompanying iterator class
  HashIterator are used to collect hash table query results and to iterate
  through the result elements.

USAGE
  Instantiation and declaration are done using a key type and a data type.
  The key type must support the [] operator. For example an array of floats 
  or a Vector3 for 3 dimensional hash tables. User may also choose to determine
  the bucket type. By default the bucket type is a vector<DataT>. The user 
  may decide on other STL containers or write one of his own. The bucket type
  must support the push_back, begin, end, size methods and the iterator and
  const_iterator typedefs.

  Instantiation may include a grid size and a dimension. 
  Here is an example using Vector3's as the keys, 
  integers as the data stored in the hash table, 3 is the dimension and 1.3 is
  the cube size of the grid.
  EXAMPLE
    GeomHash<Vector3, int> gHash(3, 1.3);
  END

  Members may be inserted using the insert command. The insert command
  recieves a key and a data element to be inserted into the proper bucket
  in the hash table. 
  EXAMPLE
    gHash.insert(Vector3(1.2, 2.3, 3.4), -1);
  END

  When querying a geometric hash table one searches for data that was
  inserted into the hash table using keys that were close to the query
  key. A radius may be given to the query defining how far the neighboring
  points should be. The query returns all points within that distance but
  will return other points that lie in neighboring grid cubes. If you wish
  to extract points that are within a given euclidean radius you'll have
  to sift through the query results.

  Before running a query one must declare a HashResult container in which the
  results will be collected. The container is sent with the query request
  and results are found in the container after the query is done.

  An example of querying the hash table with a key and sifting through the
  data to find the data's that are within a euclidean radius of the key is
  given. The example assumes 10000 points are given inside a Vector3 array
  called points and a query point is given in Vector3 q.
  EXAMPLE
  float radius=1.0;
  GeomHash<Vector3, int> gHash(3, 2*radius);  // grid cube size is 2*radius
  for (int i=0; i<10000; i++)   // insert 10000 points
    gHash.insert(points[i], i);
  
  Vector3 q(1,1,1);
  HashResult<int> result;
  gHash.query(q, radius, result);  // radius = half of cube size.
  
  // traverse list STL iterator style.
  HashResult<int>::iterator it;
  for (it = result.begin(); it != result.end(); it++)
    if (q | points[*it]) <= radius
      cout << *it << " : " << points[*it] << '\n';
  END

  In case of more complex key, the user can specify the cube size of every axis.
  For example, in case of transformation: each transformation can be represented
  as 3 rotation parameters and 3 translation parameters. The rotation parameters
  are values between -PI and PI, while the translational parameters are not limited.
  The user may want smaller bin size for rotation then for translation.
  EXAMPLE
  vector<float> radii(6);
  radii[0]=radii[1]=radii[2]=0.1;
  radii[3]=radii[4]=radii[5]=2.0;
  GeomHash<Transformation,int> gHash(6, radii);

  The same idea works in query:
  HashResult<int> result;
  gHash.query(t, radii, result);
  END
*/

class GeomHash : 
    private HashLink< KeyT, DataT, BucketT>
{
  public:
  typedef HashResult< DataT, BucketT> Result;
  typedef typename Result::iterator Iterator;
  typedef BucketT Bucket;
  typedef typename HashLink< KeyT,DataT, BucketT>::BucketsPointerList BucketsPointerList;
  
  typedef enum {
    manhattanNorm,
    euclideanNorm,
    infiniteNorm
  } NormType;
  
  //// The hash-table is instantiated by a given dimension (defualt 1)
  // and a given cube-size (default 1.0).
  explicit GeomHash(const unsigned short d=1, const float cs=1.0);

  //// The hash-table is instantiated by a given dimension and 
  //// a given cube size for each dimension.
  explicit GeomHash(const unsigned short d, const vector< float>& cs);

  //// Destructor. Frees all hash table memory.
  ~GeomHash()  {   
    erase();   
  }

  //// Copy constructor
  GeomHash(const GeomHash< KeyT,DataT,BucketT>&);

  //// Data elements can be inserted according to keys using the insert method.
  // The key determines in which d-dimensional cube the data is inserted.
  void insert(const KeyT& key, const DataT& data);

  //// Searches for all data elements lying in radius neighborhood to key.
  // Note that query will return all points lying within a given radius
  // but may also return extra points that were not inserted with keys
  // that are within a radius to the query key. 
  // Moreover, the default norm is the infinite norm 
  // All results are collected using a results container of type HashResult<DataT>. 
  void query(const KeyT& key, const float radius, Result& result) const;
  
  //// Searches for all data elements according to a given key.
  // The user may specify the type of the norm: Euclidean, Manhattan or Infinite.
  // Note that query will return all points lying within a given radius
  // but may also return extra points that were not inserted with keys
  // that are within a radius to the query key. 
  // All results are collected using a results container of type HashResult<DataT>. 
  void query(const KeyT& key, const float radius, const NormType ballType, 
             Result& result) const;

  
  //// Searches for all data elements according to a given key and a set of radii.
  // the size of the radii vector must be equal to dimension. Each axis is searches
  // with a radius specified for it.
  // This query may return extra points as well.
  void query(const KeyT& key, const vector< float>& radii, Result& result) const;

  //// Searches for all data elements lying in radius=cube size neighborhood 
  // to key. The query will return all data's that were inserted with keys
  // whose distance to the query key is less then radius. More data
  // elements may be returned due to the grid structure of the hash table. 
  // All results are 
  // collected using a results container of type HashResult<DataT>.
  void query(const KeyT& key, Result& result) const;

  //// Query the hash table with an infinite radius. Calling this method
  // results in a hash table results container which points to all hash table
  // elements. There is a choice whether to collect only non empty 
  // buckets (ehich is also the default), but if one wished to check for
  // sparsity of the table you can set the includeEmpty to true and receive all
  // the empty buckets. Notice that travesing the result must be done with caution
  // mind the NULLs ....
  void query(Result& result, bool includeEmpty=false) const;

  //// Return a vector of all the buckets currently used in the Hash. This is 
  // usefull for traversing the hash one bucket at a time, and also usefull for
  // creating a set of all the buckets now in use for follow up checks. There
  // is a flag that can be set if you want to add all the empty buckets in the 
  // last dimesion and thus check the change in the sparsity of the table.(The 
  // Hash class never changes the buckets but only copy a constant version of the 
  // pointers so that even after insertions and deletions in the Hash the vector 
  // will indicate the same set of buckets).
  BucketsPointerList *getBuckets(bool includeEmpty=false) const;

  //// Returns a pointer to a bucket at the location given by key. If no such
  // bucket exists a NULL pointer is returned.
  const Bucket* bucket(const KeyT& key) const;
  
  //// frees all memory used by hash table elements.
  void erase();

  //// Sets the hash table insertion speed. This parameter determines how
  // large the hash table arrays are made when an array resize is forced.
  // When this parameter is set to 0, arrays will be resized to be slightly
  // larger then what is currently needed by the hash table. If the parameter
  // is set to > 0, resizes will be more generous. Array sizes will grow 
  // causing a decrease in the number of resize operations and hence an
  // increase in insertion speed.
  //
  // This feature should be useful for large but sparsely populated hash tables
  // In densely populated hash tables, a gain in speed should be noticed only
  // with the first insertions. Once the table is populated resize operations
  // are rare and hence the speed gain is limited.
  //
  // Note that raising the parameter too high could actually cause the
  // insertion operations to slow down because of the overhead of managing
  // a large hash table. This parameter should probably not exceed 4.0.
  void setInsertSpeed(const float speed);

  //// returns hash table dimension
  unsigned short dimension() const;

  //// returns hash table resolution or cube size.
  float resolution(unsigned short axis=0) const;

  //// Returns hash table insertion speed. See setInsertSpeed.
  float insertSpeed() const;

private:
  GeomHashParams params;
};

/*******************************************
 * Template class GeomHash implementation. *
 *******************************************/

template< class KeyT, class DataT, class BucketT>
GeomHash< KeyT, DataT, BucketT>::GeomHash(const unsigned short d, 
                                         const float cs)
  : HashLink< KeyT, DataT, BucketT>(), params(d, cs, 1.0) {
}


template< class KeyT, class DataT, class BucketT>
GeomHash< KeyT, DataT, BucketT>::GeomHash(const unsigned short d, 
                                         const vector< float>& cs)
  : HashLink< KeyT, DataT, BucketT>(), params(d, cs, 1.0) {
}

template< class KeyT, class DataT, class BucketT>
GeomHash< KeyT, DataT, BucketT>::GeomHash(const GeomHash< KeyT,DataT,BucketT>& gh)
  : HashLink< KeyT, DataT, BucketT>(gh,gh.params.dimension-1),params(gh.params){}

template< class KeyT, class DataT, class BucketT>
void GeomHash< KeyT, DataT, BucketT>::insert(const KeyT& key, const DataT& data)
{
  // dim-1 for starting with the last axis
  put(key, data, params, params.dimension-1);
}

template< class KeyT, class DataT, class BucketT>
void GeomHash< KeyT, DataT, BucketT>::query(const KeyT& key, const float radius, 
                                           const NormType ballType, Result& result) const
{
  switch (ballType) {
  case euclideanNorm:
    getEuclidean(key, radius, params, params.dimension-1, result);
    break;
  case manhattanNorm:
    getManhattan(key, radius, params, params.dimension-1, result);
    break;
  default:
    getInfinite(key, radius, params, params.dimension-1, result);
    break;
  }
}

template< class KeyT, class DataT, class BucketT>
void GeomHash< KeyT, DataT, BucketT>::query(const KeyT& key, const float radius, 
                                           HashResult< DataT, BucketT>& result) const
{
  getInfinite(key, radius, params, params.dimension-1, result);
}

template< class KeyT, class DataT, class BucketT>
void GeomHash< KeyT, DataT, BucketT>::query(const KeyT& key, const vector< float>& radii, 
                                           HashResult< DataT, BucketT>& result) const
{
  get(key, radii, params, params.dimension-1, result);
}

template< class KeyT, class DataT, class BucketT>
void GeomHash< KeyT, DataT, BucketT>::query(const KeyT& key, HashResult< DataT, BucketT>& result) const
{
  get(key, params.cubeSizes, params, params.dimension-1, result);
}
  
template< class KeyT, class DataT, class BucketT>
void GeomHash< KeyT, DataT, BucketT>::query(Result& result,bool includeEmpty) const
{
  BucketsPointerList bresult;
  
  if (!includeEmpty)
    getAllNotEmpty(params.dimension-1, &bresult);
  else
    getAll(params.dimension-1, &bresult);
    
  for(int i=0;i<(int)bresult.size();++i)
    result.push_back((Bucket*)bresult[i]);
}


template< class KeyT, class DataT, class BucketT>
typename GeomHash< KeyT, DataT, BucketT>::BucketsPointerList* 
GeomHash< KeyT, DataT, BucketT>::getBuckets(bool includeEmpty) const
{
  BucketsPointerList *result=new BucketsPointerList();
  if (!includeEmpty)
    getAllNotEmpty(params.dimension-1, result);
  else 
    getAll(params.dimension-1 , result);
  return result;
}

template< class KeyT, class DataT, class BucketT>
const BucketT* GeomHash< KeyT, DataT, BucketT>::bucket(const KeyT& key) const
{
  return getBucket(key, params, params.dimension-1);
}

template< class KeyT, class DataT, class BucketT>
void GeomHash< KeyT, DataT, BucketT>::erase()
{
  HashLink< KeyT, DataT, BucketT>::erase(params.dimension-1);
}

template< class KeyT, class DataT, class BucketT>
void GeomHash< KeyT, DataT, BucketT>::setInsertSpeed(const float speed)
{
  params.resizeCoefficient = max2(0.0f, speed);
}

template< class KeyT, class DataT, class BucketT>
unsigned short GeomHash< KeyT, DataT, BucketT>::dimension() const
{
  return params.dimension;
}

template< class KeyT, class DataT, class BucketT>
float GeomHash< KeyT, DataT, BucketT>::resolution(unsigned short axis) const
{
  return params.cubeSizes[axis];
}

template< class KeyT, class DataT, class BucketT>
float GeomHash< KeyT, DataT, BucketT>::insertSpeed() const
{
  return params.resizeCoefficient;
}

#endif