The HashTableGrid class stores N-Dimensional spatial elements (that could be anything on which it can be computed a N-dimensional bounding box) in a regular grid, using a Hash Table having the Cell Grid coordinate as key type. More...

#include <vclib/space/complex/grid/hash_table_grid.h>

Inheritance diagram for vcl::HashTableGrid< GridType, ValueType, AllowDuplicates >:

[legend]

Public Types
using	KeyType = AbsGrid::KeyType

using	IntersectsCellFunction = AbsGrid::IntersectsCellFunction

using	Iterator = std::unordered_multimap< KeyType, ValueType >::iterator

using	ConstIterator = std::unordered_multimap< KeyType, ValueType >::const_iterator

Public Types inherited from vcl::AbstractGrid< GridType, ValueType, DerivedGrid >
using	IntersectsCellFunction = std::function< bool(const typename GridType::BBoxType &, const RemoveCVRefAndPointer< ValueType > &)>
	The IntersectsCellFunction type is a std::function that takes as input a bounding box and a value, and returns true if the value intersects the bounding box.

using	KeyType = GridType::CellCoord

template<typename QueryValueType >
using	QueryDistFunction = std::function< typename GridType::ScalarType(const QueryValueType &, const RemoveCVRefAndPointer< ValueType > &)>
	The QueryDistFunction type is a std::function that takes as input a query value and a value stored in the grid, and returns the distance between the two values.

template<typename QueryValueType >
using	QueryBoundedDistFunction = std::function< typename GridType::ScalarType(const QueryValueType &, const RemoveCVRefAndPointer< ValueType > &, typename GridType::ScalarType)>
	The QueryBoundedDistFunction type is a std::function that takes as input a query value, a value stored in the grid, and a maximum distance between the two values, and returns the distance between the two values. If the distance is greater than the maximum distance, the function must return a value greater than the maximum distance.

Public Member Functions
	HashTableGrid (const GridType &g)

template<typename ObjIterator >
	HashTableGrid (ObjIterator begin, ObjIterator end, const IntersectsCellFunction &intersects=nullptr)
	Creates an HashTableGrid that contains all the elements that can be iterated from `begin` to `end`.

template<Range Rng>
	HashTableGrid (Rng &&r, const IntersectsCellFunction &intersects=nullptr)

bool	empty () const
	Returns true if the HashTableGrid is empty (no elements in it).

bool	cellEmpty (const KeyType &k) const
	Returns true if the given cell coordinate does not contain elements in it.

std::set< KeyType >	nonEmptyCells () const
	Returns an std::set containing the cell coordinates of all the cells that contain at least one element.

std::size_t	countInCell (const KeyType &k) const
	Returns the number of elements contained in the given cell.

std::pair< Iterator, Iterator >	valuesInCell (const KeyType &k)

std::pair< ConstIterator, ConstIterator >	valuesInCell (const KeyType &k) const

void	clear ()

bool	eraseAllInCell (const KeyType &k)

void	eraseInSphere (const Sphere< typename GridType::ScalarType > &s)

Iterator	begin ()

ConstIterator	begin () const

Iterator	end ()

ConstIterator	end () const

Public Member Functions inherited from vcl::AbstractGrid< GridType, ValueType, DerivedGrid >
bool	cellEmpty (const KeyType &k) const

std::size_t	countInCell (const KeyType &k) const

bool	insert (const ValueType &v)
	Inserts the given element in the AbstractGrid.

template<typename ObjIterator >
uint	insert (ObjIterator begin, ObjIterator end)
	Inserts all the elements from `begin` to `end`. The type referenced by the iterator must be the ValueType of the AbstractGrid.

template<Range Rng>
uint	insert (Rng &&r)
	Inserts all the elements contained in the input range r, from `begin` to `end`. The type referenced by the iterator must be the ValueType of the AbstractGrid.

bool	erase (const ValueType &v)

bool	eraseAllInCell (const KeyType &k)

uint	countInSphere (const Sphere< typename GridType::ScalarType > &s) const

auto	valuesInSphere (const Sphere< typename GridType::ScalarType > &s) const

void	eraseInSphere (const Sphere< typename GridType::ScalarType > &s)

template<typename QueryValueType >
auto	closestValue (const QueryValueType &qv, QueryBoundedDistFunction< QueryValueType > distFunction, typename GridType::ScalarType &dist) const

template<typename QueryValueType >
auto	closestValue (const QueryValueType &qv, QueryDistFunction< QueryValueType > distFunction, typename GridType::ScalarType &dist) const

template<typename QueryValueType >
auto	closestValue (const QueryValueType &qv, QueryDistFunction< QueryValueType > distFunction) const

template<typename QueryValueType >
auto	closestValue (const QueryValueType &qv, typename GridType::ScalarType &dist) const

template<typename QueryValueType >
auto	closestValue (const QueryValueType &qv) const

template<typename QueryValueType >
auto	kClosestValues (const QueryValueType &qv, uint n, QueryDistFunction< QueryValueType > distFunction) const

template<typename QueryValueType >
auto	kClosestValues (const QueryValueType &qv, uint n) const

Private Types
using	AbsGrid = AbstractGrid< GridType, ValueType, HashTableGrid< GridType, ValueType, AllowDuplicates > >

using	MapType = std::unordered_multimap< KeyType, ValueType >

using	MapValueType = MapType::value_type

Private Member Functions
bool	insertInCell (const KeyType &k, const ValueType &v)

bool	eraseInCell (const KeyType &k, const ValueType &v)

Private Attributes
friend	AbsGrid

MapType	mMap

Additional Inherited Members
Protected Member Functions inherited from vcl::AbstractGrid< GridType, ValueType, DerivedGrid >
	AbstractGrid ()
	Empty constructor, creates an usable AbstractGrid, since the Grid is not initialized.

	AbstractGrid (const GridType &grid, IntersectsCellFunction intersects=nullptr)
	Creates a AbstractGrid that allows to store ValueType values on the given grid.

template<PointConcept PointType>
	AbstractGrid (const PointType &min, const PointType &max, const KeyType &sizes, IntersectsCellFunction intersects=nullptr)
	Creates a AbstractGrid that allows to store ValueType values on a Grid having `min` as minimum coordinte of the Grid, `max` as maximum coordinate of the grid, and the number of cells per dimension given by `sizes`.

template<typename BoxType >
	AbstractGrid (const BoxType &bbox, const KeyType &sizes, IntersectsCellFunction intersects=nullptr)
	Creates a AbstractGrid that allows to store ValueType values on a Grid bounded by `bbox`, and having the number of cells per dimension given by `sizes`.

template<typename ObjIterator >
	AbstractGrid (ObjIterator begin, ObjIterator end, IntersectsCellFunction intersects=nullptr)
	Creates an AbstractGrid having a proper Grid to store the elements.

template<Range Rng>
	AbstractGrid (Rng &&r, IntersectsCellFunction intersects=nullptr)
	Creates an AbstractGrid having a proper Grid to store the elements.

Protected Attributes inherited from vcl::AbstractGrid< GridType, ValueType, DerivedGrid >
IntersectsCellFunction	mIntersectsFun

Detailed Description

template<typename GridType, typename ValueType, bool AllowDuplicates = true>
class vcl::HashTableGrid< GridType, ValueType, AllowDuplicates >

The HashTableGrid class stores N-Dimensional spatial elements (that could be anything on which it can be computed a N-dimensional bounding box) in a regular grid, using a Hash Table having the Cell Grid coordinate as key type.

This Grid allows to perform insertion, deletions and queries in a time that depends only on the number of elements contained in the involved cell(s) during the operation. The total overhead of managing this data structure is the same of managing an std::unordered_multimap. The user can allow or disallow the insertion of duplicate values by setting the boolean AllowDuplicates template parameter, that is defaulted to true.

Constructor & Destructor Documentation

◆ HashTableGrid()

template<typename GridType , typename ValueType , bool AllowDuplicates = true>

template<typename ObjIterator >

vcl::HashTableGrid< GridType, ValueType, AllowDuplicates >::HashTableGrid	(	ObjIterator	begin,
		ObjIterator	end,
		const IntersectsCellFunction &	intersects = `nullptr`
	)

inline

Creates an HashTableGrid that contains all the elements that can be iterated from begin to end.

The bounding box and the sizes of the Grid are automatically computed. Bounding box is computed starting from the bounding box of all the iterated elements, and then inflated. The number of cells per dimension is computed using the vcl::bestGridSize function.

Parameters

begin
end
intersects

Member Function Documentation

◆ cellEmpty()

template<typename GridType , typename ValueType , bool AllowDuplicates = true>

bool vcl::HashTableGrid< GridType, ValueType, AllowDuplicates >::cellEmpty ( const KeyType & k ) const

inline

Returns true if the given cell coordinate does not contain elements in it.

Parameters

k

Returns

◆ countInCell()

template<typename GridType , typename ValueType , bool AllowDuplicates = true>

std::size_t vcl::HashTableGrid< GridType, ValueType, AllowDuplicates >::countInCell ( const KeyType & k ) const

inline

Returns the number of elements contained in the given cell.

Parameters

k

Returns

◆ empty()

template<typename GridType , typename ValueType , bool AllowDuplicates = true>

bool vcl::HashTableGrid< GridType, ValueType, AllowDuplicates >::empty ( ) const

inline

Returns true if the HashTableGrid is empty (no elements in it).

Returns

◆ nonEmptyCells()

template<typename GridType , typename ValueType , bool AllowDuplicates = true>

std::set< KeyType > vcl::HashTableGrid< GridType, ValueType, AllowDuplicates >::nonEmptyCells ( ) const

inline

Returns an std::set containing the cell coordinates of all the cells that contain at least one element.

Returns

The documentation for this class was generated from the following file:

vclib/core/include/vclib/space/complex/grid/hash_table_grid.h

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ HashTableGrid()

Member Function Documentation

◆ cellEmpty()

◆ countInCell()

◆ empty()

◆ nonEmptyCells()