HashLink

Template serves as the main engine of the geometric hash table. Classes defined are used by GeomHash to build, traverse and query a multi-dimensional hash-table.

Quick Index

AUTHORS

CHANGES LOG

GOALS

USAGE

Class Summary

class HashLink

{

public:
protected:
	HashLink();
	HashLink(const HashLink< KeyT, DataT, Bucket>& hl,const int axis);
static int	cube(const float coord, const float cs);
void	resize(const int newStart, const int newStop);
void	buckResize(const int newStart, const int newStop);
void	put(const KeyT& key, const DataT& data, const GeomHashParams& params, int axis);
void	getInfinite(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;
void	getEuclidean(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;
void	getManhattan(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;
void	get(const KeyT& key, const vector< float>& radii, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;
void	getAllNotEmpty(int axis, BucketsPointerList *result) const;
void	getAll(int axis, BucketsPointerList *result) const;
const Bucket*	getBucket(const KeyT& key, const GeomHashParams& params, int axis) const;
void	erase(const int axis);

}; // HashLink

Back to the top of HashLink

AUTHORS

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

Back to the top of HashLink

CHANGES LOG

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 axis. the previous get function turned to getInfinite. New get function returns the results of query by cutting each axis with different radii
8/8/99 - Ram Nathaniel:
Add support for GeomHash bucket iteration - method getAll(int dim, vector* result) const;
7/11/99- Zipi Fligelman
getAll added by Ram does not exist in that format anymore. There are 4 new functions: 1. getAllNotEmpty - that recieves either a hash result or a pointer to a vector of pointers to buckets, this will return all the non empty backets in the ALL the table 2. getAll - that really gets it all including the empty buckets in the last level it can recieve the same parameters as getAllNotEmpty, but the user must take extra care when processing it later not to fall into a segmentation fault. 3. There is a defintion of vector as BucketsPointerList.
15/5/03 - M. Shatsky Copy constructor is added

Back to the top of HashLink

GOALS

HashLink is the main engine of the geometric hash table. It is responisble for construction, traversal and querying of a multi-dimensional hash table. The class is wrapped with the GeomHash class which packages the complex methods and intricate implementation of HashLink with simple methods that can be used immediately. No methods of the class are public because this class was not meant to be used directly.

A template instance is declared using a key class KeyT which defines the means by which the hash table is referenced and queried and a data class DataT which defines the data the hash table holds. It is assumed that DataT has an operator[] which will return floating point coordinates for each dimension. An optional template parameter, allows the user to define different bucket types. The default bucket type is a vector.

The HashLink holds a dynamic array of HashLinks. This array is dynamic in the sense that it may grow but it is also dynamic in the sense that it has a virtual starting point. It is a "ranged" array. Although there may be a slight performance cost during data insertion, this implementation saves memory and rids the user of the need to pre-define sizes and ranges.

Back to the top of HashLink

USAGE

Since the class is not meant for direct use usage will not be described. See the GeomHash implementation for usage examples. The GeomHash methods pretty much coincide with the HashLink methods.

Back to the top of HashLink

HashLink();

initialized as NULL. empty HashLink.

  HashLink();

Back to the top of HashLink

HashLink(const HashLink< KeyT, DataT, Bucket>& hl,const int axis);

  HashLink(const HashLink< KeyT, DataT, Bucket>& hl,const int axis);

Back to the top of HashLink

int cube(const float coord, const float cs);

Returns the cube index of coord using cube size cs. The cube index is returned without normalizing to range.

  static int cube(const float coord, const float cs);

Back to the top of HashLink

void resize(const int newStart, const int newStop);

resize the array of HashLinks using a new range defined by newStart and newStop. It is assumed that the new range is bigger than the old one.

  void resize(const int newStart, const int newStop);

Back to the top of HashLink

void buckResize(const int newStart, const int newStop);

Resize for the bottom axis. This resize is used for the last axis which only contains pointers to buckets.

  void buckResize(const int newStart, const int newStop);

Back to the top of HashLink

void put(const KeyT& key, const DataT& data, const GeomHashParams& params, int axis);

put will insert a data element into the hash table. put is recursive it calls itself until at axis=0. it adds the data element to a bucket object it either finds or creates. The bucket objects are by default of vector type.

put must make sure that it can continue to recurse until axis = 0. this means that the array of HashLinks must be not null, and the the cube index must fall in the array's range. If this is not the case put must resize the array. Arrays are allocated with extra elements at their head and tail in an order to reduce the number of resize operations.

  void put(const KeyT& key, const DataT& data, const GeomHashParams& params,
           int axis);

Back to the top of HashLink

void getInfinite(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;

getInfinite returns a list of elements that may be within a given radius to a given key. The elements returned are all the elements found in the neighboring cubes to the given key's cube. The data elements from all these cubes are gathered in a HashResult container class passed on to the method as an argument. get is a recursive method that recurses until axis=0 at which point a bucket pointer is added to the HashResult.

  void getInfinite(const KeyT& key, const float radius, const GeomHashParams& params, int axis,
		   HashResult< DataT, Bucket>& result) const;

Back to the top of HashLink

void getEuclidean(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;

getEuclidean returns a list of elements according to Euclidean norm

  void getEuclidean(const KeyT& key, const float radius, const GeomHashParams& params, 
                    int axis,
                    HashResult< DataT, Bucket>& result) const;

Back to the top of HashLink

void getManhattan(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;

getManhattan returns a list of elements according to Manhattan norm

  void getManhattan(const KeyT& key, const float radius, const GeomHashParams& params, 
                    int axis,
                    HashResult< DataT, Bucket>& result) const;

Back to the top of HashLink

void get(const KeyT& key, const vector< float>& radii, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;

get returns a list of elements that may be within a given set of radii to a given key. The elements returned are all the elements found in the neighboring cubes to the given key's cube. The data elements from all these cubes are gathered in a HashResult container class passed on to the method as an argument. get is a recursive method that recurses until axis=0 at which point a bucket pointer is added to the HashResult.

params: ranges - a pointer to an array of size equal to the axis of the hash. The user is the responsible for a valid array. axis - is an index of the current checked axis.

  void get(const KeyT& key, const vector< float>& radii, 
	   const GeomHashParams& params, int axis,
	   HashResult< DataT, Bucket>& result) const;

Back to the top of HashLink

void getAllNotEmpty(int axis, BucketsPointerList *result) const;

This version creates a vector of all the non-empty buckets. The buckets are never changed during the use of the GeomHash, and therefore this function create a snapshot of total buckets currently in use in the hash. The function is also usefull for collecting information about the buckets which may be traversed in a Bucket iterator now.

  void getAllNotEmpty(int axis, BucketsPointerList *result) const;

Back to the top of HashLink

void getAll(int axis, BucketsPointerList *result) const;

This funciton will return all the buckets including the empty (null) ones that exists in the hash table. This function enable to check the saprsity of the hash table at least in the last level of the recursion

  void getAll(int axis, BucketsPointerList *result) const;

Back to the top of HashLink

const Bucket* getBucket(const KeyT& key, const GeomHashParams& params, int axis) const;

Using get with radius = 0 makes things simpler in terms of code and method interface. This method returns a bucket pointer to the bucket found in the position pointed to by the given key. If no bucket is found a NULL pointer is returned. This method should be faster then the general get method.

  const Bucket* getBucket(const KeyT& key, const GeomHashParams& params, int axis) const;

Back to the top of HashLink

void erase(const int axis);

erase recursively erases all the data elements in the array. This method is not called by the destructor since the HashLink elements are destructed during the insertion operations in the put function. / need to add a possibilty win axis 0 when the data is a pointer

  void erase(const int axis);

Back to the top of HashLink

All Members

public:
protected:
static int	cube(const float coord, const float cs);
void	resize(const int newStart, const int newStop);
void	buckResize(const int newStart, const int newStop);
void	put(const KeyT& key, const DataT& data, const GeomHashParams& params, int axis);
void	getInfinite(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;
void	getEuclidean(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;
void	getManhattan(const KeyT& key, const float radius, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;
void	get(const KeyT& key, const vector< float>& radii, const GeomHashParams& params, int axis, HashResult< DataT, Bucket>& result) const;
void	getAllNotEmpty(int axis, BucketsPointerList *result) const;
void	getAll(int axis, BucketsPointerList *result) const;
const Bucket*	getBucket(const KeyT& key, const GeomHashParams& params, int axis) const;
void	erase(const int axis);

Back to the top of HashLink

Ancestors

Class does not inherit from any other class.

Back to the top of HashLink

Descendants

Class is not inherited by any others.

Back to the top of HashLink

Generated from source by the Cocoon utilities on Sun Nov 15 13:35:25 2009 .

Report problems to jkotula@unimax.com